|
Чего не может компьютер, или Труднорешаемые задачи
Липецкий государственный педагогический институт
РЕФЕРАТ
Тема: Чего не может компьютер, или
труднорешаемые задачи
Студентки группы Л-2-2
Осадчей Ольги
Липецк, 1998
СОДЕРЖАНИЕ
О ЗАДАЧАХ И АЛГОРИТМАХ 3
ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ 5
ЭЛЕКТРОННЫЙ ПОДХОД К ИСКУССТВЕННОМУ ИНТЕЛЛЕКТУ 5
ДРУГИЕ ПОДХОДЫ К ИСКУССТВЕННОМУ ИНТЕЛЛЕКТУ 7
ЗАКЛЮЧЕНИЕ 9
ЛИТЕРАТУРА 10
Машина должна работать,
человек – думать.
Принцип IBM
О задачах и алгоритмах
В среде математиков известна такая притча. В
давние времена, когда никто и понятия не имел о ком-
пьютерах и их возможностях, один индийский мудрец
оказал большую услугу своему правителю. Правитель
решил отблагодарить его и предложил ему самому вы-
брать награду. На что мудрец ответил, что пожелал бы
видеть шахматную доску, на каждой клетке которой бы-
ли бы разложены зернышки пшена в следующем порядке:
на первой – 2, на второй – 2х2=4, на третьей –
2х2х2=8, на четвертой 24=16, и так далее на всех
клетках.
Сначала правитель обрадовался легкости расплаты.
Но вот выполнить обещание не смог, так как он и его
слуги вряд ли когда-нибудь смогли бы отсчитать 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.
1
3
| |
