Глава 3. Информационное моделирование
Давай разберемся, как устроен мир информационного моделирования — один из самых мощных инструментов для понимания сложных систем вокруг нас.
Моделирование помогает понять сложные системы через упрощение
§ 10. Модели и моделирование
Зачем вообще нужны модели?
Представь: ты хочешь понять, как работает новая игра, не потратив сотни часов на её прохождение. Или тебе нужно спрогнозировать, как поведет себя алгоритм рекомендаций YouTube при изменении параметров. Или ты разрабатываешь приложение и хочешь понять структуру данных до того, как напишешь первую строку кода.
Во всех этих случаях ты создаешь модель — упрощенное представление объекта, которое сохраняет его ключевые свойства, важные для твоей задачи.
💡 Ключевая идея
Модель — это не копия объекта, а его "проекция" под определенным углом зрения. Архитектурный макет здания не показывает, какие обои будут в комнатах, зато отлично демонстрирует пространственную структуру.
📚 Основные понятия
- Модель — это новый объект, который имеет свойства данного объекта, существенные для определённого исследования
- Моделирование — метод познания, заключающийся в создании и исследовании моделей
- Натурная (материальная) модель — реальный предмет, в уменьшенном или увеличенном виде воспроизводящий внешний вид, структуру или поведение моделируемого объекта
- Информационная модель — описание объекта-оригинала на одном из языков кодирования информации
🤔 Подумай!
Приведи примеры моделей, с которыми ты встречался на уроках физики, химии, биологии, истории, математики, обществознания, литературы.
Компьютерное моделирование: от идеи до эксперимента
Компьютерное моделирование — это когда информационная модель реализована с помощью программных средств (языков программирования, электронных таблиц, специализированных пакетов). Это не просто создание модели, но и проведение с ней вычислительного эксперимента.
🌟 Интересный парадокс
С помощью компьютерного моделирования мы можем исследовать то, чего еще не существует (прототипы технологий), что уже прошло (исторические процессы) или что невозможно воспроизвести в реальности (поведение черной дыры, эволюция экосистем).
Этапы компьютерного моделирования
Давай разберем, как создается компьютерная модель — это не хаотичный процесс, а четкая последовательность шагов:
┌─────────────────────────────────────────┐
│ 1. Постановка задачи и её анализ │
│ ↓ Что моделируем? Зачем? │
└─────────────────────────────────────────┘
↓
┌─────────────────────────────────────────┐
│ 2. Построение информационной модели │
│ ↓ Какие параметры важны? Как связаны?│
└─────────────────────────────────────────┘
↓
┌─────────────────────────────────────────┐
│ 3. Разработка компьютерной модели │
│ ↓ Выбор средств, создание программы │
└─────────────────────────────────────────┘
↓
┌─────────────────────────────────────────┐
│ 4. Компьютерный эксперимент │
│ ↓ Тестирование, эксперименты │
└─────────────────────────────────────────┘
↓
┌─────────────────────────────────────────┐
│ 5. Анализ результатов эксперимента │
│ ↓ Выводы, принятие решений │
└─────────────────────────────────────────┘Постановка задачи
Определяем объект моделирования и цель. Например: "Смоделировать распространение вируса в соцсети, чтобы понять, как быстро виральный пост наберет 1 млн просмотров".
Информационная модель
Выделяем параметры (количество подписчиков, вероятность репоста, время активности пользователей) и связи между ними (чем больше подписчиков, тем выше охват).
Компьютерная модель
Выбираем инструмент (Python с библиотеками для графов, электронные таблицы, специализированные симуляторы) и реализуем алгоритм.
Эксперимент
Сначала тестируем на известных данных, потом меняем параметры и наблюдаем за поведением модели. На этом этапе может выясниться, что модель нужно уточнить — и мы возвращаемся к предыдущим шагам.
Анализ
Делаем выводы и принимаем решение на основе полученных данных.
Метафора распространения информации: как виральный контент "заражает" сеть, двигаясь от узла к узлу
✨ Возможности компьютерного моделирования
Компьютерное моделирование даёт возможность:
- Существенно расширить круг исследуемых объектов (моделирование прошлого и будущего, несуществующего или невоспроизводимого в реальных условиях)
- Исследовать процессы в развитии, при необходимости ускоряя или замедляя их и проводя эксперименты многократно
- Находить оптимальные решения без затрат на изготовление пробных экземпляров
- Проводить эксперименты без риска негативных последствий для здоровья человека или окружающей среды
- Визуализировать получаемые результаты
Структуры данных: как организовать информацию
Между данными в модели всегда существуют связи, которые определяют структуру данных. Понимание структур — ключ к эффективному моделированию.
Линейные структуры
📝 Список
Линейный односвязный список — последовательность элементов, где каждый "знает" адрес следующего. Можно добавлять и удалять элементы в любом месте.
В линейном списке для каждого элемента, кроме первого, есть предыдущий элемент; для каждого элемента, кроме последнего, есть следующий элемент.
📚 Стек (LIFO)
Стек — последовательность, в которой включение и исключение элементов осуществляются с одной и той же стороны (Last In, First Out — последним пришёл, первым ушёл).
Примеры: стопка блинов, история браузера, отмена действий (Ctrl+Z), вызовы функций в программе
👥 Очередь (FIFO)
Очередь — последовательность, у которой включение элементов производится с одной стороны (хвост), а исключение — с другой (голова). First In, First Out — первым пришёл, первым ушёл.
Примеры: очередь в столовой, очередь печати документов, обработка запросов на сервере
🤔 Подумай!
Какая связь между стеком и следующими объектами: стопка тарелок, стопка книг, игрушка-пирамидка?
Почему стек является структурой типа LIFO? Почему очередь является структурой типа FIFO?
Нелинейные структуры
Примеры нелинейных структур данных — это графы и деревья.
🕸️ Граф
Граф — это множество элементов (вершин графа) вместе с набором отношений между ними.
Граф является многосвязной структурой, обладающей следующими свойствами:
- На каждый элемент может быть произвольное количество ссылок
- Каждый элемент может иметь связь с любым количеством других элементов
- Каждая связка может иметь направление и вес
Термины:
- Ребро — ненаправленная линия (без стрелки), соединяющая вершины
- Дуга — направленная линия (со стрелкой)
- Неориентированный граф — вершины соединены рёбрами
- Ориентированный граф — вершины соединены дугами
- Взвешенный граф — вершины или рёбра характеризуются дополнительной информацией (весами)
Примеры графов: карта метро, социальные сети, интернет, граф зависимостей в npm/pip, вычислительная сеть, транспортная система, схема авиалиний
Графовая структура: от карты метро до нейронных сетей — универсальный язык связей
🌳 Дерево
Дерево — это совокупность элементов (вершин), в которой выделен один элемент (корень), а остальные элементы разбиты на непересекающиеся множества (поддеревья).
Каждое поддерево является деревом, а его корень является потомком корня дерева, т. е. все элементы связаны между собой отношением «предок — потомок». В результате образуется иерархическая структура вершин.
Бинарное дерево — частный случай дерева, в котором каждая вершина может иметь не более двух потомков.
Примеры деревьев: файловая система компьютера, генеалогическое древо, дерево решений в играх, структура HTML-документа (DOM), дерево вызовов функций
🤔 А что, если посмотрим на это с другой стороны?
Почему дерево — это специальный случай графа, а не наоборот? Попробуй сформулировать условие, при котором граф становится деревом.
Таблицы: универсальный формат
Таблица — структура из строк и столбцов (граф), ячейки которой хранят данные. Это самый универсальный способ представления информации.
⚡ Важный факт
Любую структуру данных (даже граф!) можно представить в табличной форме. Это критично для компьютерной обработки, так как базы данных и электронные таблицы работают именно с табличными структурами.
Оформление таблиц
Таблицы состоят из строк и граф (столбцов, колонок), пересечение которых образуют ячейки. Таблицы применяют для наглядности и удобства сравнения показателей.
Таблица _______ — _____________________
номер название таблицы
┌────────┬─────────────────────────────┐
│Головка │ │ } Заголовки граф
│ ├──────┬──────┬──────┬────────┤
│ │ │ │ │ │ } Подзаголовки граф
├────────┼──────┼──────┼──────┼────────┤
│ │ │ │ │ │
│ │ │ │ │ │ } Строки
│ │ │ │ │ │ (горизонтальные ряды)
└────────┴──────┴──────┴──────┴────────┘
↑ ↑
Боковик Графы
(графа для (колонки)
заголовков)📋 Правила оформления таблиц
- Название таблицы должно отражать её содержание, быть точным, кратким. Название помещают над таблицей
- Заголовки граф и строк пишут с прописной буквы, подзаголовки — со строчной, если они составляют одно предложение с заголовком
- В конце заголовков и подзаголовков точки не ставят
- Заголовки и подзаголовки граф указывают в единственном числе
- Если все показатели выражены в одной единице величины, её обозначение помещают над таблицей справа
Типы таблиц
"Объект — свойство"
Содержат информацию о свойствах отдельных объектов, принадлежащих одному классу. Строки — объекты, столбцы — их свойства.
Пример: таблица характеристик смартфонов (модель, процессор, RAM, цена)
"Объект — объект"
Содержат информацию о некотором одном свойстве пар объектов, принадлежащих одному или разным классам.
Пример: таблица расстояний между городами
Двоичные матрицы
Таблицы, в которых отражено наличие или отсутствие связей между отдельными элементами некоторой системы.
Пример: матрица смежности графа
🤔 Подумай!
Приведи примеры таблиц типа «объект — свойство», «объект — объект», отражающих не только количественные, но и качественные характеристики свойств (двоичные матрицы).
Практические примеры: от графа к таблице и обратно
Пример 1: Матрица смежности
Построим таблицу, соответствующую неориентированному графу, отражающему схему дорог между населёнными пунктами A, B, C, D.
Граф дорог
Вершины A, B, C, D соединены рёбрами с весами (расстояниями):
- A-B: 7
- A-C: 6
- B-C: 9
- C-D: 13
Матрица смежности
A B C D
A – 7 6 –
B 7 – 9 –
C 6 9 – 13
D – – 13 –Замечаешь симметрию? Это признак неориентированного графа
📝 Как строится матрица смежности
Строки и столбцы таблицы соответствуют вершинам графа. Если две вершины являются смежными (соединены ребром), в ячейку записывается вес этого ребра. Если вершины не смежны — ставится 0 (или знак минус для большей наглядности).
Пример 2: От дерева к таблице
Обед в школьной столовой состоит из двух блюд и напитка. На первое — щи или окрошка, на второе — плов или пельмени, на третье — сок или компот.
Таблица вариантов обеда
Вариант Напиток 2-е блюдо 1-е блюдо
───────────────────────────────────────────────
Вариант 1 Сок Плов Щи
Вариант 2 Компот Плов Щи
Вариант 3 Сок Пельмени Щи
Вариант 4 Компот Пельмени Щи
Вариант 5 Компот Плов Окрошка
Вариант 6 Сок Плов Окрошка
Вариант 7 Компот Пельмени Окрошка
Вариант 8 Сок Пельмени ОкрошкаПолучилась таблица типа «объект — свойство»: объектами являются варианты обеда, а свойствами — составляющие его блюда. Число граф в таблице соответствует числу уровней в дереве.
🤔 Подумай!
Сколько всего вариантов обеда возможно, если на первое 2 варианта, на второе 2, на третье 2? А если вариантов больше?
Пример 3: Поиск кратчайшего пути
Найдём кратчайший путь от вершины A до вершины F в ориентированном графе.
Стратегия решения
При решении класса задач, связанного с нахождением кратчайшего пути в ориентированном графе, можно:
- От исходного графа перейти к матрице смежности
- По матрице смежности построить дерево решений
- По дереву решений выбрать подходящий вариант
Лабиринт выбора: среди множества путей всегда существует оптимальный
Пример 4: Считаем количество путей
На схеме дорог, связывающих города A, B, C, D, E, F, G, можно двигаться только по стрелкам. Сколько разных путей существует из города А в город G?
Метод 1: Дерево вариантов
По графу построить матрицу смежности, на её основе построить дерево, корнем которого будет вершина А. Число листьев = число дорог из A в G.
Метод 2: Счёт с конца
Пусть KX — число путей из A в город X.
Считаем с конца маршрута. Если в G есть дороги из C, E, F, то:
KG = KC + KE + KFМетод 3: Счёт с начала
Считаем пути с начала маршрута, помечая на графе количество способов добраться в каждую вершину. Более элегантный подход!
🤔 Сможешь придумать аналогию?
Как можно объяснить процесс подсчета путей через метафору распространения сигнала или воды по сети?
Ключевые выводы
Что важно запомнить из этого раздела
🤔 Проверь себя
Вопросы и задания для самопроверки
1. Мини-кейс: Система рекомендаций музыки
Ты разрабатываешь систему рекомендаций музыки. Какую структуру данных ты бы выбрал для хранения связей "пользователь слушает исполнителя"? Почему?
Подсказка: подумай о графах и таблицах.
2. Мысленный эксперимент: Граф перемещений
Представь граф твоих ежедневных перемещений (дом, школа, секции, магазин). Будет ли это дерево или граф общего вида? Почему?
3. Практическая задача: Определение цикла
Опиши алгоритм, который определит, есть ли цикл в графе (можно ли вернуться в исходную точку, двигаясь по ребрам).
4. Аналогия: Стек и очередь
Как бы ты объяснил младшему брату/сестре, чем стек отличается от очереди, используя только примеры из повседневной жизни?
5. Применение матрицы смежности
Где в реальной жизни можно встретить применение матрицы смежности?
Подсказка: подумай о расписаниях, маршрутах, зависимостях между задачами в проекте.
6. Что такое модель и моделирование?
Приведи примеры моделей, с которыми ты встречался на уроках физики, химии, биологии, истории, математики.
7. Этапы компьютерного моделирования
Опиши основные этапы компьютерного моделирования. Почему этот процесс может быть циклическим?
8. Линейные структуры данных
Приведи примеры линейных структур данных. Чем очередь отличается от стека?
9. Графы и деревья
Что такое граф? Какой граф называется ориентированным? Неориентированным? Взвешенным?
Что такое дерево? Какое дерево называется бинарным?
10. Табличное представление данных
Почему табличное представление данных является универсальным и предпочтительным для компьютерной обработки?
✍️ Практические задания
Задание 1: Муравьи и ямки
Муравьи идут друг за другом по тропе. На их пути встречаются ямки, в которые могут провалиться несколько муравьёв. Когда ямка заполняется, остальные проходят через неё, а затем по одному вытаскивают провалившихся.
Вопрос: Пусть по тропе идут 8 муравьёв. В каком порядке они будут идти после преодоления участка с четырьмя ямками, вмещающими 2, 4, 5 и 1 муравья соответственно?
Какую структуру данных иллюстрирует данный пример?
Задание 2: Обратная польская запись
Выясни, что представляет собой обратная польская запись, и вычисли значение выражения:
1 2 + 3 × 4 5 × +Задание 3: Генеалогическое древо
Информация о родственных связях представлена в виде:
parent(Юрий, Пётр)
parent(Анна, Ева)
parent(Ирина, Георгий)
...Запись parent(A, B) означает, что А является родителем В.
Задание: Нарисуй генеалогическое древо этой семьи. Сколько у Ирины племянников и племянниц?
Задание 4: Ёлочные игрушки
В кладовке хранятся игрушки — большие и маленькие красные и золотые шары и звёзды. Игрушки разного размера, цвета и формы хранятся в отдельных коробках.
Известно:
- Нет маленьких шаров и маленьких золотых звёзд
- Всего звёзд 25, шаров — 17
- Больших игрушек — 32; красных — 28
- Золотых звёзд на 2 больше, чем золотых шаров
Вопрос: В скольких коробках хранятся игрушки? Сколько игрушек в каждой коробке?
Построй граф и используй его для решения. Представь информацию в табличной форме.
Задание 5: Задача о мальчиках
Ваня, Кирилл, Петя и Саша учатся в 5, 6, 7 и 8 классах. Как-то они отправились в лес за грибами.
Факты:
- Шестикласснику не повезло — он не нашёл ни одного гриба
- Петя с пятиклассником нашли много грибов
- Ваня и семиклассник нашли куст малины и позвали Кирилла
- Восьмиклассник, шестиклассник и Кирилл объясняли Саше, как ориентироваться
Вопрос: В каком классе учится каждый из мальчиков?
Составь двоичную матрицу для решения.
Задание 6: Кратчайший путь
Найди кратчайший путь от вершины А до вершины F в ориентированном графе с заданными весами рёбер.
Метод:
- Построй матрицу смежности
- Построй дерево решений
- Найди оптимальный путь
Задание 7: Подсчёт путей
На схеме дорог, связывающих города A, B, C, D, E, F, G, H, I, J, можно двигаться только по стрелкам.
Вопрос: Сколько разных путей существует из города А в город J?
Используй один из трёх методов: дерево вариантов, счёт с конца или счёт с начала.
Задание 8: Соответствие графа и таблицы
Дана схема дорог и таблица с их длинами. Схему и таблицу создавали независимо, поэтому используются разные обозначения.
Задание: Выясни длину пути из пункта E в пункт F.
Подсказка: сравни степени вершин в графе с количеством дорог в таблице.
