Чего не может компьютер, или Труднорешаемые задачи

Липецкий государственный педагогический институт , -2-2 Липецк, 1998 СОДЕРЖАНИЕ О задачах и алгоритмах 3 Эвристические алгоритмы 5 Электронный подход к искусственному интеллекту 5 Другие подходы к искусственному интеллекту 7 Заключение 9 ЛИТЕРАТУРА 10 Машина должна работать, человек думать. Принцип IBM О задачах и алгоритмах В среде математиков известна такая притча.

В давние времена, когда никто и понятия не имел о компьютерах и их возможностях, один индийский мудрец оказал большую услугу своему правителю. Правитель решил отблагодарить его и предложил ему самому выбрать награду. На что мудрец ответил, что пожелал бы видеть шахматную доску, на каждой клетке которой были бы разложены зернышки пшена в следующем порядке на первой 2, на второй 2х24, на третьей 2х2х28, на четвертой 2416, и так далее на всех клетках. Сначала правитель обрадовался легкости расплаты.

Но вот выполнить обещание не смог, так как он и его слуги вряд ли когда-нибудь смогли бы отсчитать 264 зерен на последнюю клетку, что соответствует примерно 18,4 миллиардам миллиардов . Задача, сформулированная в этой притче, относится к разряду тех, при решении которых самый современный компьютер бессилен так же, как в древности слуги правителя. Зная производительность современных ЭВМ, не представляет труда убедиться в том, что пользователю не

хватит всей его жизни для отсчета зерен, но в данном случае это даже не самое главное. Суть проблемы в том, что достаточно незначительно изменить входные данные, чтобы перейти от решаемой задачи к нерешаемой. Каждый человек в зависимости от своих счетных способностей может определить, начиная с какой клетки пятнадцатой или допустим, восемнадцатой продолжать отсчитывать зерна для него не имеет смысла. То же самое можно определить и для ЭВМ, для которой подобные характеристики написаны в технической

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

с нахожденим сочетаний, перестановок, размещений каких-либо объектов. Всегда есть соблазн многие задачи решать исчерпыванием, т.е. проверкой всех возможных комбинаций. Например, так решается задача безошибочной игры в шахматы. Эта задача относится к классическим нерешаемым Ни одна современная ЭВМ не сможет сгенерировать все простые перестановки более чем 12 разных предметов более 479 млн не

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

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

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

Задачи, своими алгоритмами решения создающие предпосылки для резкого возрастания использования ресурсов, в общем виде не могут быть решены на цифровых вычислительных машинах, т.к. ресурсы всегда ограничены. Эвристические алгоритмы Другое возможное решение описанной проблемы в написании численных алгоритмов, моделирующих технологические особенности творческой деятельности и сам подход к аналитическому решению. Методы, используемые в поисках открытия нового, основанные на опыте решения родственных задач в условиях

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

Совершенно нереально исчерпывание шахматного лабиринта из 2х10116 площадок Занимаясь поиском ответа, человек пользуется другими способами, чтобы сократить путь к решению. Возможно сокращение числа вариантов перебора и для машины, достаточно сообщить ей правила, которые для человека опыт, здравый смысл. Такие правила приостановят заведомо бесполезные действия. Электронный подход к искусственному интеллекту Исторически попытки моделирования процессов мышления

для достижения аналитических решений делались достаточно давно с 50-х гг ХХ в и соответствующая отрасль информатики была названа искусственным интеллектом. Исследования в этой области, первоначально сосредоточенные в нескольких университетских центрах США - Массачусетском технологическом институте, Технологическом институте Карнеги в Питтсбурге, Станфордском университете ныне ведутся во многих других университетах и корпорациях

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

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

Предполагалось, что преодолев период электронного детства и обучившись в библиотеках всего мира, хитроумные компьютеры, благодаря быстродействию, точности и безотказной памяти постепенно превзойдут своих создателей-людей. Сейчас, в соответствии с тем, что было сказано выше, мало кто говорит об этом, а если и говорит, то отнюдь не считает, что подобные чудеса не за горами. На протяжении всей своей короткой истории исследователи в области искусственного интеллекта всегда

находились на переднем крае информатики. Многие ныне обычные разработки, в том числе усовершенствованные системы программирования, текстовые редакторы и программы распознавания образов, в значительной мере рассматриваются на работах по искусственному интеллекту. Короче говоря, теории, новые идеи, и разработки искусственного интеллекта неизменно привлекают внимание тех, кто стремится расширить области применения и возможности компьютеров, сделать их более дружелюбными

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

кругозором. Даже среди исследователей искусственного интеллекта теперь многие сомневаются, что большинство подобных изделий принесет существенную пользу. Немало критиков искусственного интеллекта считают, что такого рода ограничения вообще непреодолимы. К числу таких скептиков относится и Хьюберт Дрейфус, профессор философии Калифорнийского университета в Беркли. С его точки зрения, истинный разум невозможно отделить от его человеческой основы, заключенной

в человеческом организме. Цифровой компьютер - не человек говорит Дрейфус У компьютера нет ни тела, ни эмоций, ни потребностей. Он лишен социальной ориентации, которая приобретается жизнью в обществе, а именно она делает поведение разумным. Я не хочу сказать, что компьютеры не могут быть разумными. Но цифровые компьютеры, запрограммированные фактами и правилами из нашей, человеческой, жизни, действительно

не могут стать разумными. Поэтому искусственный интеллект в том виде, как мы его представляем, невозможен. Другие подходы к искусственному интеллекту В это же время ученые стали понимать, что создателям вычислительных машин есть чему поучиться у биологии. Среди них был нейрофизиолог и поэт-любитель Уоррен Маккалох, обладавший философским складом ума и широким кругом интересов. В 1942 г. Маккалох, участвуя в научной конференции в

Нью-Йорке, услышал доклад одного из сотрудников Винера о механизмах обратной связи в биологии. Высказанные в докладе идеи перекликались с собственными идеями Маккалоха относительно работы головного мозга. В течении следующего года Маккалох в соавторстве со своим 18-летним протеже, блестящим математиком Уолтером Питтсом, разработал теорию деятельности головного мозга.

Эта теория и являлась той основой, на которой сформировалось широко распространенное мнение, что функции компьютера и мозга в значительной мере сходны. Исходя отчасти из предшествующих исследований нейронов основных активных клеток, составляющих нервную систему животных, проведенных Маккаллохом, они с Питтсом выдвинули гипотезу, что нейроны можно упрощенно рассматривать как устройства, оперирующие двоичными числами. В 30-е годы XX в. пионеры информатики, в особенности американский ученый

Клод Шеннон, поняли, что двоичные единица и нуль вполне соответствуют двум состояниям электрической цепи включено-выключено, поэтому двоичная система идеально подходит для электронно-вычислительных устройств. Маккалох и Питтс предложили конструкцию сети из электронных нейронов и показали, что подобная сеть может выполнять практически любые вообразимые числовые или логические операции. Далее они предположили, что такая сеть в состоянии также обучаться, распознавать образы, обобщать,

т.е. она обладает всеми чертами интеллекта. Теории Маккаллоха-Питтса в сочетании с книгами Винера вызвали огромный интерес к разумным машинам. В 40-60-е годы все больше кибернетиков из университетов и частных фирм запирались в лабораториях и мастерских, напряженно работая над теорией функционирования мозга и методично припаивая электронные компоненты моделей нейронов. Из этого кибернетического, или нейромодельного, подхода к машинному разуму

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

живые организмы. Естественно, отнюдь не во всех случаях возможна аналогия с живыми организмами. Как однажды заметили Уоррен Маккаллох и его сотрудник Майкл Арбиб, если по весне вам захотелось обзавестись возлюбленной, не стоит брать амебу и ждать пока она эволюционирует. Но дело здесь не только во времени. Основной трудностью, с которой столкнулся восходящий метод на заре своего существования, была высокая

стоимость электронных элементов. Слишком дорогой оказывалась даже модель нервной системы муравья, состоящая из 20 тыс. нейронов, не говоря уже о нервной системе человека, включающей около 100 млрд. нейронов. Даже самые совершенные кибернетические модели содержали лишь неколько сотен нейронов. Столь ограниченные возможности обескуражили многих исследователей того периода. Заключение В настоящее время наличие сверхпроизводительных микропропроцессоров и дешевизна электронных

компонентов позволяют делать значительные успехи в алгоритмическом моделировании искусственного интеллекта. Такой подход дает определенные результаты на цифровых ЭВМ общего назначения и заключается в моделировании процессов жизнедеятельности и мышления с использованием численных алгоритмов, реализующих искусственный интеллект. Здесь можно привести много примеров, начиная от простой программы игрушки тамагочи и заканчивая моделями

колонии живых организмов и шахматными программами, способными обыграть известных гроссмейстеров. Сегодня этот подход поддерживается практически всеми крупнейшими разработчиками аппаратного и программного обеспечения, поскольку достижения при создании эвристических алгоритмов используются и в узкоспециальных, прикладных областях при решении сложных задач, принося значительную прибыль разработчикам. Другие подходы сводятся к созданию аппаратуры, специально ориентированной на те или иные задачи, как

правило, эти устройства не общего назначения аналоговые вычислительные цепи и машины, самоорганизующиеся системы, перцептроны и т.п С учетом дальнейшего развития вычислительной техники этот подход может оказаться более перспективным, чем предполагалось в 50-80гг. ЛИТЕРАТУРА 1 Дрейфус Х. Чего не могут вычислительные машины М. Прогресс, 1979. 2 Винер Н. Кибернетика и общество

М ИЛ, 1979 3 Компьютер обретает разум. М Мир 1990 В сборнике Психологические исследования интеллектуальной деятельности. Под.ред. О.К.Тихомирова М МГУ, 1979 4 Пекелис В. Кибернетика от А до Я. М 1990. 5 Липский В. Комбинаторика для программиста. М Мир, 1990.