Математическая логика и теория алгоритмов

§ 16. Примитивно-рекурсивность некоторых функ­ ций. Частично рекурсивные функции 256 § 17. Ламбда-исчисление 259 § 18. Основные результаты 263 § 19. Вопросы и темы для самопроверки 264 § 20. Упражнения 265 Глава 7. Сложность вычислений с помощью алгоритмов 276 § 1. Понятие о слонсности вычислений 276 § 2. Временная сложность вычислений (алгоритма)... 279 § 3. Полиномиальные алгоритмы и задачи. Класс Р 281 § 4. NP- класс 285 § 5. jVP-пЬлные и Л^Р-трудные задачи 289 § 6. Класс £ 290 § 7. Емкостная (ленточная) сложность алгоритма 292 § 8. Вопросы и темы для самопроверки 293 § 9. Упражнения 294 Приложение 296 Варианты типового задания 296 Тесты для самоконтроля 314 Тест 1. Логика высказываний 315 Тест 2. Логика предикатов 316 Тест 3. Логическое следствие и метод резолюций ... 318 Тест 4. Дедуктивные теории 320 Тест 5. Теория алгоритмов 324 Тест 6. Неклассические логики и слолшость вы­ числений ^ 327 Ответы к тестам самоконтроля 331 Список литературы 332