Курс за второй семестр. Абстрактные типы данных

Вид материала

Содержание

Границы программирования. Принципиальная и практическая неразрешимость.
О формальной спецификации.
Процедуры как функции на множестве состояний.
Задача поиска
Универсальные методы решения задач.

Подобный материал:

1 2 3 4 5 6 7 8

Введение в теоретическое программирование.

Границы программирования. Принципиальная и практическая неразрешимость.

Каковы пределы автоматизации (замены интеллектуальной деятельности «машинной») (точнее программой, написанной другими людьми)? Эти проблемы мы осветили в терминах области машинного моделирования интеллектуальной деятельности, традиционно называемой «искусственный интеллект» (ИИ). Задачи ИИ относят к самым сложным и самым необходимым.

Что такое интеллект? Как минимум – способность решать задачи. Чем умный решатель отличается от глупого? Умному достаточно постановки задачи, спецификации, он сам находит метод решения. Глупый лишь исполняет алгоритм, постановки задачи он может и не знать.

а

лгоритм

ответ

данные

алгоритм

с

пецификация ответ

данные

Языки процедурного программирования, очевидно, рассчитаны на глупого исполнителя и описывают метод, но не спецификацию.

Использование рекурсии вместо циклов даёт языки более высокого уровня, хотя и менее эффективные. Чаще действует «золотое правило»: чем более универсален метод, тем менее эффективен он в каждом частном случае.

Можно ли сделать компьютер более умным?

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

Основная задача ИИ («проба пера») – построить универсальный решатель задач, написать алгоритм, который в качестве входа принимает текст постановки задачи на некотором формальном языке спецификации, а на выходе выдаёт программу её решения на некотором языке программирования. Трактовка задачи корректна.

Язык спецификации Язык программирования

Существуют универсальные языки программирования, например: Паскаль, язык блок-схем, или Ассемблер. Существуют универсальные языки спецификаций.

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

Примеры:

1) Проблема остановки: нельзя написать программу, проверяющую по тексту входящей программы, зацикливается ли она:

а) на заданных значениях;

б) на некоторых значениях.

Либо язык не даёт зацикливаться, либо он неуниверсален.

2) Существуют синтаксические анализаторы, проверяющие по входному тексту программы, является ли она на самом деле выражением данного языка программирования.

Задача написать синтаксический анализатор неразрешима.

а) Написать программу, которая проверяет функциональную эквивалентность двух программ.

б) Написать программу, проверяющую, удовлетворяет ли данная программа заданной спецификации.

Доказательства сложны, но причина тривиальна – все они сводятся к задаче проверки бесконечного числа входов.

Уточним постановку: написать программу, которая по данной спецификации выдаёт решение задачи, либо строку «Нет решений».

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

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

Для каждой ли задачи существует полиномиальное решение? В этом суть знаменитой ПНП-проблемы.

Вернёмся к постановке задачи…

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

Пример моделирования интеллектуальной деятельности – задача «Обезьяна и банан». Содержательная постановка: в комнате находятся обезьяна, ящик и подвешенный к потолку банан. Как обезьяне его достать?

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

А как делают все? Что такое комната-ящик-банан? Как берут ящик?

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

О формальной спецификации.

Мир задачи как автомат.

Вернёмся к фундаментальному понятию типа данных в качестве модели описания статики и динамики произвольных объектов. Статика описывается множеством состояний, а динамика – множеством операторов.

Мир=<состояния, переменные >

Можно воспринимать такую модель как автомат.

Аппликация: состояние x переменные → состояние

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

Процедуры как функции на множестве состояний.

Процедуры как преобразователи предикатов.

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

Найти процедуру P такую, что:

{а – произвольный массив}={a=A₀ & A₀

[1..10]real}

P

{a – упорядоченный массив}={a=A₁ & i1..9 a[i]a[i+1]}& перестановка (A₀,A₁)

i1..10 (A₁[i]A₀) & j1..10 (A₀[j]A₁)

Постановка спецификации есть функция на множествах состояний. Решение есть процедура, то есть функция на состояние.

Задача поиска. Задан массив…

{a=ANreal} & xReal;

P-?

{xi : x=A[i]}

Любая P, удовлетворяющая этому свойству (находящая значение i с заданным свойством), будет решением.

Вернёмся к нашим обезьянам…

Мир задачи в этом случае описывается в терминах состояния каждого объекта относительно других:

1) Состояние обезьяны относительно комнаты.

Содержательное описание:

- имя переменной: обезьяна ХУ;

- множество значений: {у двери, у окна, в середине}

2) Обезьяна относительно ящика:

- имя переменной: обезьяна Z;

- множество состояний: {на ящике, на полу}

3) Ящик относительно комнаты:

- имя переменной: ящик ХУ;

- множество состояний: {совпадает с множеством значений обезьяна ХУ}

4) Банан относительно обезьяны:

- имя переменной: банан;

- множество значений: {висит, у обезьяны}

Состояние мира задачи определяется совокупностью состояний отдельных объектов, значениями переменных, соответствующих объектам.

Мир в этом случае – 4 переменные:

1) Обезьяна ХУ  {у двери, у окна, в середине};

2) Обезьяна Z  {на ящике, на полу};

3) Ящик ХУ  {у двери, у окна, в середине};

4) Банан  {висит, у обезьяны}.

Множество состояний – именованное декартово произведение.

Множество исходных состояний: любое состояние мира, в кот. мир(банан)=висит.

Множество конечных состояний: любое состояние, в кот. мир(банан)=у обезьяны.

Определение задачи заканчивается определением допустимых действий, процедур преобразования состояний.

type wState=record

ОбезьянаХY: tОбезьянаХY;

ОбезьянаZ: tОбезьянаZ;

ЯщикXY: tЯщикХY;

Банан: tБанан;

end;

procedure Схватить(var s:wState);

begin

with s do

if (банан=висит) and (обезьянаXY=середина) and (обезьянаZ=на ящике)

then банан:=у обезьяны;

end;

procedure Залезть(var s:wState);

begin

with s do

if ящикXY=обезьянаXY…

procedure Подвинуть(var s:wState; p1,p2:tОбезьяна);

{Подвинуть ящик из точки p1 в точку p2}

{Очевидно, соответствует более компактному описанию семейства функций}

begin

with s do

begin

if (ящикXY=обезьянаXY) and (обезьянаXY=p1) then

begin

обезьянаXY:=p2;

ящикXY:=p2;

end;

end;

procedure Перейти(var s:wState; p1,p2:обезьянаXY);

{Обезьяна переходить из точки p1 в точку p2}

begin

with s do

if обезьянаXY=p1 then обезьянаXY:=p2;

end;

1) Строго говоря, мы хотим, чтобы спецификация состояний и процедур была не частью программы, но входными данными.

2) Как решать задачу?

Входом должна быть последовательность обращения к процедурам.

Универсальные методы решения задач.

Все реально работающие алгоритмы искусственного интеллекта основаны на переборе с возвратом, базирующемся на некотором приоритете (упорядочении) действий по «степени их пригодности» для достижения конечной цели. Алгоритм GPS (General Problem Solve) (конец 50-х гг.) – от приоритета средств к приоритету цели.

Как бы сами решали эту задачу?

Единственный ход рассуждений человека в этом случае – не прямой (от начального состояния к конечному), а обратный. Главная цель – попасть в конечное состояние «банан=у обезьяны». Как можно его достичь?

Единственное действие в нашем мире, меняющее состояние банана – схватить. Если схватить получается (функция схватить определена), то всё ОК, а если нет, то спрашиваем себя: «Почему?!».

Условием хватания является свойство:

(банан=висит) and (обезьянаXY=в середине) and (обезьянаZ=на ящике).

Цель «банан=висит» удовлетворена по условию, то есть главная цель разбивается на две конъюнктивные подцели.

Мы не можем преследовать сразу две цели, попробуем удовлетворить наиболее важную цель – встать на ящик. Какие средства приводят к этой цели?

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

Какая дополнительная информация (кроме, собственно, спецификации) неявно использовалась в наших рассуждениях? Ответ: различия в ситуации; точки – приоритет этих различий. Различие состояний определяется по координатам:

D1: положение банана;

D2: Z – положение обезьяны;

D3: XY – положение ящика;

D4: XY – положение обезьяны.

Приоритет: D1>D2>D3>D4.

Procedure GPS(s:tState;{начальное состояние}цель: set of wState; var успех:boolean

{спецификация});

begin

with s do if s in цель{цель достигнута: различия между желанным и настоящим состояниями нет} then успех:=true

else

begin

{удалить все различия в порядке важности}

for D:=D₁ to D_n do

if S.D<>цель.D then {найти подходящую функцию для удаления

найденного различия}

for p:=p₁ to p_m {перебираем имена процедур (схватить и т.д.)} do

if s in Dom(p) {область определения} then GPS(s, p^-1(цель), успех);

Решение любой задачи можно свести к поиску путей в графе, либо поиску пути в лабиринте. Что помимо перебора с возвратом можно предложить в качестве универсального решателя?

1) Эвристические алгоритмы – перебор правдоподобных решений (мох на стене);

2) Вероятностный алгоритм (бросить монету);

3) Параллельные (распределённые) алгоритмы – предполагают наличие нескольких исполнителей.

Лекции читал: Бухараев Н.Р.

P.S. Вот, наконец-то, закончилась пытка под названием «набор лекций».

Надеюсь, что Читатель был доволен качеством выполненной работы.

К экзамену лучше всего готовиться именно по лекциям, ибо, как скромно сказал Наиль Раисович: «Лучшего нигде не найдёте!»

Желаю всем удачи на экзамене!

Blog

Курс за второй семестр. Абстрактные типы данных

Содержание