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

4. Временная сложность алгоритма в наихудшем случае, вре­ менная сложность алгоритма в среднем. 5. Могут ли для решения одной и той же задачи суш;ествовать алгоритмы разной сложности? Если да, то какова сложность задачи? 6. Полиномиальная сложность алгоритма, задачи. 7. Классификация задач по сложности. 8. Класс Р, примеры задач из этого класса. 9. iVP-wiacc. 10. Недетерминированная машина Тьюринга, ее отличие от детерминированной машины Тьюринга. 11. Задачи из jVP-класса. 12. iVP-трудные и iVP-полные задачи, в чем их различие? 13. Примеры iVP-полныхзадач. 14. Класс Е, 15. Емкостная (ленточная) слонсность алгоритма, оценка лен­ точной сложности через временную сложность алгоритма. § 9. Упражнения Рассмотрим известную задачу коммивояжера. Имеется п горо­ дов С={с\,съ •••, € „} и известны расстояния d {ci,cj) между каждой па городов ci,cj из С. Нужно найти обход городов, чтобы побывать в каж­ дом городе из С один и только один раз, и вернуться в исходный го­ род, т. е. найти упорядоченный набор {с^ьси. ••••Сь) й этот набор дол­ жен минимизирйвать суммарное расстояние обхода: «-1 (7.3) 1=1 Эта задача, очевидно, алгоритмически разрешима, ибо можно перебрать все возмолсные варианты обходов и выбрать тот, для кото­ рого указанное суммарное расстояние минимально. Легко найти, что число обходов п городов равно М=(п-\)\ / 2. Известно [26], что число 50! имеет около 65 десятичных знаков. Пусть для выбора одного варианта обхода городов и вычисле­ ния величины S по формуле (7.3) требуется ^0= 0,001 с. 294