Читать «Журнал «Компьютерра» №31 от 30 августа 2005 года» онлайн - страница 70

Этой проблемой занимается теория сложности: пытается придумать алгоритмы, которые бы работали быстро, а затем доказать, что они быстро работают. Или, на худой конец, доказать, что таких алгоритмов придумать нельзя.

Но как связаны теория и практика? Насколько то, чем занимаются гуру теоретической информатики, применимо к живым, практически полезным вычислениям? Или практическая польза была целиком извлечена во времена Эдсгера Дейкстры (Edsger Dijkstra), а современная теория сложности - лишь теоретическая забава, занимающая умы математиков, применения которой неясны и отдаленны (таковыми сейчас являются или по крайней мере кажутся многие области математики)? Попробуем разобраться…

Немного теории

Теория сложности (complexity theory) - это раздел теоретической информатики, связанный с оценками сложности работы алгоритмов. Сложность - понятие многогранное: здесь и время работы, и память, которая требуется алгоритму, и возможность его распараллеливания на несколько «процессоров»… Кстати, процессоры в теории сложности, как правило, моделируются машинами Тьюринга[Алан Тьюринг, один из отцов-основателей современной computer science, заложил основы теории сложности в середине 30-х годах прошлого века, когда из компьютеров (то есть «устройств для счета») доступны были абаки, арифмометры да не доведенная до «железа» машина Бэббиджа. Возможно, без его основополагающих работ никаких компьютеров бы и не появилось] - системами из бесконечной ленты и одной пишущей и читающей головки, безо всякого произвольного доступа; оказывается, в такое прокрустово ложе можно уместить все разнообразие компьютерных архитектур… но это уже тема для отдельного обстоятельного разговора.

Что же это такое - сложность алгоритма (в рамках статьи речь пойдет лишь о временно,й сложности [time complexity] классических детерминированных алгоритмов, а о сложности по объему требуемой памяти, вероятностных алгоритмах, протоколах для бесед вездесущих Боба и Алисы, параллельных и квантовых вычислениях мы, возможно, расскажем в следующих сериях)? Интуитивно это понятие довольно простое. У алгоритма есть вход (input) - описание задачи, которую нужно решить. На ее решение алгоритм тратит какое-то время (то есть количество операций). Сложность - это функция от длины входа, значение которой равно максимальному (по всевозможным входам данной длины) количеству операций, требуемых алгоритму для получения ответа.

Пример. Пусть дана последовательность из нулей и единиц, и нам нужно выяснить, есть ли там хоть одна единица. Алгоритм будет последовательно проверять, нет ли единицы в текущем бите, а затем двигаться дальше, пока вход не кончится. Поскольку единица действительно может быть только одна, для получения точного ответа на этот вопрос в худшем случае придется проверить все n символов входа. В результате получаем сложность порядка cn, где c - количество шагов, потребное для проверки текущего символа и перехода к следующему. Поскольку такого рода константы сильно зависят от конкретной реализации, математического смысла они не имеют, и их обычно прячут за символом O: в данном случае специалист по теории сложности сказал бы, что алгоритм имеет сложность O(n); иными словами, он линейный. Говорят, что алгоритм полиномиальный, если его сложность оценивается сверху некоторым многочленом p(n); алгоритм экспоненциальный, если его сложность имеет порядок 2cn. В реальных, тем более промышленных, задачах редко используются алгоритмы со сложностью больше экспоненты: уже экспоненциальная сложность стала во многих (но не во всех, как мы увидим ниже) случаях синонимом практической неразрешимости и ужасной немасштабируемости. В этой статье мы более никакими теоретико-сложностными концепциями, кроме полиномиального и экспоненциального алгоритма, пользоваться не будем.