Программирование и комп-ры

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

      Липецкий государственный педагогический институт



                                   РЕФЕРАТ

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



                                                      Студентки группы Л-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.


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