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

стол); физические , химические , биологические процессы, метеорологические явления (гроза, смерч); экономические и социальные процессы.

системе.

цели моделирования признаки изучаемого предмета, процесса или явления.

Моделирование – метод познания, заключающийся в создании и исследовании моделей.

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

По способу реализации информационные модели делятся на компьютерные и некомпьютерные.

своим составом и назначением.
Их называют структурами данных.

По видам описания структур данных выделяют:
Графы
Иерархические структуры
Таблицы

и рёбра.

Сеть

Возможно множество различных путей перемещения по ребрам между некоторыми парами вершин.

Для сетей характерно наличие замкнутых путей – циклов.

Неориентированный граф или симметричная связь

Ориентированный граф или несимметричная связь

Рёбра дуги

Петля – линия, выходящая и входящая в одну и ту же вершину.

дороги проложены между: Д и Б, Д и К, Б и К, Б и М, Р и К

Неориентированный граф

Граф отображает элементный состав системы и структуру связи.

Ориентированный граф

Пример, 2 переливание крови от одного человека другому зависит от группы крови

Составные части графа : вершины , рёбра

…)
Ветви
Листья (1,2,3)

Связь - один ко многим

Структура, в которой одни элементы «подчиняются» другим, называется иерархия (от древнегреческого ἱεραρχία – «священное правление»). В информатике иерархию называют деревом.

существует единственный путь.
Деревья не содержат циклов и петель.

Корень дерева

Ветви

Исходные вершины

Порождённые вершины

Листья

Поддерево

«объект – объект»
Отражаются взаимосвязи между различными объектами.

Двоичная матрица - отображает качественную связь между объектами: есть связь или нет связи.

элементами.

Каждая строка относится к конкретному объекту, а столбцы отражают свойства объекта

качественную связь между объектами: есть связь или нет связи

можно свести к табличной форме.

Матрица симметрична относительно главной диагонали для неориентированного графа

существуют следующие связи (взаимоотношения): дружат: Саша и Маша, Саша и Даша, Маша и Гриша, Гриша и Саша. Глядя на полученный граф, ответьте на вопрос: с кем Саша может поделиться секретом, не рискуя, что он станет известен кому-то другому?

Нарисовать ориентированный граф (блок-схему) проверки учителем тетрадей. В систему команд входят команды : проверить работу; взять тетрадь из пачки; выставить оценку; выяснить, остались ли ещё не проверенные тетради.

Нарисуйте два варианта графа системы «Компьютер», содержащего следующие вершины: процессор, оперативная память, внешняя память, клавиатура, монитор, принтер; а) линия связи обозначает отношение «передает информацию»; б) линия связи обозначает отношение «управляет».

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

Задания

Попробуйте таким путем решить следующие задачи.

Имена Иванова, Петрова, Семенова и Николаева — Иван, Петр, Семен и Николай, причем только у Николаева имя совпадает с фамилией, т. е. его зовут Николай. Семенова зовут не Петром. Определить фамилию и имя каждого человека.

В Норильске, Москве, Ростове и Пятигорске живут четыре супружеские пары, причем в каждом городе — только одна пара. Имена этих супругов: Антон, Борис, Давид, Григорий, Ольга, Мария, Светлана, Екатерина. Антон живет в Норильске, Борис и Ольга — супруги, Григорий и Светлана не живут в одном городе, Мария живет в Москве, Светлана — ростовчанка. Кто на ком женат и кто где живет?

Задания

Андреев. Один из них — будущий музыкант, другой преуспел в бальных танцах, третий — солист школьного хора, четвертый подает надежды как художник.

О них известно следующее:
Иванов и Сидоров присутствовали в зале консерватории, когда там солировал в хоре мальчиков певец.
Петров и музыкант вместе позировали художнику.
Музыкант раньше дружил с Андреевым, а теперь хочет познакомиться с Ивановым.
Иванов не знаком с Сидоровым, так как они учатся в разных классах и в разные смены.
Кто чем увлекается?

совпадает с фамилией

Из таблицы видим:
Иванов - Пётр, следовательно он не может быть Семёном.

Петров Семён
Семёнов Иван

Сидоров не могут быть певцами. В таблице занесем в соответствующие клетки знак «—».
Петров — не художник и не музыкант (из пункта 2).
Андреев и Иванов — не музыканты (из пункта 3).
После этих рассуждений таблица выглядит так:

Следовательно, Сидоров — музыкант, он не может быть ни солистом, ни танцором, ни художником, что и зафиксируем знаками «—» и его строчке.

Сопоставим теперь второй и третий пункты условия задачи. Петров и Сидоров вместе позировали художнику, но Иванов не знает Сидорова, значит художник — не Иванов. Отметим этот факт « —» в соответствующей клетке.