Читать реферат по информатике, вычислительной технике, телекоммуникациям: "Чего не может компьютер, или Труднорешаемые задачи" Страница 1

(Назад) (Cкачать работу)

11

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

труднорешаемые задачи Студентки группы Л-2-2

Осадчей Ольги Липецк, 1998

СОДЕРЖАНИЕ

О задачах и алгоритмах 3 Эвристические алгоритмы 5 Электронный подход к искусственному интеллекту 5 Другие подходы к искусственному интеллекту 7 Заключение 9 ЛИТЕРАТУРА 11 Машина должна работать,

человек – думать.

Принцип IBM

В среде математиков известна такая притча. В давние времена, когда никто и понятия не имел о компьютерах и их возможностях, один индийский мудрец оказал большую услугу своему правителю. Правитель решил отблагодарить его и предложил ему самому выбрать награду. На что мудрец ответил, что пожелал бы видеть шахматную доску, на каждой клетке которой были бы разложены зернышки пшена в следующем порядке: на первой – 2, на второй – 2х2=4, на третьей – 2х2х2=8, на четвертой 24=16, и так далее на всех клетках.

Сначала правитель обрадовался легкости расплаты. Но вот выполнить обещание не смог, так как он и его слуги вряд ли когда-нибудь смогли бы отсчитать 264 зерен на последнюю клетку, что соответствует примерно 18,4 миллиардам миллиардов (!).

Задача, сформулированная в этой притче, относится к разряду тех, при решении которых самый современный компьютер бессилен так же, как в древности слуги правителя. Зная производительность современных ЭВМ, не представляет труда убедиться в том, что пользователю не хватит всей его жизни для отсчета зерен, но в данном случае это даже не самое главное. Суть проблемы в том, что достаточно незначительно изменить входные данные, чтобы перейти от решаемой задачи к нерешаемой. Каждый человек в зависимости от своих счетных способностей может определить, начиная с какой клетки (пятнадцатой или допустим, восемнадцатой) продолжать отсчитывать зерна для него не имеет смысла. То же самое можно определить и для ЭВМ, для которой подобные характеристики написаны в технической документации.

В случаях, когда незначительное увеличение входных данных задачи ведет к возрастанию количества повторяющихся действий в степенной зависимости, то специалисты по алгоритмизации могут сказать, что мы имеем дело с неполиномиальным алгоритмом, т.е. количество операций возрастает в зависимости от числа входов по закону, близкому к экспоненте ех (е≈2,72; другое название – экспоненциальные алгоритмы).Подобные алгоритмы решения имеет чрезвычайно большой круг задач, особенно комбинаторных проблем, связанных с нахожденим сочетаний, перестановок, размещений каких-либо объектов. Всегда есть соблазн многие задачи решать исчерпыванием, т.е. проверкой всех возможных комбинаций. Например, так решается задача безошибочной игры в шахматы. Эта задача относится к классическим нерешаемым! Ни одна современная ЭВМ не сможет сгенерировать все простые перестановки более чем 12 разных предметов (более 479 млн.), не говоря уже о всех возможных раскладках колоды из 36 игральных карт.

Поэтому труднорешаемой (нерешаемой) задачей можно называть такую задачу, для которой не существует эффективного алгоритма решения. Экспоненциальные алгоритмы решений, в том числе и исчерпывающие, абсолютно неэффективны для

Похожие работы