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

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

РЕФЕРАТ

Тема: Чего не может компьютер, или

труднорешаемые задачи

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