Рабочая программа для студентов специальности 10. 05. 01 «Компьютерная безопасность»



страница3/4
Дата31.07.2016
Размер0.66 Mb.
ТипРабочая программа
1   2   3   4





Основные понятия логической модели представления знаний
ЗАДАНИЕ №7 (выберите один вариант ответа)

По Вашему мнению, рассматриваются ли в современных системах ИИ противоречивые исчисления?


ВАРИАНТЫ ОТВЕТОВ:

1)

В широко известных системах нет

2)

Чаще всего исчисление получается противоречивым из-за ошибки программиста

3)

Да, конечно








Основные понятия логической модели представления знаний
ЗАДАНИЕ №8 (выберите один вариант ответа)

По вашему мнению, имеется разница между понятиями “вероятности события” и “степени принадлежности” (по Л.Заде)?


ВАРИАНТЫ ОТВЕТОВ:

1)

Это идентичные понятия

2)

Это совершенно разные понятия

3)

Имеется некоторое пересечение, но понятия разные








Основы языка PROLOG
ЗАДАНИЕ №1 (выберите один вариант ответа)

По Вашему мнению, имеет ли список “длина([10, (11, 11), 12], 4)” длину, равную 4?


ВАРИАНТЫ ОТВЕТОВ:

1)

Да

2)

Нет








Основы языка PROLOG
ЗАДАНИЕ №2 (выберите один вариант ответа)

Установите, сопоставляется ли данная пара: [ЖАК. ЖИЛЬ] и [A, B|C].


ВАРИАНТЫ ОТВЕТОВ:

1)

Да

2)

Нет








Основы языка PROLOG
ЗАДАНИЕ №3 (выберите один вариант ответа)

Установите, сопоставляется ли данная пара: [дом, осёл, лошадь] и [H, T].


ВАРИАНТЫ ОТВЕТОВ:

1)

Да

2)

Нет








Основы языка PROLOG
ЗАДАНИЕ №4 (выберите один вариант ответа)

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


ВАРИАНТЫ ОТВЕТОВ:

1)

16



2)

4

3)



6

4)

Данное выраже



ие не является структурой






Основы языка PROLOG
ЗАДАНИЕ №5 (выберите один вариант ответа)

По Вашему мнению, раздел программы на PROLOG, предназначенный для задания внутренних баз данных, объявляется как …


ВАРИАНТЫ ОТВЕТОВ:

1)

Domains

2)

Clauses

3)

Goals

4)

Predicates

5)

Databases








Основы языка PROLOG
ЗАДАНИЕ №6 (выберите один вариант ответа)

По Вашему мнению, операция отсечения в PROLOG обозначается …


ВАРИАНТЫ ОТВЕТОВ:

1)

%

2)

Cut

3)

!

4)

Такой операции в PROLOG нет








Основы языка PROLOG
ЗАДАНИЕ №7 (выберите один вариант ответа)

Укажите допустимые в PROLOG реляционные операторы.


ВАРИАНТЫ ОТВЕТОВ:

1)

>

2)

<

3)

=

4)

=>

5)

<=

6)

<>

7)

><

8)

<=>








Основы языка PROLOG
ЗАДАНИЕ №8 (выберите один вариант ответа)

По Вашему мнению, какие из фрагментов программы на PROLOG позволяют вычислять выражение и вывести результат.


ВАРИАНТЫ ОТВЕТОВ:

1)

GOAL

A=4+2, write(A)



2)

GOAL

A=4+2


3)

_:=4+2

4)

Ни один из фрагментов








Основы объектной модели
ЗАДАНИЕ №1

По Вашему мнению, инкапсуляция – это …


ВАРИАНТЫ ОТВЕТОВ:

1)

Механизм обеспечения наследования в объектах

2)

Совершенно бессмысленное слово

3)

Способ объединения кода и данных в объектах








Основы объектной модели
ЗАДАНИЕ №2

По Вашему мнению, может ли один и тот же терминал входить в два разных фрейма одной системы?


ВАРИАНТЫ ОТВЕТОВ:

1)

Зависит от контекста

2)

Не может

3)

Может








Основы объектной модели
ЗАДАНИЕ №3

По Вашему мнению, для обмена данными в объектно-ориентированном программировании используется


ВАРИАНТЫ ОТВЕТОВ:

1)

Глобальная переменная

2)

Локальная переменная

3)

Механизм “сообщений”








Основы объектной модели
ЗАДАНИЕ №4

По Вашему мнению, к основным свойствам объектов относятся …


ВАРИАНТЫ ОТВЕТОВ:

1)

Полиморфизм

2)

Наследование

3)

Инкапсуляция








Основы объектной модели
ЗАДАНИЕ №5

По Вашему мнению, представление знаний фреймами эффективно при …


ВАРИАНТЫ ОТВЕТОВ:

1)

Анализе пространственных сцен



2)

Автоматическом переводе



3)

Способ объединения кода и данных



объектах






Основы объектной модели
ЗАДАНИЕ №6

По Вашему мнению, нижние уровни фрейма-экземпляра …


ВАРИАНТЫ ОТВЕТОВ:

1)

Называются “маркерами”

2)

Заполнены характерными примерами или данными

3)

Пусты








Основы объектной модели
ЗАДАНИЕ №7

По Вашему мнению, объекты-экземпляры, которые во время выполнения программы могут принимать различные формы представления от объекта своего типа до любого из потомков, называют …


ВАРИАНТЫ ОТВЕТОВ:

1)

Полиморфными

2)

Виртуальными

3)

Динамическими








Основы объектной модели
ЗАДАНИЕ №8

По Вашему мнению, представление знаний фреймами значительно более эффективно, чем при помощи …


ВАРИАНТЫ ОТВЕТОВ:

1)

Эффективность зависит от решаемой задачи

2)

Семантических сетей

3)

Правил продукций

4)

Нечёткой логики








Основы объектной модели
ЗАДАНИЕ №9

По Вашему мнению, фрейм может быть описан при помощи правил продкукций?


ВАРИАНТЫ ОТВЕТОВ:

1)

Зависит от контекста

2)

Нет

3)

Да








Основы объектной модели
ЗАДАНИЕ №6

По Вашему мнению, терминалы фрейма-образца заполнены …


ВАРИАНТЫ ОТВЕТОВ:

1)

Совершенно пусты

2)

Так называемыми “заданиями отсутствия”

3)

Терминальными фактами

4)

Переменными





Перечень теоретических и практических вопросов, заданий и упражнений к зачёту:

  1. Предложите и аргументируйте собственное понятие искусственного интеллекта.

  2. Приведите критические замечания по поводу тьюринговского критерия “разумности” компьютерной программы.

  3. Сформулируйте Ваш собственный критерий “разумности” компьютерной программы.

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

  5. Выберите проблемную область, в которой, как Вы считаете, затраты на разработку экспертной системы бели бы оправданы. Разъясните в общих чертах суть проблемы. На основании своей интуиции скажите: какие аспекты принятия решений будет наиболее сложно автоматизировать?

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

  7. Поясните, почему Вы считаете такой сложной проблему машинного обучения?

  8. Считаете ли Вы возможным для компьютера понимать и использовать естественный (человеческий) язык?

  9. Попытайтесь унифицировать следующие пары выражений. Найдите их наиболее общие унификаторы или же объясните, почему они не могут быть унифицированы:

  1. P(X,Y) и P(a,Z);

  2. P(X,X) и P(a,b);

  3. Ancestor(X, father(X)) и ancestor(bill, father(bill));

  4. Ancestor(X, father(X)) и ancestor(david, george);

  5. P(X) и ¬P(X).

  1. Дайте определение декартова произведения множеств и раскройте его сущность.

  2. Прокомментируйте множества подстановок (a/X, Y/Z) и (X/W, b/Y). Докажите, что композиция множеств подстановок ассоциативна. Постройте пример, демонстрирующий, что композиция не коммутативна.

  3. Реализуйте алгоритм unify на выбранном Вами языке программирования.

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

  5. Я женился на вдове (W), которая имеет взрослую дочь (D). Мой отец (F), который весьма часто навещал нас, влюбился в мою падчерицу и женился на ней. Поэтому мой отец стал моим зятем, а моя падчерица стала моей мачехой. Спустя несколько месяцев моя жена родила сына (S1), который стал шурином (зятем) моему отцу, а потому моим дядей. Жена моего отца, то есть моя падчерица, тоже родила сына (S2). Используя исчисление предикатов, создайте набор выражений, описывающих данную ситуацию. Добавьте выражения, описывающие основные отношения в семье, в том числе определение свекра (или тестя), и, используя правило modus ponens, докажите заключение “Я сам себе дедушка”.

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

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

  8. Приведите пример задачи о коммивояжёре, в которой стратегия ближайшего соседа при нахождении оптимального пути приводит к неудаче. Предложите другую эвристику для этой задачи.

  9. Реализуйте алгоритм поиска с возвратами на языке программирования по Вашему выбору.

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

  1. Диагностика неисправностей автомобиля.

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

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

  4. Программа автоматического доказательства теорем по планиметрии.

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

  6. Экспертная система, которая поможет человеку классифицировать растения по виду, роду и так далее.

  1. Обоснуйте выбор поиска в ширину или в глубину для примеров из предыдущего пункта.

  2. Запишите алгоритм поиска с возвратами для графа И/ИЛИ.

  3. Приведите ещё один пример задачи поиска на графе И/ИЛИ и сформируйте фрагмент пространства поиска.

  4. Добавьте к правилам русской грамматики, описанным в материале, правила для прилагательных и наречий.

  5. Добавьте к правилам русской грамматики правила для фраз с предлогами.

  6. Сравните три эвристики для игры в “пятнашки” с эвристикой сложения суммы расстояний для фишек, находящихся не на своих местах, с удвоенным числом прямых перестановок. Сравните их по следующим критериям:

  1. Точность оценки расстояния к цели. Для этого требуется найти кратчайший путь к решению, а затем использовать как эталон.

  2. Информированность. Какая из упомянутых эвристик наиболее эффективно сокращает пространство состояний.

  3. Монотонность для игры “пятнашки”.

  4. Допустимость. Какая из этих эвристик ограничена сверху фактической стоимостью пути к цели? Обоснуйте свои предположения для общего случая или приведите контрпример.

  1. Как известно из предложенного материала, “жадный” алгоритм поиска для предотвращения зацикливания использует список closed. А что если отказаться от этого теста и определять зацикливания на основе g(n)? сравните эффективность этих двух подходов.

  2. Функция best_first_search не проверяет, является ли состояние целевым, пока оно не удалено из списка open. Эту проверку можно выполнять при рассмотрении новых состояний. Как это отразится на эффективности алгоритма? На допустимости?

  3. Докажите, что алгоритм A* допустим. Подсказка: при доказательстве следует показать, что:

  1. Для алгоритма A* поиск закончится.

  2. В списке open всегда существует узел, который находится на оптимальном пути к цели.

  3. Если путь к цели существует, то алгоритм A* закончится нахождением оптимального пути к цели.

  1. Подразумевает ли допустимость выполнение свойства монотонности эвристики? Если нет, опишите, когда допустимость подразумевает монотонность.

  2. Докажите, что набор состояний, рассмотренных в алгоритме A*, является подмножеством состояний поиска в ширину.

  3. Докажите, что более информированная эвристика просматривает более узкую область поиска.

  4. Шифр Цезаря – это простая схема кодирования, основанная на циклических перестановках алфавита, в которой i-й символ алфавита заменяется (i+n)-м символом. Например, при использовании шифра Цезаря со сдвигом 4 слово “Caesar” запишется как “Geiwev”.

  1. Приведите три эвристики, которые можно использовать для расшифровки шифра Цезаря.

  2. В простом шифре подстановки каждый символ заменяется другим на основе некоторого произвольного взаимно однозначного отображения. Какие из возможных эвристик, предложенных для шифра Цезаря можно использовать для расшифровки такого шифра?

  1. Рассмотрите трехмерную игру в “крестики-нолики”. Проанализируйте сложность пространства состояний. Предложите эвристику для этой игры.

  2. Напишите рекурсивный алгоритм поиска в ширину (с использованием списков open и closed). Можно ли с учётом рекурсии обойтись без списка open? Объясните.

  3. Проследите выполнение рекурсивного алгоритма поиска в глубину (без использования списка open) в пространстве состояний, показанном на рисунке.



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

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

  1. Поиск от цели.

  2. Поиск на основе данных.



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

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

  3. Опишите изображённые на рисунке концептуальные графы на естественном языке.



  1. Операции join (объединить) и restrict (ограничить) определяют обобщённое упорядочение на концептуальных графах. Покажите, что отношение обобщения является транзитивным.

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

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

  4. Транслируйте концептуальные графы, изображённые на рисунке, в исчисление предикатов.



  1. Используя концептуальные зависимости, определите сценарий для:

  1. Ресторана быстрого приготовления пищи.

  2. Общения с продавцом бывших в употреблении автомобилей.

  3. Похода в оперный театр.

  1. Постройте иерархию подтипов для понятия “транспортное средство”. Например, его подтипами могли бы быть “наземное транспортное средство” или “водное транспортное средство”. Они, в свою очередь, могли бы иметь свои подтипы. Сделайте то же самое для понятий “перемещаться” и “сердитый”.

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

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

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

  5. Вернитесь к предыдущему вопросу. Создайте на русском языке или псевдокоде 15 правил “если …, то …” (отличных от описанных в предыдущем вопросе) для представления отношений в этой предметной области. Постройте граф, представляющий взаимосвязи этих 15 правил.

  6. Рассмотрите граф из предыдущего вопроса. Какой поиск вы рекомендуете на основе данных или на основе цели? Поиск в ширину или глубину? Каким образом здесь могут помочь эвристики поиска? Обоснуйте ответы на эти вопросы.

  7. Выберите другую область для разработки экспертной системы. Ответьте на предыдущие три вопроса для этого приложения.

  8. Реализуйте экспертную систему, используя коммерческую оболочку (рекомендуется оболочка CLIPS).

  9. Постройте механизм рассуждений на примерах из произвольно выбранного приложения, например, задачи выбора курсов при изучении базовых дисциплин или получении степени магистра. Используйте коммерческое программное обеспечение для построения системы рассуждений для привёденных примеров. Если нет готового программного обеспечения, постройте такую систему на языках PROLOG, LISP или JAVA.

  10. В учебном материале был представлен планировщик, созданный в Стэндфордском университете. Адаптивное планирование позволяет описывать продолжительные действия, то есть такие, которые остаются истинными в течение определённых временных периодов. Почему системы адаптивного планирования предпочтительнее планировщиков типа STRIPS? Постойте адаптивный планировщик на языках PROLOG, LISP или Java.

  11. Укажите три прикладные области, в которых необходимы рассуждения в условиях неопределённости. Выберите одну из этих областей и разработайте шесть правил вывода, отражающих рассуждения в ней.

  12. Даны следующие правила, применяемые в экспертной системе, работающей на основе “обратной цепочки”.





Система может вывести следующие факты (с заданной достоверностью).







Используйте стэндфордскую алгебру фактора уверенности для определения E и его достоверности.



  1. С использованием литературных источников опишите две области, в которых применимо нечёткое управление. Разработайте множество нечётких правил для этих областей.

  2. Реализуйте алгоритм поиска в пространстве версий на языке PROLOG или на любом другом языке программирования. Если Вы выбрали PROLOG, то воспользуйтесь рекомендациями.

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


Таблица



  1. С помощью формулы Шеннона докажите, что информативность сообщения о результатах вращения рулетки выше, чем информативность сообщения о результате подбрасывания монеты.

  2. В некоторой предметной области составьте таблицу примеров, наподобие классификации животных по видам, и продемонстрируйте процесс построения дерева решений с помощью алгоритма ID3.

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

  4. Разработайте алгоритм обучения на основе объяснения на любом языке программирования. Если Вы выбрали PROLOG, воспользуйтесь алгоритмом из учебного материала.

  5. Вспомните игру в “крестики-нолики”. Реализуйте алгоритм обучения на основе временных разностей на любом языке программирования. Как изменится алгоритм, если принять во внимание симметричность задачи? что произойдет, если алгоритм на основе временных разностей будут использовать оба игрока?

  6. Ещё одной тестовой задачей для обучения с подкреплением является так называемая проблема решётки. На рисунке показана решётка размера 4x4. Две заштрихованные ячейки по углам решётки – это целевые конечные состояния агента. Из любой другой ячейки агент может двигаться вверх, вниз, влево и вправо. Он не может выйти за пределы решётки: при такой попытке состояние не изменяется. Вознаграждение для всех ходов, за исключением перехода в конечное состояние, составляет -1. Постройте решение на основе временных разностей.

  7. Постройте нейрон Мак-Каока-Питтса, вычисляющий функцию логического следования .

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




X1

X2

Выход

1,0

1,0

1

9,4

6,4

-1

2,5

2,1

1

8,0

7,7

-1

0,5

2,2

1

7,9

8,4

-1

7,0

7,0

-1

2,8

0,8

1

1,2

3,0

1

7,8

6,1

-1




  1. Сгенерируйте свой набор данных и используйте его для решения задачи классификации;

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

  1. Реализуйте сеть прямого распространения на языке LISP или C++ и используйте её для решения задачи “исключающего ИЛИ”. Решите эту задачу с помощью нескольких сетей различной архитектуры, например сети с двумя скрытыми узлами без пороговых нейронов. Сравните скорость сходимости разных сетевых структур.

  2. Реализуйте сеть Кохонена на языке LISP или C++ и используйте её для решения задачи классификации данных из таблицы.




X1

X2

Выход

1,0

1,0

1

9,4

6,4

-1

2,5

2,1

1

8,0

7,7

-1

0,5

2,2

1

7,9

8,4

-1

7,0

7,0

-1

2,8

0,8

1

1,2

3,0

1

7,8

6,1

-1




  1. Реализуйте сеть встречного распространения и используйте её для решения задачи “исключающего ИЛИ". Сравните полученные результаты с данными для сети прямого распространения, приведёнными в учебном материале. Используйте свою сеть встречного распространения для разделения классов из таблицы.




X1

X2

Выход

1,0

1,0

1

9,4

6,4

-1

2,5

2,1

1

8,0

7,7

-1

0,5

2,2

1

7,9

8,4

-1

7,0

7,0

-1

2,8

0,8

1

1,2

3,0

1

7,8

6,1

-1




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

  2. Выберите входной образ и примените метод обучения Хэбба без учителя для распознавания этого образа.

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

  4. Вспомните сеть ДАП, описанную в учебном материале. Измените пары ассоциаций, выбранные в этом материале, и постройте для них матрицу весов. Выберите новые векторы и протестируйте свою сеть ДАП.

  5. Опишите различия между сетью ДАП и линейным ассоциатором. Что такое помехи и как предотвратить их появление?

  6. Постройте сеть Хопфилда для решения задачи коммивояжёра для десяти городов.

  7. Генетический алгоритм должен поддерживать поиск в пространстве вероятных комбинаций и обеспечивать выживание на основе генетических шаблонов. Опишите как эти задачи решаются с помощью различных генетических операторов.

  8. Вспомните проблему разработки представления для генетических операторов при решении задач из различных предметных областей. В чём состоит роль индуктивного порога?

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

  10. Постройте генетический алгоритм для решения задачи представимости в конъюктивной нормальной форме.

  11. Подумайте над проблемой выбора соответствующего представления для задачи коммивояжёра. Определите другие возможные генетические операторы и меры качества для этой задачи.

  12. Определите роль представления, в том числе кодирования Грея, для описания пространства поиска в генетических алгоритмов. Приведите примеры двух предметных областей, в которых этот вопрос играет важную роль.

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

  14. Как алгоритм “пожарной цепочки” связан с методом обратного распространения ошибки?

  15. Напишите программу, решающую задачу моделирования третьего закона Кеплера.

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

  17. Ознакомьтесь с писанием игры “Жизнь”. Назовите другие структуры искусственной жизни, подобные планеру.

  18. Напишите программу моделирования искусственной жизни.

  19. Определите роль индуктивного порога в выборе представления стратегий поиска и операторов, используемых в моделях обучения. Является ли генетическая модель обучения изолированной или её можно распространить на более широкие области?

  20. Изучите глубже вопросы эволюции и эмерджентности. Прочтите и обсудите некоторые из них.

  21. С помощью процедуры резолюции докажите какое-либо утверждение по выбору.

  22. Как можно использовать процедуру резолюции для реализации поиска в продукционной системе.

  23. Воспользуйтесь резолюцией для решения задачи о человеке, волке, козе и капусте.

  24. Воспользуйтесь методом резолюции для решения задачи. условия задачи следующие. Четыре человека – Роберта, Тельма, Стив и Пит – работают на восьми различных работах. Каждый из них работает ровно на двух работах. Они занимают следующие должности: руководитель, охранник, санитар, телефонист, полицейский, учитель, актёр и боксёр. Санитар – это мужчина. Муж руководителя – телефонист. Роберта – не боксёр. Пит не имеет высшего образования. Роберта, руководитель и полицейский любят вместе играть в гольф. Кто на какой работе работает? Покажите, как изменится задача с учётом пола каждого из сотрудников.

  25. Приведите два примера гиперрезолюции, где ядро состоит не менее чем из четырёх литералов.

  26. Приведите следующее выражение из предикатной формы к дизъюнктивной

.

  1. Создайте граф И/ИЛИ для решения следующей задачи на основе данных.

Факт: .

Правила: и и .

Доказать: .


  1. Докажите, что стратегия линейной входной формы не является полной в смысле опровержения.

  2. Создайте граф И/ИЛИ для решения следующей задачи и объясните, почему невозможно получить целевое выражение.

.

Факт: .



Правила: и .

  1. Используйте процедуры факторизации и резолюции для опровержения следующих выражений и . Постарайтесь построить опровержение без факторизации.

  2. Альтернативной семантической моделью для логического программирования является Flat Concurrent PROLOG. Сравните эту модель с семантикой языка PROLOG.

  3. Как стохастический подход можно объединить с методами анализа баз данных.

  4. Использование стохастического подхода для изучения образов, содержащихся в реляционных базах данных, – важное современное направление исследований, которое иногда называют “добычей данных”. Как можно использовать этот подход для ответов на запросы к реляционным базам данных?

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

  6. Напишите на PROLOG программу проверки принадлежности элемента списку. Что произойдет, если элемент не принадлежит списку? Дополните эту спецификацию таким образом, чтобы она позволяла разбивать список на элементы.

  7. Напишите на PROLOG программу вычисления количества элементов в списке (список в списке считается одним элементом). Разработайте программу подсчёта атомов в списке (вычисления количества элементов во всех списках). Совет: можно воспользоваться несколькими матапредикатами типа atom().

  8. Напишите на PROLOG код программы, решающей задачу перевозки человека, волка, козы и капусты.

  1. Выполните этот код и постройте граф поиска.

  2. Измените порядок следования правил для получения альтернативных путей решения.

  3. Используйте оболочку для реализации поиска в ширину.

  4. Опишите полезные для данной задачи эвристики.

  5. Постройте решение на основе эвристического поиска.

  1. Выполните те же задания из предыдущего вопроса для следующей задачи.

Три миссионера и три каннибала стоят на берегу реку и хотят переправиться через неё. У берега находится лодка, в которую могут поместиться только два человека, и ни один из них не умеет плавать. Если на одном из берегов реки миссионеров окажется больше, чем каннибалов, то каннибалы станут миссионерами. Требуется найти последовательность перемещений через реки, при которой не произойдёт изменений количественного и качественного состава групп.

  1. В учебном материале имеется пример реализации алгоритма ID3 на языке LISP. Создайте реализацию этого алгоритма на языке PROLOG. Не пытайтесь при этом перевести код LISP на PROLOG. Эти языки различны и, подобно естественным языкам, для описания одних и тех же объектов требуют различных идиом.

  2. Постройте на PROLOG ANT-анализатор.

  3. Напишите на PROLOG для подмножества правил русского языка.

  4. Описанный в учебном материале простой анализатор естественного языка допускает грамматически некорректные предложения, например, “Человек кусает собаку”. Такие предложения можно исключить из грамматики, добавив в неё данные о семантической допустимости. Разработайте на PROLOG семантическую сеть, позволяющую рассуждать о некоторых аспектах возможной интерпретации грамматических правил русского языка.

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

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

  7. Напишите на LISP рекурсивную функцию обращения элементов списка (не используя встроенную функцию reverse). Оцените сложность реализации. Можно ли реализовать обращение списка за линейное время?

  8. Напишите на LISP генератор случайных чисел. Эта функция должна поддерживать глобальную переменную seed и возвращать разные случайные числа при каждом вызове. Описание алгоритма генерации случайных чисел можно найти в специальной литературе.

  9. Множества можно представить с помощью списков, не содержащих повторяющихся элементов. Напишите на LISP свою реализацию операций объединения, пересечения и вычитания множеств (не пользуйтесь встроенными в Common LISP версиями этих функций).

  10. Задача башен Ханоя основана на следующей легенде.

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

  1. Диски можно перемещать только по одному.

  2. Ни один диск не может располагаться поверх диска меньшего размера.

Согласно легенде, когда задача будет решена, наступит конец света.

Напишите на LISP решение этой задачи. Для простоты рассмотрите 3 или 4 диска.



  1. Напишите компилятор для оценки арифметических выражений вида

(оператор операнд1 операнд2),

где оператор – это “сложение”, “вычитание”, “умножение” или “деление”, а операндами являются числа или вложенные выражения. Примером допустимого выражения является (x(+ 3 6)(- 7 9)). Допустим, что целевая машина поддерживает инструкции:

(move value register)

(add register-1 register-2)

(subtract register-1 register-2)

(time register-1 register-2)

(divide register-1 register-2) ^^|

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



  1. Реализуйте алгоритм поиска в глубину с возвратами для решения задачи о миссионерах и каннибалах.

  2. Реализуйте алгоритм поиска в глубину для решения задачи о емкостях с водой.

Имеются две ёмкости по 3 и 5 литров соответственно. Их можно заполнять, опорожнять и переливать воду из одной в другую, пока одно из них не окажется полной или пустой. Выработайте последовательность действий, при которой в большей ёмкости окажется 4 литра воды.

  1. Каталог: files
    files -> Чисть I. История. Введение: Предмет философии науки Глава I. Философия науки как прикладная логика: Логический позитивизм
    files -> Занятие № Философская проза Ж.=П. Сартра и А. Камю. Философские истоки литературы экзистенциализма
    files -> -
    files -> Взаимодействие поэзии и прозы в англо-ирландской литературе первой половины XX века
    files -> Эрнст Гомбрих История искусства москва 1998
    files -> Питер москва Санкт-Петарбург -нижний Новгород • Воронеж Ростов-на-Дону • Екатеринбург • Самара Киев- харьков • Минск 2003 ббк 88. 1(0)
    files -> Антиискусство как социальное явлеНИе
    files -> Издательство
    files -> Список иностранных песен
    files -> Репертуар группы


    Поделитесь с Вашими друзьями:
1   2   3   4


База данных защищена авторским правом ©uverenniy.ru 2019
обратиться к администрации

    Главная страница