Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Вопросы и темы для самопроверки 213 Упражнения 214 ГЛАВА 7. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ С ПОМОЩЬЮ АЛГОРИТМОВ 217 § 1. Нонятие о сложности 218 § 2. Временная сложность вычислений (алгоритма) 220 § 3. Нолиномиальные алгоритмы и задачи. Класс Р 221 § 4. NP класс 225 § 5. NP-полные и NP-трудные задачи 228 § 6. Класс Е 230 § 7. Емкостная (ленточная) сложность алгоритма 231 § 8. Проблемы анализа сложности алгоритмов 232 Вопросы и темы для самопроверки 233 Упражнения 233 Приложения 235 1. Варианты типового задания 235 2. Тесты для самоконтроля 246 Ответы к тестам самоконтроля 257 Список литературы 258 264