Автор очень ответственно и профессионально подходит к выполнению заказов. Большое спасибо!
Информация о работе
Подробнее о работе
Лабораторна робота №2 з курсу "Теорія алгоритмів" Спеціальність: Інформаційні управляючі системи та технології
- 1 страниц
- 2017 год
- 138 просмотров
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
-
-
КПИ (Киевский политехнический институт)
-
# -*- coding: utf-8 -*-
"""
Лабораторна робота №2 з курсу "Теорія алгоритмів"
Спеціальність: Інформаційні управляючі системи та технології
МЕТА:
Дослідити поведінку алгоритмів сортування методами включення та злиття.
ОПИС РОБОТИ:
В даній роботі досліджуються два методи сортування - метод сортування
включенням (insertion sort) та метод сортування злиття (merge sort).
Відомо, що час роботи алгоритму сортування включенням складає О(n^2), тоді
як час для алгоритму сортування злиттям - O(n*lg(n)). Це означає, що
метод злиття працює швидше ніж метод включення для достатньо великих
розмірностей вхідних даних. Для вхідних даних малої розмірності це
може бути не так. Адже, в асимптотичних позначеннях нехтують константами
та меншими членами функцій, які, насправді, можуть мати значний вплив при
невеликих розмірностях входу алгоритму.
В роботі пропонується визначити розмір вхідних даних, при яких метод
сортування включенням працює швидше, за метод сортування злиттям.
На основі даних (для яких входів краще використовувати метод включення,
аніж метод злиття) можна створити, так званий, гібридний метод сортування.
Ідея його полягає в тому, щоб використовувати як основний метод
злиття, проте, коли при рекурсивних викликах процедури сортування для
масивів меншої розмірності ця розмірність досягає певної наперед визначеної
величини, то для таких підзадач використовувати метод сортування включенням.
ЗАВДАННЯ:
1) Реалізувати алгоритм сортування методом злиття. Для цього написати
функцію merge на основі наведеного псевдокоду (див. коментарі до функції).
2) Знайти розмірність вхідних даних, при яких сортування методом включення
працює швидше за метод злиття. Для цього провести експерименти, підібравши
значення параметрів у функції compare_ins_and_merge. Відповідь на
поставлене питання можна знайти шляхом аналізу графіку порівнянь роботи
двох алгоритмів (див. виклик фукнції plot_data у кінці функції
compare_ins_and_merge).
Вказати значення розмірності вхідних даних, після яких метод злиття починає
працювати швидше за метод включення.
ВІДПОВІДЬ:
3.1) (На додаткові 2 бали) Реалізувати гібридний алгоритм (функція
hybrid_sort), який використовує як базовий метод злиття, але при певних
розмірностях підзадач переходить до використання методу включення (див.
функцію insertion_sort).
Вказати значення розмірності підмасиву, для якого у гібридному методі буде
використовуватись метод включення.
ВІДПОВІДЬ:
3.2) Порівняти час роботи алгоритмів за методом злиття та гібридним методом.
Для цього використати функцію compare_merge_and_hybrid. Зробити висновок
щодо отриманих результатів.
ДОКУМЕНТАЦІЯ:
Python v2.7.3 documentation:
- http://docs.python.org/2/
- http://oim.asu.kpi.ua/python/docs (дзеркало, доступне з кафедральних комп'ютерів)
Книга "Dive Into Python":
- http://www.diveintopython.net/
- http://oim.asu.kpi.ua/python/diveintopython/html/ (дзеркало, доступне з кафедральних комп'ютерів)
"""
-
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
