Теорія алгоритмів

Мета вивчення дисципліни: розвинути здатності студентів до логічного і алгоритмічного мислення, закласти основи знань в галузі теорії алгоритмів, необхідних для ефективного вирішення задач предметної області; освоєння фундаментальних алгоритмів різного призначення, принципів їх створення та аналізу, математичного обґрунтування їх застосування та вибору найбільш ефективного алгоритму для вирішення конкретної задачі

Практичне значення та використання отриманих знань: вивчення фундаментальних алгоритмів різного призначення, принципів їх побудови, функціонування та аналізу; освоєння математичних основ аналізу алгоритмів, видів ефективності алгоритмів, особливостей їх роботи; ознайомитися з основними класами складності алгоритмів та стратегіями вирішення задач; вивчити базові структури алгоритмів, даних, фундаментальні операції над структурами, їх переваги та недоліки, навчитися обирати відповідні структури для різних типів задач;

Основні результати навчання

ПРН1. Застосовувати знання основних форм і законів абстрактно-логічного мислення, основ методології наукового пізнання, форм і методів вилучення, аналізу, обробки та синтезу інформації в предметній області комп'ютерних наук.
ПРН2. Використовувати сучасний математичний апарат неперервного та дискретного аналізу, лінійної алгебри, аналітичної геометрії, в професійній діяльності для розв’язання задач теоретичного та прикладного характеру в процесі проектування та реалізації об’єктів інформатизації.
ПРН5. Проєктувати, розробляти та аналізувати алгоритми розв’язання обчислювальних та логічних задач, оцінювати ефективність та складність алгоритмів на основі застосування формальних моделей алгоритмів та обчислюваних функцій.

Тематика та види навчальних занять
 
1 тиждень.
Лекція  1 «Інтуїтивне поняття алгоритму і його властивості. Класифікація алгоритмів. Способи подання алгоритмів/ Визначення алгоритму. Обчислювальний процес. Властивості алгоритму».
Самостійна робота здобувача. Консультація.
 
2 тиждень.
Лекція  2 «Класифікації алгоритмів. Опис алгоритмів. Середовище та виконавець алгоритму, системи команд та елементарних дій. Поняття псевдокоду».
Лабораторне заняття 1 «Розробка лінійних та алгоритмів, що розгалужуються.»
Самостійна робота здобувача. Консультація.
 
3 тиждень.
Лекція  3 «Запис алгоритмів за допомогою мови блок-схем. Основні алгоритмічні структури. Лінійна  та розгалужена структури. Приклади запису алгоритму за допомогою мови блок-схем.»
Самостійна робота здобувача. Консультація.

4 тиждень.
Лекція  4 «Запис алгоритмів за допомогою мови блок-схем. Ітераційні та вкладені цикли. Обробка масивів та матриць. Приклади запису алгоритму за допомогою мови блок-схем.»
Лабораторне заняття 2 «Розробка циклічних алгоритмів.»
Самостійна робота здобувача. Консультація.
 
5 тиждень.
Лекція  5 «Класична теорія алгоритмів. Обчислюваної функції, розв'язні і перелічуваних безлічі. Графік обчислюваної функції. Виникнення математичної теорії алгоритмів. Парадокси теорії множин. Обчислюваної функції. Розв'язні і перелічуваних безлічі. Ефективно обчислювана функція. Підходи до визначення класу обчислюваних функцій.»
Самостійна робота здобувача. Консультація.

6тиждень.
Лекція  6 «Рекурсивні функції. Загальне-рекурсивні функції. Базові функції, оператори суперпозиції і примітивної рекурсії. Частково рекурсивні функції. Оператор мінімізації. Натуральні числа як конструктивний об'єкт.»
Лабораторне заняття 3 «Розробка алгоритмів обробки одномірних і двомірних масивів. Робота з матрицями.»
Самостійна робота здобувача. Консультація.

7 тиждень.
Лекція  7 «Рекурсивні функції. Визначення рекурсивних функцій по Черчу. Базові рекурсивні функції. Оператор суперпозиції. Правило суперпозиції. Оператор примітивної рекурсії. Правило примітивної рекурсії. Оператор побудови за першим нулю (оператор мінімізації). Правило мінімізації. Тези.»
Отримання завдання до розрахунково-графічної роботи. Підбір необхідних літературних джерел.
Самостійна робота здобувача. Консультація.
Модульний контроль 1.
 
 
 
 
8 тиждень.
Лекція  8 «Машина Т’юринга. Універсальна машина Т’юринга. Уточнення поняття «алгоритм». Поняття алфавіту, літери, слова. Визначення машини Т’юринга (МТ). Опис МТ. Правило зупинки. Програма МТ. Теза Т’юринга. Приклад програми МТ.» 
Лабораторне заняття 4 «Розробка програм для машини Т’юрінгу.» 
Виконання розрахунково-графічної роботи. Блок-схема роботи алгоритму.
Самостійна робота здобувача. Консультація.

9 тиждень.
Лекція  9  «Машина Поста (МП) Опис МП. Функціонування МП. приклади програм МП. Порівняння МТ і МП. Гіпотеза Посту.»
Виконання розрахунково-графічної роботи. Блок-схема роботи алгоритму.
Самостійна робота здобувача. Консультація.
 
10 тиждень.
Лекція  10 «Нормальні алгоритми Маркова. Поняття алгоритму Маркова. Марковська підстановка. Етапи вирішення завдань. Порядок дії алгоритмів Маркова Приклад алгоритмів Маркова. Еквівалентність описаних теорій.»
Лабораторне заняття 5 «Розробка програм для машини Поста та машини Т’юрінгу.»
Виконання розрахунково-графічної роботи. Блок-схема роботи алгоритму.
Самостійна робота здобувача. Консультація.
 
11 тиждень.
Лекція  11 «Алгоритмічно нерозв'язні проблеми. Масові проблеми. Екстраалгорітм і нерозв'язні проблеми. Самозастосування. Теорема Геделя. Теорема Райса.»
Виконання розрахунково-графічної роботи. Основні принципи роботи машини Т’юрінгу.
Самостійна робота здобувача. Консультація.

12 тиждень.
Лекція  12 «Формальні мови та граматики. Способи опису граматик. Природні і формальні мови. Ланцюги символів, операції над ними. 
Лабораторне заняття 6 «Нормальні алгоритми Маркова (НАМ)».
Захист розрахунково-графічної роботи.
Самостійна робота здобувача. Консультація.

13 тиждень.
Лекція  13 «Поняття мови. Формальне визначення мови. Способи завдання мов. Поняття граматики мови. Рекурсивність в правилах граматики. Опис граматики за допомогою синтаксичних діаграм і мета символів».
Захист розрахунково-графічної роботи.
Самостійна робота здобувача. Консультація.

14 тиждень.
Лекція  14 «Класифікація мов і граматик. Розпізнавати завдання розбору. Класифікація мов і граматик. Чотири типу граматик по Хомського. Класифікація мов. Приклади класифікації мов.»
Лабораторне заняття 7 «Нормальні алгоритми Маркова (НАМ).»
Самостійна робота здобувача. Консультація.
Модульний контроль 2.
 
15 тиждень.
Лекція  15. Основи теорії NP-повноти. Алгоритми і складність. Класифікація алгоритмів з тимчасової складності. Теорія NP-повноти.
Самостійна робота здобувача. Консультація.

 
Оцінювання результатів навчання

Оцінювання результатів навчання з дисципліни здійснюється за накопичувальною системою, яка дає можливість здобувачеві протягом семестру отримати максимально 100 балів.

Модуль 1
Повне виконання лабораторних №№ 1-2 – по 4 бали кожне, № 3 – 5 балів.
Активна робота на лабораторному занятті – максимально по 3 бали за заняття.
Модульна контрольна робота 1 – бездоганне виконання 20 балів (в кожному завданні модульної контрольної роботи наведено максимальну кількість балів за виконання кожного завдання).

Модуль 2
Повне виконання лабораторних №№ 4-6 – по 3 бали кожне, № 7 – 4 бали.
Активна робота на лабораторному занятті – максимально по 3 бали за заняття.
Модульна контрольна робота 2 – бездоганне виконання 20 балів (в кожному завданні модульної контрольної роботи наведено максимальну кількість балів за виконання кожного завдання).

Розрахунково-графічна робота – повне виконання і захист оцінюється в 10 балів.

Посилання на рекомендовані джерела

Колеснікова, К.В. Методичні вказівки щодо виконання практичних завдань з дисципліни «Теорія алгоритмів» [Електронний варіант] / К.В. Колеснікова, Ю.С. Барчанова, О.В. Савєльєва. – Одеса: ОНПУ, 2018. – 25 с.
Колеснікова, К.В. Методичні вказівки щодо виконання розрахунково-графічної роботи з дисципліни «Теорія алгоритмів» [Електронний варіант] / К.В. Колеснікова, Ю.С. Барчанова, О.В. Савєльєва. – Одеса: ОНПУ, 2018. – 20 с.
Лекційний матеріал з дисципліни “Теорія алгоритмів” для студентів усіх форм навчання Спеціальність – 122  Комп’ютерні науки, Спеціалізація: Комп’ютерний дизайн/ Укл.: Лопаков О.С., Космачевський В.В. – Одеса: ОНПУ, 2020. – 92 с.
http//www.window.edu.com/resource/124/25124 – Математическая логика и теория алгоритмов (навчальний посібник).
http//www. knigafund.net/tags/3367 – (навчальний посібник)