 |
НАУЧНАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Чего не может компьютер или Труднорешаемые задачи
Чего не может компьютер или Труднорешаемые задачи
Липецкий государственный педагогический институт
РЕФЕРАТ
Тема: Чего не может компьютер, или
труднорешаемые задачи
Студентки группы Л-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.
| |
|
|
