рефераты

Рефераты

рефераты   Главная
рефераты   Краткое содержание
      произведений
рефераты   Архитектура
рефераты   Астрономия
рефераты   Банковское дело
      и кредитование
рефераты   Безопасность
      жизнедеятельности
рефераты   Биографии
рефераты   Биология
рефераты   Биржевое дело
рефераты   Бухгалтерия и аудит
рефераты   Военное дело
рефераты   География
рефераты   Геодезия
рефераты   Геология
рефераты   Гражданская оборона
рефераты   Животные
рефераты   Здоровье
рефераты   Земельное право
рефераты   Иностранные языки
      лингвистика
рефераты   Искусство
рефераты   Историческая личность
рефераты   История
рефераты   История отечественного
      государства и права
рефераты   История политичиских
      учений
рефераты   История техники
рефераты   Компьютерные сети
рефераты   Компьютеры ЭВМ
рефераты   Криминалистика и
      криминология
рефераты   Культурология
рефераты   Литература
рефераты   Литература языковедение
рефераты   Маркетинг товароведение
      реклама
рефераты   Математика
рефераты   Материаловедение
рефераты   Медицина
рефераты   Медицина здоровье отдых
рефераты   Менеджмент (теория
      управления и организации)
рефераты   Металлургия
рефераты   Москвоведение
рефераты   Музыка
рефераты   Наука и техника
рефераты   Нотариат
рефераты   Общениеэтика семья брак
рефераты   Педагогика
рефераты   Право
рефераты   Программирование
      базы данных
рефераты   Программное обеспечение
рефераты   Промышленность
      сельское хозяйство
рефераты   Психология
рефераты   Радиоэлектроника
      компьютеры
      и перифирийные устройства
рефераты   Реклама
рефераты   Религия
рефераты   Сексология
рефераты   Социология
рефераты   Теория государства и права
рефераты   Технология
рефераты   Физика
рефераты   Физкультура и спорт
рефераты   Философия
рефераты   Финансовое право
рефераты   Химия - рефераты
рефераты   Хозяйственное право
рефераты   Ценный бумаги
рефераты   Экологическое право
рефераты   Экология
рефераты   Экономика
рефераты   Экономика
      предпринимательство
рефераты   Юридическая психология

 
 
 

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

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

РЕФЕРАТ

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

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

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

Бабаева Ю.Д. К вопросу о формализации процесса целеобразования

Брушлинский А.В. Возможен ли "искусственный интеллект"?

Ноткин Л.И. "Искусственный интеллект" и проблемы обучения


© 2011 Рефераты