Продолжение цикла. Начало см. в №№18 (163) за 2007 г. и 1 (164) за 2008 г. журнала RELGA.

Рассказ 5-й. Три задачи

Задача первая, совершенно канцелярская (из жизни нашего издательства)

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

Можно делать так: брать от начала к концу по две и проверять, правильно ли, что вторая стоит дальше первой («сравнивая» каждые две подряд идущие). Если карточек N, то придётся сделать N сравнений (и по N операций доставания пары карточек и закладки их обратно). То есть всего придётся сделать что-то около 2*N на доставание да 2*N на возврат обратно да N сравнений, всего 5*N операций. И насколько же это легче, чем сортировать!!! Знай себе перебирай карточки да смотри на каждые две под пальцами. Пролистал, и готово.
Математики говорят, что трудоёмкость этой проверки О(N) операций. То есть операций нужно примерно N (множитель 5 несущественен. Ну, может, 4 или 6. Интуитивно понятно, что на трудоёмкость это не сильно влияет)
Но раз так легко проверить, почему не так легко сделать?
Решить задачу сортировки действительно труднее, чем проверить решение. Плохие алгоритмы сортировки имеют сложность О(N в квадрате). Пишем O(N**2). Здесь «**» - обозначение степени. 2**3=2*2*2=8
То есть если Вы опрометчиво рассыпали не 20, а сотни две карточек, то для укладки их обратно Вам придётся сделать 200**2=200*200=40 000 операций. Это будут операции подхода к кучке, просмотра каждой карточки в той кучке, куда вставлять, сравнения с той, что в руках и т.п. Простые операции, но их 40 тысяч.
Лучшие известные алгоритмы сортировки имеют трудоёмкость O(N *logN). Это при больших N куда меньше, чем N**2, но куда больше, чем просто N… Логарифм по какому основанию, это для оценки трудоёмкости несущественно.

Задача вторая, «экономическая»

Разной экономике учат в наших «вузах» … только не настоящей… но мы отвлеклись. Рассмотрим –модельную- задачу, называемую «Задача коммивояжёра». Коммивояжёру нужно обойти по коммерческой надобности N городов, побывав в каждом городе ровно по одному разу, так, чтобы длина пути была кратчайшей.
Начнём с более простого, а именно: как проверить полученное решение. Допустим, что решения лежат где-то в куче, и на каждом написана его длина пути. Берём первое и кладём посреди комнаты. Берём следующее и смотрим: если оно длинее чем то, выбрасываем его. А если очередное выбранное из кучи короче того, что посреди комнаты, тогда кладём его в середину, а то выбрасываем. Это – алгоритм поиска наименьшего, он имеет трудоёмкость O(N). Но мы забыли, что ещё ж нужно проверять правильность пути в каждом варианте! То есть тот факт, что коммивояжёр не схалтурил, был в каждом городе. И только по одному разу. Наверно, труднее, чем O(N)…

Можно доказать, что трудоёмкость –проверки- задачи комивояжёра(К) такая же, как у –решения- задачи сортировки.
А вот какая же тогда трудоёмкость –решения- задачи К?
Ответ удивительный.
Трудоёмкость куда больше, чем O(N**2) и даже больше, чем O(N**M), где M-любая константа. Такие задачи историк математики Б.В Бирюков назвал NP-сложными (НеПолиномиально сложными). Есть и другой термин, который обозначает похожее: NP-полная задача (NP-complete).
Итак, для решения задачи обхода 20 городов может понадобиться куда больше, чем 20**4= 20*20*20*20=160000 операций… Конечно, если повезёт, и будет какая-нибудь очень лёгкая комбинация городов (например- много расположены в ряд), то меньше. А в общем случае без компьютера точно не обойтись.
А при больших N и компьютер не поможет.
Задача К имеет трудоёмкость O(M**N). Чему равно M, несущественно. Всё равно это такие большие числа… Пусть 100 городов, тогда пусть 2*100, это сколько будет?...
Сегодня не умеем решать задачу К.
Ничем. Ни мозгами, на копьютерами…. С увеличением N трудоёмкость растёт слишком быстро. Не хватит всех компьютеров галактики.
Задача сортировки P-сложная (принципиально проще).

У тех учёных, которые шли вот этим путём мысли и сравнивали трудоёмкость решения задачи и трудоёмкость проверки решения задачи, возникли предположения.

(1)Если решение задачи просто проверить, это была трудная (но решаемая) задача
Если решение задачи очевидно, то это была простая задача
Уж если решение задачи проверить трудно, то это была вовсе неподьёмная задача.

(2) Голос оптимиста говорит, что если уж возможна P-сложная проверка, то и сама задача была не более чем P-сложная. Это голос вредных преподов: «Мы же тут за пивком их контрольные проверяем, так значит, они там за пивком вполне могут их решать». Сложность проверки и решения принципиально одинаковы (с точностью до коффициента M). Задача К на самом-то деле тоже всего лишь P-сложная (как и сортировка), но мы просто ещё не знаем этого алгоритма, а знаем только NP-сложные алгоритмы.

Предположение вредных преподов (2) – это гипотеза, которая в математике не опровергнута и не доказана.
Мы можем почувствовать, что есть задачи принципиально разной сложности.
Возможно, есть реально неразрешимые даже для машин.
Возможно, простых задач вообще мало.

Задача третья, охотничья

Допустим, охотник идёт по лесу и видит мелькнувшую впереди большую жёлтую кошку. Он стреляет в кошку.
Таки это и была кошка. В окрестностях села встречается хозяин кошки, который ломает ружьё и самого охотника об дерево.
Допустим, охотник идёт по лесу и видит быстро мелькнувшую кошку. Он полагает, что это и есть кошка, тем более, что до села недалеко. Теряет бдительность, и через полчаса становится добычей рыси, которая прыгает ему на шею с ветки. Рысь то была…
Рысь лишь немногим больше хорошего кота. Что до кисточек, то их ещё надо разглядеть (если они вообще там есть). В рыси есть: усы, цвет=жёлтый, форма=кошка.форма и пр. ( вспомним рассказ про фреймовое представление знаний)
Допустим, Вы идёте по Москве, вдобавок без документов, и в конце квартала видите двоих мужчин с кучерявыми движениями, и один подносит к лицу не то рацию не то большой мобильник. Вы человек нервный, и прижимаетесь к стене. Те тоже нервные - они разворачиваются и стремительно убегают. Ни они, ни Вы и не милиционеры и не бандиты.
Всё это ошибки распознавания.
Рассмотрим эту задачу.
Назовём графом набор узлов, свяанных линиями. Удобно представлять узлы в виде шариков различного размера и цвета. Связи – в виде цветны верёвочек. Связи показывают ОТНОШЕНИЯ между компонентами понятия, например, если на голове есть фуражка, то от головы идёт линия к фуражке. От человека – к мобильнику (коммуникатору). В узлах хранятся, например, числовые характеристики (например, размер коммуникатора: большой, маленький).
Предположим, что есть два графа, узлы и верёвочки которых перепутали, и в таком виде сети бросили на пол. Как узнать, одинаковые ли это графы?
Или хоть в каком-нибудь смысле похожие?
Задача установления изоморфима графов является NP-сложной.
То есть В ПРИНЦИПЕ, даже имея как угодно мощный компьютер, графы можно сравнить лишь приблизительно.
И если наши понятия о предметах представимы в виде графов (а фреймовые - представимы), тогда мы эти предметы даже толком сравнить не можем.
Идентифицировать (распознать) не можем.
Такие ситуации Вам знакомы. Иногда мы распознаём ситуацию с точностью до имеющегося у нас в понятиях фрейма (внешнй облик, одежда). Образ врага по одежде и речи. Что внутри фрейма (экземпляра врага), на разбор этого у нас не хватает времени… Действительно, иногда похоже, что сознание орудует фреймами и графами. Тогда не удивительно, что мы так глупы.

Это вовсе не разум слаб, это задачи сложны.

А если совершенство разума всё-таки возможно? Гипотеза (2) не опровергнута. Вдруг в мире фреймов(подграфов) и графов есть быстрые алгоритмы сравнения, только им надо научиться?
Вдруг марсиане что-то такое умеют?
Вдруг в наших понятиях вмещаются не все вообще графы, а только такие, с которыми можно быстро работать?
Так думали математики некоторое время, пока не узнали, какие на самом деле и как мы решаем задачи. Об этом в следующих рассказах.



Рассказ 6-й. Матрица

Мозги промыть,
отварить,
откинуть на дуршлаг
и подавать с горошком
(Книга о вкусной
и здоровой пище)

Ответ заключается в том, что мозг вовсе не сравнивает обьекты и не порождает обьекты.
У него другая задача.

Вы чувствуете и делаете. Для того, чтобы сделать, у Вас есть руки, ноги, это для работы; коленки, лопатки, и ещё много восхитительных вещей… Какое-то количество органов для действий у Вас есть; и есть какое-то количество входов, через которые поступают чувства. Говорят, что их 5. Вернее будет сказать, что это каналы, через которые поступает информация.
Сколько её поступает, и сколько информации мы производим? Мы видим глазами очень подробные и сложные картины «на входе», и вроде бы производим в ответ движения, взятые из довольно стандартного набора, «на выходе». Кажется, что информации на выходе у нас меньше, чем на входе. Если так, тогда мозг – это машина свёртки, т е отображения многих параметров в немногие. Может, оно и так, а может, и не так. Ведь движения и положения тела у нас плавные, число «степеней свободы» нашего тела+голоса довольно велико. Пока что зафиксируем найденное нами свойство (или функцию) организма:
- он производит действия в ответ на действия, которые производят с ним.

Жизнеспособный организм «правильно» реагирует на ситуацию, иначе его, например, сьест рысь (см. рассказ 4). Но в самом деле, откуда берётся такая гордыня полагать, что только наш Разум может разбираться в событиях мира? :) Ведь разборщиков вокруг полно, и это все звери да птицы да мыши. Все прекрасно исполняют свои низменные функции, а если и ошибаются, то не чаще нас. А вот кто или что в них разбирается, и как, это мы сейчас посмотрим.

Функции. «Функция» - это одно из самых частых слов в математике. Функция делает из набора входных параметров набор выходных. Записывается это так: Y=F(X). Здесь Y-параметры на выходе, Х - на входе (X и Y - это векторы, т е не по одному числу, а по многу), F- формула, или набор формул (правил), или прибор, который в ответ на поступиший вектор X выдаёт на «исполнительные органы» вектор Y. Исполнительный орган в зависимости от величины чисел Y, поступающих на мышцы, прыгает или низко, или высоко.

Если формула (прибор) F простая, то у неё будет мало гибкости в выходных реакциях.
Можно попытаться по обстановке корректировать какие-то параметры (детали) прибора F. Для этого, понятно, нужны какие-то ещё другие приборы рядом.

Именно так устроены мозги, которых вокруг нас в природе полным-полно. Первый странный факт состоит в том, что если просто рядом свалить и лишь бы как соединить очень-очень простые приборы F, то на выходе этого клубка проводов и деталей можно получить достаточно разнообразные, «гибкие» сигналы.

При этом отпадает надобность в сознательной регулировке каждого прибора извне. Оно всё само бессознательно регулируется и, надеемся пока, устаканивается.

Каждый прибор (а они все одинаковы) – это нейрон. Нейрон имеет один выход и много входов. Выходной провод (это и в самом деле провод) называется аксон, входные – дендриты. Нейрон реализует какое ему повезёт от рождения, но примерно одно и то же F: Y=F(X). В исследованиях без ограничения общности полагают, что F нейрона - это сумма входных сигналов (некотрые поступают со знаком «минус», то есть вычитаются, а Y- всего одно число, а не вектор (один аксон на выходе). То есть совсем завалящие простенькие нашлись в природе нейроны…

Выходы нейронов соединены хаотически (так оно само выросло) со входами других, а некоторые выходы торчат из мозга наружу и подключены к органам движения и к другим органам. Также некоторые дендриты начинаются в органах (чувств). Есть относительно специализированные «промежуточные» нейроны . Схема приблизительна, но на обьяснение работы это не влияет.

Где же здесь находится сама бездна морали, т е «содержание» нейронной сети? Ведь мы отметили, что вид функций F не меняется. То есть сами клетки (нейроны) не изменяются (пока их не прихлопнут водкою. Они даже не делятся. Именно в нервной, не-регенерирующейся ткани были впервые обнаружены т. н. стволовые, или недифференцированные исходные клетки, из которых теоретически могли бы вырасти новые нейроны взамен погибщих. Но эта ремонтная система не работает). Итак, нейроны неизменны, а что же меняется?

Меняется проводимость в тех местах, где аксоны (выходы) одни нейронов соединяются со входами (дендритами) других. В каждом месте соединения проводов от нейронов (на контактной площадке) как бы заключено ЧИСЛО сопротивления сигналу. Эти числа могут изменяться. Изменяются они сами по себе, и вот каким с виду естественным образом. Если через данное место стыка сигнал проходит часто, сопротивление здесь становится меньше нормального, и тогда сигналу проходить легче. Если сила сигнала превышена, контакт перегорает полностью или частично, сопротивление повышается, и возвращается к нормальному лишь через некоторое время.

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

Это и есть нейронная сеть. Это ворох сумматоров, соединённых проводами с контактиками, на которых написаны ЧИСЛА проводимости. В этих числах всё содержание сознания…

Пока подумаем, а как же получается, что РАЗНЫЕ топологии сети и, наверно, разные наборы чисел определяют такие похожие сознания? (топология – это что с чем соединено)
_________________________________________

© Титов Александр Алексеевич

Окончание следует