16.2 Представление задач в пространстве состояний

Состояние задачи это конфигурация системы на определённом этапе поиска. Решение задачи возможно только при наличии описания конфигурации т.к. сами конфигурации выясняются только в процессе поиска.

Описание задачи осуществляется посредствам формы. Например в пятнашках это матрица 4х4.

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

Таким образом для представления проблемы в пространстве состояний необходимо:

1) Определение пространства состояний по средствам какой-нибудь формы.

2) Множество операторов воздействующих на состояние.

3) Описание целевого состояния.

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

Рассмотрим задачу, которую придумал Амарель. (1966)

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

Пространство состояний описывается списком из 5 переменных. [W,U,V,P,Z]

Здесь W - положение обезьяны, V - положение ящика, Z - положение банана, U- единица, если обезьяна на ящике, ноль - если на полу. P - единица, если обезьяна достала банан, ноль, когда не достала.

ОПЕРАТОРЫ:

1)Подойти к точке А: [W,O,V,P,Z]->[A,O,V,P,Z]

2)Передвинуть ящик в точку В: [W,O,W,P,Z]->[B,O,B,P,Z]

3)Взобраться на ящик: [B,O,B,P,Z]->[W,1,W,P,Z]

4)Взять банан: [W,1,W,0,W]-> [W,1W,1,W]

Целевой список это любой список, для которого Р=1

Начальное состояние системы так же задаётся списком.

16.3 Лвс Ethernet. Общая шина: Метод доступа.

В ЛВС Ethernet применяется метод CSMA/CD. Все рабочие станции подключены к общей шине. Действия, которые должны предприниматься для предотвращения одновременной передачи данных и для организации повторных передач регламентируются стандартом 802.3 IEEE.

При передаче данных согласно протоколу CSMA/CD станции выполняют 5 шагов:

1. Прослушивание до начала передачи.

2. Задержка (ожидание), если канал занят.

3. Передача и прослушивание коллизий. Если канал свободен не менее, чем 9,6 мс, станция может начать передачу. пакет передается по кабельной системе в обоих направлениях. Если в то же самое время передаст пакет еще одна станция, то возникнет коллизия. Пакеты, вовлеченные в коллизию превратятся в фрагменты. Возникновение коллизии распознается станциями по уровню сигнала и начинают передавать сигнал затора jam - сообщение длиной не менее 32 бит.Станции, вовлеченные в коллизию, увеличивают свои счетчики числа попыток передачи на 1.

4. При возникновении коллизий ожидание перед повторной передачей. Для выбора момента повторной передачи станция станция действует согласно алгоритма отступления.

5. Повторная передача или прекращение работы. Станция может попытаться начать передачу до 16 раз, прежде чем прекратит свои попытки.

Для приема данных активная станция, подключенная к сегменту, должна выполнить 4 шага:

1. Просмотр поступающих пакетов данных и обнаружение фрагментов. Если кадр имеет допустимую длину >=64 байт, то он не является фрагментом, порожденным коллизией.

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

3. Проверка целостности пакета данных, если пакет поступил на станцию-получатель. Проверяется длина пакета. Кадр длиннее 1528 байт считается переполненным. Если CRC некорректна, проверяется выровненность пакета. Все пакеты должны содержать целое число байт и оканчиваться на 8-битовой границе. Если CRC кадра некорректна, но кадр корректно выровнен, то считается, что имеет место ошибка контрольной последовательности.

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

Стандарт 802.3 содержит спецификации кабеля, пригодные для реализации ЛВС Ethernet: 10Base5 (толстый коаксиальный кабель) ; 10Base2 (тонкий коаксиальный кабель) ; 10BaseT (неэкранированная витая пара проводов) ;10BaseFL (оптоволокно).

Структуры кадров Ethernet

Сущ. 4 типа кадров, не все протоколы могут быть использованы с каждым допустимым типом кадров:

Тип кадра                  Протокол

Ethernet_II                  IPX/SPX, TCP/IP, AppleTalk Phase I

Ethernet_802.2            IPX/SPX, FTAM

Ethernet_802.3            IPX/SPX

Ethernet_SNAP           IPX/SPX, TCP/IP, AppleTalk Phase II

Чтобы определить является ли кадр искаженным или некорректно сформированным, нужно знать структуру каждого типа кадров ЛВС Ethernet.

Стандарт Ethernet_SNAP

Sub-Network Access Protocol - протокол доступа к подсети. Структура кадра является развитием структуры кадра в стандарте Ethernet_802.2

Преамбула и начальный ограничитель кадра SFD (8 байт)

 Адрес получателя (6 байт)

Адрес источника (6 байт)

Длина данных(2 байта)

Точка доступа к услугам получателя DSAP (1 байт)

Точка доступа к услугам источника SSAP (1 байт)

Управление (1 байт)

Код организации (3 байта)

 Тип Ethernet (2 байта)

 Данные (45-1500 байт)

Контрольная последовательность кадра FCS(4 байта)

Минимальная длина кадра - 64 байта, максимальная - 1518 байт.

Стандарт Ethernet_II

Структура кадра отличается тем, что поле типа следует за полем источника.

Преамбула и начальный ограничитель кадра SFD (8 байт)

Адрес получателя (6 байт)

Адрес источника (6 байт)

Тип (2 байта)

Данные (46-1500 байт)

Контрольная последовательность кадра FCS(4 байта)

Минимальная длина кадра - 64 байта, максимальная - 1518 байт.