Сложность. 
Философия науки

В контексте теоретического анализа центральным для информатики является понятие сложности. Неформально сложность — это «информационная сопротивляемость среды», т. е. то, что мешает решать задачи, принципиально запрещает автоматизировать те или иные вещи. Кроме неформального определения сложности, теоретики информатики придумали несколько гораздо более хорошо формализованных видов сложности, которые фокусируются на более узких свойствах задач.

Первый такой вид сложности — это энтропия, или количество байт, нужных для того, чтобы описать задачу. Надо сказать, что названия совпадают не зря, этот вид сложности удивительно похож на термодинамическую энтропию как количество возможных состояний. Понятие информационной энтропии, которое использует в своей работе К. Шеннон, в рамках конструктивистских идей рассматривается как «сложность» структуры, лежащей в основе системы (в том числе и коммуникационной).

Второй вид сложности — это «запутанность» структур данных. Численной характеристики для него нет, но для программиста он заметнее всего. Дело в том, что большинство алгоритмов «построены» в виде манипулирования некими структурами данных. Часто усложнения в программе происходят за счет не самих алгоритмов, а за счет усложнения структур, представляющих данные^[1]. Кроме того, иерархическому усложнению подвержены не только структуры данных, но и алгоритмы работы с ними. Виртуальная машина, используемая программистом при написании программ на некотором языке высокого уровня, является иерархической системой виртуальных машин¹. Важным с точки зрения развития компьютерных технологий становится этот переход к языкам «высокого уровня». С этого момента программирование действительно становится деятельностью по созданию сложных систем.

Третий вид сложности — колмогоровская. Она представляет собой математически оформленный аналог «запутанности». Наличие или отсутствие больших объемов работы и сложности модели не исчерпывают принципиальных проблем, с которыми сталкиваются люди при создании автономных систем. Есть еще некая довольно неочевидная характеристика, которая говорит нам, насколько вообще задача, которую мы пытаемся решить, поддается алгоритмизации. Эта характеристика имеет числовую величину и называется колмогоровской сложностью.

Весьма любопытно, что колмогоровская сложность имеет связь с энтропией Шеннона, упомянутой в начале главы. И та и другая в некотором смысле помогают формализовать задачу «снижения уровня неопределенности».

Если с этих позиций подойти к понятию вычисления с точки зрения математики, то «сложность» в смысле алгоритмизируемое™ — это сложность относительно оптимального языка, измеряющаяся длиной кратчайшего описания этого вычисления. Чем сложнее объект, тем больше информации он содержит. Эта «длина описания», задающая модель вычислений, которая описывается как длина двоичных слов (технически — конечные последовательности битов) и называется «колмогоровской сложностью».

То есть на инженерном уровне сложность и будет описанием способа конструирования, хотя на уровне теории вычислимых функций она задается функционально: «…способ описания есть вычислимая функция из множеств двоичных слов».

В некотором смысле, в математике колмогоровской сложности доказано, что «для случайных данных» колмогоровская сложность (длина программы, моделирующей эти данные) будет примерно равна энтропии Шеннона этих данных. Тем не менее показано, что для неслучайных данных колмогоровская сложность мала, что, собственно, и позволяет программистам писать программы, моделирующие разные системы^[2][3] [9, с. 65].

Четвертая разновидность сложности — вычислительная.

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

Ответ на этот вопрос — и да, и нет. В этом месте информатика ставит перед нами вопрос о том, имеет ли смысл решать крайне трудоемкие задачи вообще. Вычислительная сложность — это вполне конкретная числовая характеристика, описывающая, сколько времени потребуется работать машине, чтобы решить задачу, в зависимости от объема исходных данных. Самое поразительное, что для большого количества вполне четко определенных и хорошо формализованных задач оценка на сложность получается очень большой¹. Несмотря на триумф компьютерных наук и технологий, множество вполне прикладных задач, например, экономики или физики, которые казалось, могли бы быть легко и точно решены, требуют качественно иных вычислительных мощностей, чем те, что доступны на настоящее время и будут доступны в обозримом будущем.

В заключение главы кратко рассмотрим связи информатики с другими науками и некоторые перспективы ее развития.

Компьютерная наука способствовала расширению содержания множества дисциплин, в том числе гуманитарных. Так, например, некоторые идеи, полученные в ходе математико-логических исследований (в том числе принципы анализа языков программирования), оказались значимыми с точки зрения общих проблем семиотики и получили продолжение в виде такой дисциплины, как математическая лингвистика^[4][5].

Широко развился математический подход к решению произвольных системных задач, по-другому называемый Operations Research^[6] [12]. На данный момент сами компьютерные технологии становятся средством, позволяющим связать предмет (какой-либо научной области) с идеей, направляющей научное исследование, как раз за счет возможностей ее формализации. Открытым же остается вопрос о степени «формализуемости» каждой из предметных областей.

Другим актуальным направлением исследований (уже конца XX — начала XXI в.) является тема взаимодействия «человек-машина» {Human-Computer

Interaction), которая, с одной стороны, продолжает тему «искусственного интеллекта», с другой — сосредоточивает внимание на физиологических (и прочих психологических, биологических и т. д.) особенностях восприятия человеком компьютера и компьютерных технологий.

На прикладном уровне — т. е. уровне компьютерных технологий — тема взаимодействия «человек-машина» связана с проектами пользовательских интерфейсов, планированием (как прогнозированием и оценкой рисков) и управлением (как поиском оптимального решения). Исследования в этих областях ставят ряд проблем этического характера, связанных с вопросами симуляции процессов, определенных дискретной (бинарной) рациональностью. Эта тема рассматривается в рамках немецкой философской традиции.

В самой же информатике не оставляются попытки опровергнуть тезис Тьюринга или придумать вычислитель, обладающий большей вычислительной мощью. Основаниями для этого, в частности, стали понятия нормального алгорифма, универсального алгоритма. На период начала XXI в. особый интерес проявляется к так называемому квантовому компьютеру и всем следствиям, к которым может привести его использование.

• [1] Простейший пример структуры данных — это вектор. Вектор — это набор занумерованных чисел. Простейший алгоритм для работы с векторами — это сложение. Нужно пройтино двум векторам, складывая их поэлементно. Простейший пример усложнения — это когдавместо векторов действительных чисел требуется перейти к векторам из комплексных чисел. Простое применение «в лоб» алгоритма сложения векторов не пройдет — ведь вместо одногочисла на месте i возникнет два. Тем не менее, если переопределить одну операцию сложения, сам алгоритм прохода по векторам можно оставить — ведь он действует.
• [2] Концепцию виртуальной машины языка программирования можно пояснить на следующем примере. Пусть на листе бумаги 1 можно написать программу на естественном языке. На листе бумаги 2 можно написать программу исполнения программы на листе 1 и приложить лист 1. Если конструкции на листе 1 будут выглядеть как-то похоже на «Записать случайное число», то на листе 2 они будут выглядеть как: «Прочитать первую строку листа 1». Можно также написать лист 3, который будет содержать инструкции по обработке листа 2. В какой-то момент вложенность должна дойти до физического вычислителя, но на какомименно уровне — не важно. Всегда можно добавить еще один.
• [3] Давайте бросим (самую что ни на есть честную) монету миллион раз. Полученнуюпоследовательность нулей и единиц попробуем сжать с помощью какого-то из практическииспользуемых компрессоров, скажем, с помощью программы gzip. (Для этого ее надо вначале разбить на восьмибитовые байты.) Можно быть уверенным, что мы не получим сжатиябольше чем на 1%, сколько раз ни повторяй этот опыт. В самом деле, такая степень сжатиявозможна лишь для 2−10 000-доли всех последовательностей. Это утверждение (невозможность сжатия) подтверждается экспериментально ничуть не хуже, чем многие другие законы. Внимание, вопрос: является ли этот закон следствием известных законов классической механики или это некоторый дополнительный (по отношению к ней) закон?
• [4] В частности, хорошо известная проблема равенства классов сложности Р = NP [19]заключается в том, что неизвестно, есть ли модели, эволюцию которых нельзя никак предсказать, кроме как перебрав все возможные варианты развития. Во многих случаях кажется, что поиск правильного ответа всегда будет включать в себя исчерпывающий поиск по всемвозможным вариантам. Проблема Р = NP как бы спрашивает, а можно ли избежать полногопоиска «в общем случае». Кажется очевидным, что в общем случае — нет. Однако доказатьэто никому до сих пор не удалось [15].
• [5] Так, в 1960;е гг. в РГГУ и МГУ на базе теоретического семинара создаются отделениятеоретической и прикладной лингвистики.
• [6] «Исследование операций» — применение математических, количественных методовдля обоснования решений во всех областях целенаправленной человеческой деятельности. Исследование операций начинается тогда, когда для обоснования решений применяется тотили другой математический аппарат.