- •ВВЕДЕНИЕ
- •Глава 1. ЛОГИКА ВЫСКАЗЫВАНИЙ
- •§1. Высказывание. Логические операции
- •§ 2. Пропозициональные буквы, связки и формы (формулы логики высказываний). Построение таблиц истинности
- •§ 3. Упрощения в записях пропозициональных форм
- •§ 4. Тавтологии (общезначимые формулы). Противоречия
- •§ 5. Равносильность пропозициональных форм
- •§ 6. Важнейшие пары равносильных пропозициональных форм
- •§ 7. Зависимости между пропозициональными связками
- •§ 8. Нормальные формы
- •§ 9. Совершенные нормальные формы
- •§ 10. Булева (переключательная) функция
- •§ 11. Приложение алгебры высказываний к анализу и синтезу контактных (переключательных) схем
- •§ 12. Приложение алгебры высказываний к анализу и синтезу схем из функциональных элементов
- •§ 13. Вопросы и темы для самопроверки
- •§ 14. Упражнения
- •Глава 2 ЛОГИКА ПРЕДИКАТОВ
- •§ 1. Понятие предиката
- •§ 2. Кванторы
- •§ 3. Формулы логики предикатов
- •§ 4. Интерпретация. Модель
- •§ 5. Свойства формул в данной интерпретации
- •§ 6. Логически общезначимые формулы. Выполнимые и равносильные формулы
- •§ 8. Правила перестановки кванторов
- •§ 9. Правила переименования связанных переменных
- •§ 10. Правила вынесения кванторов за скобки. Предваренная нормальная форма
- •§ 11. Вопросы и темы для самопроверки
- •§ 12. Упражнения
- •Глава 3. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ И МЕТОД РЕЗОЛЮЦИЙ
- •§ 1. Логическое следствие и проблема дедукции в логике высказываний
- •§ 2. Резольвента дизъюнктов логики высказываний
- •§ 3. Метод резолюций в логике высказываний
- •§ 4. Метод насыщения уровня
- •§ 5. Стратегия вычеркивания
- •§ 6. Лок-резолюция
- •§ 7. Метод резолюций для хорновских дизъюнктов
- •§ 8. Преобразование формул логики предикатов. Сколемовская стандартная форма
- •§ 9. Унификация
- •§ 10. Метод резолюций в логике предикатов
- •§ 11. Приложение метода резолюций для анализа силлогизмов Аристотеля.
- •§ 12. Использование метода резолюций в языке ПРОЛОГ
- •§ 13. Введение и использование правил в ПРОЛОГе
- •§ 14. Рекурсивное задание правил в ПРОЛОГе
- •§ 15. Особенности ПРОЛОГа
- •§ 16. Вопросы и темы для самопроверки
- •§ 17. Упражнения
- •Глава 4. ДЕДУКТИВНЫЕ ТЕОРИИ
- •§ 1. Понятие об эффективных и полуэффективных процессах (методах)
- •§ 2. Дедуктивные теории
- •§ 3. Свойства дедуктивных теорий
- •§ 4. Пример полуформальной аксиоматической теории - геометрия
- •§ 5. Формальные аксиоматические теории
- •§ 6. Свойства выводимости
- •§ 7. Исчисление высказываний (теория L)
- •§ 8. Некоторые теоремы исчисления высказываний
- •§ 9. Эквивалентность двух определений непротиворечивости
- •§ 11. Свойства исчисления высказываний
- •§ 12. Другие аксиоматизации исчисления высказываний
- •§ 13. Теории первого порядка
- •§ 14. Формальная арифметика (теория S)
- •§ 15. Свойства теорий первого порядка
- •§ 16. Значение аксиоматического метода
- •§ 17. Теория естественного вывода
- •§ 18. Вопросы и темы для самопроверки
- •§ 19. Упражнения
- •Глава 5. НЕКЛАССИЧЕСКИЕ ЛОГИКИ
- •§ 1. Трехзначные логики
- •§ 2. Многозначные логики
- •§ 3. Понятие нечеткого множества
- •§ 4. Нечеткие высказывания и максиминные операции над ними
- •§ 5. Понятие о нечеткой лингвистической логике
- •§ 6. Модальные логики
- •§ 7. Временные (темпоральные) логики
- •§ 8. Вопросы и темы для самопроверки
- •§ 9. Упражнения
- •Глава 6. ТЕОРИЯ АЛГОРИТМОВ
- •§1. Неформальное понятие алгоритма
- •§ 2. Алфавит. Слова. Алгоритм в алфавите. Вполне эквивалентные алгоритмы
- •§ 3. Нормальный алгоритм (алгоритм А. А. Маркова)
- •§ 4. Функции частично вычислимые и вычислимые по Маркову
- •§ 5. Замыкание, распространение нормального алгоритма
- •§ 6. Операции над нормальными алгоритмами
- •§ 7. Машина Тьюринга
- •§ 8. Задание машины Тьюринга
- •§ 9. Алгоритм Тьюринга. Вычислимость по Тьюрингу
- •§ 10. Связь между машинами Тьюринга и нормальными алгоритмами
- •§ 11. Основная гипотеза теории алгоритмов (принцип нормализации или тезис Черча)
- •§ 12. Проблема алгоритмической неразрешимости
- •§ 13. Примеры алгоритмически неразрешимых массовых проблем
- •§ 14. Сведение любого преобразования слов в алфавите к вычислению значений целочисленных функций
- •§ 15. Примитивно рекурсивные и общерекурсивные функции
- •§ 16. Примитивно рекурсивность некоторых функций. Частично - рекурсивные функции
- •§ 17. Ламбда-исчисление
- •§ 18. Основные результаты
- •§ 19. Вопросы и темы для самопроверки
- •§ 20. Упражнения
- •Глава 7. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ С ПОМОЩЬЮ АЛГОРИТМОВ
- •§ 1. Понятие о сложности
- •§ 2. Временная сложность вычислений (алгоритма)
- •§ 3. Полиномиальные алгоритмы и задачи. Класс Р
- •§ 4. NP класс
- •§ 5. NP-полные и NP-трудные задачи
- •§ 6. Класс Е
- •§ 7. Ёмкостная (ленточная) сложность алгоритма
- •§ 8. Вопросы и темы для самопроверки
- •§ 9. Упражнения
- •ЛИТЕРАТУРА
- •ПРИЛОЖЕНИЯ
- •Варианты типового задания
- •Тесты для самоконтроля
- •Тест по логике высказываний (тест № 1)
- •Тест по логике предикатов (тест № 2)
- •Тест по логическому следствию и методу резолюций (тест № 3)
- •Тест по дедуктивным теориям (тест № 4)
- •Тест по теории алгоритмов (тест № 5)
- •Тест по неклассическим логикам и сложности вычислений (тест № 6)
- •Ответы к тестам самоконтроля
235
11.Задачи из NP класса.
12.NP-трудные и NP-полные задачи, в чем их различие?
13.Примеры NP-полных задач.
14.Класс Е.
15.Емкостная (ленточная) сложность алгоритма, оценка ленточной сложности через временную сложность алгоритма.
§ 9. Упражнения
Рассмотрим известную задачу коммивояжера. Имеется n городов С={c1,c2,…,cn} и известны расстояния d(ci,cj) между каждой парой городов ci,cj из С. Нужно найти обход городов чтобы побывать в каждом городе из С один и только один раз, и вернуться в исходный город, т. е. найти
упорядоченный набор ck1,ck2,…,ckn и этот набор должен минимизировать суммарное расстояние обхода:
n−1 |
d(cki,ck(I+1))+d(ckn,ck1). |
(7.3) |
S = ∑ |
|
|
i =1 |
|
|
Эта задача, очевидно, алгоритмически разрешима, ибо можно перебрать все возможные варианты обходов и выбрать тот, для которого указанное суммарное расстояние минимально. Число обходов n городов равно M=(n-1)! / 2.
Легко найти, что число обходов n городов равно M=(n-1)! / 2. Известно [26], что число 50! имеет около 65 десятичных знаков. Пусть для выбора одного варианта обхода городов и вычисления величины S по формуле (7.3) требуется t0 = 0,001 секунд.
1.Оценить какое должно быть быстродействие ЭВМ которая переберет все варианты обхода городов задачи коммивояжера для n = 51 за миллиард лет непрерывной работы.
2.Оценить время непрерывной работы ЭВМ с современными вычислительными возможностями для перебора всех указанных в задаче 1 вариантов.
3.Построить алгоритм нахождения наибольшего элемента множества S, содержащего n действительных чисел, где n – степень числа 2, на базе стратегии дублирования. Оценить временную сложность построенного алгоритма.
4.Построить алгоритм нахождения наименьшего элемента множества S, содержащего n действительных неотрицательных чисел, на базе стратегии дублирования. Оценить временную сложность построенного алгоритма.
5.Пусть А массив размера n, состоящий из целых чисел
(положительных и отрицательных), причём А1<A2<…<An. Построить алгоритм нахождения числа i, для которого Аi=i (если такое i существует). Каков порядок времени работы алгоритма.
236
6.Построить алгоритм умножения двух полиномов степени n, где n=2k, k {1,2,3,…}, по стратегии дублирования и определить вычислительную сложность.
7.Доказать, что сложности умножения, деления, обращения и возведения в квадрат (M(n), D(n), R(n) и S(n)) целых двоичных чисел размера n совпадают с точностью до постоянных множителей и имеют порядок 0(nlog2n), если n – степень числа 2.
8.Доказать, что сложности умножения, деления, обращения и возведения в квадрат (M(n), D(n), R(n) и S(n)) полиномов степени n совпадают
сточностью до постоянных множителей и имеют порядок 0(nlog2n), если n – степень числа 2.