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