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

Липецкий государственный педагогический институт , -2-2 Липецк, 1998 СОДЕРЖАНИЕ О задачах и алгоритмах 3 Эвристические алгоритмы 5 Электронный подход к искусственному интеллекту 5 Другие подходы к искусственному интеллекту 7 Заключение 9 ЛИТЕРАТУРА 10 Машина должна работать, человек думать. Принцип IBM О задачах и алгоритмах В среде математиков известна такая притча. В давние времена, когда никто и понятия не имел о компьютерах и их возможностях, один индийский мудрец оказал большую услугу своему правителю.

Правитель решил отблагодарить его и предложил ему самому выбрать награду. На что мудрец ответил, что пожелал бы видеть шахматную доску, на каждой клетке которой были бы разложены зернышки пшена в следующем порядке на первой 2, на второй 2х24, на третьей 2х2х28, на четвертой 2416, и так далее на всех клетках. Сначала правитель обрадовался легкости расплаты. Но вот выполнить обещание не смог, так как он и его слуги вряд ли когда-нибудь смогли бы отсчитать 264 зерен на последнюю клетку, что соответствует примерно 18,4 миллиардам миллиардов. Задача, сформулированная в этой притче, относится к разряду тех, при решении которых самый современный компьютер бессилен так же, как в древности слуги правителя.

Зная производительность современных ЭВМ, не представляет труда убедиться в том, что пользователю не хватит всей его жизни для отсчета зерен, но в данном случае это даже не самое главное.

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

Подобные алгоритмы решения имеет чрезвычайно большой круг задач, особенно комбинаторных проблем, связанных с нахожденим сочетаний, перестановок, размещений каких-либо объектов.

Всегда есть соблазн многие задачи решать исчерпыванием, т.е. проверкой всех возможных комбинаций. Например, так решается задача безошибочной игры в шахматы. Эта задача относится к классическим нерешаемым Ни одна современная ЭВМ не сможет сгенерировать все простые перестановки более чем 12 разных предметов более 479 млн не говоря уже о всех возможных раскладках колоды из 36 игральных карт. Поэтому труднорешаемой нерешаемой задачей можно называть такую задачу, для которой не существует эффективного алгоритма решения.

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

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

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

Эвристические алгоритмы

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

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

Исторически попытки моделирования процессов мышления для достижения ан... Интересы другой группы лежат в области техники они стремятся расширить... Многие ныне обычные разработки, в том числе усовершенствованные систем... Несмотря на многообещающие перспективы, ни одну из разработанных до си... Даже среди исследователей искусственного интеллекта теперь многие сомн...

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

Столь ограниченные возможности обескуражили многих исследователей того... Но дело здесь не только во времени. Высказанные в докладе идеи перекликались с собственными идеями Маккало... В 40-60-е годы все больше кибернетиков из университетов и частных фирм... Из этого кибернетического, или нейромодельного, подхода к машинному ра...

Заключение

Заключение В настоящее время наличие сверхпроизводительных микропропроцессоров и дешевизна электронных компонентов позволяют делать значительные успехи в алгоритмическом моделировании искусственного интеллекта.

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

Другие подходы сводятся к созданию аппаратуры, специально ориентированной на те или иные задачи, как правило, эти устройства не общего назначения аналоговые вычислительные цепи и машины, самоорганизующиеся системы, перцептроны и т.п С учетом дальнейшего развития вычислительной техники этот подход может оказаться более перспективным, чем предполагалось в 50-80гг.

ЛИТЕРАТУРА

ЛИТЕРАТУРА 1 Дрейфус Х. Чего не могут вычислительные машины М. Прогресс, 1979. 2 Винер Н. Кибернетика и общество М ИЛ, 1979 3 Компьютер обретает разум.

М Мир 1990 В сборнике Психологические исследования интеллектуальной деятельности. Под.ред. О.К.Тихомирова М МГУ, 1979 4 Пекелис В. Кибернетика от А до Я. М 1990. 5 Липский В. Комбинаторика для программиста.

М Мир, 1990.