Математические основы программирования

Обозначения и сокращения 5 Введение 6 Глава 1. АЛГЕБРА ВЫСКАЗЫВАНИЙ И АЛГЕБРА ПРЕДИКАТОВ 7 1.1. Основные понятия алгебры логики 7 1.1.1. Определение логических операций 8 1.1.2. Логические вентили, схемы, структуры 10 1.2. Булевы функции и их обобщение 14 1.2.1. Минимизация булевых функций 17 1.2.2. Совершенные нормальные формы 18 1.2.3. Минимизация методом диаграмм Вейча (карт Карно) 19 1.3. Исчисление высказываний 23 1.3.1. Понятие формулы исчисления высказываний 23 1.3.2. Определение доказуемой формулы 24 1.3.3. Правила вывода 24 1.3.4. Понятие выводимости формулы из совокупности формул 26 1.3.5. Связь между алгеброй высказываний и исчислением высказываний 28 1.3.6. Метод резолюций 28 1.4. Логика предикатов 30 1.4.1. Понятие предиката 30 1.4.2. Логические операции над предикатами 31 1.4.3. Кванторные операции 31 1.4.4. Формулы логики предикатов 32 1.4.5. Равносильные формулы логики предикатов 33 1.4.6. Предваренная нормальная форма 34 1.4.7. Сколемовская форма и сколемизация формул 34 1.4.8. Общезначимость и выполнимость формул 35 1.4.9. Проблема разрешимости для общезначимости и выполнимости 36 Глава 2. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ 39 2.1. Понятие алгоритма 39 2.2. Математическая теория алгоритмов 40 2.3. Машина Тьюринга 40 2.4. Нормальные алгорифмы Маркова 44 Глава 3. КОНЕЧНЫЕ АВТОМАТЫ. ОБЩИЕ ОПРЕДЕЛЕНИЯ 48 3.1. Автоматы-преобразователи 48 3.1.1. Классификация 48 3.1.2. Модели конечных автоматов 49 3.1.3. Абстрактный синтез КА. Минимизация КА 52 3.1.4. Примеры синтеза 55 3.1.5. Преобразование автомата Мили в эквивалентный автомат Мура и обратно 58 3.2. Автоматы-распознаватели (читающие автоматы) 60 3.2.1. Регулярные выражения и регулярные языки 60 3.2.2. Этапы синтеза читающих автоматов 61 3.2.3. Задача анализа читающего автомата 64 Глава 4. ЧИСЛО: ОПРЕДЕЛЕНИЯ, ВИДЫ И ЗНАЧЕНИЕ В МАТЕМАТИКЕ 67 4.1. Иерархия чисел 67 4.2. Комплексные числа 68 4.3. Гиперкомплексные числа 71 4.3.1. Кватернионы 71 4.3.2. Кватернионный CORDIC 74 4.3.3. Октонионы. Октонионный CORDIC 75 Глава 5. СРАВНЕНИЯ И МОДУЛЬНАЯ АРИФМЕТИКА 78 5.1. Сравнения и вычеты 78 5.2. Операции по модулю 79 5.3. Инверсии и алгоритм Евклида 79 5.4. Модульная арифметика в криптографии 81 Глава 6. АНАЛИЗ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ АЛГОРИТМОВ 83 6.1. Формы представления алгоритмов 83 6.2. Задача теории сложности вычислений 84 6.3. Асимптотический анализ алгоритмов 88 6.4. Методы асимптотической оценки сложности рекурсивных алгоритмов 93 Глава 7. МЕТОДЫ ПОСТРОЕНИЯ АЛГОРИТМОВ 96 7.1. Алгоритмические стратегии 96 7.2. Метод декомпозиции («разделяй и властвуй») 96 7.2.1. Применение метода декомпозиции для построения алгоритма быстрого умножения вектора на кронекерово произведение матриц 98 7.2.2. Аппаратурно-ориентированная структура АБУКПВ 99 7.3. Динамическое программирование 102 7.4. Жадные алгоритмы 106 7.5. Вероятностные алгоритмы 109 7.6. Эволюционные алгоритмы оптимизации 111 7.7. NP-сложные задачи 114 Заключение 117 Литература 118