- •Программирование и алгоритмические языки. Курс за второй семестр. Абстрактные типы данных.
- •Задача о раскраске.
- •Перечисление последовательностей фиксированной длины.
- •Var I:tСтраны; c:tЦвет;
- •Два взгляда на диаграммы – графы и автоматы.
- •Деревья
- •Как сократить перебор с возвратом. Перечисление последовательностей переменной длины
- •Словарный порядок на последовательностях произвольной длины
- •Статическая реализация стеков.
- •Очереди. Статическая реализация.
- •Статическая реализация деревьев.
- •Автоматы как структуры данных
- •Статическая реализация графов. Проблема фрагментации памяти. Списочные структуры.
- •Общая схема реализации автомата как списка.
- •Обработка кучи.
- •Динамическая реализация абстрактных типов ссылками. Ссылочные типы Паскаля.
- •Ссылочные типы Паскаля. Синтаксис типов.
- •Объявление списочной структуры в Паскале.
- •Реализация стеков.
- •Реализация очередей.
- •Основные операции над списками.
- •Обработка деревьев. Деревья выражений.
- •Поиск атома.
- •Различные объединения типов. Записи типов с вариантами.
- •Создание дерева. Перевод из префиксной записи. Представление записи.
- •Анализ алгоритма вычисления. Дерево как последовательность ветвей.
- •Задача синтаксического анализа.
- •Графы-выражения.
- •Раздельное описание абстрактных типов. Модульное программирование.
- •Проблема с кратным использованием модулей.
- •Деревья как структуры данных.
- •Деревья поиска.
- •Поиск в дереве поиска.
- •Включение в дерево поиска.
- •Другие обходы дерева. Обход в ширину.
- •Рекурсивные процедуры и функции. Примеры применения.
- •Поиск в дереве.
- •Проблемы с семантикой рекурсии.
- •Введение в машинно-ориентированное (ссылочное) программирование. Оператор Goto.
- •Создание новых структурных операторов.
- •Формальная семантика goto и неструктурных программ.
- •Мини-Паскаль.
- •Представление сложных типов. Адресная арифметика.
- •Проблемы реализации ввода-вывода. Идея буферизации.
- •Реализация процедур read и write.
- •Реализация структур управления.
- •Путь наверх. Реализация процедур-подпрограмм.
- •Передача параметров.
- •Сохранение и восстановление значений. Соглашение о связях.
- •Введение в теоретическое программирование. Границы программирования. Принципиальная и практическая неразрешимость.
- •О формальной спецификации. Мир задачи как автомат.
- •Процедуры как функции на множестве состояний. Процедуры как преобразователи предикатов.
- •Универсальные методы решения задач.
Универсальные методы решения задач.
Все реально работающие алгоритмы искусственного интеллекта основаны на переборе с возвратом, базирующемся на некотором приоритете (упорядочении) действий по «степени их пригодности» для достижения конечной цели. Алгоритм GPS (General Problem Solve) (конец 50-х гг.) – от приоритета средств к приоритету цели.
Как бы сами решали эту задачу?
Единственный ход рассуждений человека в этом случае – не прямой (от начального состояния к конечному), а обратный. Главная цель – попасть в конечное состояние «банан=у обезьяны». Как можно его достичь?
Единственное действие в нашем мире, меняющее состояние банана – схватить. Если схватить получается (функция схватить определена), то всё ОК, а если нет, то спрашиваем себя: «Почему?!».
Условием хватания является свойство:
(банан=висит) and (обезьянаXY=в середине) and (обезьянаZ=на ящике).
Цель «банан=висит» удовлетворена по условию, то есть главная цель разбивается на две конъюнктивные подцели.
Мы не можем преследовать сразу две цели, попробуем удовлетворить наиболее важную цель – встать на ящик. Какие средства приводят к этой цели?
Это основная идея нисходящей технологии программирования и вариант перебора с возвратом, в котором заранее описываются цепочки, не ведущие в конечное состояние.
Какая дополнительная информация (кроме, собственно, спецификации) неявно использовалась в наших рассуждениях? Ответ: различия в ситуации; точки – приоритет этих различий. Различие состояний определяется по координатам:
D1: положение банана;
D2: Z – положение обезьяны;
D3: XY – положение ящика;
D4: XY – положение обезьяны.
Приоритет: D1>D2>D3>D4.
procedure GPS(s:wState;{начальное состояние}цель: set of wState; var успех:boolean
{спецификация});
begin
with s do if s in цель{цель достигнута: различия между желанным и настоящим состояниями нет} then успех:=true
else
begin
{удалить все различия в порядке важности}
for D:=D1 to Dn do
if S.D<>цель.D then {найти подходящую функцию для удаления
найденного различия}
for p:=p1 to pm {перебираем имена процедур (схватить и т.д.)} do
if s in Dom(p) {область определения} then GPS(s, p-1(цель), успех);
Решение любой задачи можно свести к поиску путей в графе, либо поиску пути в лабиринте. Что помимо перебора с возвратом можно предложить в качестве универсального решателя?
1) Эвристические алгоритмы – перебор правдоподобных решений (мох на стене);
2) Вероятностный алгоритм (бросить монету);
3) Параллельные (распределённые) алгоритмы – предполагают наличие нескольких исполнителей.
Лекции читал: Бухараев Н.Р.
Набрал: Иванов Нияз (гр. 9109).