Учебное пособие. — М.: МГАПИ, 2003. — 47 с., 80 с.Предлагаемое издание рекомендуется в качестве учебного пособия для подготовки студентов различных специальностей, изучающих математическую логику и теорию алгоритмов. Издание может быть использовано в качестве учебного пособия по разделу «Математическая логика» дисциплины «Математическая логика и теория алгоритмов».
В первой части учебного пособия рассмотрены основы таких разделов математической логики как: исчисление высказываний, исчисление предикатов, модальная логика, немонотонные рассуждения и методы поиска в глубину и ширину, а так же элементы нечёткой логики.
Во второй части учебного пособия рассмотрены основы таких разделов теории алгоритмов как: классическая теория алгоритмов (машина Поста, машина Тьюринга, алгоритмически неразрешимые задачи), асимптотический анализ сложности алгоритмов, сложностные классы и практический сравнительный анализ вычислительных алгоритмов.Оглавление
Часть 1.Cистемы счисления
Понятие системы счисления
Позиционные системы счисления
Нетрадиционная фибоначчиева система счисления
Примеры перевода чисел из одной системы счисления в другуюЛогика высказываний
Краткий экскурс в историю логики высказываний
Логика и исчисление высказываний
Классическое определение исчисления высказываний
Конструктивное определение исчисления высказываний.
Другие аксиоматизации исчисления высказыванийИсчисление предикатов
Логика и исчисление предикатов
Правила вывода в логике предикатов первого порядка
Метод резолюции для логики предикатов первого порядкаМодальная логика
Основные понятия модальной логики
Синтаксис и семантика модальной логики
Схемы модальных формул
Бинарные отношения и семантика возможных миров
Обзор других формально-логических моделейНемонотонные рассуждения и методы поиска
Модифицируемые рассуждения и свойства немонотонных логик
Зацикливание немонотонных рассуждений и его преодоление
Стратегии немонотонного вывода в глубину и ширинуЭлементы нечёткой логики6. ЭЛЕМЕНТЫ НЕЧЁТКОЙ ЛОГИКИ
Основные понятия и определения
Нечёткие логические формулы
Основные операции над нечёткими множествами и их свойстваЧасть 2Введение в теорию алгоритмов
Исторический обзор
Цели и задачи теории алгоритмов
Практическое применение результатов теории алгоритмов
Формализация понятия алгоритмаМашина Поста
Основные понятия и операции
Финитный 1–процесс
Способ задания проблемы и формулировка 1Машина Тьюринга и алгоритмически неразрешимые проблемы
Машина Тьюринга
Алгоритмически неразрешимые проблемы
Проблема соответствий поста над алфавитом ΣВведение в анализ алгоритмов
Сравнительные оценки алгоритмов
Система обозначений в анализе алгоритмов
Классификация алгоритмов по виду функции трудоёмкости
Асимптотический анализ функцийТрудоемкость алгоритмов и временные оценки
Элементарные операции в языке записи алгоритмов
Примеры анализа простых алгоритмов
Переход к временным оценкам
Пример пооперационного временного анализаТеория сложности вычислений и сложностные классы задач
Теоретический предел трудоемкости задачи
Сложностные классы задач
Проблема P = NP
Класс NPC (NP–полные задачи)
Примеры NP–полных задачПример полного анализа алгоритма решения задачи о сумме
Формулировка задачи и асимптотическая оценка
Алгоритм точного решения задачи о сумме (метод перебора)
Анализ алгоритма точного решения задачи о суммеРекурсивные функции и алгоритмы
Рекурсивные функции
Рекурсивная реализация алгоритмов
Анализ трудоемкости механизма вызова процедуры
Анализ трудоемкости алгоритма вычисления факториалаРекурсивные алгоритмы и методы их анализа
Логарифмические тождества
Методы решения рекурсивных соотношений
Рекурсивные алгоритмы
Основная теорема о рекуррентных соотношенияхПрямой анализ рекурсивного дерева вызовов
Алгоритм сортировки слиянием
Слияние отсортированных частей (merge)
Подсчет вершин в дереве рекурсивных вызовов
Анализ трудоемкости алгоритма сортировка слияниемТеория и алгоритмы модулярной арифметики
Алгоритм возведения числа в целую степень
Сведения из теории групп
Сведения из теории простых чиселКриптосистема RSA и теория алгоритмов
Мультипликативная группа вычетов по модулю n
Степени элементов в Zn* и поиск больших простых чисел
Криптосистема RSA
Криптостойкость RSA и сложность алгоритмов факторизации
