Шрифт:
* * *
СТИРАЛЬНЫЕ МАШИНЫ С НЕЧЕТКОЙ ЛОГИКОЙ
Чтобы оптимизировать длительность и качество стирки, полезно точно указать, является одежда очень грязной, слегка грязной или практически чистой. Простейшие стиральные машины с нечеткой логикой присваивают каждой загрузке белья значение загрязнения от 0 до 1. Затем к фиксированному интервалу стирки продолжительностью в десять минут добавляется определенное время в зависимости от степени загрязнения одежды. Машина может, например, определить, что для чистого белья (0) достаточно базового времени стирки, а для очень грязного (1) — на две минуты больше. Следовательно, если мы положим в стиральную машину слегка грязную рубашку, продолжительность стирки увеличится на одну минуту. В других, более сложных моделях, с целью экономии электроэнергии учитывается степень жирности (жирные пятна отстирываются тяжелее других) и вес загруженного белья.
* * *
«Любовь» и «справедливость» — слишком расплывчатые понятия, чтобы их можно было описать двоичной логикой. Множество оттенков серого, простирающееся между «он меня любит» и «он меня не любит», между виной и невиновностью, описывается нечеткой логикой. С ростом сложности возникает потребность в новом мышлении. Следовательно, полезно ввести оценку сложности понятий, однако само понятие «сложность» не поддается попыткам дать ему определение. Даже в царстве математики, где правит абсолютная точность, нельзя однозначно отделить сложные проблемы от простых. Именно это происходит и с машинами Тьюринга: если в прошлой главе работа с идеальными компьютерами позволила нам получить теоретические результаты, касающиеся проблем, которые не может решить машина, то теперь нас интересует, какие расчеты она может провести с учетом ограничений в объеме памяти и времени выполнения программ. Именно так, за неимением лучшего определения, мы будем отличать простые задачи от сложных.
В первом приближении мы можем определить сложность как число операций, необходимых для решения задачи. Представим коммивояжера, которому нужно посетить несколько городов, после чего вернуться в исходный. Следовательно, его целью будет максимально сократить пройденный путь. Если этими городами будут, например, Париж (П), Лондон (Л), Берлин (Б) и Рим (Р) и коммивояжер начинает поездку в Париже, то его секретарь может составить расписание шестью разными способами: ПЛБРП, ПЛРБП, ПБЛРП, ПБРЛП, ПРБЛП и ПРЛБП. Учитывая примерные расстояния Париж — Лондон (455 км), Париж — Берлин (1050 км), Париж — Рим (1435 км), Лондон — Берлин (1095 км), Лондон — Рим (1855 км) и Берлин — Рим (1515 км), можно рассчитать общую длину каждого маршрута и выбрать кратчайший из них:
Учитывая данные, представленные в таблице, оптимальным будет маршрут Париж — Лондон — Берлин — Рим — Париж или он же, но в обратном направлении: Париж — Рим — Берлин — Лондон — Париж. Но что произойдет, если коммивояжеру нужно будет посетить не три города, а четыре, пять или любое другое количество городов? Для решения этой задачи всего для двадцати городов компьютеру средней производительности потребуется 80 тысяч лет, и в свете этого возможная потеря времени от неправильного выбора маршрута уже несущественна.
Если мы попытаемся решить задачу «грубой силой», то потребуется рассмотреть уже не шесть случаев — их число будет равно произведению 1·2·3· … и т. д. до 20. Запись этого числа содержит девятнадцать цифр. В математике это число называется 20 факториал и обозначается восклицательным знаком после числа. Так, 3! = 1·2·3 = 6; 4! = 1·2·3·4 = 24; в общем случае n! равен произведению первых n натуральных чисел.
Факториал — это пример функции, вычислить значение которой теоретически очень просто, однако на практике компьютеры пасуют перед этой задачей. Как мы уже отмечали в предыдущей главе, все рекурсивные функции являются вычислимыми. Напомним, что функция является рекурсивной, если значение f(n) можно вычислить на основе значений, которые принимает эта функция для чисел, меньших n. Факториал — это классический пример рекурсивной функции, так как если мы хотим вычислить 4! = 1·2·3·4, мы можем сначала найти произведение 1·2·3, а затем умножить его на 4. Но что представляет собой произведение 1·2·3? Оно равно 3! таким образом, если известно значение 3! то чтобы найти 4! достаточно одной операции. В общем случае n! = (n — 1)!·n — это доказывает, что факториал является рекурсивной, а следовательно, и вычислимой функцией. Для машины Тьюринга, способной работать бесконечное время, вычисление n! не представляет трудностей. Но на практике значения факториала возрастают столь быстро, что с ними вскоре становится невозможно работать.
График, показывающий рост значений факториала.
Предыдущий пример был бы не более чем любопытным фактом, если бы факториал не описывал число перестановок элементов конечных множеств, то есть число способов, которыми можно упорядочить их элементы. Так, фразы «3! = 6» и «множество {1, 2, 3} можно записать шестью разными способами (123, 132, 213, 231, 312 и 321)» содержат одинаковую информацию. Так как примитивный метод решения многих задач, схожих с задачей коммивояжера, требует последовательного перебора всех элементов множества, которое может быть достаточно большим, то скорость, с которой возрастают значения факториала, имеет фатальные последствия.
* * *
ИЗОБРЕТАТЕЛЬ ШАХМАТ
По легенде, персидский царь хотел наградить изобретателя шахмат и подарить ему все, что он пожелает. Тогда мудрец удивил царя просьбой, которая показалась скромной: он хотел получить одно зерно за первую клетку доски, два — за вторую, четыре — за третью и т. д. — на каждой клетке доски должно было находиться в два раза больше зерен, чем на предыдущей. Эта просьба показалась царю насмешкой, и он, рассерженный, повелел слугам немедленно исполнить просьбу мудреца и выслать ему столько зерна, сколько тот просил. Каково же было его удивление, когда один из советников на следующий день сообщил ему, что для этого не хватит зерна в амбарах всего мира. Функция, принимавшая значения 1, 2, 4, 8… возрастала столь быстро, что общее число зерен составило 18446744073 709551615.
* * *
В одном из простых определений сложными называются задачи, решение которых требует выполнения сопоставимого числа операций, а простыми считаются те, которые разрешимы не только с теоретической, но и с практической точки зрения, то есть в разумное время. Эти задачи часто обозначаются буквой Р (по первой букве английского слова «полином»), так как число операций для их решения примерно равно некоторому многочлену от времени выполнения.