Программирование и комп-ры : Чего не может компьютер, или Труднорешаемые задачи
Чего не может компьютер, или Труднорешаемые задачи
Липецкий государственный педагогический институт
РЕФЕРАТ
Тема: Чего не может компьютер, или
труднорешаемые задачи
Студентки группы Л-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.
Липский В. Комбинаторика для программиста. М.,Мир, 1990.
|
