close

Вход

Забыли?

вход по аккаунту

?

Otchet laba8 ASD

код для вставкиСкачать
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
"Харківський політехнічний інститут"
Кафедра "Автоматизовані системи управління"
ЗВІТ
з лабораторної роботи №8
по курсу "Алгоритми та структури даних"
ВИКОНАВ
Студент групи ІФ 32-Г
Рейзвих М. В.
ПЕРЕВІРИЛА
Асс. каф. АСУ
Гонтар Ю. М.
Харків 2013
Тема: Математичні основи теорії алгоритмів
Мета: навчитися визначати складність алгоритмів.
Завдання: Для кожного реалізованого алгоритму з попередніх робіт визначити складність. Для цього для кожного рядку алгоритму потрібно вказати кількість разів, які він виконується, в залежності від розмірності вхідних даних. Результат записати у вигляді Θ -позначення. Для алгоритмів робіт "Базові структури даних" та "Фундаментальні алгоритми на графах і деревах" визначити, чи є обрані структури даних оптимальними, а якщо ні - запропонувати такі, що призводять до зменшення часу роботи алгоритму.
Хід роботи:
1. Лабораторна робота №1
В цій лабораторній роботі треба було реалізувати одну із заданих структур даних. В моєму варіанті требі було реалізувати чергу.
Треба було розробити програму, яка читає з клавіатури послідовність N цілих чисел, де N<256:
Додавання елементів реалізовано в одному циклі, який буде працювати доти, доки не буде введено слово "stop". Тому даний алгоритм буде працювати за час О(n).
T(n) = Θ (n).
2. Лабораторна робота №2
В другій лабораторній роботі треба було розробити програму, яка читає з клавіатури цілі числа N, M (1 < N, M < 256), N пар <ключ, значення>, жодний з яких не повторюється та ще M ключів:
Кожен інший цикл проходить N, або менше разів. Тому складність роботи алгоритму дорівняє O(n).
T(n) = Θ (n)
3. Лабораторна робота №3
Згідно з завданням лабораторної роботи треба було розробили червоно-чорне дерево з поворотом, зміною кольору, пошуком та додаванням елементів до дерева. Кожного разу швидкість роботі зростає в два рази. Складність даного алгоритму дорівнює O(log(n)):
T(n) = Θ (log(n))
4. Лабораторна робота №4
Треба було розробити програму, яка зчитує з клавіатури послідовність N цілих чисел, а потім відтворити бульбашкове сортування:
Вище представлен код для даного сортування. Алгоритм працює за час О(n2), тому що цикл while знаходиться у циклі for.
T(n) = Θ (n2)
5. Лабораторна робота №5
Згідно з завданням треба було розробити програму, яка читає з клавіатури число N (1 < N < 256) та параметри генератору випадкових чисел та виводить на екран послідовність з N згенерованих чисел.
Складність роботи генератору залежить від кількості чисел, тому складність генератору випадкових чисел - O(n). Цю послідовність чисел потрібно було аналізувати на випадковість використовуючи побітовий тест. Він також працює за час O(n).
T(n) = Θ (n).
6. Лабораторна робота №6
Треба розробити програму, яка читає з клавіатури числа N, M (1 < N, M < 256) - кількість вершин та ребер графу; послідовність M пар цілих чисел - ребра графу. Програма зберігає граф та виконує над ним алгоритм у глибину. Процес додавання точок виконується за час O(n).
Один з циклів викликає на кожній своїй ітерації функцію, яка містить інший цикл. Кожний з цих циклів обробляє усі N-вершин графа. Складність алгоритму в глибину дорівнює O(n2).
T(n) = Θ (n2).
7. Лабораторна робота №7
В останній лабораторній роботі треба було розробити програму, що для кожної нової ланки вказує, в яку сторону вона повернута.
Алгоритм не містить складних циклів, тому впевнено можна стверджувати, що складність алгоритму дорівняє O(n).
T(n) = Θ (n).
Висновок: виконуючи дану лабораторну роботу я навчився визначати складність алгоритмів, проаналізувавши усі алгоритми перших семи лабораторних робіт. Я навчився розпізнавати залежність складності від кількості циклів в алгоритмі, і побачив, що різні підходи до розв'язку задачі використовують алгоритми з різною складністю. Щодо оптимальних алгоритмів - у першій використоно алгоритм з оптимальною складністю, у шостій - не з оптимальною. Можна використати список суміжності. 
Документ
Категория
Рефераты
Просмотров
51
Размер файла
46 Кб
Теги
asd, laba, otchet
1/--страниц
Пожаловаться на содержимое документа