Введение в схемы, автоматы и алгоритмы

Булевы функции от n переменных
Табличное представление
Булевы функции от 1-ой и 2-х переменных
Формулы
Эквивалентность булевых формул
Дизъюнктивные и конъюнктивные нормальные формы
Графы
Деревья

Введение в схемы, автоматы и алгоритмы

Логические схемы (схемы из функциональных элементов)
Схемы и линейные программы
Сложение по модулю 2
Сумматор
Задачи

Введение в схемы, автоматы и алгоритмы

Основные определения
Сокращенные УБДР
Построение сокращенных УБДР по формулам

Задачи

Введение в схемы, автоматы и алгоритмы

Переработка информации с помощью конечных автоматов
Детерминированные конечные автоматы (ДКА) и автоматные языки
Произведение автоматов
Недетерминированные конечные автоматы и их детерминизация
Задачи

Введение в схемы, автоматы и алгоритмы

Регулярные выражения и языки
Автоматы для регулярных языков
Задачи

Введение в схемы, автоматы и алгоритмы

Замкнутость относительно гомоморфизмов и их обращений
Теорема о разрастании для автоматных языков
Примеры неавтоматных языков
Задачи

Введение в схемы, автоматы и алгоритмы

Что такое алгоритм?
Структурированные программы

Задачи

Введение в схемы, автоматы и алгоритмы

Определение рекурсивных функций
Примеры
Программная вычислимость рекурсивных функций
Леммы о рекурсивных функциях

Задачи

Введение в схемы, автоматы и алгоритмы

Основные определения
Тьюрингово программирование
Стандартная заключительная конфигурация
Односторонние машины Тьюринга
Последовательная и параллельная композиции машин Тьюринга
Ветвление (условный оператор)

Повторение (цикл)
Задачи

Введение в схемы, автоматы и алгоритмы

Вычислимость частично рекурсивных функций по Тьюрингу
Моделирование структурированных программ машинами Тьюринга
Частичная рекурсивность функций, вычислимых по Тьюрингу
Тезис Тьюринга-Черча и алгоритмически неразрешимые проблемы

Задачи
Содержание раздела

---