|
|
Читальный зал ->
Крючкова Е.Н. Основы математической логики и теории алгоритмов: Учебное пособие. - Барнаул: Изд-во АлтГТУ, 2010. – 277 с.
 Скачать полный текст
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1 ФОРМАЛЬНЫЕ ТЕОРИИ
1.1 Формальные модели
1.2 Исчисление высказываний
1.2.1 Алфавит исчисления высказываний
1.2.2 Множество формул исчисления высказываний
1.2.3 Множество аксиом исчисления высказываний
1.2.4 Правила вывода исчисления высказываний
1.2.5 Теорема о дедукции исчисления высказываний
1.3 Исчисление предикатов
1.3.1 Определение формальной теории исчисления предикатов
1.3.2 Алфавит и множество формул исчисления предикатов
1.3.3 Множество аксиом исчисления предикатов
1.3.4 Правила вывода исчисления предикатов
1.3.5 Теорема о дедукции исчисления предикатов
1.3.6 Теоремы о полноте
1.3.7 Логическое следствие
1.3.8 Сколемовская нормальная форма и метод резолюций
1.3.9 Логическое программирование
1.4 Другие логические теории
1.4.1 Пороговая логика
1.4.2 K–значные логики
1.4.3 Нечеткая логика и приближенные рассуждения
1.4.4 Темпоральная логика
1.5 Контрольные вопросы к разделу
1.6 Тесты для самоконтроля к разделу
2 ЧАСТИЧНО–РЕКУРСИВНЫЕ ФУНКЦИИ
2.1 Свойства алгоритмов
2.2 Примитивно–рекурсивные функции
2.3 Оператор минимизации
2.4 Ограниченный оператор минимизации
2.5 Быстро растущие функции
2.6 Частично–рекурсивные функции и тезис Черча
2.7 Рекурсивные и рекурсивно перечислимые множества
2.8 Контрольные вопросы к разделу
2.9 Упражнения к разделу
2.9.1 Задача 1
2.9.2 Варианты заданий
2.9.3 Задача 2
2.9.4 Варианты заданий
2.10 Тесты для самоконтроля к разделу
3 МАШИНЫ ТЬЮРИНГА
3.1 Неформальное определение машины Тьюринга
3.2 Формальное определение машины Тьюринга
3.3 Способы представления машины Тьюринга
3.4 Функции, вычислимые по Тьюрингу
3.5 Машина Тьюринга с полулентой
3.6 Разветвление и повторение
3.7 Тезис Тьюринга
3.8 Контрольные вопросы к разделу
3.9 Упражнения к разделу
3.9.1 Задача
3.9.2 Варианты заданий
3.10 Тесты для самоконтроля к разделу
4 ОБЩАЯ ТЕОРИЯ АЛГОРИТМОВ
4.1 Геделевский номер машины Тьюринга
4.2 Проблема остановки машины Тьюринга
4.3 Метод сводимости и доказательство неразрешимости
4.4 Алгоритмы Маркова
4.5 Эквивалентность алгоритмических моделей
4.6 Теорема об эквивалентности Машин Тьюринга и частично–рекурсивных функций
4.7 Теорема об эквивалентности машин Тьюринга и алгоритмов Маркова
4.8 Контрольные вопросы к разделу
4.9 Упражнения к разделу
4.9.1 Задача
4.9.2 Варианты заданий
4.10 Тесты для самоконтроля к разделу
5 ТЕОРИЯ СЛОЖНОСТИ АЛГОРИТМОВ
5.1 Понятие временной и емкостной сложности алгоритмов
5.2 Практическая оценка временной сложности
5.3 NP–полные задачи
5.4 NP-полнота задачи о дизъюнкциях
5.5 Несколько NP–полных задач
5.6 Методы решения NP-полных задач
5.7 Контрольные вопросы к разделу
5.8 Упражнения к разделу
5.8.1 Задача 3 – выполнимость
5.8.2 Варианты заданий
5.9 Тесты для самоконтроля к разделу
6 ПОСТРОЕНИЕ И АНАЛИЗ ЭФФЕКТИВНЫХ АЛГОРИТМОВ
6.1 Типы рекурсивных алгоритмов
6.2 Устранение рекурсии
6.3 Методы отсечения
6.4 Динамическое программирование
6.4.1 Понятие динамического программирования
6.4.2 Многоуровневые динамические массивы
6.5 Виртуальные графы
6.6 Эффективные алгоритмы на графах
6.7 Производящие функции
6.8 Контрольные вопросы к разделу
6.9 Упражнения к разделу
6.9.1 Задача
6.9.2 Варианты заданий
6.10 Тесты для самоконтроля к разделу
7 ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ
7.1 Понятие порождающей грамматики и языка
7.2 Классификация грамматик
7.3 Основные свойства КС–языков и КС–грамматик
7.4 Грамматический разбор
7.5 Преобразования КС–грамматик
7.5.1 Преобразование 1 — правила с одним нетерминалом
7.5.2 Преобразование 2 — правила с одинаковыми правыми частями
7.5.3 Преобразование 3 — неукорачивающие грамматики
7.5.4 Преобразование 4 — непродуктивные нетерминалы
7.5.5 Преобразование 5 — независимые нетерминалы
7.5.6 Преобразование 6 — терминальные правила
7.5.7 Преобразования 7 и 8 — леворекурсивные и праворекурсивные правила
7.6 Теорема о языке a^n b^n c^n
7.7 Контрольные вопросы к разделу
7.8 Упражнения к разделу
7.8.1 Задача
7.8.2 Варианты заданий
7.9 Тесты для самоконтроля к разделу
8 ЯЗЫКИ И АВТОМАТЫ
8.1 Понятие автомата и типы автоматов
8.2 Формальное определение автомата
8.3 Конечные автоматы
8.4 Регулярные множества
8.5 Минимизация конечных автоматов
8.6 Операции над регулярными языками
8.7 Автоматные грамматики и конечные автоматы
8.8 Автоматы с магазинной памятью и КС–языки
8.9 Разбор с возвратом
8.10 Контрольные вопросы к разделу
8.11 Упражнения к разделу
8.11.1 Задача
8.11.2 Варианты заданий
8.12 Тесты для самоконтроля к разделу
9 АВТОМАТЫ—ПРЕОБРАЗОВАТЕЛИ
9.1 Поведение автоматов с выходом
9.2 Автоматы Мили
9.3 Автоматы Мура
9.4 Равносильность автоматов Мили и Мура
9.5 Синтез конечных преобразователей
9.6 Эксперименты по распознаванию состояний
9.7 Алгоритмически разрешимые и неразрешимые проблемы
теории формальных грамматик и языков
9.8 Контрольные вопросы к разделу
9.9 Упражнения к разделу
9.9.1 Задача
9.9.2 Варианты заданий
9.10 Тесты для самоконтроля к разделу
ЗАКЛЮЧЕНИЕ
Читальный зал
|
