АНАЛИЗЫ: Теория и практика сложности
Компьютеры становятся все быстрее, объемы памяти - все больше. Можно подумать, что уже не столь важно, какие алгоритмы применять, - современный компьютер может все. Однако алгоритм для решения какой-нибудь нехитрой задачки на триста-пятьсот переменных грубой силой (brute force - вполне официальный термин в computer science) может потребовать порядка 2300 шагов - больше, чем во Вселенной элементарных частиц…
Этой проблемой занимается теория сложности: пытается придумать алгоритмы, которые бы работали быстро, а затем доказать, что они быстро работают. Или, на худой конец, доказать, что таких алгоритмов придумать нельзя.
Но как связаны теория и практика? Насколько то, чем занимаются гуру теоретической информатики, применимо к живым, практически полезным вычислениям? Или практическая польза была целиком извлечена во времена Эдсгера Дейкстры (Edsger Dijkstra), а современная теория сложности - лишь теоретическая забава, занимающая умы математиков, применения которой неясны и отдаленны (таковыми сейчас являются или по крайней мере кажутся многие области математики)? Попробуем разобраться…
Немного теории
Теория сложности (complexity theory) - это раздел теоретической информатики, связанный с оценками сложности работы алгоритмов. Сложность - понятие многогранное: здесь и время работы, и память, которая требуется алгоритму, и возможность его распараллеливания на несколько «процессоров»… Кстати, процессоры в теории сложности, как правило, моделируются машинами Тьюринга[Алан Тьюринг, один из отцов-основателей современной computer science, заложил основы теории сложности в середине 30-х годах прошлого века, когда из компьютеров (то есть «устройств для счета») доступны были абаки, арифмометры да не доведенная до «железа» машина Бэббиджа. Возможно, без его основополагающих работ никаких компьютеров бы и не появилось] - системами из бесконечной ленты и одной пишущей и читающей головки, безо всякого произвольного доступа; оказывается, в такое прокрустово ложе можно уместить все разнообразие компьютерных архитектур… но это уже тема для отдельного обстоятельного разговора.
Что же это такое - сложность алгоритма (в рамках статьи речь пойдет лишь о временно,й сложности [time complexity] классических детерминированных алгоритмов, а о сложности по объему требуемой памяти, вероятностных алгоритмах, протоколах для бесед вездесущих Боба и Алисы, параллельных и квантовых вычислениях мы, возможно, расскажем в следующих сериях)? Интуитивно это понятие довольно простое. У алгоритма есть вход (input) - описание задачи, которую нужно решить. На ее решение алгоритм тратит какое-то время (то есть количество операций). Сложность - это функция от длины входа, значение которой равно максимальному (по всевозможным входам данной длины) количеству операций, требуемых алгоритму для получения ответа.
