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

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

РЕФЕРАТ

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

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

Студентки группы Л-2-2

Осадчей Ольги

Липецк,1998

СОДЕРЖАНИЕ

TOC o «1-3» Озадачах и алгоритмах… PAGEREF _Toc418235221h 3

Эвристические алгоритмы… PAGEREF _Toc418235222h 5

Электронный подход к искусственному интеллекту… PAGEREF _Toc418235223h 5

Другие подходы к искусственному интеллекту… PAGEREF _Toc418235224h 7

Заключение… PAGEREF _Toc418235225h 9

ЛИТЕРАТУРА… PAGEREF _Toc418235226h 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)

5)

еще рефераты

Еще работы по компьютерам и переферийным устройствам

Реферат по компьютерам и переферийным устройствам

Устройство ПЭВМ фирмы IBM. Периферийное оборудование. Назначение и история создания ПЭВМ

29 Августа 2013

Реферат по компьютерам и переферийным устройствам

Суперкомпьютеры

29 Августа 2013

Реферат по компьютерам и переферийным устройствам

Современное поколение персональных компьютеров

29 Августа 2013

Реферат по компьютерам и переферийным устройствам

Средства мультимедиа

29 Августа 2013