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