Коллоквиум №2

● Поиск в глубину

Вначале вводится понятие глубины вершины:

■глубина корня дерева равна нулю;

■глубина каждой не корневой вершины на единицу больше глубины ее родительской вершины.

Основные шаги базового алгоритма ограниченного перебора вглубь (с граничной глубиной D) таковы:

■Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open. Установить ее глубину (0).

■Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к следующему шагу.

■Шаг 3. Выбрать первую вершину из списка Open (назовем ее Current) и перенести ее в список раскрытых вершин Closed.

■Шаг 4. Если глубина вершины Current равна граничной глубине D, то перейти к шагу 2, в ином случае перейти к следующему шагу.

■Шаг 5. Раскрыть вершину Current, построив все ее дочерние вершины. Если дочерних вершин нет, то перейти к шагу 2, иначе поместить все дочерние вершины (в произвольном порядке; с указанием их глубины) в начало списка Open и построить указатели, ведущие от этих вершин к родительской вершине Current.

■Шаг 6. Если среди дочерних есть хотя бы одна целевая вершина, то окончание алгоритма и выдача решения задачи, получающегося просмотром указателей от найденной целевой вершины к начальной. В противном случае перейти к шагу 2.

● Поиск в ширину

Базовый алгоритм поиска вширь состоит из следующей последовательности шагов (здесь и далее предполагаем, что начальная вершина не является целевой):

■Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open.

■Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к следующему шагу.

■Шаг 3. Выбрать первую вершину из списка Open (назовем ее Current) и перенести ее в список раскрытых вершин Closed.

■Шаг 4. Раскрыть вершину Current, образовав все ее дочерние вершины. Если дочерних вершин нет, то перейти к шагу 2, иначе поместить все дочерние вершины (в любом порядке) в конец списка Open и построить указатели, ведущие от этих вершин к родительской вершине Current.

■Шаг 5. Проверить, нет ли среди дочерних вершин целевых. Если есть хотя бы одна целевая вершина, то окончание алгоритма и выдача решения задачи, получающегося просмотром указателей назад от найденной целевой вершины к начальной. В противном случае перейти к шагу 2.

● Игра в 8 (попасть в одно из сост с помощью поиска в глубину(ширину));

● Что такое продукционная система?

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

Продукция - это пара “условие - действие”, которая определяет одну порцию знаний, необходимых для решения задачи.

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

● Из каких частей состоит продукционная система представления знаний;

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

■Продукция – правило вида p: a->b, где p – предусловие, a - антецедент, b - консеквент.

■Система знаний – система продукционных правил + стратегия выбора правил.

■База знаний – система знаний в компьютерном представлении.

■Основные операции: вывод (применение правила, определение правила-преемника и т.д.)

● Дан алгоритм поиска в ширину. Модифицировать его таким образом, чтобы он стал алгоритмом поиска в глубину с ограничением глубины.

Всё, что нужно изменить:

a. при добавлении новых вершин (тех, которых мы раскрываем на каком-то шаге) добавлять их не в конец списка, а в начало.

b. перед раскрытием вершины проверить её глубину, если превышает ограничение, то не раскрывать..

● Чем удобен механизм бэктрекинга.

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

● Что такое эвристическая функция?

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

А эвристическая функция - это функция, используемая эвристикой для определения “хорошести” ситуации, в которой находится поиск.

см. в более полном варианте в экзамене 2009

● Теоретический вопрос по ЭС.

Экспертная система (ЭС) – вычислительная система, в которой представлены знания специалистов в некоторой конкретной узко-специализированной предметной области и которая в рамках этой области способна принимать решения (решать задачи) на уровне эксперта - профессионала.

● Составные части решателя экспертной системы.

i.выборка (правил-кандидатов)

ii.сопоставление / означивание

iii.разрешение конфликтов

iv.выполнение / действия

v.переход на НАЧАЛО

● Описать алгоритм, который исправляет в тексте ошибки типа удвоения букв.

см. ниже

● Задача типа, найдите в тексте двусмыслености: "консорциум купил журнал". Дано предложение, нужно записать все возможные трактовки.

В данном случае к мог купить ж или ж мог купить к.

Надо записать в каком-то умном виде. Вроде, называется диаграмма чего-то там...

У меня надо было записать в виде продукции. Выглядит на данном примере примерно так:

true: консорциум -> купил журнал (консорциум - покупатель)

true: журнал -> купил консорциум (журнал - покупатель)

● Интеллектуальные роботы, основные подходы:

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

В наши дни ведутся работы по «интеллектуализации» технических/промышленных роботов.

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

Иногда предполагается возможность передачи роботу (человеком-оператором) управляющих команд.

■Робот не может причинить вред человеку или своим бездействием допустить, чтобы человеку был причинен вред.

■Робот должен подчиняться командам человека, если эти команды не противоречат первому закону.

■Робот должен заботиться о своей безопасности, пока это не противоречит первому и второму законам.

● Задача про башни из кубиков

См. в экзамене 2009, а лучше в AI-2010 Day 07

● Что такое естественный язык?

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

● Что такое вытеснение знаний? Покажите на примере, почему вытеснение является одним из защитных механизмов сознания.

Вытеснение – неосознанное вытеснение (удаление) из сферы Сознания информации, вызывающей тревогу, отрицательные эмоции и т.п. Защитные механизмы личности – некоторая психическая информация вытесняется из сознательного в сферу подсознания, т.к. она, например, социально неприемлема (это - неосознанное действие!). В нормальной ситуации человек не помнит, что с ним произошло, но то, что вытеснилось, продолжает влиять на сознательное, но не в явной форме, а в каком-то искаженном виде => происходит замещение вытесненной информации какими-то истерическими симптомами. [источник не указан 100500 дней]

Дата добавления: 2015-06-27