Урок 8
Использование графов
(§7. Системный подход в моделировании)

Содержание урока

Введение

Табличные модели

Диаграммы

Диаграммы. Задачи 1 и 2

Иерархические модели

Сетевые модели

Игровые стратегии

Вопросы и задания

Задачи с 1 по 8

Задачи с 9 по 16

Сетевые модели

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

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

Сетевые модели широко применяются для планирования производства, есть даже специальный термин «сетевое планирование». Предположим, что изготовление аппарата МУХ-8-ККВ включает 8 операций, причём некоторые из них можно выполнять одновременно. Чтобы определить время изготовления, строят схему (граф, сеть), на которой узлы обозначают события (когда можно начинать очередную операцию), дуги — работы, а числа около дуг (веса) — длительность этих работ, например, в днях (рис. 2.10).

Рис. 2.10

По этой схеме видно, что в самом начале можно выполнять три работы параллельно. Чтобы начать работу Г-Д, нужно закончить работы А-Г и Б-Г, на это требуется 5 дней. Чтобы выполнить последнюю операцию и получить готовое изделие, нужно закончить работы Г-Д и В-Д, на это требуется 8 дней. Поэтому аппарат будет готов только через 9 дней с момента начала работ.

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

Рис. 2.11

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

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

Следующая страница Игровые стратегии

Cкачать материалы урока