- •Зміст дисципліни.
- •Найменування тем, їхній зміст, обсяг у годинах лекційних занять
- •Вказівки з використанНя літературних джерел
- •Алгоритми й структури даних
- •Стеки, списки
- •Дерева пошуку Бінарні дерева
- •Двійкові дерева
- •Червоно- чорні дерева
- •Частково впорядковані дерева Статья 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 |
|
|
|
Вступна лекція. Знання й управління. Визначення знань, їхня роль у процесах управління, уявлення про процес вирішення проблем і необхідність представлення й обробки знань. Алгоритми і їхня роль. Стисла характеристика напрямків представлення знань. |
|
|
1 |
Розділ 5. Проблеми і алгоритми. Алгоритми, розв’язність, обчислюваність, перераховність. Основні етапи повної побудови алгоритму. Структурне програмування зверху-вниз і правильність програм. Базові структури даних. Розвиток уявлень про структури даних |
|
|
2 |
Розроблення та аналіз алгоритмів. Методи розроблення алгоритмів. Алгоритми перебору з відходом назад. Метод гілок і границь. Жадібні алгоритми. Рекурсія. Амортизаційний аналіз. |
|
|
3 |
Алгоритми розв’язання окремих класів проблем. Алгоритми пошуку в глибину і ширину для задач теорії графів. Алгоритми визначення кістякового дерева мінімальної ваги. Алгоритми паралельних обчислень. Алгоритми пошуку підрядків. |
|
|
4 |
Роздiл 6. Уточнення алгоритму за Т’юрінгом і дослідження Модельних властивостей теорiЇ S-арифметики. Уточнення інтуїтивного означення алгоритму за Т’юрінгом. Приклади розв’язуваних і нерозв’язуваних предикатів, обчислюваних і необчислюваних функцій. Теорема Черча. Аналіз модельних властивостей теорії S-арифметики за допомогою апарату машини Тьюрінга. |
|
|
5 |
Теорія рекурсивних функцій та її застосування для встановлення нерозв’язуваності масових проблем Рекурсивні функції. Розвиток уявлень про рекурсивність арифметичних функцій. Обчислюваність, розв’язуваність та рекурсивність. Десята проблема Гільберта. Схема встановлення нерозв`язуваності. |
|
|
6 |
Обчислюваність та розв’язуваність за марковим. Нормальні алгорифми Маркова. |
|
|
7 |
Розділ 7. Важкорозв’язувані проблеми і теорія звідності. Теорія складності. Базові поняття теорії звідності. Елементи теорії NP-повних проблем (теорії NP-повноти). Методи доведення NP-повноти. Приклади проблем та їх аналізу методами теорії алгоритмів. Застосування теорії NP-повноти для аналізу проблем. |
|
|
8 |
NP-тяжкі задачі. Зводимість за Т’юрінгом і NP-тяжкі проблеми. Історична довідка. |
|
|
9 |
Розділ 8 Підхід до автоматизованого виробництва програм Алгебри і алгоритми. Алгоритми і засоби їх проектування. Проектування схем алгоритмів. Перетворення схем алгоритмів. Приклади проектування алгоритмів для пошуку і символьного оброблення інформації. |
|
|
10 |
Аксіоматичний підхід Застосування формальних теорій до програмування. Метод індуктивних тверджень Флойда. Реалізація схеми Флойда. |
|
|
