Навчальний посібник. — Київ: МГАПІ, 2003. — 47 та 80 сторінок. Цей випуск рекомендується як навчальний посібник для підготовки студентів різних спеціальностей, що вивчають математичну логіку та теорію алгоритмів. Його можна використовувати для вивчення розділу «Математична логіка» дисципліни «Математична логіка і теорія алгоритмів». У першій частині посібника розглядаються основи таких розділів математичної логіки, як: алгебра висловлювань, алгебра предикатів, модальна логіка, немонотонні висновки та методи пошуку в глибину і ширину, а також елементи нечіткої логіки. У другій частині подано основи теорії алгоритмів: класична теорія алгоритмів (машина Поста, машина Тьюринга, задачі, що є алгоритмічно не розв’язними), асимптотичний аналіз складності алгоритмів, класи складності та практичний порівняльний аналіз обчислювальних алгоритмів. Зміст Частина 1. Системи числення Поняття системи числення Позиційні системи числення Нетрадиційна фібоначчієва система числення Приклади перетворення чисел із однієї системи в іншу Висловлювальна логіка Короткий огляд історії логіки висловлювань Логіка і висловлювальні обчислення Класичне визначення алгебри висловлювань Конструктивне визначення алгебри висловлювань Інші аксіоматизації цієї логіки Алгебра предикатів Логіка і алгебра предикатів Правила виведення у логіці першого порядку Метод резолюції для логіки предикатів Модальна логіка Основні поняття модальної логіки Синтаксис і семантика Схеми модальних формул Бінарні відношення і семантика можливих світів Огляд інших формально-логічних моделей Немонотонні висновки і пошукові методи Модифіковані висновки та властивості немонотонних логік Зациклювання немонотонних висновків і способи його подолання Стратегії немонотонного виведення в глибину і ширину Елементи нечіткої логіки Основні поняття та визначення Нечіткі логічні формули Основні операції над нечіткими множинами і їхні властивості Частина 2. Вступ до теорії алгоритмів Історичний огляд Цілі та задачі теорії алгоритмів Практичне застосування результатів цієї галузі Формалізація поняття алгоритму Машина Поста Основні поняття та операції Обчислювальні процеси з кінцевим числом кроків Постановка задачі та її формулювання Машина Тьюринга і алгоритмічно не розв’язні задачі Машина Тьюринга Задачі, що не мають алгоритмічного рішення Задача відповідностей Поста над алфавітом Σ Вступ до аналізу алгоритмів Порівняльна оцінка алгоритмів Позначення в аналізі Класифікація алгоритмів за складністю функцій часу Асимптотичний аналіз Оцінки трудомісткості та часу виконання Основні операції у мові опису алгоритмів Приклади аналізу простих алгоритмів Перехід до часових оцінок Приклад поопераційного аналізу часу Теорія складності обчислень і класи задач Теоретичний межа трудомісткості задачі Класи складності: P, NP, NP–повні задачі Приклади NP–повних задач Приклад повного аналізу алгоритму для задачі суми чисел Формулювання задачі та асимптотична оцінка Метод перебору для точного розв’язання Аналіз рекурсивних функцій та алгоритмів Рекурсивні функції і їх реалізація Аналіз складності рекурсивних викликів Приклади рекурсивних алгоритмів Логарифмічні тотожності та методи розв’язання рекурсивних рівнянь Основна теорема про рекурентні співвідношення Аналіз дерева викликів Алгоритм сортування злиттям Злиття відсортованих частин Підрахунок вузлів у дереві рекурсивних викликів Аналіз складності сортування злиттям Теорія і алгоритми модульної арифметики Обчислення степеня числа Відомості з теорії груп Відомості з теорії простих чисел Криптографічна система RSA та її застосування Мультиплікативна група залишків за модулем n Степені елементів у Zn* і пошук великих простих чисел Криптосистема RSA Криптостійкість RSA і складність факторизації.