Книга: Золотой билет

Вычислительная сложность

Вычислительная сложность

В пятидесятых годах цифровые компьютеры распространились уже довольно широко; требовалось как-то оценивать объем вычислений, необходимый для решения той или иной задачи. Первые методы оценки появились в результате попыток формализовать процесс человеческого мышления и поведения.

В 1943 году нейропсихологи Уоррен Маккаллок и Уолтер Питтс разработали нейронную сеть – теоретическую модель, описывающую деятельность человеческого мозга. В пятидесятых годах математик и логик Стивен Клини изобрел конечный автомат – частный случай машины Тьюринга – и изучал свойства разрешимых на нем задач. При помощи конечных автоматов удобно описывать алгоритмы работы простейших агрегатов (к примеру, автомата с газировкой), однако что-то более сложное они уже не потянут.

Примерно в тот же период, в пятидесятых годах, лингвист Ноам Хомский исследовал механизмы построения предложений в английском и некоторых других языках. Он сформулировал понятие контекстно-свободной грамматики, в которой предложениям ставились в соответствие схемы, называемые «деревьями разбора». На рисунке ниже представлено дерево разбора для английского предложения The quick brown fox jumped over the lazy dog.

Рис. 5.2. Дерево разбора

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

Как выяснилось, такие грамматики прекрасно подходят для описания языков программирования и разметки (XML), а вот интуитивное понятие эффективных вычислений им уже не по зубам (как и конечным автоматам).

В последующие годы было создано множество вычислительных моделей, однако настоящий прорыв совершили в 1962 году Юрис Хартманис и Ричард Стернс, работавшие в то время в Исследовательской лаборатории General Electric в Скенектади, штат Нью-Йорк. Для оценки качества работы программы ученые предлагали смотреть, как меняются время ее выполнения и объем задействованной памяти при увеличении объема входных данных. Блестящая идея! В 1965 году вышла их совместная статья «О вычислительной сложности алгоритмов», заложившая основы нового раздела математики – теории сложности вычислений. В 1993 году Хартманис и Стернс получили за эту работу премию Тьюринга.

В 1960-х теория вычислительной сложности развивалась сразу в двух направлениях. Приверженцы одного выбирали конкретные вычислительные модели, ограничивали время исполнения и доступный объем памяти и пытались определить, какие задачи могут быть решены при таких условиях, а какие – не могут. Мануэль Блюм, работая над диссертацией в Массачусетском технологическом институте, использовал иной – совершенно абстрактный – подход, не зависящий ни от вычислительной модели, ни от времени и памяти и каких-либо других ресурсов. Ни один из вариантов не приблизил ученых к понятию вычислительной эффективности.

Оглавление книги