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

Установить нижнюю оценку - значит доказать, что никакой алгоритм вы­ числения не имеет сложности меньшей, чем заданная граница. Для получения результатов такого типа необходима точная фиксация рассматриваемой алго­ ритмической модели, и такие результаты получены только в очень жестких вы­ числительных моделях. В связи с этим получила развитие проблематика полу­ чения "относительных" нижних оценок. Вопросы и темы для самопроверки 1. Понятие о сложности вычислений. 2. Размер исходных данных задачи для случаев, когда входом является чис­ ло, матрица, граф. 3. Временная сложность алгоритма. Временная сложность задачи. 4. Временная сложность алгоритма в наихудшем случае, временная слож­ ность алгоритма в среднем. 5. Могут ли для решения одной и той же задачи суш,ествовать алгоритмы разной сложности? Если да, то какова сложность задачи? 6. Полиномиальная сложность алгоритма, задачи. 7. Классификация задач по сложности. 8. Класс Р, примеры задач из этого класса. 9. ЛТ'-класс. 10. Педетерминированная машина Тьюринга, её отличие от детерминиро­ ванной машины Тьюринга. 11. Задачи из М^-класса. 12. ТУР-трудные и ТУР-полные задачи, в чем их различие? 13. Примеры ТУР-ПОЛНЫХ задач. 14. Класс е. 15. Емкостная (ленточная) сложность алгоритма, оценка ленточной сложно­ сти через временную сложность алгоритма. Упражнения 1. Рассмотрим известную задачу коммивояжера. Имеется п городов C={ci,c2,...,cn} И известны расстояния d(Ci,Cj) между каждой парой городов Ci,Cj из с . Нужно найти обход городов, чтобы побывать в каждом городе из с один и только один раз, и вернуться в исходный город, т. е. найти упорядоченный на­ бор {ckj,ck2> ••• >ckn) И ЭТОТ набор должен минимизировать суммарное расстояни обхода: п-1 (7.3) S d-(c]^j,c^j+i^)~^d(c]^yi,c]^i). i=i Эта задача, очевидно, алгоритмически разрешима, ибо можно перебрать все возможные варианты обходов и выбрать тот, для которого указанное сум­ марное расстояние минимально. 233