Чего не может компьютер, или Труднорешаемые задачи
Липецкий государственный педагогический институт
РЕФЕРАТ
Тема: Чего не может
компьютер, или
труднорешаемые задачи
Студентки группы Л-2-2
Осадчей Ольги
Липецк, 1998
СОДЕРЖАНИЕ
О задачах и алгоритмах................................................................................................................................... 3
Эвристические алгоритмы............................................................................................................................. 5
Электронный подход к искусственному интеллекту............................................................. 5
Другие подходы к искусственному интеллекту......................................................................... 7
Заключение................................................................................................................................................................. 9
ЛИТЕРАТУРА................................................................................................................................................................. 10
Машина должна
работать,
человек – думать.
Принцип IBM
О задачах и алгоритмах
В среде математиков известна такая притча. В
давние времена, когда никто и понятия не имел о компьютерах и их возможностях,
один индийский мудрец оказал большую услугу своему правителю. Правитель решил отблагодарить
его и предложил ему самому выбрать награду. На что мудрец ответил, что пожелал
бы видеть шахматную доску, на каждой клетке которой были бы разложены зернышки
пшена в следующем порядке: на первой – 2, на второй – 2х2=4, на третьей – 2х2х2=8,
на четвертой 24=16, и так далее на всех клетках.
Сначала правитель
обрадовался легкости расплаты. Но вот выполнить обещание не смог, так как он и
его слуги вряд ли когда-нибудь смогли бы отсчитать 264 зерен на
последнюю клетку, что соответствует примерно 18,4 миллиардам миллиардов (!).
Задача, сформулированная в
этой притче, относится к разряду тех, при решении которых самый современный
компьютер бессилен так же, как в древности слуги правителя. Зная
производительность современных ЭВМ, не представляет труда убедиться в том, что пользователю
не хватит всей его жизни для отсчета зерен, но в данном случае это даже не
самое главное. Суть проблемы в том, что достаточно незначительно
изменить входные данные, чтобы перейти от решаемой задачи к нерешаемой. Каждый
человек в зависимости от своих счетных способностей может определить, начиная с
какой клетки (пятнадцатой или допустим, восемнадцатой) продолжать отсчитывать
зерна для него не имеет смысла. То же самое можно определить и для ЭВМ, для
которой подобные характеристики написаны в технической документации.
Подобные алгоритмы решения
имеет чрезвычайно большой круг задач, особенно комбинаторных проблем, связанных
с нахожденим сочетаний, перестановок, размещений каких-либо объектов. Всегда
есть соблазн многие задачи решать исчерпыванием, т.е. проверкой всех возможных
комбинаций. Например, так решается задача безошибочной игры в шахматы. Эта
задача относится к классическим нерешаемым! Ни одна современная ЭВМ не сможет
сгенерировать все простые перестановки более чем 12 разных предметов (более 479
млн.), не говоря уже о всех возможных раскладках колоды из 36 игральных карт.
Поэтому труднорешаемой
(нерешаемой) задачей можно называть такую задачу, для которой не существует
эффективного алгоритма решения. Экспоненциальные алгоритмы решений, в том
числе и исчерпывающие, абсолютно неэффективны для случаев, когда входные данные
меняются в достаточно широком диапазоне значений, следовательно, в общем случае
считать их эффективными нельзя. Эффективный алгоритм имеет не настолько резко
возрастающую зависимость количества вычислений от входных данных, например
ограниченно полиномиальную, т.е х находится в основании, а не в показателе
степени. Такие алгоритмы называются полиномиальными, и, как правило, если
задача имеет полиномиальный алгоритм решения, то она может быть решена на ЭВМ с
большой эффективностью. К ним можно отнести задачи соритровки данных,
многие задачи математического программирования и т.п.
Чего же не может и, скорее
всего, никогда не сможет компьютер в его современном (цифровая вычислительная
машина) понимании? Ответ очевиден: выполнить решение полностью аналитически.
Постановка задачи заключается в замене аналитического решения численным
алгоритмом, который итеративно (т.е. циклически повторяя операции) или рекурсивно
(вызывая процедуру расчета из самой себя) выполняет операции, шаг за шагом
приближаясь к решению. Если число этих операций возрастает, время выполнения, а
возможно, и расход других ресурсов (например, ограниченной машинной памяти),
также возрастает, стремясь к бесконечности. Задачи, своими алгоритмами
решения создающие предпосылки для резкого возрастания использования ресурсов, в
общем виде не могут быть решены на цифровых вычислительных машинах, т.к. ресурсы
всегда ограничены.
Другое возможное решение
описанной проблемы – в написании численных алгоритмов, моделирующих технологические
особенности творческой деятельности и сам подход к аналитическому решению.
Методы, используемые в поисках открытия нового, основанные на опыте решения
родственных задач в условиях выбора вариантов, называются эвристическими.
На основе таких методов и выполняется машинная игра в шахматы. В эвристике шахматы
рассматриваются как лабиринт, где каждая позиция представляет собой площадку
лабиринта. Почему же именно такая модель?
В психологии мышления
существует т.н. лабиринтная гипотеза, теоретически представляющая
решение творческой задачи как поиск пути в лабиринте, ведущего от начальной
площадки к конечной. Конечно, можно проверить все возможные пути, но
располагает ли временем попавший в лабиринт? Совершенно нереально исчерпывание
шахматного лабиринта из 2х10116 площадок! Занимаясь поиском ответа,
человек пользуется другими способами, чтобы сократить путь к решению. Возможно
сокращение числа вариантов перебора и для машины, достаточно «сообщить» ей
правила, которые для человека – опыт, здравый смысл. Такие правила приостановят
заведомо бесполезные действия.
Исторически попытки моделирования процессов мышления
для достижения аналитических решений делались достаточно давно (с 50-х гг ХХ
в.), и соответствующая отрасль информатики была названа искусственным
интеллектом. Исследования в этой области, первоначально сосредоточенные в
нескольких университетских центрах США - Массачусетском технологическом институте,
Технологическом институте Карнеги в Питтсбурге, Станфордском университете, -
ныне ведутся во многих других университетах и корпорациях США и других стран. В
общем исследователей искусственного интеллекта, работающих над созданием
мыслящих машин, можно разделить на две группы. Одних интересует чистая наука и
для них компьютер- лишь инструмент, обеспечивающий возможность
экспериментальной проверки теорий процессов мышления. Интересы другой группы
лежат в области техники: они стремятся расширить сферу применения компьютеров и
облегчить пользование ими. Многие представители второй группы мало заботятся о
выяснении механизма мышления - они полагают, что для их работы это едва ли
более полезно, чем изучение полета птиц в самолетостроении.
В настоящее время, однако,
обнаружилось, что как научные, так и технические поиски столкнулись с несоизмеримо
более серьезными трудностями, чем представлялось первым энтузиастам. На первых
порах многие пионеры искусственного интеллекта верили, что через какой-нибудь
десяток лет машины машины обретут высочайшие человеческие таланты.
Предполагалось, что преодолев период "электронного детства" и
обучившись в библиотеках всего мира, хитроумные компьютеры, благодаря
быстродействию, точности и безотказной памяти постепенно превзойдут своих
создателей-людей. Сейчас, в соответствии с тем, что было сказано выше, мало кто
говорит об этом, а если и говорит, то отнюдь не считает, что подобные чудеса не
за горами.
На протяжении всей своей короткой истории исследователи
в области искусственного интеллекта всегда находились на переднем крае
информатики. Многие ныне обычные разработки, в том числе усовершенствованные
системы программирования, текстовые редакторы и программы распознавания
образов, в значительной мере рассматриваются на работах по искусственному интеллекту.
Короче говоря, теории, новые идеи, и разработки искусственного интеллекта
неизменно привлекают внимание тех, кто стремится расширить области применения и
возможности компьютеров, сделать их более "дружелюбными" то есть
более похожими на разумных помощников и активных советчиков, чем те педантичные
и туповатые электронные рабы, какими они всегда были.
Несмотря на многообещающие перспективы, ни
одну из разработанных до сих пор программ искусственного интеллекта нельзя назвать
"разумной" в обычном понимании этого слова. Это объясняется тем, что
все они узко специализированы; самые сложные экспертные системы по своим возможностям
скорее напоминают дрессированных или механических кукол, нежели человека с его
гибким умом и широким кругозором. Даже среди исследователей искусственного
интеллекта теперь многие сомневаются, что большинство подобных изделий принесет
существенную пользу. Немало критиков искусственного интеллекта считают, что
такого рода ограничения вообще непреодолимы.
К числу таких скептиков относится и
Хьюберт Дрейфус, профессор философии Калифорнийского университета в Беркли. С
его точки зрения, истинный разум невозможно отделить от его человеческой
основы, заключенной в человеческом организме. "Цифровой компьютер - не
человек, - говорит Дрейфус. - У компьютера нет ни тела, ни эмоций, ни
потребностей. Он лишен социальной ориентации, которая приобретается жизнью в
обществе, а именно она делает поведение разумным. Я не хочу сказать, что
компьютеры не могут быть разумными. Но цифровые компьютеры, запрограммированные
фактами и правилами из нашей, человеческой, жизни, действительно не могут стать
разумными. Поэтому искусственный интеллект в том виде, как мы его представляем,
невозможен".
В это же время ученые стали понимать, что создателям
вычислительных машин есть чему поучиться у биологии. Среди них был
нейрофизиолог и поэт-любитель Уоррен Маккалох, обладавший философским складом
ума и широким кругом интересов. В 1942 г. Маккалох, участвуя в научной
конференции в Нью-Йорке, услышал доклад одного из сотрудников Винера о механизмах
обратной связи в биологии. Высказанные в докладе идеи перекликались с
собственными идеями Маккалоха относительно работы головного мозга. В течении
следующего года Маккалох в соавторстве со своим 18-летним протеже, блестящим
математиком Уолтером Питтсом, разработал теорию деятельности головного мозга.
Эта теория и являлась той основой, на которой сформировалось широко
распространенное мнение, что функции компьютера и мозга в значительной мере сходны.
Исходя отчасти из предшествующих исследований
нейронов (основных активных клеток, составляющих нервную систему животных),
проведенных Маккаллохом, они с Питтсом выдвинули гипотезу, что нейроны можно
упрощенно рассматривать как устройства, оперирующие двоичными числами. В 30-е
годы XX в. пионеры информатики, в особенности американский ученый Клод Шеннон,
поняли, что двоичные единица и нуль вполне соответствуют двум состояниям
электрической цепи (включено-выключено), поэтому двоичная система идеально
подходит для электронно-вычислительных устройств. Маккалох и Питтс предложили
конструкцию сети из электронных "нейронов" и показали, что подобная
сеть может выполнять практически любые вообразимые числовые или логические
операции. Далее они предположили, что такая сеть в состоянии также обучаться,
распознавать образы, обобщать, т.е. она обладает всеми чертами интеллекта.
Теории Маккаллоха-Питтса в сочетании с книгами
Винера вызвали огромный интерес к разумным машинам. В 40-60-е годы все больше
кибернетиков из университетов и частных фирм запирались в лабораториях и
мастерских, напряженно работая над теорией функционирования мозга и методично
припаивая электронные компоненты моделей нейронов.
Из этого кибернетического, или
нейромодельного, подхода к машинному разуму скоро сформировался так называемый
"восходящий метод" - движение от простых аналогов нервной системы
примитивных существ, обладающих малым числом нейронов, к сложнейшей нервной
системе человека и даже выше. Конечная цель виделась в создании
"адаптивной сети", "самоорганизующейся системы" или
"обучающейся машины" - все эти названия разные исследователи
использовали для обозначения устройств, способных следить за окружающей обстановкой
и с помощью обратной связи изменять свое поведение, т.е. вести себя так же как
живые организмы. Естественно, отнюдь не во всех случаях возможна аналогия с
живыми организмами. Как однажды заметили Уоррен Маккаллох и его сотрудник Майкл
Арбиб, "если по весне вам захотелось обзавестись возлюбленной, не стоит
брать амебу и ждать пока она эволюционирует".
Но дело здесь не только во времени.
Основной трудностью, с которой столкнулся "восходящий метод" на заре
своего существования, была высокая стоимость электронных элементов. Слишком
дорогой оказывалась даже модель нервной системы муравья, состоящая из 20 тыс.
нейронов, не говоря уже о нервной системе человека, включающей около 100 млрд.
нейронов. Даже самые совершенные кибернетические модели содержали лишь неколько
сотен нейронов. Столь ограниченные возможности обескуражили многих
исследователей того периода.
В
настоящее время наличие сверхпроизводительных микропропроцессоров и дешевизна
электронных компонентов позволяют делать значительные успехи в алгоритмическом моделировании
искусственного интеллекта. Такой подход дает определенные результаты на цифровых
ЭВМ общего назначения и заключается в моделировании процессов жизнедеятельности
и мышления с использованием численных алгоритмов, реализующих искусственный интеллект.
Здесь можно привести много примеров, начиная от простой программы игрушки «тамагочи»
и заканчивая моделями колонии живых организмов и шахматными программами,
способными обыграть известных гроссмейстеров. Сегодня этот подход поддерживается
практически всеми крупнейшими разработчиками аппаратного и программного
обеспечения, поскольку достижения при создании эвристических алгоритмов используются
и в узкоспециальных, прикладных областях при решении сложных задач, принося
значительную прибыль разработчикам.
Другие подходы сводятся к созданию
аппаратуры, специально ориентированной на те или иные задачи, как правило, эти
устройства не общего назначения (аналоговые вычислительные цепи и машины, самоорганизующиеся
системы, перцептроны и т.п.). С учетом дальнейшего развития вычислительной
техники этот подход может оказаться более перспективным, чем предполагалось в
50-80гг.
1)
Дрейфус Х. Чего не могут
вычислительные машины.- М.: Прогресс, 1979.
2)
Винер Н. Кибернетика и
общество.-М: ИЛ, 1979
3)
Компьютер обретает разум.
М., Мир., 1990 В сборнике: Психологические исследования интеллектуальной деятельности.
Под.ред. О.К.Тихомирова.- М., МГУ, 1979
5) Липский В. Комбинаторика для программиста. М.,Мир, 1990.