Краткое содержание: Параграф § 10 / Информатика 11 класс

Основные понятия моделирования

Человечество постоянно стремится к познанию окружающего мира: его объектов, процессов и явлений. Для этого используются модели – новые объекты, отражающие существенные свойства оригиналов для конкретного исследования. Моделирование – это метод познания, включающий создание и изучение моделей. Различают натурные (материальные), которые физически воспроизводят оригинал (в уменьшенном или увеличенном виде), и информационные модели, представляющие описание объекта-оригинала на языке кодирования информации. Информационные модели делятся на знаковые, образные и смешанные. Для построения информационной модели необходимо определить цель, а также выделить свойства объекта-оригинала, соответствующие этой цели.

Компьютерное моделирование

Информационные модели, реализованные с помощью программного обеспечения (систем программирования, электронных таблиц и т.д.), называются компьютерными моделями. Компьютерное моделирование – это процесс реализации информационной модели на компьютере и её исследование путем проведения вычислительных экспериментов. Компьютерное моделирование применяется для решения многих задач, включая прогнозирование погоды, климатических изменений, конструирование транспортных систем, создание лекарственных препаратов, стратегическое управление организациями, прогнозирование цен, а также исследование поведения зданий и конструкций.

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

Процесс компьютерного моделирования включает следующие основные этапы:

• Постановка задачи и её анализ: Определение объекта моделирования, цели создания модели, ожидаемых результатов и исходных данных. Выделение параметров объекта и целей.
• Построение информационной модели: Определение параметров и связей между ними, математическое описание зависимостей.
• Разработка компьютерной модели: Выбор или разработка алгоритма, подбор программных средств и реализация алгоритма на компьютере.
• Компьютерный эксперимент: Тестирование модели на известных данных для проверки правильности. Проведение целенаправленного эксперимента, сознательное изменение условий и сбор данных о поведении модели.
• Анализ результатов эксперимента: Анализ полученных результатов, формулирование выводов о моделируемом объекте и принятие решения.

Компьютерное моделирование дает возможность исследовать объекты, проводить многократные эксперименты без риска, находить оптимальные решения и визуализировать результаты.

Списки, графы, деревья и таблицы как структуры данных

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

• Линейный односвязный список: Последовательность связанных элементов, где разрешены операции добавления и удаления элемента в произвольном месте.
• Стек: Линейный односвязный список, в котором включение и исключение элементов происходит только с одной стороны (вершины). Работает по принципу LIFO (Last In, First Out – последний пришел, первый ушел).
• Очередь: Линейный односвязный список, где включение элементов происходит с одной стороны (хвост), а исключение – с другой (голова). Работает по принципу FIFO (First In, First Out – первый пришел, первый ушел).

Примеры нелинейных структур данных:

• Граф: Множество элементов (вершин) вместе с набором отношений между ними (ребер для неориентированного графа или дуг для ориентированного). Графы могут быть взвешенными, если ребра/дуги имеют дополнительную информацию (веса).
• Дерево: Разновидность графа, иерархическая структура с выделенным одним элементом (корнем), где остальные элементы разбиты на непересекающиеся множества (поддеревья). Дерево используется для представления родственных связей (генеалогическое древо) или для анализа стратегии в играх.

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

Применение структур данных для решения задач на графах

Задачи на графах, такие как нахождение кратчайшего пути (Пример 3) или подсчет количества путей (Пример 4) между двумя вершинами, могут быть решены с помощью следующих методов:

• Построение дерева перебора решений: На основе исходного графа строится дерево, где каждый путь от корня до листа соответствует одному из возможных вариантов (например, маршрутов). Число листьев в построенном дереве будет равно числу путей.
• Использование матрицы смежности: Матрица смежности позволяет систематизировать данные о связях и переходах. Для нахождения кратчайшего пути в взвешенном графе применяется, например, модифицированный алгоритм Дейкстры.
• Метод подсчета с начала или с конца: Число путей до вершины \( X \) (\( K_X \)) можно вычислить как сумму путей, приходящих в эту вершину из всех смежных с ней вершин \( Y_i \):\[ K_X = \sum K_{Y_i} \]