Сложность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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