ГДЗ: Параграф § 10 / Информатика 11 класс

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

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

По форме представления модели делятся на натурные (материальные) и информационные. Информационные, в свою очередь, подразделяются на знаковые, образные и смешанные.

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

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

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

• Исследовать объекты, которые невозможно или нецелесообразно изучать в реальных условиях.
• Проводить многократные эксперименты, меняя условия.
• Находить оптимальные решения без затрат на дорогостоящие образцы.
• Проводить эксперименты без риска негативных последствий.
• Визуализировать получаемые результаты.

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

• Стек — структура типа LIFO, где добавление и удаление элементов происходит с одной стороны (вершины).
• Очередь — структура типа FIFO, где добавление происходит с одной стороны (хвост), а удаление — с другой (голова).

Граф — это множество элементов (вершин) и отношений между ними (ребер или дуг).

• Неориентированный граф — вершины соединены ребрами (без направления).
• Ориентированный граф — вершины соединены дугами (с направлением).
• Взвешенный граф — граф, ребра/дуги или вершины которого характеризуются дополнительной информацией — весами.

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

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

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

Пример: Модель движения тела под действием силы тяжести.

• Объект: Свободно падающее тело.
• Значимые величины: Время \( t \), скорость \( v \), ускорение свободного падения \( g \) (постоянная).
• Форма выражения (функция/уравнение): Зависимость скорости от времени при равноускоренном движении: \( v(t) = v_0 + g t \) (если \( v_0=0 \)).
• Форма выражения (словесно): Скорость свободно падающего тела прямо пропорциональна времени падения (при отсутствии начальной скорости).

• Физика: Модель атома Резерфорда (образная), закон сохранения энергии (математическая модель).
• Химия: Шаростержневая модель молекулы (натурная), уравнение реакции (знаковая модель).
• Биология: Скелет человека (натурная), схема цепи питания (знаковая/образная модель).
• Математика: График функции \( y = \sin(x) \) (графическая/знаковая).
• История: Карта Древнего мира (знаковая/образная).

Цель: Рассчитать необходимое количество обоев для оклейки комнаты.

• Знаковая форма: Формула для вычисления площади стен: \( S = 2 \cdot (a + b) \cdot h \), где \( a \) и \( b \) — длины стен, \( h \) — высота комнаты. Дополнительно — площадь окон и дверей, которые нужно вычесть.
• Графическая форма: Чертеж (план) комнаты с указанием размеров стен, высоты, расположения окон и дверей.

На основе таблицы расстояний (матрицы смежности) необходимо найти кратчайший путь. Таблица симметрична, значит граф неориентированный. Ищем кратчайший путь от \( D \) до \( F \).

• Пути из \( D \): \( D \to E \) (25), \( D \to G \) (25).
• \( D \to E \): \( D \to E \) (25 км). Из \( E \) в \( F \): \( E \to G \) (10), \( E \to F \) (15). Общий путь \( D \to E \to F = 25 + 15 = 40 \) км.
• \( D \to G \): \( D \to G \) (25 км). Из \( G \) в \( F \): \( G \to E \) (10), \( G \to F \) (15). Общий путь \( D \to G \to F = 25 + 15 = 40 \) км.
• Другие пути: \( D \to B \to C \to F \): \( 25 + 10 + 30 = 65 \) км.
• Кратчайший путь \( D \to E \to F \) или \( D \to G \to F \) имеет длину 40 км.

Задача решается методом подсчета путей с начала маршрута, где \( K_X \) — число путей, ведущих в вершину \( X \). \( K_A = 1 \).

• \( K_B = K_A = 1 \) (\( A \to B \)).
• \( K_C = K_A = 1 \) (\( A \to C \)).
• \( K_D = K_A = 1 \) (\( A \to D \)).
• \( K_E = K_B + K_C = 1 + 1 = 2 \) (\( A \to B \to E \); \( A \to C \to E \)).
• \( K_F = K_D = 1 \) (\( A \to D \to F \)).
• \( K_G = K_C + K_F = 1 + 1 = 2 \) (\( A \to C \to G \); \( A \to D \to F \to G \)).
• \( K_H = K_E + K_G = 2 + 2 = 4 \).
• \( K_I = K_H = 4 \).
• \( K_J = K_H + K_I = 4 + 4 = 8 \).

Существует 8 различных путей из города \( A \) в город \( J \).

Используем метод последовательного нахождения минимальных расстояний (алгоритм Дейкстры):

• \( A \) (0).
• Пути из \( A \): \( A \to C \) (3), \( A \to B \) (7), \( A \to D \) (13). Выбираем \( C \) (3).
• Из \( C \) (3): \( C \to D \) (\( 3+16=19 \)). \( D \) остается \( 13 \). Выбираем \( B \) (7).
• Из \( B \) (7): \( B \to D \) (\( 7+9=16 \)). \( D \) остается \( 13 \). \( B \to E \) (\( 7+4=11 \)). Выбираем \( E \) (11).
• Из \( D \) (13): \( D \to E \) (\( 13+1=14 \)). \( E \) остается \( 11 \). \( D \to F \) (\( 13+11=24 \)).
• Из \( E \) (11): \( E \to F \) (\( 11+4=15 \)). \( F \) становится \( 15 \).
• Кратчайший путь от \( A \) до \( F \) имеет длину 15. Путь: \( A \to B \to E \to F \) ( \( 7+4+4=15 \) ).

Используем метод подсчета путей с начала маршрута (рис. 3.10):

• \( K_A = 1 \) (начало).
• \( K_B = K_A = 1 \).
• \( K_C = K_A = 1 \).
• \( K_D = K_A + K_B = 1 + 1 = 2 \).
• \( K_F = K_D = 2 \).
• \( K_E = K_B + K_C = 1 + 1 = 2 \).
• \( K_G = K_C + K_E + K_F = 1 + 2 + 2 = 5 \).

Существует 5 различных путей из города \( A \) в город \( G \).

Пример с муравьями, где они попадают в ямки и вытаскиваются по одному, иллюстрирует принцип работы стека, так как последний муравей, попавший в ямку, будет вытащен первым (LIFO).

Муравьи идут в порядке \( 8, 7, 6, 5, 4, 3, 2, 1 \). После преодоления четырех ямок (4, 2, 5, 1) порядок следования муравьев изменится, так как муравьи будут вытаскиваться в порядке \( 1, 5, 2, 4 \) (порядок 'входа' в ямку, от последних к первым).

Если ямки (4, 2, 5, 1) работают как стек:

• Муравьи \( 8, 7, 6, 5, 4 \) — \( 4 \) попадает в первую ямку (стек).
• \( 3, 2 \) — \( 2 \) попадает во вторую ямку.
• \( 5 \) вытаскивается первым.
• \( 1 \) попадает в четвертую ямку.

Если муравьи, мешающие движению, — это \( 2, 4, 5, 1 \), то они попадают в ямки по очереди.

Правильный порядок муравьев, которые будут идти по тропе после преодоления препятствий, остается 87653, а муравьи из ямок \( 4, 2, 5, 1 \) будут выходить в порядке 1, 5, 2, 4 (если ямка — это стек).