Модели и моделирование

Общие сведения о моделировании

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

Из курса информатики основной школы вам известно, что:

• модель — это новый объект, который имеет свойства данного объекта, существенные для определённого исследования;
• моделирование — метод познания, заключающийся в создании и исследовании моделей;
• натурная (материальная) модель — реальный предмет, в уменьшенном или увеличенном виде воспроизводящий внешний вид, структуру или поведение моделируемого объекта;
• информационная модель — описание объекта-оригинала на одном из языков кодирования информации;
• по форме представления можно выделить знаковые, образные и смешанные информационные модели;
• для создания информационной модели объекта необходимо:

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

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

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

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

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

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

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

С помощью компьютерного моделирования решаются многие научные и производственные задачи:

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

Рассмотрим основные этапы компьютерного моделирования более подробно (рис. 3.1).

Рис. 3.1. Основные этапы компьютерного моделирования

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

На втором этапе определяются параметры модели и связи между ними; приводится математическое описание зависимостей между параметрами модели.

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

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

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

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

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

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

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

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

Различают линейные и нелинейные структуры данных.

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

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

Ещё одним частным случаем линейного односвязного списка является очередь — последовательность, у которой включение элементов производится с одной стороны последовательности, а исключение — с другой. Сторона, где происходит включение элементов, называется хвостом; сторона, где происходит исключение, — головой. Понятие очереди как структуры данных очень близко к бытовому понятию «очередь» (рис. 3.2).

Рис. 3.2. Иллюстрация понятия «очередь»

Подумайте, какая связь между стеком и следующими объектами:

Примеры нелинейных структур данных вам также хорошо известны — это графы и деревья (рис. 3.3).

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

Рис. 3.3. Примеры графовых структур

Граф является многосвязной структурой, обладающей следующими свойствами:

1) на каждый элемент может быть произвольное количество ссылок;
2) каждый элемент может иметь связь с любым количеством других элементов;
3) каждая связка может иметь направление и вес.

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

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

 Одной из разновидностей графа является дерево.

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

Частным случаем дерева является бинарное дерево, в котором каждая вершина может иметь не более двух потомков.

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

Ещё одной знакомой вам структурой данных являются таблицы, состоящие из строк и граф (столбцов, колонок), пересечение которых образуют ячейки. Таблицы применяют для наглядности и удобства сравнения показателей.

Оформляют таблицы в соответствии с рисунком 3.4.

Рис. 3.4. Оформление таблицы

Название таблицы, при его наличии, должно отражать её содержание, быть точным, кратким. Название следует помещать над таблицей.

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

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

Эти и другие требования к оформлению таблиц содержатся в ГОСТ 2.105-95 «ЕСКД. Общие требования к оформлению текстовых документов».

В курсе информатики основной школы вы познакомились с таблицами типа:

• «объект — свойство», содержащими информацию о свойствах отдельных объектов, принадлежащих одному классу;
• «объект — объект», содержащими информацию о некотором одном свойстве пар объектов, принадлежащих одному или разным классам.

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

Вспомните и приведите примеры таблиц типа «объект — свойство», «объект — объект», отражающих не только количественные, но и качественные характеристики свойств (двоичные матрицы).

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

Списки, графы, деревья и таблицы (продолжение)

Пример 1. Построим таблицу, соответствующую неориентированному графу (рис. 3.5), отражающему схему дорог между некоторыми населёнными пунктами.

Рис. 3.5. Граф схемы дорог

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

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

Матрица смежности неориентированного графа симметрична относительно главной диагонали, идущей от левого верхнего угла к правому нижнему углу. У матрицы смежности неориентированного графа такая симметрия отсутствует.

Пример 2. Обед в школьной столовой состоит из двух блюд и напитка. На первое можно выбрать щи или окрошку, на второе — плов или пельмени, на третье — сок или компот. Все возможные варианты представлены с помощью дерева на рисунке 3.6.

Рис. 3.6. Дерево вариантов обеда

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

Получилась таблица типа «объект-свойства»: объектами в ней являются варианты обеда, а свойствами — составляющие его блюда. При этом число граф в полученной таблице соответствует числу уровней в дереве.

При решении класса задач, связанного с нахождением кратчайшего пути в ориентированном графе, можно:

1) от исходного графа перейти к матрице смежности;
2) по матрице смежности построить дерево решений;
3) по дереву решений выбрать подходящий вариант.

Пример 3. Найдём кратчайший путь от вершины А до вершины F в графе, приведённом на рисунке 3.7.

Рис. 3.7. Ориентированный граф

Составим матрицу смежности, соответствующую данному ориентированному графу:

По матрице смежности построим полное дерево перебора решений — рисунок 3.8.

Рис. 3.8. Полное дерево перебора решений

На рисунке 3.8 видно, что кратчайший путь из вершины А в вершину F равен 17 и имеет вид A-B-E-F.

Пример 4. На рисунке 3.9 представлена схема дорог, связывающих города А, Б, С, D, Е, F, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько разных путей существует из города А в город G?

Рис. 3.9. Схема дорог.

Существует несколько способов решения этой задачи. Рассмотрим их.

Вариант 1. По графу можно построить матрицу смежности, а на её основе построить дерево, корнем которого будет служить вершина А. Число листьев построенного дерева будет равно числу дорог из города А в город G.

Постройте дерево и подсчитайте число дорог из города А в город G самостоятельно.

Вариант 2. Пусть Кх — число путей из города А в город X.

Начнем считать число путей с конца маршрута. Так как в город G есть дороги из городов С, E, F, то K_G = К_C + К_Е + K_F.

В свою очередь К_C = 1 + K_D = 1 + 1 = 2, К_Е = К_B + K_C =1 + 2 = 3, К_F = K_C = 2.

Таким образом, K_G = 2 + 3 + 2 = 7.

Вариант 3. Можно считать число путей с начала маршрута. При этом процесс подсчёта удобно изображать на самом графе — рисунок 3.10.

Рис. 3.10. Схема дорог с подсчётом числа путей

Пример 5. На рисунке 3.11 представлена схема дорог, связывающих населённые пункты А, В, С, D, Е, F, G. В таблице содержатся сведения о длинах этих дорог (в километрах). Схему и таблицу создавали независимо друг от друга, поэтому в них используются разные обозначения. Необходимо выяснить длину пути в километрах из пункта D в пункт F.

Рис. 3.11. Схема дорог и таблица их длин

Рассмотрим имеющийся граф и выясним степень каждой вершины — число рёбер, соединяющих некоторую вершину с другими вершинами. Получим:

На основании имеющейся таблицы мы также можем сделать выводы о том, сколькими дорогами соединён тот или иной населённый пункт с другими населёнными пунктами:

Сопоставив полученную информацию, можем сказать, что через Г1 в таблице обозначен населённый пункт F, а через Г7 — D. Согласно таблице, расстояние между этими пунктами равно 25 км.

САМОЕ ГЛАВНОЕ

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

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

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

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

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

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

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