МОДЕЛИ И МОДЕЛИРОВАНИЕ

1.

МК
МОДЕЛИ И МОДЕЛИРОВАНИЕ

2.

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

3.

МК
Общие сведения о моделировании
Модель
Моделирование
Натурная модель
Информационная
модель
В информатике
Реальный предмет, в
рассматриваются общие
илиимеет
Новыйуменьшенном
объект, который
подходы
кпознания,
созданию и
Описание
Метод
объекта-оригинала
увеличенном
свойства
данного виде
объекта,
заключающийся
наиспользованию
одном извязыков
создании и
воспроизводящий
существенныевнешний
для
информационных
моделей,
кодирования
исследовании
информации
моделей
вид,
структуру или
поведение
определённого
исследования
связанные с использованием
моделируемого объекта
компьютерной техники.

4.

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

5.

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

6.

МК
Списки, графы, деревья и таблицы
Структуры данных
Линейные
Односвязный список
Стек
Очередь
Нелинейные
Дерево
Граф
Таблица
В англ.
От
Для
Элементы
Множество
англ.
каждого
ячейках
Last
First
элементов
элемента,
In,
In, First
иерархической
содержится
Firstвместе
Out
кроме
Out –
последним
первым
крайних,
сструктуры
информация
набором
пришёл,
есть
отношений
пришёл,
освязаны
предыдущий
первым
свойстве
между
первым
ушёл.
отнопар
и
ушёл. «предок
следующий
шением
ними.
объектов.
элементы.
- потомок».

7.

МК
Списки, графы, деревья и таблицы
Неориентированный Ориентированный
Таблица
Вершина
Ребро
Дуга
Невзвешенный
Вес вершины
19
Вес ребра
Таблица
Граф
Взвешенный
10
8
3
40
17
8
10
3
40
17

8.

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

9.

МК
Списки, графы, деревья и таблицы
A
A
B
+
C
+
B
C
15
+
8
+
D
3
+
+
D
10
+
+
F
F
12
+
5
+
6
+
Такую таблицу называют матрицей
смежности. Матрица смежности неориентированного графа симметрична
относительно главной диагонали. У
ориентированного
графа
такая
симметрия отсутствует.
+
11
+
+
15
A
+
G
G
7
+
+
E
E
+
B
8
3
C
10
7
E
5
D
Дерево
Таблица
Граф
6
12
F
11
G

10.

МК
ЗадачаЗадача
о количестве
дорог дорог
о количестве
Задание 1. Сколько существует различных маршрутов от A до H?
B1
Решение
K(X) – количество
маршрутов от
С
начала до X.
1
K(A)=1
K(B)=K(A)=1
K(C)=K(B)=1
K(D)=K(B)=1
А1
K(E)=K(C)+K(D)=1+1=2
K(G)=K(D)+K(E)=1+2=3
K(F)=K(C)+K(E)+K(G)=1+2+3=6
K(H)=K(G)+K(F)=3+6=9
Ответ: 9
D
G3
1
E
2
H9
F
6

11.

МК
Списки, графы, деревья и таблицы
Задание 2. На рисунке представлена схема дорог, связывающих
населённые пункты A, B, C, D, E, F. В таблице содержатся сведения о
стоимости проезда. На схеме информация об этих же дорогах. Отсутствие
значения означает, что прямого рейса нет. Определить минимальную
стоимость проезда из пункта E в пункт C.
2 3 4 2 1 2
CE B4
B B2
D B3
A B5
B1
F B6
E
5
4
2
2
D
10
5 6
E
3
B
B1
10
A
B
D
B2
9 4
5
D
10
9
4
6
2
B3
C 6 9
B 2
9 2 13С
6
A
B4
4 2
A2
C
C
16
В5
13
F C
4
F 1
14
13
E 1110 5
В6
Ответ:
Выясним
Степени
Каждая
Найдем
По
Осталась
Все
данным
таблице
способы
11из
вершин
вершину
единственная
степень
ввершин
видно,
передвижения
таблице
отметим
A,что
со
каждой
ее
подпишем
вершина
степенями
неустановленная
от
наот
всех
графе
вершины
пункта
вес
Cостальных
иявляется
1,определенных
вE3,
таблице.
до4–вершина
пункта
встречается
число
смежной
отличает
C –можно
ребер,
ребер.
E.вершиной
то,
Вес
один
что
рассмотреть
ребра
соединяющих
раз.
вершина
четырем
BE-10,
Значит,
на
Aа
некоторую
можно
является
вершинам
ребра
дереве
DE-5.
установить
решений.
смежной
–вершину
D, A, FМинимальная
взаимно-однозначное
и
вершиной
сB1.
другими
Вес ребра
для
вершинами.
стоимость
двух
CB –уже
6. соответствие
определенных
при перемещении
между
вершин
ними.
E-D-A-C.
– D и C.

12.

МК
Самое главное
Модель – объект, который имеет свойства данного объекта,
существенные для определённого исследования. Моделирование –
метод познания, заключающийся в создании и исследовании моделей.
Информационная модель – описание объекта-оригинала на одном из
языков кодирования информации.
Информационные модели, реализованные с помощью систем
программирования, ЭТ, специализированных программных средств для
моделирования, называются компьютерными моделями. Компьютерное
моделирование включает в себя процесс реализации информационной
модели на компьютере и исследование с помощью этой модели объекта
моделирования – проведение вычислительного эксперимента.
Между данными информационной модели всегда существуют связи,
определяющие структуру данных. Различают линейные и нелинейные
структуры данных.

13.

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