ТЕОРІЯ АЛГОРИТМІВ
Робоча програма навчальної дисципліни (Силабус)
Реквізити навчальної дисципліни
| Рівень вищої освіти | Перший (бакалаврський) |
|---|---|
| Галузь знань | 12 Інформаційні технології |
| Спеціальність | 126 Інформаційні системи та технології |
| Освітня програма | Інтегровані інформаційні системи |
| Статус дисципліни | Нормативна |
| Форма навчання | очна(денна)/заочна/дистанційна |
| Рік підготовки, семестр | 1 курс, весінній семестр |
| Обсяг дисципліни | 180 годин (54 години – Лекції, 36 годин – Лабораторні, 90 годин – СРС) |
| Семестровий контроль/ контрольні заходи | Залік/залікова робота, модульна контрольна робота |
| Розклад занять | http://rozklad.kpi.ua |
| Мова викладання | Українська |
| Інформація про керівника курсу / викладачів |
Лектор: декан ФІОТ, професор кафедри АУТС, д.т.н., професор Теленик Сергій Федорович Лабораторні: асистент кафедри АУТС Цимбал Святослав Ігорович Telegram: @sv_tsymbal |
| Розміщення курсу | https://campus.kpi.ua |
Програма навчальної дисципліни
Опис навчальної дисципліни, її мета, предмет вивчання та результати навчання
Опис дисципліни. При проходженні даної дисципліни, студенти познайомляться з поняттям «алгоритм», класичними алгоритмами та структурами даних, підходами до побудови та аналізу алгоритмів, підходами до автоматизації проектування алгоритмів. На лабораторних заняттях опанують етапи розв’язання алгоритмічних задач. В курсі передбачений контроль якості отриманих знань у вигляді модульних контрольних робіт. Сформовані директорії на гугл-диску для обміну інформацією викладач-студент.
Предмет навчальної дисципліни: вивчення студентами основ алгоритмізації процесів комп’ютеризації управління, розуміння взаємозв’язків між проблемами та алгоритмами, одержання навичок з розроблення та аналізу алгоритмів, формування уявлень про способи уточнення алгоритму та встановлення невирішуваності масових проблем і вміння аналізу експоненційних проблем, ознайомлення з теорією автоматизації проектування алгоритмів і практикою автоматизації програмування.
Міждисциплінарні зв’язки. Дисципліна Теорія алгоритмів базується на дисциплінах: Програмування – 1. Основи програмування; Спеціальні розділи математики-1. Дискретна математика.
Мета навчальної дисципліни. Метою навчальної дисципліни є формування у студентів здатностей: аналізувати проблеми алгоритмізації при створенні комп’ютеризованих систем управління та автоматики; виконувати розроблення, аналіз, обґрунтування, оцінювання та реалізацію алгоритмів.
Основні завдання навчальної дисципліни
Знання:
ролі та місця алгоритмів та структур даних в задачах проектування і реалізації комп’ютеризованих систем управління та автоматики;
основних прийомів розроблення алгоритмів;
основних класів алгоритмів, важливих для створення алгоритмічного забезпечення комп’ютеризованих систем управління та автоматики;
методики оцінювання складності алгоритмів;
основних методів уточнення алгоритмів і схеми встановлення невирішуваності масових проблем;
особливостей класів поліноміальних і експоненційних проблем;
методики встановлення NP-повноти масових проблем;
основ автоматизації виробництва алгоритмів.
Уміння:
розробляти алгоритми;
оцінювати алгоритми;
використовувати структури даних для розроблення алгоритмів;
будувати машини Т’юринга для елементарних функцій;
будувати рекурсивні схеми для елементарних функцій;
проектувати схеми алгоритмів;
використовувати сучасне програмне забезпечення, яке дозволяє автоматизувати розроблення алгоритмів.
Пререквізити та постреквізити дисципліни (місце в структурно-логічній схемі навчання за відповідною освітньою програмою)
Пререквізити: вміти користуватися комп’ютером на рівні користувача, вміти писати код однією з розповсюджених мов програмування (С/С++, Java, C#, Python).
Постреквізити: розробка та аналіз алгоритмів.
Після проходження дисципліни студенти зможуть вибирати існуючі алгоритми та структури даних для вирішення поставлених задач, розробляти та адаптувати алгоритми, проводити аналіз алгоритмів, документувати розроблені алгоритми.
Зміст навчальної дисципліни
Очна форма
Лекційні заняття
Розділ 1. Проблеми та алгоритми. Розроблення та аналіз алгоритмів.
Розділ 2. Уточнення алгоритму та встановлення невирішуваності масових проблем
Розділ 3. Теорія складності та звідності
Розділ 4. Автоматизація проектування алгоритмів.
Лабораторні заняття
1. Прості алгоритми.
2. Списки.
3. Рекурсія.
4. Алгоритми сортування.
5. Дерева пошуку.
6. Хеш-таблиці.
7. Динамічне програмування, жадібні алгоритми.
8. Машини Тюрінга.
Заочна форма
Лекційні заняття
Розділ 1. Проблеми та алгоритми. Розроблення та аналіз алгоритмів.
Розділ 2. Теорія складності та звідності
Лабораторні заняття
1. Прості алгоритми. Списки.
2. Рекурсія. Алгоритми сортування. Дерева пошуку.
Навчальні матеріали та ресурси
Базова література
Теорія алгоритмів. Конспект лекцій. Упорядник С.Ф.Теленик.
Методичні вказівки з теорії алгоритмів. Укладачі: С.Ф.Теленик, О.А. Амонс, М.М. Букасов.
Роберт Седжвик. Фундаментальные алогоритмы на С, 3 редакция. – Киев: издательство «DiaSoft», 2003г.– 1127с.
С. Гудман, С. Хидетниеми. Введение в разработку и анализ алгоритмов.– Москва: Мир, 1981. – 366 с.
Кормен «Алгоритми: побудова та аналіз»
Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1986. 320с.
Гери М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. – 420с.
Ющенко К.Л., Суржко С.В., Цейтлин Г.О., Шевченко А.І. Алгоритмічні алгебри: Навч.посібник. – К.:ІЗМН, 1997. – 480 с.
Допоміжна література
Марков А.А., Нагорный Н.М. Теория алгоритмов. – М.: Наука, 1984.- 420с.
Катленд Н. Вычислимость. – М.: Мир, 1983. – 180с.
Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. – К.: Наукова думка, 1984. – 360с.
Навчальний контент
Методика опанування навчальної дисципліни (освітнього компонента)
Очна форма
Лекційні заняття
| № з/п | Назва теми лекції та перелік основних питань (перелік дидактичних засобів, посилання на літературу та завдання на СРС) |
|---|---|
| 1 | Тема 1.1. Структура та зміст курсу. РСО. Тема 1.2. Проблеми і алгоритми. Лекція 1. Вступ. Загальні поняття. Проблеми і алгоритми. Структура курсу Теорія алгоритмів, РСО. Інтуїтивне визначення алгоритму. Вирішуваність, обчислюваність, перераховність. Сутність і особливості етапів вирішення проблем: постановка проблеми; побудова моделі; розроблення алгоритму; встановлення правильності алгоритму; реалізація алгоритму; аналіз алгоритму і його складності; перевірка правильності; документування. Література: [1 ст. 2-40] Завдання на СРС. Структурне програмування зверху-вниз: сутність структурного програмування; програмування зверху-вниз і правильність програм; розвиток уявлень про структурне програмування. |
| 2 | Тема 1.3. Структури даних. Лекція 2. Структури даних. Масиви та списки. Базові структури даних. Масиви. Зв’язані списки. Списки суміжності. Стеки, черги. Література: [1 ст. 47-80] Завдання на СРС. Впорядковані списки. Розріджені списки. Ефективні структури даних на основі списків зі списків. |
| 3 | Тема 1.3. Структури даних. Лекція 3. Структури даних. Двійкові дерева пошуку. Двійкові дерева пошуку. Основні операції, порівняння зі списками. АВЛ-дерева. Література: [1 ст. 47-80] Завдання на СРС. Червоно-чорні дерева: визначення; операції; оцінки; застосування. |
| 4 | Тема 1.3. Структури даних. Лекція 4. Структури даних. Б-дерева. Б-дерева: визначення; операції; оцінки; застосування. Література: [1 ст. 116-132] Завдання на СРС. Піраміди: визначення; операції; оцінки; застосування. |
| 5 | Тема 1.3. Структури даних. Лекція 5. Структури даних. Хеш-таблиці. Розвиток уявлень про структури даних. Загальна характеристика хешуван-ня. Хеш-функції. Відкрита адресація. Література: [1 ст. 80-100] Завдання для СРС. Порівняння різних підходів відкритої адресації. |
| 6 | Тема 1.4. Розроблення та аналіз алгоритмів Лекція 6. Методи розроблення алгоритмів. Методи розроблення алгоритмів. Схема часткових цілей. Схема підйому. Література: [1 ст. 133-146] Завдання для СРС. Метод гілок і границь. Загальна схема. Розгалуження. Оцінювання. особливості застосування. |
| 7 | Тема 1.4. Розроблення та аналіз алгоритмів Лекція 7. Інтерпретація методів розроблення алгоритмів. Методи розроблення алгоритмів. Схема відпрацювання назад. Інтерпретація методів розроблення алгоритмів на прикладі методів перебору з відходом назад. Література: [1 ст. 133-146] Завдання для СРС. Порівняння методів розроблення алгоритмів. |
| 8 | Тема 1.4. Розроблення та аналіз алгоритмів Лекція 8. Динамічне програмування. Динамічне програмування. Загальна схема. Умови застосування. Реалізація схеми динамічного програмування для задач множення матриць, оптимальної тріангуляції багатокутників Література: [1 ст. 162-189] Завдання для СРС. Реалізація схеми динамічного програмування для задачі найбільшої загальної підпослідовності. |
| 9 | Тема 1.4. Розроблення та аналіз алгоритмів Лекція 9. Рекурсія. Рекурсія. Застосування рекурсивної схеми до визначення факторіалу, чисел Фібоначчі, функції Акермана, розбиття цілого, ідентифікації мови. Література: [1 ст. 215-221] Завдання для СРС. Евристики. Евристичні алгоритми для задач комівояжера і теорії розкладів Оцінювання якості наближених алгоритмів. |
| 10 | Тема 1.5. Алгоритми розв’язання окремих класів проблем Лекція 10. Алгоритми сортування. Алгоритми сортування. Прості алгоритми, швидкі алгоритми. Оцінка та порівняння алгоритмів Література: [1 ст. 306-348] Завдання для СРС. Алгоритми сортування за лінійний час з додатковими обмеженнями. Алгоритми зовнішнього сортування. |
| 11 | Тема 1.5. Алгоритми розв’язання окремих класів проблем Лекція 11. Алгоритми паралельних обчислень. Алгоритми паралельних обчислень. Моделі паралельних машин. Ефективна паралельна обробка префіксів. Література: [1 ст. 306-348] Завдання для СРС. Паралельні алгоритми сортування. |
| 12 | Тема 1.5. Алгоритми розв’язання окремих класів проблем Лекція 12. Алгоритми на графах. Алгоритми на графах. Пошук в глибину і ширину. Пошук кістякових дерев. Рекурсія і ітерація. Література: [1 ст. 273-280] Завдання для СРС. Порівняння алгоритмів на графах та деревах. |
| 13 | Тема 1.5. Алгоритми розв’язання окремих класів проблем Лекція 13. Алгоритми на графах. Мережі і проблема визначення кістякового дерева мінімальної ваги. Алгоритм PRIM. Реалізація алгоритму. Аналіз складності алгоритму. Перевірка програми. Література: [1 ст. 280-306] Завдання для СРС. Алгоритми пошуку мінімальної відстані в графах. |
| 14 | Тема 1.5. Алгоритми розв’язання окремих класів проблем Лекція 14. Алгоритми пошуку підрядків. Алгоритми пошуку підрядків. Проблема пошуку підрядків. Найпростіший алгоритм. Алгоритм Рабіна-Карпа. Література: [1 ст. 348-382]. Завдання для СРС. Алгоритми на основі скінчених автоматів. Алгоритм Кнута-Моріса-Прата. Алгоритм Боєра-Мура. |
| 15 | Лекція 15. Модульна контрольна робота На контрольну роботу виноситься увесь попередній матеріал, що включає розглянуті алгоритми та структури даних. Завдання включають теоретичну частину та практичну частини. Завдання для СРС. Повторити матеріал 1-14 лекцій. |
| 16 | Тема 2.1. Уточнення алгоритму за Тюрінгом і дослідження модельних властивостей теорiї S-арифметики Лекція 16. Машини Тюрінга. Уточнення інтуїтивного визначення алгоритму за Тюрінгом. Машина Тюрінга. Уточнення алгоритму за допомогою машини Тюрінга. Література: [1 ст. 383-391] Завдання для СРС. Приклади розв’язуваних і не розв’язуваних предикатів, обчислювальних і не обчислювальних функцій. Теорема Черча. Індекс машини Тюрінга. Застосування підходу Тюрінга до аналізу модельних властивостей теорії S-арифметики: невирішуваність, неповнота, несуперечливість.. |
| 17 | Тема 2.2. Теорія рекурсивних функцій та її застосування для встановлення невирішуваності масових проблем Лекція 17. Рекурсивні функції. Рекурсивні функції. Уявлення про примітивно-рекурсивні функції, частко-во-рекурсивні функції і загально-рекурсивні функції. Визначення і властивості примітивно-рекурсивних функцій, визначення і властивості частково-рекурсивних функцій і загально-рекурсивних функцій. Література: [1 ст. 410-418]. Завдання для СРС. Розвиток уявлень про примітивну рекурсивність. Примітивна рекурсивність відношень ділимості і простоти натуральних чисел. |
| 18 | Тема 2.2. Теорія рекурсивних функцій та її застосування для встановлення невирішуваності масових проблем Лекція 18. Обчислюваність, вирішуваність і рекурсивність Обчислюваність, вирішуваність і рекурсивність. Рекурсивна обчислюваність. Рекурсивна вирішуваність, примітивно-рекурсивні множини, рекурсивні множини, частково-рекурсивні множини. Властивості рекурсивних і примітивно-рекурсивних множин. Рекурсивно-перераховні множини. Література: [1 ст. 429-440] Завдання для СРС. Нумерація пар і кортежів ( n-ок ) чисел. |
| 19 | Тема 2.3. Обчислюваність та вирішуваність за Марковим Лекція 19. Нормальні алгорифми Маркова. Нормальні алгорифми Маркова. Конструктивні процеси і вербальні алгори-тми, нормальні алгорифми Маркова,принципи нормалізації Маркова, обчи-слюваність за Марковим. Література: [1 ст. 448-456] Завдання для СРС. 10 проблема Гільберта. Схема встановлення нерозв’язаність, 10 проблема, властивості діофантовності. |
| 20 | Тема 3.1. Важковирішувані проблеми і теорія звідності Лекція 20. Теорія складності і класи P, NP. Теорія складності. Проблеми і кодування, обчислювальна модель і класи P, NP. Базові поняття теорії звідності, співвідношення класів P, NP і NP-повних проблем, звідність, теорема Кука. Література: [1 ст. 458-489] Завдання для СРС. Інші класи складності – PSPACE, EXPTIME, EXPSPACE. |
| 21 | Тема 3.1. Важковирішувані проблеми і теорія звідності Лекція 21. Елементи теорії NP-повноти. Елементи теорії NP-повноти. Проблема 3-виконуваність, проблема «тривимірне сполучення», проблема «вершинне покриття», проблема «Кліка», проблема розбиття. Література: [1 ст. 458-489] Завдання для СРС. Проблема «Гамільтонів цикл», проблема «точне покриття 3-множинами», ієрархія NP-повних проблем. |
| 22 | Тема 3.1. Важковирішувані проблеми і теорія звідності Лекція 22. Методи доведення NP-повноти Методи доведення NP-повноти. Загальна характеристика прийомів доведення NP- повноти, звуження проблеми, локальна заміна, побудова компонентів. Аналіз під проблем. Проблеми з числовими параметрами і сильна NP-повнота. Література: [1 ст. 513-531]. Завдання для СРС. Застосування теорії NP-повноти для аналізу проблем. Проблема розкладу, проблема розфарбування, проблема максимального розрізу. Приклади проблем та їх аналізу методами теорії алгоритмів.. |
| 23 | Тема 3.2. NP-важкі задачі. Лекція 23. NP-важкі задачі Зведення за Тюрінгом і NP-важкі проблеми. Визначення NP-важких проблем, проблема «K-i по порядку підмножини», проблема добудови туру комівояжера. Література: [1 ст. 584-599]. Завдання для СРС. Нумерація пар і кортежів ( n-ок ) чисел. |
| 24 | Лекція 24. Модульна контрольна робота На контрольну роботу виноситься увесь попередній матеріал, що включає розглянуті теоретичні методи та підходи. Завдання включають теоретичну частину та практичну частини. Завдання для СРС. Повторити матеріал 16-23 лекцій. |
| 25 | Тема 4.1. Алгебраїчний підхід до автоматизованого виробництва програм Лекція 25. Алгебраїчні конструкції для зображення програм Алгебраїчні конструкції для зображення програм. Граф-схеми інтерпретації, логіко-функціональні моделі, алгебри, схеми алгоритмів. Література: [1 ст. 604-624] Завдання для СРС. Алгоритми і засоби їх проектування. Формалізоване проектування алгоритмів. Алгебра Дейкстри, алгебра схем Янова.. |
| 26 | Тема 4.1. Алгебраїчний підхід до автоматизованого виробництва програм Лекція 26. Проектування схем алгоритмів Проектування схем алгоритмів. Метаправила конструювання, позначення багаторівневих файлів. Пошук. Література: [1 ст. 644-664] Завдання для СРС. Граф-схеми алгоритмів, системи алгебр алгоритмів (САА) Глушкова, алгебра узагальнених граф-схем. |
| 27 | Тема 4.2. Аксіоматичний підхід до автоматизованого виробництва програм Лекція 27. Аксіоматичний підхід до автоматизованого виробництва програм Метод індуктивних тверджень Флойда. Зображення програм операторними схемами, структурне програмування і автоматизація програмування. Література: [1 ст. 664-684]. Завдання для СРС. Реалізація схеми Флойда. Встановлення часткової коректності програм і ілюстрація методу на прикладі. |
Лабораторні заняття
| № | Назва лабораторної роботи | Кількість ауд. годин |
|---|---|---|
| 1 | Лабораторна робота 1. Прості алгоритми. Необхідно виконати усі етапи вирішення алгоритмічної задачі на прикладах простих задач. Результатом проведеної роботи повинен бути звіт з детальним описом усіх виконаних кроків. Література: [1] |
4 |
| 2 | Лабораторна робота 2. Списки. Необхідно реалізувати списки на основі масивів та зв’язних списків. Результатом проведеної роботи повинен бути звіт з детальним описом реалізованих алгоритмів та структур даних, зокрема порівняння теоретичної та практичної складності. Література: [1] |
4 |
| 3 | Лабораторна робота 3. Рекурсія. Необхідно вирішити алгоритмічні задачі з використанням рекурсії. Результатом проведеної роботи повинен бути звіт з детальним описом реалізованих алгоритмів та структур даних, зокрема порівняння теоретичної та практичної складності. Література: [1] |
4 |
| 4 | Лабораторна робота 4. Алгоритми сортування. Необхідно реалізувати декілька класичних алгоритмів сортування. Результатом проведеної роботи повинен бути звіт з детальним описом реалізованих алгоритмів та структур даних, зокрема порівняння теоретичної та практичної складності. Література: [1] |
4 |
| 5 | Лабораторна робота 5. Дерева пошуку. Необхідно реалізувати дерева пошуку. Результатом проведеної роботи повинен бути звіт з детальним описом реалізованих алгоритмів та структур даних, зокрема порівняння теоретичної та практичної складності. Література: [1] |
6 |
| 6 | Лабораторна робота 6. Хеш-таблиці. Необхідно реалізувати хеш таблиці на основі додаткових контейнерів та відкритої адресації. Результатом проведеної роботи повинен бути звіт з детальним описом реалізованих алгоритмів та структур даних, зокрема порівняння теоретичної та практичної складності. Література: [1] |
6 |
| 7 | Лабораторна робота 7. Динамічне програмування, жадібні алгоритми. Необхідно вирішити алгоритмічні задачі з використанням жадібних алгоритмів та методів динамічного програмування. Результатом проведеної роботи повинен бути звіт з детальним описом реалізованих алгоритмів та структур даних, зокрема порівняння теоретичної та практичної складності. Література: [1] |
4 |
| 8 | Лабораторна робота 8. Машини Тюрінга. Необхідно реалізувати алгоритми для вирішення простих задач з використанням машини Тюрінга. Результатом проведеної роботи повинен бути звіт з детальним описом реалізованих алгоритмів та структур даних, зокрема порівняння теоретичної та практичної складності. Література: [1] |
4 |
Заочна форма
Лекційні заняття
| № з/п | Назва теми лекції та перелік основних питань (перелік дидактичних засобів, посилання на літературу та завдання на СРС) |
|---|---|
| 1 | Тема 1.1. Структура та зміст курсу. РСО. Тема 1.2. Проблеми і алгоритми. Тема 1.3. Структури даних. Лекція 1. Вступ. Загальні поняття. Проблеми і алгоритми. Класичні структури даних Структура курсу Теорія алгоритмів, РСО. Інтуїтивне визначення алгоритму. Сутність і особливості етапів вирішення проблем: постановка проблеми; побудова моделі; розроблення алгоритму; встановлення правильності алгоритму; реалізація алгоритму; аналіз алгоритму і його складності; перевірка правильності; документування. Класичні структури даних: списки, дерева, хеш-таблиці. Література: [1, ст. 2-100] Завдання на СРС. Класичні алгоритми. Сортування, алгоритми на графах, алгоритми пошуку підрядків |
| 2 | Тема 1.4. Розроблення та аналіз алгоритмів Тема 2.1. Уточнення алгоритму за Тюрінгом Тема 2.2. Важковирішувані проблеми і теорія звідності Лекція 2. Методи розроблення та аналізу алгоритмів. Формальна теорія алгоритмів. Методи розроблення алгоритмів. Схема часткових цілей. Схема підйому. Рекурсія. Динамічне програмування. Жадібні алгоритми. Машини Тюрінга. Елементи теорії NP-повноти. Література: [1, 133-531] Завдання для СРС. Нормальні алгорифми Маркова. Рекурсивні та примітивно-рекурсивні функції. Автоматизація програмування на основі алгебраїчних підходів. |
Лабораторні заняття
| № | Назва лабораторної роботи | Кількість ауд. годин |
|---|---|---|
| 1 | Лабораторна робота 1. Прості алгоритми. Списки. Необхідно реалізувати прості алгоритми та алгоритми на основі списків. Результатом проведеної роботи повинен бути звіт з детальним описом реалізованих алгоритмів та структур даних, зокрема порівняння теоретичної та практичної складності. Література: [1]. |
2 |
| 2 | Лабораторна робота 2. Рекурсія. Алгоритми сортування. Дерева пошуку.. Необхідно реалізувати алгоритми на основі рекурсії, алгоритми сортування та дерева пошуку. Результатом проведеної роботи повинен бути звіт з детальним описом реалізованих алгоритмів та структур даних, зокрема порівняння теоретичної та практичної складності. Література: [1]. |
2 |
Самостійна робота студента/аспіранта
Очна форма
|
Назва теми, що виноситься на самостійне опрацювання | Кількість годин СРС |
|---|---|---|
| 1 | Структурне програмування зверху-вниз: сутність структурного програмування; програмування зверху-вниз і правильність програм; розвиток уявлень про структурне програмування. | 2 |
| 2 | Впорядковані списки. Розріджені списки. Ефективні структури даних на основі списків зі списків. | 2 |
| 3 | Червоно-чорні дерева: визначення; операції; оцінки; застосування. | 2 |
| 4 | Піраміди: визначення; операції; оцінки; застосування. | 2 |
| 5 | Порівняння різних підходів відкритої адресації. | 2 |
| 6 | Метод гілок і границь. Загальна схема. Розгалуження. Оцінювання. особливості застосування. | 2 |
| 7 | Порівняння методів розроблення алгоритмів. | 2 |
| 8 | Реалізація схеми динамічного програмування для задачі найбільшої загальної підпослідовності. | 4 |
| 9 | Евристики. Евристичні алгоритми для задач комівояжера і теорії розкладів Оцінювання якості наближених алгоритмів. | 4 |
| 10 | Алгоритми сортування за лінійний час з додатковими обмеженнями. Алгоритми зовнішнього сортування. | 4 |
| 11 | Паралельні алгоритми сортування. | 8 |
| 12 | Порівняння алгоритмів на графах та деревах. | 4 |
| 13 | Алгоритми пошуку мінімальної відстані в графах. | 2 |
| 14 | Алгоритми на основі скінчених автоматів. Алгоритм Кнута-Моріса-Прата. Алгоритм Боєра-Мура. | 4 |
| 15 | Підготовка до МКР. Повторити матеріал 1-14 лекцій. | 6 |
| 16 | Приклади розв’язуваних і не розв’язуваних предикатів, обчислювальних і не обчислювальних функцій. Теорема Черча. Індекс машини Тюрінга. Застосування підходу Тюрінга до аналізу модельних властивостей теорії S-арифметики: невирішуваність, неповнота, несуперечливість.. | 2 |
| 17 | Розвиток уявлень про примітивну рекурсивність. Примітивна рекурсивність відношень ділимості і простоти натуральних чисел. | 2 |
| 18 | Нумерація пар і кортежів ( n-ок ) чисел. | 2 |
| 19 | 10 проблема Гільберта. Схема встановлення нерозв’язаність, 10 проблема, властивості діофантовності. | 4 |
| 20 | Інші класи складності – PSPACE, EXPTIME, EXPSPACE. | 2 |
| 21 | Проблема «Гамільтонів цикл», проблема «точне покриття 3-множинами», ієрархія NP-повних проблем. | 2 |
| 22 | Застосування теорії NP-повноти для аналізу проблем. Проблема розкладу, проблема розфарбування, проблема максимального розрізу. Приклади проблем та їх аналізу методами теорії алгоритмів.. | 2 |
| 23 | Нумерація пар і кортежів ( n-ок ) чисел. | 2 |
| 24 | Підготовка до МКР. Повторити матеріал 16-23 лекцій. | 6 |
| 25 | Алгоритми і засоби їх проектування. Формалізоване проектування алгоритмів. Алгебра Дейкстри, алгебра схем Янова. | 2 |
| 26 | Граф-схеми алгоритмів, системи алгебр алгоритмів (САА) Глушкова, алгебра узагальнених граф-схем. | 2 |
| 27 | Реалізація схеми Флойда. Встановлення часткової коректності програм і ілюстрація методу на прикладі. | 2 |
| 28 | Підготовка до заліку по всьому матеріалу модуля. | 10 |
**
**
Заочна форма
|
Назва теми, що виноситься на самостійне опрацювання | Кількість годин СРС |
|---|---|---|
| 1 | Алгоритми сортування | 24 |
| 2 | Алгоритми на графах | 32 |
| 3 | Алгоритми пошуку підрядків | 32 |
| 4 | Нормальні алгорифми Маркова. | 20 |
| 5 | Рекурсивні та примітивно-рекурсивні функції. | 20 |
| 6 | Автоматизація програмування на основі алгебраїчних підходів. | 24 |
| 7 | Підготовка до заліку по всьому матеріалу модуля. | 20 |
Політика та контроль
Політика навчальної дисципліни (освітнього компонента)
Система вимог, які ставляться перед студентом:
відвідування лекційних та лабораторних занять є обов’язковою складовою вивчення матеріалу;
на лекції викладач користується власним презентаційним матеріалом; використовує гугл-диск для викладання матеріалу поточної лекції, додаткових ресурсів, лабораторних робіт та інше; викладач відкриває доступ до певної директорії гугл-диска для скидання електронних лабораторних звітів та відповідей на МКР;
на лекції заборонено відволікати викладача від викладання матеріалу, усі питання, уточнення та ін. студенти задають в кінці лекції у відведений для цього час;
лабораторні роботи захищаються у два етапи – перший етап: студенти виконують завдання на допуск до захисту лабораторної роботи; другий етап – захист лабораторної роботи. Бали за лабораторну роботу враховуються лише за наявності електронного звіту;
модульні контрольні роботи пишуться на лекційних заняттях без застосування допоміжних засобів (мобільні телефони, планшети та ін.); результат пересилається у файлі до відповідної директорії гугл-диску;
заохочувальні бали виставляються за: активну участь на лекціях; участь у факультетських та інститутських олімпіадах з навчальних дисциплін, участь у конкурсах робіт, підготовка оглядів наукових праць; презентацій по одній із тем СРС дисципліни тощо. Кількість заохочуваних балів не більше 10;
штрафні бали виставляються за: невчасну здачу лабораторної роботи. Кількість штрафних балів не більше 10.
Види контролю та рейтингова система оцінювання результатів навчання (РСО) (очна форма)
Рейтинг студента з дисципліни складається з балів, що він отримує за:
виконання та захист 8 лабораторних робіт;
виконання 2 модульних контрольних робіт (МКР);
заохочувальні та штрафні бали.
Система рейтингових балів та критерії оцінювання
Лабораторні роботи:
«відмінно», повна відповідь на питання під час захисту (не менш ніж 90% потрібної інформації) та оформлений належним чином електронний протокол до лабораторної роботи – 10 балів;
«добре», достатньо повна відповідь на питання під час захисту (не менш ніж 75% потрібної інформації) та оформлений належним чином електронний протокол до лабораторної роботи – 8-9 балів;
«задовільно», неповна відповідь на питання під час захисту (не менш ніж 60% потрібної інформації), незначні помилки та оформлений належним чином електронний протокол до лабораторної роботи – 6-7 балів;
«незадовільно», незадовільна відповідь та/або не оформлений належним чином електронний протокол до лабораторної роботи – 0-5 балів.
За кожне заняття запізнення з поданням лабораторної роботи до захисту від встановленого терміну оцінка знижується на 2 бали.
Модульні контрольні роботи:
«відмінно», повна відповідь (не менш ніж 90% потрібної інформації) – 10 балів;
«добре», достатньо повна відповідь (не менш ніж 75% потрібної інформації), або повна відповідь з незначними помилками – 8-9 балів;
«задовільно», неповна відповідь (але не менш ніж 60% потрібної інформації) та незначні помилки – 6-7 балів;
«незадовільно», незадовільна відповідь (неправильний розв’язок задачі), потребує обов’язкового повторного написання в кінці семестру – 0-5 балів.
Заохочувальні бали
– за виконання творчих робіт з кредитного модуля (наприклад, участь у факультетських та інститутських олімпіадах з навчальних дисциплін, участь у конкурсах робіт, підготовка оглядів наукових праць тощо); за активну роботу на лекції (питання, доповнення, зауваження за темою лекції, коли лектор пропонує студентам задати свої питання) 1-2 бали, але в сумі не більше 10;
– презентації по СРС – від 1 до 5 балів.
Міжсесійна атестація
За результатами навчальної роботи за перші 7 тижнів максимально можлива кількість балів – 50 балів (3 лабораторні, МКР-1). На першій атестації (8-й тиждень) студент отримує «зараховано», якщо його поточний рейтинг не менший ніж 30 балів.
За результатами 13 тижнів навчання максимально можлива кількість балів – 80 балів (6 лабораторних, МКР-2). На другій атестації (14-й тиждень) студент отримує «зараховано», якщо його поточний рейтинг не менший ніж 48 балів.
Максимальна сума вагових балів контрольних заходів протягом семестру складає:
RD = 8*rлаб+2*rмкр + (rз - rш)=8*10+2*10+ (rз - rш)=100 + (rз - rш),
де rлаб – бал за лабораторну роботу (0…10);
rмкр – бал за написання МКР (0…10);
rз – заохочувальні бали за активну участь на лекціях, презентації, участь в олімпіадах, конкурсі роботи, наукові роботи за тематикою дисципліни (0…10);
rзш – штрафні бали.
Залік:
Умовою допуску до заліку є зарахування всіх лабораторних робіт, написання обох модульних контрольних робіт та стартовий рейтинг не менше 40 балів.
Студенти, які виконали умови допуску і отримали RD ≥ 60 , отримують відповідну до набраного рейтингу оцінку без додаткових випробувань.
Студенти, які виконали умови допуску і отримали 40<RD<60, складають залікову контрольну роботу (або проходять залікову співбесіду) на останньому за розкладом занятті з дисципліни в семестрі.
Сума стартових балів та балів за залік переводиться до загальної оцінки згідно з таблицею:
Таблиця 1. Переведення рейтингових балів до оцінок за університетською шкалою
| Кількість балів | Оцінка |
| 100-95 | Відмінно |
| 94-85 | Дуже добре |
| 84-75 | Добре |
| 74-65 | Задовільно |
| 64-60 | Достатньо |
| Менше 60 | Незадовільно |
Є не зараховані лабораторні роботи або не зарахована модульна контрольна робота |
Не допущено |
Додаткова інформація з дисципліни (освітнього компонента)
передбачена можливість закривати частину лабораторного та лекційного матеріалу шляхом здобування сертифікатам по online курсам (наприклад, COURSERA) відповідних розділів та тем дисципліни;
перелік теоретичних питань, які виносяться на семестровий контроль наведено в Додатку 1;
на початку семестру викладач аналізує існуючі курси по тематиці дисципліни та пропонує пройти відповідні безкоштовні курси студентам. Після отриманням студентом сертифікату проходження дистанційних чи онлайн курсів за відповідною тематикою, викладач закриває відповідну частину курсу (лабораторні чи лекції) за попередньою домовленістю з групою.
Робочу програму навчальної дисципліни (Силабус):
Складено декан ФІОТ, професор кафедри АУТС, д.т.н., професор Теленик Сергій Федорович
Ухвалено кафедрою АУТС (протокол № 1 від 27.08.2020 р.)
Погоджено Методичною комісією факультету[1] (протокол № 1 від 02.09.2020 р.)
Додаток 1
Перелік теоретичних питань на залік
Поняття алгоритму. Приклади алгоритмів з програмування, математики, алгоритми в повсякденному житті.
Чому важливо вивчати алгоритми?
Області Computer Science (комп'ютерні науки) і Software Engineering (програмна інженерія). Подібності та відмінності. Приклади завдань з цих областей. Яка з них більш важлива?
Етапи рішення алгоритмічних задач (з області Computer Science). Короткий опис кожного етапу, навіщо він потрібен? Порядок виконання етапів. Порівняти з етапами рішення промислових задач (з області Software Engineering).
Етап постановки задачі. Навіщо він потрібен, що на ньому треба робити? Навести приклади.
Етап побудови математичної моделі. Навіщо він потрібен, що на ньому треба робити? Що таке модель? Навести приклади.
Етап розробки алгоритму. Навіщо він потрібен, що на ньому треба робити? Навести приклади. Порівняти з етапом реалізації алгоритму.
Етап перевірки правильності алгоритму. Навіщо він потрібен, що на ньому треба робити? Навести приклади.
Доведення правильності алгоритму з використання передумов, постумов і інваріантів. Навести приклади.
Доведення скінченності алгоритму. Основні підходи і методи. Навести приклади.
Етап реалізації алгоритму. Навіщо він потрібен, що на ньому треба робити? Навести приклади. Порівняти з етапом розробки алгоритму.
Етап перевірки програми. Навіщо він потрібен, що на ньому треба робити? Методи і підходи перевірки. Навести приклади.
Порівняти етапи перевірки правильності алгоритму і перевірки програми. Подібності та відмінності. Чи можна обмежитися тільки одним з них?
Етап аналізу алгоритму і його складності. Навіщо він потрібен, що на ньому треба робити? Методи і підходи аналізу. Навести приклади.
Big O notation. Визначення, приклади використання. Навіщо це потрібно, і чому зручно використовувати? Використання для аналізу часу роботи алгоритму. Аналіз складності стандартних конструкцій програм (послідовне виконання, розгалуження, цикли).
Етап розробки документації. Навіщо він потрібен, що на ньому треба робити? Навести приклади.
Блок схеми. Що це таке, навіщо потрібно? Нотація для основних елементів алгоритму. Навести приклади.
Математичні об’єкти для зберігання багатьох елементів. Порівняти, навести приклади.
Уніфікований механізм обходу різних структур даних. Приклади.
Навіщо потрібно сортування? Навести приклади.
Критерії сортування. Які бувають, переваги та недоліки, навести приклади.
Властивості алгоритмів сортування – стабільність, in-place, адаптивність. Чому вони важливі? Навести приклади алгоритмів, що мають та не мають цих властивостей.
Tail call optimization. Що це таке, навіщо потрібно, як працює, як реалізовується. Приклади алгоритмів, де це може бути корисно.
Поняття comparison sort. Чому воно актуальне? Навести приклади алгоритмів, що мають та не мають цю властивість. Оцінка найгіршої складності для таких алгоритмів.
Зовнішнє сортування. Навіщо потрібне, приклади алгоритмів.
Навіщо потрібні деревовидні структури даних? Навести приклади.
Порядки обходу дерев.
Масив фіксованого розміру. Операції доступу за індексом, модифікації за індексом, вставки в кінець, вставки в довільне місце, видалення за індексом та за значенням, пошуку за значенням.
Список на основі масиву (динамічний масив). Операції доступу за індексом, модифікації за індексом, вставки в кінець, вставки в довільне місце, видалення за індексом, пошуку за значенням.
Однозв'язний список. Операції доступу за індексом, модифікації за індексом, вставки в кінець, вставки в початок, вставки в середину (після відомого вузла), видалення (відомого вузла), пошуку за значенням.
Двозв'язний список. Операції доступу за індексом, модифікації за індексом, вставки в кінець, вставки в початок, вставки в середину (після відомого вузла), видалення (відомого вузла), пошуку за значенням.
Однозв'язний циклічний список. Операції доступу за індексом, модифікації за індексом, вставки в середину (після відомого вузла), видалення (відомого вузла), обходу.
Двозв'язний циклічний список. Операції доступу за індексом, модифікації за індексом, вставки в середину (після відомого вузла), видалення (відомого вузла), обходу.
Стек (LIFO) на основі масиву змінної довжини та на основі зв'язного списку. Операції додавання, видалення, перегляду вершини стека.
Черга (FIFO) на основі масиву змінної довжини та на основі зв'язного списку. Операції додавання в кінець, видалення з початку.
Впорядкований список на основі масиву змінної довжини. Операції доступу за індексом, вставки, видалення, пошуку за значенням.
Впорядкований список на основі зв'язного списку. Операції доступу за індексом, вставки, видалення, пошуку за значенням.
Розріджений список на основі масиву змінної довжини. Операція доступу за індексом, модифікації за індексом, вставки, видалення, пошуку за значенням.
Розріджений список на основі зв'язного списку. Операція доступу за індексом, модифікації за індексом, вставки, видалення, пошуку за значенням.
Алгоритми Bubble Sort та Selection Sort, порівняння.
Алгоритми Bubble Sort та Insertion Sort, порівняння.
Алгоритми Insertion Sort та Selection Sort, порівняння.
Алгоритм Quicksort.
Алгоритм Merge Sort.
Алгоритм Heap Sort.
Алгоритм Counting Sort.
Алгоритм LSDF Radix Sort.
Алгоритм MSDF Radix Sort.
Алгоритм Bucket Sort.
Бінарні дерева пошуку. Операції пошуку, вставки, видалення за значенням.
АВЛ дерева. Операції пошуку, вставки, видалення за значенням.
Червоно-чорні дерева. Операції пошуку, вставки, видалення за значенням.
Splay tree. Операції пошуку, вставки, видалення за значенням.
B tree. Операції пошуку, вставки, видалення за значенням.
B+ tree. Операції пошуку, вставки, видалення за значенням.
Піраміди (heap). Основні операції, використання, порівняння з деревами пошуку.
Машини Тюрінга. Визначення, призначення, приклади.
Алгоритмічно нерозв’язні задачі. Приклади.
Теорія складності. Класи складності P, NP.
NP-повні задачі. Теорема Кука.
Приклади NP-повних задач.
[1] Методичною радою університету – для загальноуніверситетських дисциплін.
