- •Зміст дисципліни.
- •Найменування тем, їхній зміст, обсяг у годинах лекційних занять
- •Вказівки з використанНя літературних джерел
- •Алгоритми й структури даних
- •Стеки, списки
- •Дерева пошуку Бінарні дерева
- •Двійкові дерева
- •Червоно- чорні дерева
- •Частково впорядковані дерева Статья I.При створенні чуд елементи вводилися в наступному порядку: (13, 6, 15, 5, 10, 6, 3, 13, 5, 6, 35, 8). Пояснити побудова (переформування) дерева.
- •Рекурсія
- •Перебір з поверненням
- •Машина Тьюрінга
- •Приклади Послідовний пошук
- •Структури даних. Масиви Решето Ератосфена
- •Обчислення найближчої точки
- •Структури даних. Списки Приклад циклічного списку (задача Йосипа)
- •Сортування методом вставки в список
- •Звертання порядку проходження елементів списку
- •Структури даних. Рядки Сортування масиву рядків
- •Абстрактні типи даних (атд) Інтерфейс абстрактного типу даних стека
- •Реалізація черги fifo на базі масиву
- •Реалізація черги fifo на базі зв'язного списку
- •Перетворення з інфіксної форми в постфіксну
- •Рекурсія Алгоритм Евклида
- •Рекурсивна програма для оцінки префіксних виразів
- •Розв’язання
- •Приклад 2 Завдання
- •Розв’язання
- •Приклад 3 Завдання
- •Розв’язання
- •Приклад 4 Завдання
- •Розв’язання
- •Приклад 5 Завдання
- •Розв’язання
- •Приклад 6 Завдання
- •Розв’язання
- •Приклад 7 Завдання
- •Розв’язання
- •Алгоритм роботи машини т’юринга
- •Дослідження функції на рекурсивність
- •Нормальні алгоритми Маркова
- •Алгоритм роботи програми.
- •Приклад роботи програми.
- •Варіанти курсових робіт
- •Варіанти виконання Алгоритм виконання курсової роботи:
- •Приклад1.
- •Побудова моделі.
- •Розроблення алгоритму.
- •Правильність алгоритму.
- •Реалізація алгоритму.
- •Перевірка програми.
- •Приклад2
- •Постановка задачі
- •Перший варіант розв’язку
- •Другий варіант розв’язку.
- •Приклад3
- •Опукла оболонка
- •Метод обходу Грехема
- •Метод обходу Джарвіса
- •Алгоритм апроксимації опуклої оболонки
- •Швидкі методи побудови опуклої оболонки
- •Алгоритм типу розділяй та пануй
- •Побудова опуклої оболонки простого многокутника
- •Динамічні алгоритми побудови опуклої оболонки
- •Порівняльний аналіз алгоритмів побудови опуклої оболонки
- •Висновки
Реалізація алгоритму.
На цьому етапі кроки алгоритму безпосередньо виражаються конструкціями мови програмування, наслідком чого є програма для комп’ютера. Найсуттєвіші труднощі реалізації:
1) кроки алгоритму можуть не відповідати мовним конструкціям, наприклад, крок може вимагати цілої підпрограми для його реалізації;
2) потрібно побудувати цілу систему структур даних для представлення важливих аспектів моделі, яка використовується.
Для подолання зазначених труднощів можна використовувати сучасні технології програмування, використовувати набутий досвід роботи з структурами даних тощо. Необхідно щоб правильний алгоритм перетворювався в правильну машинну програму.
Аналіз алгоритму і його складності.
Необхідність цього етапу обумовлена як практичними, так і теоретичними чинниками. Перші пов’язані із отриманням оцінок або меж для дорогих обчислювальних ресурсів – пам’яті чи часу роботи, які потрібні алгоритму для оброблення конкретних даних, щоб видати результат, важливий для розв’язання практично корисної проблеми. Другі пов’язані з природним бажанням кількісно оцінити ресурси, які вимагаються різними алгоритмами – претендентами на розв’язання однієї й тієї ж проблеми – для вибору з них найефективнішого. Крім цього, так званого кількісного аналізу, потрібен і абсолютний аналіз, пов’язаний із обґрунтуванням оптимальності розв’язку проблеми. Інакше кажучи, абсолютний аналіз дозволяє встановити, коли наш алгоритм настільки гарний, що неможливо (незалежно від наших розумових здібностей) значно його покращити). Отже, необхідні чіткі критерії оцінки алгоритму.
Взагалі, потрібен механізм для виявлення найбільш ефективних алгоритмів і заміни застарілих. Проблема в тому, що іноді неможливо скласти чітку думку про відносну ефективність двох алгоритмів (один може в середньому краще працювати, наприклад, на випадкових вхідних даних, тоді як інший краще працює на певних спеціальних вхідних даних).
Нехай А – алгоритм для розв’язання деякого класу проблем, а п – розмір окремої проблеми із цього класу. В нашому прикладі п - просто скаляр, рівний числу вершин графу. В загальному випадку п може бути масивом чи довжиною послідовності, що вводиться. Визначимо fA(п) як робочу функцію, що дає верхню межу для максимального числа основних операцій (додавання, порівняння тощо), які повинен виконати алгоритм А для розв’язання будь-якої проблеми розміру п. Назвемо алгоритм А поліноміальним, якщо fA(п) зростає не швидше, ніж поліном від п, в супротивному випадку алгоритм A назвемо експоненціальним.
Функцію f(n) визначимо як О[g(n)] і будемо говорити, що вона є функцією порядку g(n) для великих п, якщо
.
Будемо використовувати позначення f(n) = 0[g(n)].
Функцію f(n) визначимоо[g(n)] для великих n, якщо
.
Ці символи вимовляються відповідно, як «О велике» і «о маленьке». Інтуїтивно, якщо f(n) є 0[g(n)], то ці дві функції, по суті, зростають з однаковою швидкістю при n . Якщо f(n) є o[g{n)], то g(n) зростає значно швидше, ніж f(n).
Наприклад,
поліном f(n)
= 2n5+6n4+6n2+18
є O(n5),
тому що
,
о(n5,1),
о(еn),
о(2n)
і «о
маленьким» від будь-якої функції, що
зростає швидше, ніж поліном п’ятого
ступеня. Функція f(n)=2n
є о(n!),
тому що
.
Однак 2n
є 0(2n
+
1)
і о(5n-1).
Функція f(n)
= 1000
є о(n).
Отже, алгоритм поліноміальний, якщо fA(n) = 0(Pk (n)) або fA(n) = o(Pk(n)), де Рk(п) – деякий поліном від змінної п довільного фіксованого ступеня k. В супротивному випадку алгоритм є експоненціальним.
Очевидно, ми краще б уявляли дії алгоритму A, якби знали, що fA (n) = 2.5n2+3.7п-5.2, ніж якби нам було відомо тільки, що fA (n) = 0(n2). Але точні коефіцієнти fA (n) в загальному випадку залежать від реалізації, тоді як характеристика 0(n2) загалом властива алгоритму і не залежить від особливостей реалізації. Стосовно експоненціальних алгоритмів важливо знати також, що їх оцінка скажімо 0(2n), а не О(n!) чи О(nn). На жаль для багатьох практично важливих проблем відомі тільки експоненціальні алгоритми, серед них і задача комівояжера. Зазначимо, що ETS – експоненціальний алгоритм з оцінкою принаймні О(n!). Дійсно, число перестановок (п-1)!, що навіть за умови тільки одного кроку для кожної з них (груба недооцінка), буде вимагати 0(п-1)! кроків. Якщо для кожної перестановки можна знайти відповідний тур і його вартість за О(n) кроків, то будемо мати для будь-якої верхньої межі для загального часу роботи принаймні О(n!).
Для задачі комівояжера на 20 міст, припустивши існування феноменального алгоритму для кроку 1, який генерує нову перестановку тільки за один крок, і використання комп’ютера, який виконує кожний елементарний крок (наприклад, порівняння, додавання, пошук елементу матриці) за 10-7 с, розв’язок з застосуванням алгоритму ETS буде отримано трохи менше ніж за 70 століть, тому що 20! 2 1018.
Тому необхідно досліджувати алгоритми, щоб напрацювати чіткий підхід до розроблення алгоритмів.
