1.1 Неформальне тлумачення алгоритму
1.1.1 Історія поняття алгоритму
1.1.2 Визначення алгоритму
1.1.3 Основні властивості алгоритму
1.1.4 Параметри алгоритму
1.1.5 Базові структури алгоритмів (алгоритмічні
конструкції). Теорема Бьома-Якопіні.
1.1.6 Рекурсивні алгоритми
1.1.7 Паралельні алгоритми
1.1.8 Недетерміновані алгоритми
1.1.9 Імовірнісні алгоритми (увипадковлені алгоритми)
1.2 Формалізація поняття алгоритму
(продовження в частині курсу, яка присвячена моделям обчислень(тема №6))
1.2.1 Введення в теорію алгоритмів
1.2.2 Абстрактні моделі алгоритму
1.2.3 Формальні алгоритмічні системи (ФАС)
1.2.4 Скінченний автомат
1.2.4.1 Детермінований скінченний автомат (DFA)
1.2.4.2 Недетермінований скінченний автомат (NFA) та імовірнісний автомат(PA).
1.2.4.3 ω-автомат
1.2.4.4 Автомат з однобуквеними переходами. Формування автомату з однобуквеними переходами за заданим недетермінованим автоматом.
1.2.4.5 Видалення непродуктивних та недосяжних станів скінченного автомату
1.3.4.6 Видалення λ-переходів та ε-переходів у недетермінованому скінченному автоматі
1.3.4.7 Детермінізація квазідетермінованого скінченного автомату
1.3.4.8 Мінімізація скінченого детермінованого автомату
1.2.5 Перетворювачі (трансдуктори) на основі детермінованого скінченного автомату
1.2.5.1 Автомат Мура (Moore machine)
1.2.5.2 Автомат Мілі (Mealy machine)
1.2.6 Автомат з магазинною пам'яттю (МП-автомат, PDA)
1.2.7 Машина Тюрінга та її варіанти
1.2.8 Числення Поста
1.2.9 Нормальні алгоритми Маркова
1.2.10 Регістрова машина
1.2.11 РАМ-машина
1.2.12 ПРАМ-машина та варіанти пам’яті із впорядкованим доступом
1.3 Формальні граматики та формальні мови
1.3.1 Формальні граматики, мови та ієрархія Хомського
1.3.2 Регулярні мови та вирази
1.3.2.1 Властивості граматик регулярних мов. Автоматні граматики. Доповнення автоматної мови.
1.3.2.2 Лема про накачку для регулярних мов
1.3.2.3 Знаходження мови для заданої регулярної граматики
1.3.2.4 Регулярні вирази
1.3.2.5 Формування регулярного виразу для заданого недетермінованого скінченного автомату
1.3.2.6 Формування недетермінованого скінченного автомату для заданої регулярної граматики
1.3.2.7 Формування недетермінованого скінченного автомату для заданого регулярного виразу
1.3.3 КВ-мови (контекстно-вільні мови) та нотації БНФ
1.3.3.1 Властивості граматик КВ-мов
1.3.3.2 Лема про накачку для КВ-мов
1.3.3.3 Дерева розбору КВ-граматик
1.3.3.4 Створення МП-автомату для заданої КВ-граматики
1.3.3.5 Нотації БНФ та РБНФ
1.3.3.6 Нормальна форма Хомського для КВ-граматик
1.3.3.7 Алгоритм Кока-Касамі-Янгера для КВ-граматик у нормальній формі Хомського
1.4 Формалізація поняття алгоритму (доповнення до 1.2)
1.4.1 Детермінізація недетермінованого скінченного автомату (доповнення до 1.2.4)