Моделирование и графы

Слайд 1. Моделирование и графы

Основы информационного моделирования и структуры данных для 9 класса

Слайд 2. Понятие модели

Модель — это объект-заменитель, который отражает существенные для решаемой задачи свойства оригинала.

Моделирование необходимо, когда оригинал слишком велик, мал, опасен или дорог для прямого исследования.

Слайд 3. Типы моделей

Предметные копии объектов: макет здания, глобус, модель автомобиля.

Описания объектов и процессов в виде текста, схем, таблиц, формул или графов.

Информационные модели, созданные и исследуемые с помощью компьютерных программ.

Слайд 4. Задачи моделирования

Представление объектов реальности в цифровом виде

Исследование свойств и поведения системы

Прогнозирование развития процессов

Управление объектом на основе полученных данных

Слайд 5. Этапы компьютерного моделирования

Этап 1

Этап 2

Этап 3

Этап 4

Постановка задачи и описание свойств

Формализация (математическая модель)

Разработка алгоритма и программы

Компьютерный эксперимент и анализ

Слайд 6. Математическая модель

Математическая модель — это описание объекта или процесса на языке математики с помощью формул, уравнений и неравенств.

Примеры:

— Формула пути: $s=v\cdot t$

— Второй закон Ньютона: $F=m\cdot a$

— Модель стоимости покупки: $C=p\cdot n$

Слайд 7. Понятие графа

Граф — это математическая модель, состоящая из вершин и рёбер, которые показывают связи между объектами.

Слайд 8. Ориентированный граф

Связи между вершинами имеют направление, которое обозначается стрелками. Такие связи называют дугами.

Пример: схема одностороннего движения дорог.

Слайд 9. Пример ориентированного взвешенного графа

Слайд 10. Неориентированный граф

В неориентированном графе рёбра не имеют направления. Если вершины $A$ и $B$ соединены ребром, по этой связи можно двигаться в обе стороны.

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

Слайд 11. Весовая матрица графа

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

Слайд 12. Поиск оптимального пути

Оптимальным считается путь с минимальным суммарным весом ребер.

Основные методы:

— Метод простого перебора

— Алгоритм Дейкстры

— Динамическое программирование

Слайд 13. Пути в ациклическом графе

В направленном ациклическом графе (DAG) количество путей в вершину $X$ вычисляется как сумма количеств путей во все вершины, из которых ведут стрелки в $X$.

Это позволяет быстро считать общее число маршрутов без их прямого перечисления.

Слайд 14. Понятие дерева

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

Деревья используют для представления иерархий: файловой системы, структуры организации, родословной или меню сайта.

Слайд 15. Структура дерева

Корень — вершина, не имеющая предков

Узел — вершина, имеющая потомков

Лист — вершина без потомков

Ребро — связь между узлами

Высота — максимальное количество уровней

Слайд 16. Перебор вариантов с помощью дерева

Начальное состояние задачи или первый выбор.

Все возможные варианты действий на каждом этапе.

Конечные результаты или комбинации.

Слайд 17. Основные выводы

Модель — упрощенное представление реальности для решения задач.

Графы позволяют визуализировать связи между объектами.

Деревья — частный случай графа для описания иерархий.

Математическая модель — основа для компьютерных вычислений.