2014-02-24
7533
Сложность является определяющим свойством систем и поэтому заслуживает отдельного рассмотрения. Сложность в применении к системам имеет разный смысл – структурная сложность, динамическая сложность, вычислительная. Обычно степень сложности оценивается количеством информации, необходимой для описания реальной системы. При таком подходе сложность ставится в зависимость от наблюдателя. Например, для нейрофизиолога мозг сложен и его адекватное описание требует много информации, для мясника мозг прост, так как ему нужно только отличить его от других сортов мяса, для чего он использует сравнительно мало информации (log230» 5 бит). Мы будем различать сложность как свойство систем и сложность самих задач, соответственно будем говорить о сложности систем и сложности задач, последнюю называют также вычислительной сложностью. Вне зависимости от типа сложности можно выделить два принципа оценки сложности систем.
Первый принцип связан с понятием количества информации и состоит в том, что сложность системы должна быть пропорциональна объему информации, необходимой для описания этой системы (так называемая дескриптивная сложность). Одним из способов оценки дескриптивной (описательной) сложности является оценка числа элементов, входящих в систему (переменных, состояний, компонентов), и разнообразия взаимозависимостей между ними.
Второй принцип связан с понятием энтропии (мера неопределенности или неясности) и состоит в том, что сложность системы должна быть пропорциональна объему информации, необходимому для разрешения (уменьшения) неопределенности (неясности) в системе (так называемая сложность познания). Оба принципа дополняют друг друга в том смысле, что для изучаемой системы при увеличении одной сложности уменьшается другая и наоборот (именно так соотносятся между собой количество информации и энтропия). Отметим, что при переходе от более простой системы к более сложной обе сложности – описательная и сложность познания – возрастают.
Структурная сложность включает такие составляющие, как схема связности, многообразие компонентов, число связей, сила взаимодействия. Динамическая сложность – это сложность предсказания поведения системы. Система со сложной структурой имеет сложное поведение, но обратное, вообще говоря, неверно. Вычислительная сложность определяется сложностью алгоритма, используемого для решения системных задач.
Предел Бреммерманна. Американский ученый Ханс Бреммерманн в 1962 г. получил следующий результат: "Не существует системы обработки данных, искусственной или естественной, которая могла бы обрабатывать более чем 2×1047 бит в секунду на грамм своей массы". Этот результат может быть выведен из соотношения неопределенностей Гейзенберга.
Полученное соотношение является очень большим и не может быть достигнуто имеющимися средствами. Так при энергии лазера Е = 10 Дж, воздействующей на атомную систему с частотой перехода D Е @ 109 Гц (сверхтонкая структура ядерных переходов щелочно-земельных элементов) для N имеем N @ 1026. Соотношение реализуется для атомных пучков со скоростью, близкой к скорости света.
Используя полученный предел для обработки информации граммом массы за 1 с процессорного времени, Бреммерманн вычислил число бит, которые могла бы обработать гипотетическая компьютерная система, имеющая массу, равную массе Земли, за период, равный примерному возрасту Земли (Это вся информация, которой располагает человечество). Так как т 3»6×1027 г, а возраст » 1010 лет, т.е. 3,14·1017 с, то такой компьютер мог бы обработать» 2,56·1092 бит или 1093 бит. Это число называют пределом Бреммерманна, а задачи, требующие обработки более чем 1093 бит информации, называют трансвычислительными задачами.
Предел Бреммерманна является весьма строгим ограничением. Решение многих задач для систем даже небольшого размера требует большего объема информации. Например, если имеется система из n переменных с k состояниями каждая, то задача классификации системы на множестве подмножеств систем может быть трансвычислительной. Действительно, для этого необходимо обработать kn бит информации, т е. задача становится трансвычислительной при kn > 1093, что выполняется при k = 2 и п = 308; k = 3 и п = 194т.д.
Аналогичной является задача распознавания образов, решаемая на массиве q ´ q типа шахматной доски, причем каждая клетка может быть одного из k цветов. Всего может быть kn шаблонов раскраски, где п = q 2. Тогда задача поиска наилучшей классификации шаблонов является трансвычислительной при q = 18, k = 2 или q = 10, k = 9.
Сетчатка состоит примерно из миллиона светочувствительных колбочек. Если даже считать, что каждая имеет только два состояния, то исследование сетчатки потребует 210 = 10300000 бит. Та же проблема возникает при решении задачи тестирования СБИС (сверхбольших интегральных схем), например, для схемы с 308 входами и 1 выходом (тестирующий сигнал имеет два состояния).
Если задача является трансвычислительной, то чтобы ее можно было решить, она должна быть переформулирована. Наиболее распространенный способ состоит в использовании эвристик, ослаблении условий. Например, поиск приближенного (а не точного) решения, агрегирование вариантов. Одно из наиболее важных следствий из существования предела Бреммерманна состоит в том, что прежде чем решать задачу (изучать систему), надо оценить информационные запросы. Если нужно 2·103 бит, то все в порядке, если же оценка дает 10300 бит, то следует применять эвристические методы либо отказаться от решения такой задачи, если эффективный алгоритм отсутствует.
Вычислительная сложность. Конкретные вычислительные средства накладывают, конечно, более строгие ограничения на сложность задач, чем предел Бреммерманна – 1093 бит. Вычислительная сложность связана с поиском алгоритма, т. е. набора команд, описывающих план действий по решению задачи определенного типа за конечное число шагов. При рассмотрении алгоритмов используется понятие машины Тьюринга, которая представляет собой устройство, состоящее из автомата (блока управления) с конечным числом состояний и ленты. Автомат обладает памятью, что позволяет ему находиться в одном из состояний, принадлежащих конечному множеству состояний, например Z = { z 1, z 2, …, zn }. Потенциально бесконечная в обоих направлениях лента разбита на отрезки одинаковой длины – ячейки. В каждой ячейке записана буква из конечного набора букв алфавита. Одна из букв, например x 0,интерпретируется как пробел (пустая ячейка). Связь между автоматом и лентой осуществляется с помощью читающей-пишущей головки, которая может считать букву с ленты или записать ее на ленту. Одновременно головке доступна только одна ячейка. Машина Тьюринга реализует некоторый алгоритм, принимаемый за исходный при сравнении. Автомат на каждом шаге изменяет свое состояние и выполняет одно из следующих действий: а) записывает на ленту вместо текущей буквы новую; б) сдвигается по ленте на одну ячейку влево или вправо; в) прекращает вычисление (операция остановки). Машина называется детерминированной, если запрещается, чтобы любые две четверки из этого множества начинались с одной и той же пары zc, xr, в противном случае машина Тьюринга называется недетерминированной. Общепринятая гипотеза, известная как тезис Черча, утверждает, что если функцию можно вычислить на детерминированной машине Тьюринга, то она считается вычислимой. Таким образом, машины Тьюринга дают аппарат, позволяющий формально определить существование алгоритмов решения различных задач. Задача считается неразрешимой, если не существует алгоритма ее решения. Для доказательства неразрешимости задачи достаточно доказать, что ее нельзя решить на машине Тьюринга. Неразрешимые задачи образуют один из трех классов задач. Во второй класс входят задачи, про которые не доказано, что они неразрешимы, но для которых не найдены решающие алгоритмы. Остальные задачи образуют класс разрешимых, т. е. они в принципе разрешимы. Однако их решение может потребовать больших затрат времени, поэтому вычислительная сложность изучается с позиций этого ресурса. На практике разрешимость задачи зависит от применяемого алгоритма, конкретной системы, имеющихся вычислительных мощностей. При заданном алгоритме время ее решения удобно представлять как переменную, зависящую от размера рассматриваемых систем. Эта переменная, называемая размерностью варианта задачи, определяет объем входной информации, необходимый для описания этих систем. Так как любой метод (алгоритм) позволяет решать несколько однотипных задач с различными исходными данными, то критерием качества метода в целом является решение наихудшего возможного случая из всех, допускающих применение данного алгоритма. При этом определяющим является общее число элементарных операций (время) как функция размерности входных данных. Таким образом, сложностью алгоритма называется выраженная в виде функции от размерности входных данных верхняя граница числа операций (времени), необходимого для выполнения алгоритма, решающего вариант задачи. Функция называется временной функцией сложности (¦). Выделяют три класса задач, отличающихся скоростью роста их функций сложности.
К первому классу (классу P) относятся полиномиальные алгоритмы Задача называется "хорошей", или принадлежащей классу Р, если для нее известен алгоритм, сложность которого составляет полином заданной постоянной степени, не зависящей от размерности входной величины п. К задачам этого класса относятся деление, извлечение корня, решение квадратного уравнения и т.п.
Ко второму классу (классу Е) относятся экспоненциальные алгоритмы. Экспоненциальной считается задача, сложность которой порядка не менее ¦ п (где ¦ – константа или полином от п),например, в случае, когда число ожидаемых ответов уже само по себе экспоненциально. Сложность соответствующих алгоритмов превосходит сложность o (nk) при любом k. Например, к этому классу относятся задачи, в которых требуется построить все подмножества некоторого множества, все клики (полные подграфы) некоторого графа; задача распознавания правильных выражений на языках с несложными алфавитами и правилами построения единиц (ее сложность превышает, где п – размерность входных данных).
При небольших п экспоненциальный алгоритм может быть более быстрым, чем полиномиальный, однако различие между этими классами задач всегда велико и проявляется при больших п. Поэтому полиномиальные алгоритмы считаются эффективными, экспоненциальные – неэффективными, а соответствующие задачи – поддающимися и неподдающимися решению.
Задачи, не попадающие ни в класс Р, ни в класс Е. К ним относятся:
– решение систем уравнений с целочисленными переменными;
– существование среди заданных подмножеств покрытия;
– составление расписаний (раскрасок), учитывающих определенные
условия (бинарные отношения);
– существование множества значений логических переменных,
которые позволяют сделать значение произвольного заданного
логического выражения истинным;
– оптимизация пути коммивояжера через сеть городов;
– отбор файлов при запросе в информационный банк данных для
получения информации с наименьшей стоимостью;
– размещение обслуживающих центров (телефон и т.п.) для
максимального числа клиентов при минимальном числе центров;
– оптимальная загрузка емкости (рюкзак, поезд, корабль, самолет)
при наименьшей стоимости;
– оптимальный раскрой (бумага, картон, стальной прокат);
– оптимизация маршрутов в воздушном пространстве, инвестиций,
станочного парка;
– диагностика (болезни, поломки, дефекты печатных схем).
Все эти задачи эквивалентны по сложности. Класс хороших задач мал, остальные задачи являются трудными и решаются методами искусственного интеллекта.
Класс NР: недетерминированные полиномиальные задачи. Для большинства практических задач неизвестно, существует ли полиномиальный алгоритм их решения, но и не доказано, что они не поддаются решению. Общим для них является то, что они могут быть решены за полиномиальное время на недетерминированных машинах Тьюринга (НДМТ). Такие задачи и называют NР -задачами. Под решением здесь понимается, что машина может проверить правильность предложенного решения за полиномиальное время. К NР -задачам относятся:
– разрешимость логического выражения;
– трехцветная раскраска графа;
– построение покрытия или разбиения множества;
– построение клики (полного подграфа) из k вершин на
неориентированном графе;
– задача о рюкзаке;
– разбиение числового множества на две непересекающиеся части такие,
что сумма чисел в одной равна сумме чисел в другой;
– существование на ориентированном графе такого циклического
маршрута коммивояжера, общая стоимость которого меньше заданного
числа k.
Кроме времени важно бывает оценить также и необходимый объем памяти компьютера. Это можно сделать с помощью пространственной функции сложности. Любая задача, решаемая за полиномиальное время, решается в полиномиальном пространстве, так как за конечное время автомат использует конечное пространство (число ячеек), не большее числа шагов вычисления. Обратное неверно.
