Контрольная работа по "Программированию"

Ответы на задание:

1. Какие известны способы представления задач?

Списочное представление;

Графовые представления;

Представление в пространстве состояний;

Представление в пространстве задач;

Представление в виде теорем.

2. Как формально описываются представления в пространстве состояний?

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

{S,S0, F, Sk}

где F={f1,f2,….fn}- есть множество операторов преобразования, управляющих переводом из состояния Si в другое состояние Sj. S0— начальное состояние, Sk— конечное состояние. S─множество состояний пространства состояний

3. Какие известны стратегии поиска в пространстве состояний?

Поиск в пространстве состояний можно вести в двух направлениях: от исходных дан¬ных задачи к цели (стратегия прямой волны) и в обратном направлении от цели к исходным данным (стратегия обратной волны).

4. В чем различие методов поиска в глубину и в ширину?

Разница в алгоритмах обхода графа, поиск в ширину проходит по уровням с использованием списков open closed, поиск в глубину старается максимально углубится в область поиска и если потомки состояния не найдены в области поиска переходит к вершинам братьям.

5. Как различаются графы типа И и ИЛИ?

Для решения исходной задачи графа с дугами И требуется решить все задачи.

Для решения исходной задачи графа с дугами ИЛИ требуется решить одну задачу.

6.