28. 10.2011 Лекция 5

План

1. Поиск

2. Дерево

3. Поиск в глубину

Область, в которой ищется возможное решение, называется пространством поиска.

Прежде чем что-то искать каким-то методом, нужно проверить применим ли этот метод.

Стислий опис

Компрютерна програма обчислення розрізаючої множини неорієнтованого корневого графа.

Кореневий граф є трійка (V,E,r) де G = (V,E), корінь r належить V, і для кожного vЄV існує шлях з r в v. Для використання у випадку неорієнтованого кореневого графа алгоритма обчислення його розрізаючої множини граф повинен бути представлений його структурною суміжності. На протязі цього підрозділу всі графи є скінченними і такими, які не мають петель та кратних ребер, якщо неоговорене протилежне.

Гра складається з множини вершин і множини ребер. Надалі позначимо #V – число вершин, #E – число ребер.

Граф може бути орієнтованим, якщо його ребра є орієнтовані пари і неорієнтованим ,коли його ребра є наорієнтовані пари, як позначаємо також через (u,v),

Пакет програм обчислює розрізаючи множину неорієнтованого графа.

Нижче приведена структура пакета програми (функції) на мові Аллегро-ЛІСР обчислення розрізаючої множини неорієнтованого кореневого графа. Мова Аллегро-ЛИСР є модифікацією мови КОММОН_ЛІСП. Пакет обчислення розрізаючої множини неорієнтованого кореневого графа містить наступні функції.

Функція Cutset обчислює розрізаючи множину неорієнтованого кореневого графа, алгоритмм обчислення цієї фцнуції, який базується на ДФС методі, програмна реалізація його, також як і весь пакет, розролені автором даного стислого опису.

Основні завдання програми:

1. Обхід неорієнтованого кореневого графа методом перший пошук у глибину.

2. Обчислення розрізаючої множини неорієнтованого кореневого графа з отриманням результатів в зручній для користувача формі.

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

11.11.2011 Семантические модели данных

Семантическая модель связана с семантикой и семантической моделью.

Семантическая сеть – информационная модель областно-ориентированного графа, вершины которого соответствуют объектам дуги (ребра) задают отношения между ними.

Отношения. Их свойства:

1. Симметричность

2. Транзитивность

3. Рефлективность