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

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

РЕФЕРАТ

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

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

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