Модели и моделирование. Структуры данных

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

Чему ты научишься. различать структуры данных — список, стек, очередь, граф, дерево — и понимать, чем они отличаются.

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

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

Список, стек, очередь

Линейный список — упорядоченный набор элементов. Два важных частных случая:

СТЕК (LIFO — последним пришёл, первым ушёл):
   │ 3 │← вершина: кладём и берём с одного конца
   │ 2 │   как стопка тарелок
   │ 1 │

ОЧЕРЕДЬ (FIFO — первым пришёл, первым ушёл):
   вход → [1][2][3] → выход   кладём в конец, берём из начала

Граф и дерево

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

ГРАФ:  (A)──(B)        Матрица смежности:
        │  ╱             A B C
       (C)            A  0 1 1
  рёбра A-B, A-C      B  1 0 0   (1 — есть ребро, 0 — нет)
                      C  1 0 0

Контрольный вопрос. Структура данных, где элемент кладут и берут с одного конца (как стопка тарелок), — это…

Астек

Бочередь

Подсказка: Найди в ASCII-схеме этого урока подпись рядом с рисунком стопки.

Онлайн-проверка ответа появится позже

Контрольный вопрос. Упрощённый заменитель объекта, который используют для его исследования, называется ______. Впиши слово.

Подсказка: Например, глобус — это … Земли.

Онлайн-проверка ответа появится позже

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

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

Бструктурой данных

Вматрицей смежности

Подсказка: Одно из слов ответа уже есть в самой формулировке вопроса.

Онлайн-проверка ответа появится позже

Контрольный вопрос. Набор вершин, соединённых рёбрами, называется…

Аграф

Бдерево

Всписок

Подсказка: У дерева тоже есть вершины и рёбра, но в этой структуре допустимы и замкнутые пути (циклы).

Онлайн-проверка ответа появится позже

Контрольный вопрос. Способ записи связей графа в виде таблицы из нулей и единиц называется матрицей ______. Впиши слово.

Подсказка: Единица в ячейке означает, что между вершинами ЕСТЬ ребро.

Онлайн-проверка ответа появится позже

Контрольный вопрос. Граф без замкнутых путей, с корнем, называется…

Адерево

Бматрица

Подсказка: Ветвится от корня.

Онлайн-проверка ответа появится позже

Контрольный вопрос. Структура «первым пришёл — первым ушёл» (как очередь в магазине) называется…

Аочередь

Бстек

Подсказка: Посмотри в схему урока — там подписаны вход и выход этой структуры.

Онлайн-проверка ответа появится позже

Контрольный вопрос. У графа между вершинами A и Б есть ребро только в направлении от A к Б (не наоборот). Такой граф называется…

Аориентированный

Бвзвешенный

Вбинарное дерево

Подсказка: Обрати внимание на слово «направление» — у таких рёбер есть стрелка.

Онлайн-проверка ответа появится позже

Контрольный вопрос. У рёбер графа дорог между городами указано расстояние в километрах. Такой граф называется…

Авзвешенный

Бориентированный

Вбинарное дерево

Подсказка: У каждого ребра есть число — вес (расстояние, стоимость и т.п.).

Онлайн-проверка ответа появится позже

Задание. Придумай сеть из минимум 4 объектов, которые связаны друг с другом (например, друзья в соцсети, станции метро или страницы сайта со ссылками).
1) Опиши свои объекты как вершины графа и связи между ними как рёбра (перечисли минимум 4 ребра).
2) Построй для своего графа матрицу смежности.
3) Определи, является ли твой граф деревом (нет ли в нём замкнутых путей) — объясни, почему да или нет.

Подсказка: Вершины — это объекты, рёбра — связи между ними; в матрице смежности 1 — есть ребро, 0 — ребра нет; дерево — граф БЕЗ замкнутых путей, с корнем.

Онлайн-проверка ответа появится позже

Итог. Компьютерное моделирование — исследование объекта через его модель на компьютере, а данные для неё хранят в структурах данных. Стек работает по правилу «последним пришёл — первым ушёл», очередь — наоборот. Граф — это вершины, соединённые рёбрами, а дерево — граф без замкнутых путей, с корнем.

Что дальше

Графы — не просто картинки: на них решают серьёзные задачи. О моделировании на графах следующий урок.

← Назад  ·  ↑ В начало урока  ·  ⌂ В начало курса  ·  Вперёд →