Ответы по СИИ

Вопросы по курсам

«Системы искусственного интеллекта» и

«Интеллектуальные информационные системы»

1. Генетические алгоритмы (основные понятия и определения, операторы ГА).

2. Знания и данные. Представления знаний (логические модели).

3. Знания и данные. Представления знаний (продукционные модели).

4. Знания и данные. Представления знаний (сетевые модели).

5. Знания и данные. Представления знаний (фреймовые модели).

6. ИИ в играх и творчестве.

7. Искусственная жизнь.

8. Искусственные нейронные сети (основные понятия и определения, виды НС, область применения).

9. Искусственные нейронные сети: алгоритмы обучения (алгоритм обратного распространения ошибки).

10. Искусственные нейронные сети: алгоритмы обучения (алгоритм обучения по дельта-правилу).

11. Исследователи ИИ: А. А Ляпунов, В.М. Глушков.

12. Исследователи ИИ: А. Тьюринг.

13. Исследователи ИИ: Д. А. Поспелов, Г. С. Поспелов.

14. Исследователи ИИ: М. Минский, Ф. Розенблатт.

15. Компьютеры V, VI поколения.

16. Многоагентные системы.

17. Нейронная сеть Кохонена.

18. Нейронная сеть Хемминга.

19. Нейронная сеть Хопфилда.

20. Основные направления исследований в ИИ.

21. Роботы: I , II, III поколение.

22. Системы ИИ. Историческая справка.

23. Системы поддержки принятия решений (определение, назначение структура, область применения).

24. Теория нечетких множеств (нечеткие отношения).

25. Теория нечетких множеств (основные понятия и определения, операции над множествами).

26. Теория нечетких множеств (понятие лингвистической переменной, нечеткие высказывания).

27. Эвристическое программирование.

28. Экспертные системы (классификация, проектирование и разработка).

29. Экспертные системы (определение, назначение, структура, область применения).

30. Языки искусственного интеллекта: Prolog, Рефал, LISP.

1. Различные подходы к определению понятия «искусственный интеллект» Искусственный интеллект – св-во автоматических систем брать на себя отдельные функции человека. 4 подхода: 1)думают подобно людям; 2)думают рационально; 3)действуют подобно людям; 4)действуют рационально. Осн. черты интеллектуальной деятельности - способности к: 1)обучению, 2)обобщению; 3)накоплению опыта(знаний и навыков); 4)адаптации к изменяющимся условиям.	2.Системы ИИ. Историческая справка. 1)Начальные работы – Ньюсли, Саймон, Шоу -1956 г.,программа «Логик-теоретик», «Общ.решатель задач» (головоломки, интегралы). 2)Шеннон,Тьюринг – конец 1950-. яз. ИПЛ1, далее ЛИСП ;А.Самуэль – программа игры в шашки -1962–победа в турнире; «Каисса»-СССР 1974 победа на шахматном турнире. Действуя по оценочным ф-циям, накапливала опыт, меняя коэф. в оценочных ф-циях.При созд. игровых программ применялся метод эвристики – выбора в усл. неопределённости. Конец 60х – Д.Маккарти –доказательство теорем, исчисление предикатов 1 порядка. 3)Персептрон -1957 г. – модель зрит. нервной системы (Френк Розенбладт). Решает только огр. задачи классификации. 4) работа с текстом на естеств. языках. 5)экспертные системы -70-е гг. Метод построения: 1) логический вывод; 2)немонотонные логики (с появлением новых фактов может меняться истинность старых);3) накопление знаний по голосованию за и против фактов. К.Грин – вопросо-ответная система. 6)Робототехника – эл-ты интеллекта служат прежде всего для организации целенапр. движений; +восприятие окр. среды с помощью иск. органов чувств. 7)нейронные сети – прогнозир.; шифрование; распознавание; В дальнейшем появились многосл. нейронный сети. 8)Агент – всё, что действует: способность автономно работать; восприн. свою среду; существовать в теч. длит. времени; адапт. к изменениям. Рац. агент – чтобы можно былодостичь наил. результата.	3.Области применения ИИ. 1)Восприятие и распознавание образов – получение исх.данных от органов восприятия. С этим лучше всего справляются нейронные сети. 2)Математика и автоматическое доказательство теорем – теория доказательств. Применяется в робототехнике, поиске информации и базах данных. 3)Игры. – шашки, шахматы и др. игры, где нет однозначного алгоритма выигрыша. 4)Экспертные системы - В некоторых слабо формализ. областях системы иск. инт. явл. единств. возможностью заменить человека компьютерной программой. 5) Понимание естественного языка. - Анализ и генерация текстов, выявление знаний, необходимых для понимания текстов, т.е. знаний синтаксических, прагматических и семантических, модели нечёткой логики. 6)Управление динамическими объектами. – задача может быть решена с помощью нейронных сетей и нечёткой логики. 7)Получение новых знаний. – задача обучения нейронных сетей без учителя.	4.Области применения ИИ. Экспертные системы ЭС- это набор программ, выполняющий ф-ции эксперта при решении задач из некоторой предметной области. Экспертная система состоит из базы знаний (части системы, в которой содержатся факты), подсистемы вывода (множества правил, по которым осуществляется решение задачи), подсистемы объяснения(пользователь должен иметь возможность узнать, почему было получено решение), подсистемы приобретения знаний(возможность обучения и развития) и диалогового процессора (интерфейс пользователя). Для функционирования экспертной системы сначала формируются эвристики (правила, записанные на естественном языке), затем они записываются в форме правил (предложений, построенных по схеме «если..то»), потом переписать правила в виде предикатов истинности. Теперь можно задавать экспертной системе вопросы, и она будет на них отвечать, используя механизм логического вывода.	5.Области применения ИИ. Системы машинного зрения. Система машинного зрения состоит из камеры, платы захвата ввода изображения и блока анализа (программные средства). Изображение с камеры поступает на плату ввода, затем анализируется и в результате система машинного зрения принимает решение, что делать. Часто системы машинного зрения применяются в промышленном контроле качества продукции: напр. если внешний вид продукта не соответствует стандарту, конвейер останавливается. Создание систем машинного зрения достаточно трудоемко и технически сложно, так как требуется объединить решение задач, связанных с извлечением информации из поступающих с необходимой скоростью и качеством изображений (задача технического зрения) и с высокой точностью принять решение, т.е. разработать компоненты, отвечающие за техническое зрение и принятие решений, и объединить их единую в систему..
6. Области применения ИИ. Системы понимания естественного языка. Бывают 2 типов: основанные на 1.правилах и 2.примерах. В первых лучше проработаны правила и грамматика. Системы, основанные на примерах – самообучающиеся, могут выводить правила, исходя из конкретных примеров. В любом случае такие системы используют словари и правила работы со словарями + учёт семантических (смысловых) связей между словами, когда любое слово включается в граф как запись со следующей структурой: <I, C1…Cn, G> где I-информационная единица(слово, знак препинания или устойчивое выражение): С – связи этой единицы с другими единицами –вершинами графа G.	7.Представление знаний. Логические модели. Представление знаний – это их описание в доступной форме. их черты: 1)внутренняя интерпретируемость – каждая инф.единица должна иметь уникальное имя, по кот. ИС находит её и отвечает на запросы, в кот. это имя упомянуто. 2)структурированность. (иерархическая или люб. др. организация); 3)связность (связи отражают отношения м/у инф. един. в ИС должна быть возможность устранения связи м/у инф. един.). Возможны след. отн.: а)совместимость; б)аргумент-функция; в)причина-следствие; г)релевалентность(ситуационная близость); 4)активность(выполнение программ в ИС может инициализироваться текущим состоянием инф. базы) Выполнение программ может вкл. в себя добавление новых эл-тов и связей. Формальная(логическая) модель представления знаний – плюсы: в основе лежит строгая математическая теория; основная операция – логический вывод; минусы: закрытость, жесткость. Осн. мн-ва: 1)В – мн-во базовых эл-тов 2)Р - мн-во синтаксических правил; 3)А – мн-во аксиом; 4)V – мн-во правил вывода.	8.Представление знаний. Продукционные модели. Продукционные модели представления знаний состоят из правил вывода конечного результата – продукций. Применяется следующая схема: i: Q,P,AB;N где i- имя продукции. Q – сфера применения. Р – условие выполнения ядра. АB – ядро продукции. N – действие постусловия(что произойдёт после выполнения ядра). Р может выступать как функция вероятности того, что из А последует В. Можно ввести в модель ядро АB,C. Тогда из значения Р прогнозируется результат: В или С? Выбор правила для данной конкретной ситуации происходит в 2 этапа: 1)Включение метаправил (правил вывода правил); 2)распределение всех продукций по категориям; 3)отсеивание ненужных продукций. Плюсы продукционных моделей – простота обслуживания и модернизации.	9.Представление знаний. Сетевые модели. Сетевая модель представляет собой семантическую сеть, состоящую из объектов, событий и связей между ними. Эти элементы объединяются в граф. При этом каждый эл-т можно представить в след. виде: <I, C1…Cn, G> где I-информационная единица(слово, знак препинания или устойчивое выражение): С – связи этой единицы с другими единицами –вершинами графа G. Связи определяют тип отношения м/у 2 единицами – напр. «подмножество», «начало», «конец». Семантические сети часто применяются для переводов с естественных языков. При этом используются отношения, например: Сети бывают 2 видов: статические и динамические (сценарии) – в последних узлы являются событиями.	10.Представление знаний. Фреймовые модели. Фрейм – структура, состоящая из заголовка, имён слотов и их значений. Применяется для описания типовых ситуаций. Различают фрейм-прототип и фрейм-экземпляр. Первый является описанием класса фреймов, а второй – его конкретной реализацией. Например: фрейм-прототип – название: работник; название слотов: фамилия, имя, должность; фрейм-экземпляр: значения слотов: Иванов, Сергей, слесарь. Значениями слота могут быть: тексты, математические отношения, ссылки на другие фреймы, набор слотов более низкого уровня. При этом возможно создавать новые фреймы на основе предыдущих, добавляя новые слоты и наследуя имеющиеся от фрейма более высокого уровня.

11. Формальные системы (определение, формальное доказательство)

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

Нельзя заменять слова-связки: ЕСЛИ, СЛЕДОВАТЕЛЬНО.

Заданная формальная система – если:

• задан конечный алфавит,

• определена процедура построения формул формулой системы,

• определено некоторое множество формул – аксиомы,

• задано конечное множество правил вывода, которое позволяет получать из некоторого конечного множества формул другое множество формул.

Формальное доказательство – конечная последовательность формул, каждая из которых является аксиомой или получена из предыдущей формулы.

Формула называется теоремой, если существует доказательство, в котором она является последней.

Правила:

1. постановки

2. продукционные

1)x<y и y<z -> x<z – продукционное.

2)x – x -> 0 – правило подстановки(переписывания).

1) {a,b,[]} – символы.

2) Любая цепочка из этих символов – формула.

3) a[]a – аксиома.

4) с1[]c2 -> c1b[]c2b – правило вывода.

5) теорема – ba[]ba, bba[]bba.

6) не теорема – baba[]baab.

12. Формальные системы. Разрешимость и интерпретация.

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

Интерпретация – распространение положений какой-либо формальной системы на реальный мир. Между символом формальной системы и объектом реального мира устанавливается взаимнооднозначное соответствие.

ТИ НТИ	ТЛ Нет Л
a <-> 0 b <-> [] <-> =	Аксиомы: 0=0 ba[]ba 1=1 bba[]bba 2=2
a <-> … [] <-> = b <-> ¬ bba[]a – ИТ

13. Формальные системы. Алгоритмы унификации.

H -> C

E

(a+b)² -> a²+2ab+b²;

Sin²x+cos²x -> 1;

Sin²3a+cos²a – нельзя унифицировать.

• Выражение Е и гипотезу Н рассматриваем на одну и ту же глубину.

• Выполняются только те подстановки, которые необходимы.

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

• Можно замещать только свободные переменные.

• Если мы заменяем Х термом, то этот терм не может содержать переменную Х.

• Нельзя замещать операторы и константы, они должны находиться в Е и Н на аналогичных позициях, иначе невозможна унификация.

• Выражения Е и Н представляются в виде дерева.

• Этот алгоритм распространяется и на Н₁, Н₂, Н₃ … -> C.

x-x -> 0 0 -> x-x	Оставлять только одно, чтобы доказательство не зацикливалось.
x^4y^3z^2 y^3z^2x^4	Выражение записывается по убывающей степени.

Пример:

1) p^q -> q^p;

2) p^(q^r) -> (p^q)^r;

3) p^(pЭq) -> q;

4) ¬q^(pЭq) -> ¬p;

5) ¬¬p -> p;

6) p -> ¬¬p.

Доказать что (sЭ¬t)^t -> ¬s.

Д-во:

14. Алгоритмы унификации. Принцип резолюций.

Впервые был описан Робинсоном в 1965 г. Вместо многих правил вывода системы автоматического доказательства теорем используют единственное – принцип резолюций. Пусть имеются выражения U и С, такие, что U=(U₁,U₂…), C=(C₁,C₂,…) и U_i=¬(не)С_i. Тогда U’=U¬U_i,С’=C¬C_i и £= U' & ф' – резольвента шага резолюции. Основная компонента систем автоматического доказательства теорем – система опровержения резолюций: Для того чтобы доказать, что р следует из некоторого описания состояния (или теории) Т, нужно положить —р и попытаться доказать, что из этого предположения следует утверждение, противоречащее Т. Если это удастся сделать, то тем самым подтверждается утверждение р, а в противном случае оно опровергается. Основная операция сопоставления в доказательстве теорем с помощью резолюций называется унификацией. Например, выражения БЕЖИТ_БЫСТРЕЕ_ЧЕМ(Х, улитка) и БЕЖИТ_БЫСТРЕЕ _ЧЕМ (черепаха, Y) превращаются в идентичные при подстановке {Х=черепаха, Y=улитка}. Такая подстановка называется унификатором. Цель алгоритма - отыскать наиболее общую подстановку такого рода.

15. Классификация задач по мере сложности.

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

Самые хорошие алгоритмы – линейные.

Класс полиноминальных алгоритмов – сложность представляет полином некоторой степени, зависящих от входных данных. (Сортировки, эйлеровый цикл, обнаружение в тексте слова длины n, алгоритм Декстера).

Проверка планарности графов – ее сложность составляет n^c. В 70-х гг. разработаны алгоритмы для n², n^log, n^m.

Экспоненциальная задача – fⁿ, где f – константа или полином от n переменных. К этому классу относятся задачи – нужно построить все подмножества заданного множества, задача распознания всех возможностей, написанных на разных языках.

Решение систем уравнений в целых числах – цикл Гамильтона, составление расписаний, оптимальная загрузка емкости. Эти задачи решаются перебором, сначала перебираются решения, которые могут быть реальными алгоритмами для этих задач. Механизм с помощью машины Тьюринга + еще одна функция «выбор» - создает столько копий текущих состояний, сколько…

Для всех перечисленных задач была доказана их эквивалентность: если мы решаем одну из них, то мы можем автоматически решить и другие: недетерминированные задачи – автомат, который выполняет «+», «-», читать информацию, записывать информацию, «и», «или», «если то», повторение.

16. Стратегии решения задач. Поиск в глубину.

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

Алгоритм перебора в глубину:

1) Раскрывается начальная вершина, соответствующая начальному состоянию.

2) Раскрывается первая вершина, получаемая в результате раскрытия начальной. Ставится указатель.

3) Если она раскрывается, то следующей будет раскрываться вновь порожденная вершина. Если вершина не раскрывается, то процесс возвращается в предыдущую вершину.

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

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

17. Стратегии решения задач. Поиск в ширину.

Вершины раскрываются в том порядке, в котором они строются. Основной алгоритм состоит в выполнении следующих действий:

1) Начальная вершина раскрывается до тех пор, пока ее можно раскрыть, применяя один и тот же (или разные, смотря по условию) оператор. При этом образуются вершины первого уровня s2, s3, s4. Они раскрываются, образуя в свою очередь вершины второго уровня и т.д.

2) Расставляются указатели, ведущие от новых вершин к корню.

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

Полный перебор в ширину гарантирует нахождение целевой вершины как раз потому, что перебор полный. Путей достижения цели, вообще говоря, может быть много. В этом случае имеется возможность выбрать наикратчайший (самый дешевый\легкий\быстрый и т.п.) путь. Но может быть случай, когда граф поиска окажется бесконечным, и тогда этот алгоритм никогда не кончит свою работу. Имеется класс задач, для которых этот метод эффективен. Классическим примером является задача «лабиринтного поиска», впервые решенная К.Шенноном. Здесь пространство различных вариантов действия невелико: «повернуть направо», «налево», «вперед» и решение обычно лежит на некоторой заданной (обычно небольшой) глубине.

18. Представление задач в виде И\ИЛИ графов. Базовые процедуры поиска в И\ИЛИ графах.

И/ИЛИ-граф - это направленный граф, вершины которого соответствуют задачам, а дуги отношениям между задачами.

И/ИЛИ-представление основано на философии сведения задач к подзадачам.

Вершины И/ИЛИ-графа соответствуют задачам. связи между вершинами - отношениям между задачами.

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

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

При заданном И/ИЛИ-графе конкретная задача специфицируется заданием стартовой вершины и целевого условия для распознавания целевых вершин.

Целевые вершины соответствуют тривиальным задачам.

Решение представляется в виде решающего графа - подграфа всего И/ИЛИ-графа.

Представление задач в форме пространства состояний можно рассматривать как специальный частный случай И/ИЛИ-представления, когда все вершины И/ИЛИ-графа являются ИЛИ-вершинами.

И/ИЛИ-представление имеет преимущество в том случае, когда вершинами, находящимися в отношении И, представлены подзадачи, которые можно решать независимо друг от друга. Критерий независимости можно несколько ослабить, а именно потребовать, чтобы существовал такой порядок решения И-задач, при кото­ром решение более «ранних» подзадач не разрушалось бы при решении более «поздних» подзадач.

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

Простейший способ организовать поиск в И/ИЛИ-графах средствами Пролога - это использовать переборный механизм, заложенный в самой пролог-системе. Пролог-система производит поиск в глубину в дереве и проходит через все вершины подграфа.

19. Эвристический поиск.

Этап 1. Выбрать из множества возможных действий некоторое.

Этап 2. Осуществить выбранное действие и изменить текущую ситуацию.

Этап 3. Оценить ситуацию.

Этап 4. Отбросить бесполезные ситуации.

Этап 5. Если достигнута конечная ситуация—конец; если нет, выбрать новую исходную ситуацию и начать сначала.

Методы эвристического поиска:

1)• с учетом соответствия цели:

- уменьшение некоторого нежелательного различия,

- непосредственное решение той или иной подзадачи;

• с учетом опыта: повторение прошлого, обнаружение ключевого действия;

• с учетом необходимых условий:

- решение, обусловленное анализом ситуации,

- исключение неосуществимого варианта;

- с учетом фактора случайности:

- предпочтение отдается разнообразию.

3)• по аналогии: известна сама задача, известна подзадача;

• по величине расстояния до цели:

— расстояние между двумя ситуациями,

— количество усилий, затрачиваемых на поиск;

• по математическому критерию:

— составление перечня необходимых и/или достаточных для получения данного решения характеристик,

— численная оценочная функция, верхние и нижние границы,

— сумма стоимостей, выбранных подходящим способом;

• по ожидаемому выигрышу (критерий, связанный с прошлым опытом):

— простота ситуации, коэффициент расширения поиска,

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

• двигаться только вперед:

— систематическое развитие последней порожденной ситуации;

• выполнять все действия параллельно:

— поочередное выполнение всех действий;

в качестве исходной выбирать самую многообещающую ситуацию:

— в отношении оценочной функции,

— в отношении незначительного числа входящих в нее действий;

• идти на компромисс между:

— глубиной поиска, оценкой ситуации.

20. Метод ветвей и границ.

Метод ветвей и границ — метод решения переборных задач.

В основе этого метода лежит идея последовательного разбиения множества допустимых решений на подмножества (стратегия «разделяй и властвуй»). Метод ветвей и границ — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. Метод был сначала предложен A. H. Land и A. G. Doig в 1960 г. для решения задач целочисленного линейного программирования.

Общая идея метода может быть описана на примере нахождения решения задачи минимизации функции f(x) по множеству допустимых решений x. Как f, так и x могут быть произвольными. Метод ветвей и границ использует две процедуры: ветвление и нахождение оценок (границ). Ветвление покрывает область допустимых решений областями допустимых решений меньших размеров. Процедура называется ветвлением, так как она повторяется рекурсивным образом далее к каждой из полученных подобластей, образуя дерево, называемое деревом поиска или деревом ветвей и границ. Вершины этого дерева соответствуют построенным подобластям. Другая процедура — нахождение оценок, которая является быстрым методом нахождения верхних и нижних границ оптимального решения в подобласти допустимых решений.

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