- •Зміст дисципліни.
- •Найменування тем, їхній зміст, обсяг у годинах лекційних занять
- •Вказівки з використанНя літературних джерел
- •Алгоритми й структури даних
- •Стеки, списки
- •Дерева пошуку Бінарні дерева
- •Двійкові дерева
- •Червоно- чорні дерева
- •Частково впорядковані дерева Статья I.При створенні чуд елементи вводилися в наступному порядку: (13, 6, 15, 5, 10, 6, 3, 13, 5, 6, 35, 8). Пояснити побудова (переформування) дерева.
- •Рекурсія
- •Перебір з поверненням
- •Машина Тьюрінга
- •Приклади Послідовний пошук
- •Структури даних. Масиви Решето Ератосфена
- •Обчислення найближчої точки
- •Структури даних. Списки Приклад циклічного списку (задача Йосипа)
- •Сортування методом вставки в список
- •Звертання порядку проходження елементів списку
- •Структури даних. Рядки Сортування масиву рядків
- •Абстрактні типи даних (атд) Інтерфейс абстрактного типу даних стека
- •Реалізація черги fifo на базі масиву
- •Реалізація черги fifo на базі зв'язного списку
- •Перетворення з інфіксної форми в постфіксну
- •Рекурсія Алгоритм Евклида
- •Рекурсивна програма для оцінки префіксних виразів
- •Розв’язання
- •Приклад 2 Завдання
- •Розв’язання
- •Приклад 3 Завдання
- •Розв’язання
- •Приклад 4 Завдання
- •Розв’язання
- •Приклад 5 Завдання
- •Розв’язання
- •Приклад 6 Завдання
- •Розв’язання
- •Приклад 7 Завдання
- •Розв’язання
- •Алгоритм роботи машини т’юринга
- •Дослідження функції на рекурсивність
- •Нормальні алгоритми Маркова
- •Алгоритм роботи програми.
- •Приклад роботи програми.
- •Варіанти курсових робіт
- •Варіанти виконання Алгоритм виконання курсової роботи:
- •Приклад1.
- •Побудова моделі.
- •Розроблення алгоритму.
- •Правильність алгоритму.
- •Реалізація алгоритму.
- •Перевірка програми.
- •Приклад2
- •Постановка задачі
- •Перший варіант розв’язку
- •Другий варіант розв’язку.
- •Приклад3
- •Опукла оболонка
- •Метод обходу Грехема
- •Метод обходу Джарвіса
- •Алгоритм апроксимації опуклої оболонки
- •Швидкі методи побудови опуклої оболонки
- •Алгоритм типу розділяй та пануй
- •Побудова опуклої оболонки простого многокутника
- •Динамічні алгоритми побудови опуклої оболонки
- •Порівняльний аналіз алгоритмів побудови опуклої оболонки
- •Висновки
Перевірка програми.
Коли програма написана, виправлені синтаксичні та логічні помилки, перш ніж її експлуатувати необхідно пересвідчитись, що програма здійснює саме те, що повинна здійснювати. Тут не досить прогнати програму на простому прикладі (такому, який може бути перевірений вручну). Мова повинна йти про експериментальну спробу установити межі використання алгоритму (програми). Програма повинна бути перевірена для широкого спектру допустимих вхідних даних. Це може бути не легкою задачею, але саме так ми можемо виявити помилки представлення правильного алгоритму у вигляді програми, забуті часткові випадки тощо. Немає загального підходу до вибору вхідних даних для тестування. Він залежить від складності програми, ресурсу часу, персоналу тощо. Загалом множина всіх комбінацій вхідних даних величезна і повна перевірка практично неможлива. Тому потрібно достатньо повно перевірити випадки, які з великою ймовірністю зустрінуться на практиці.
Крім того, перевірка дозволить експериментально підтвердити результати аналізу алгоритму. Досвід підказує, що аналіз середнього функціонування алгоритму більш важливий і трудомісткий, ніж аналіз найкращого та найгіршого випадків. Якщо можливий аналіз найгіршого випадку, то важливо експериментально установити, чи працює алгоритм значно краще в середньому, ніж найгіршому випадку.
Аналітичний і експериментальний аналіз доповнюють один одного. Аналітичний аналіз може бути неточним, якщо зроблені надто сильні припущення для спрощення. В цьому випадку можуть бути отримані лише грубі оцінки. З іншого боку, отримати достатнє експериментальне підтвердження для гарантій будь-якої статистичної достовірності може виявитися неможливим чи непрактичним. Експериментальні результати можуть бути однорічними.
Тестування також дозволить визначити обчислювальні обмеження програм, вхідні дані, на яких програма працює добре, а на яких погано. Так, алгоритм ETS працює добре для n 6 і погано для n 15. На жаль і перехід не плавний – алгоритм працює погано впроміжних випадках. Особливо важливо знати, для яких вхідних даних алгоритм розв’язує проблему за експоненціальний час, а для яких – проблема може бути розв’язана за поліноміальний час.
Документування.
В дійсності важливо, щоб цей етап переплітався з іншими. Документування дозволяє одному зрозуміти програму, що написана іншим. Документація в широкому розумінні містить блок-схеми, доведення правильності, результати тестування,описи форматів тощо.
Приклад2
Тема Пошук лексикографічно найменшого циклічного зсуву заданої стрічки
Постановка задачі
Дано стрічку з l (l>0) символів, які пронумеровані зліва направо від 0 до l‑1. Розглядаються всі можливі її циклічні зсуви. Серед цих циклічних зсувів знайти лексикографічно найменший, тобто вказати номер символу, з якого слід починати зсув, щоб отримати лексикографічно найменшу стрічку. Якщо таких символів декілька – то вказати номер найлівішого з них.
Ця задача має цікаві застосування. Наприклад, за допомогою відповіді на поставлене запитання можна дуже швидко перевірити, чи є дана стрічка нерозкладною (за Рибаком).
Стрічка називається нерозкладною, якщо її не можна подати у вигляді конкатенації більше, ніж однієї непорожньої стрічки таким чином, щоб стрічки, які є аргументами конкатенації, йшли за лексикографічним незростанням – як у словнику, тільки навпаки. Критерієм нерозкладності є те, що вищепоставлене запитання для даної стрічки має відповідь 0 та що ця стрічка не має періодів з довжиною, яка є дільником l, меншим за l. Виявляється, що кількість таких нерозкладних стрічок довжиною l над алфавітом з q літер дорівнює кількості незвідних поліномів ступеня l зі старшим коефіцієнтом – одиницею над q‑елементним полем (за умови існування q‑елементного поля).
