|
01.1. Основные способы задания двоичных функций. Табличный способ задания
|
|
01.2. Геометрический способ задания
|
|
01.3. Задание двоичных функций формулами
|
|
02.1. Основные способы задания двоичных функций (продолжение). Нормальные формы двоичных функций
|
|
02.2. Многочлен Жегалкина и действительный многочлен двоичной функции
|
|
02.3. Теорема о разложении в ряд Фурье
|
|
03.1. Полнота и замкнутость. Функционально полные системы
|
|
03.2. Замкнутые классы булевых функций
|
|
03.3. Критерий полноты системы булевых функций
|
|
04.1. Псевдобулевы функции
|
|
04.2. Функции K-значной логики
|
|
05.1 Минимизация двоичных функции
|
|
05.2. Геометрическая интерпретация минимизации ДНФ
|
|
06.1. Метод Квайна;— Мак-Класки нахождения сокращённой ДНФ двоичной функции
|
|
06.2. Метод нахождения тупиковых ДНФ
|
|
06.3. Метод Петрика нахождения тупиковых ДНФ
|
|
07.1. Алгебраические системы. Булевы алгебры
|
|
07.2. Изоморфизм алгебраических систем
|
|
08.1. Алгебры высказываний. Предикаты и операции над ними. Основные логические операции и их свойства
|
|
08.2. Предикаты и операции над ними
|
|
09.1. Исчисление предикатов. Общее понятие о логическом исчислении
|
|
09.2. Формулы алгебры предикатов
|
|
09.3. Равносильность формул. Основные отношения равносильности
|
|
09.4. Использование равносильностей для упрощения формул
|
|
09.5. Построение исчисления предикатов
|
|
09.6. Выводимость и доказуемость формул
|
|
09.7. Семантика исчисления предикатов
|
|
10. Понятие о теории моделей
|
|
11. Элементы теории алгоритмов
|
|
11.1. Основные требования к алгоритмам
|
|
11.2. Машина Тьюринга и функции, вычислимые по Тьюрингу
|
|
11.3. Машины произвольного доступа и вычислимые функции
|
|
12. Частично рекурсивные функции и их вычислимость
|
|
12.1. Вычислимость суперпозиции
|
|
12.2. Вычислимость рекурсии
|
|
12.3. Вычислимость минимизации
|
|
13. Нумерация наборов чисел и слов
|
|
14. Нормальные алгоритмы
|
|
15. Нумерация алгоритмов. Нумерация машин Тьюринга
|
|
15.1. Нумерация МПД-программ
|
|
15.2. Универсальные функции
|
|
16.1. Алгоритмически неразрешимые проблемы
|
|
16.2. Примечательные алгоритмически неразрешимые проблемы
|
|
17. Характеристики сложности вычислений
|
|
18.1. Классы сложности P и NP и их взаимосвязь
|
|
18.2. NP-полные задачи. Теорема Кука
|
|
18.3. Основные NP-полные задачи. Сильная NP-полнота
|
|
ВВЕДЕНИЕ
|
|
Список Литературы
|
