Использование графов | Сетевые модели (11_68_pol) (68 часов в уч. год)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, сокращённый курс, по 2 часа в неделю)


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



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

Введение

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

Диаграммы

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

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

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

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

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

Задачи с 1 по 8

Задачи с 9 по 16


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


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

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

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

Рис. 2.10

Рис. 2.10

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

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

Рис. 2.11

Рис. 2.11

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

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

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



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







Наверх