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