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

Структуры данных: деревья, сети, графы, таблицы. 10 класс Объектом информационного моделирования может быть всё что угодно: отдельные предметы (дерево, стол); физические , химические , биологические процессы, метеорологические явления (гроза, смерч); экономические и социальные процессы. Рассмотрение множества объектов, объединенных единой целью функционирования позволяет говорить уже о системе. Модель – это новый объект, который отражает существенные с точки зрения цели моделирования признаки изучаемого предмета, процесса или явления. Моделирование – метод познания, заключающийся в создании и исследовании моделей. Материальные модели иначе можно назвать предметными или физическими. Они воспроизводят геометрические свойства оригинала и имеют реальное воплощение. Примеры материальных моделей: Детские игрушки (куклы – модель ребенка, машинки – модели реальных автомобилей и т.д.). Глобус – модель планеты Земля.Школьные пособия (скелет человека – модель реального скелета, модель атома кислорода и т.д.)Физические и химические опыты.Информационная модель – совокупность информации, характеризующая свойства и состояния объекта, процесса, явления, а также взаимосвязь с внешним миром. Примеры моделей:Чертеж кухонной мебели – модель мебели для кухни.Схема Московского метрополитена – модель метро. График изменения курса евро – модель роста курса евро.По способу реализации информационные модели делятся на компьютерные и некомпьютерные. Данные, на которых базируются информационные модели, представляют собой структурированные системы со своим составом и назначением. Их называют структурами данных. По видам описания структур данных выделяют:ГрафыИерархические структурыТаблицы Д Р К М Б Графы Отображают элементный состав системы и структуру связей. Составные части графа - вершины и рёбра. К С О И Н Сеть Возможно множество различных путей перемещения по ребрам между некоторыми парами вершин. Для сетей характерно наличие замкнутых путей – циклов. Неориентированный граф или симметричная связь I II III IV Ориентированный граф или несимметричная связь Рёбра дуги Петля – линия, выходящая и входящая в одну и ту же вершину. Д Р К М Б Графы Пример 1, район состоит из пяти посёлков: Д,Б,Р,К, М. Автомобильные дороги проложены между: Д и Б, Д и К, Б и К, Б и М, Р и К Неориентированный граф Граф отображает элементный состав системы и структуру связи. I III IV II Ориентированный граф Пример, 2 переливание крови от одного человека другому зависит от группы крови Составные части графа : вершины , рёбра Иерархические структуры (деревья) Элементы дерева:Корень дерева, вершины, ( шк1, шк3, нач.кл …)ВетвиЛистья (1,2,3) Связь - один ко многим Образование Школа 1 Школа 3 Школа 8 Школа 9 Нач. классы Нач. классы старшие классы старшие классы 1 2 3 Структура, в которой одни элементы «подчиняются» другим, называется иерархия (от древнегреческого ἱεραρχία – «священное правление»). В информатике иерархию называют деревом. Иерархические структуры – деревья Основное свойство – между любыми двумя вершинами существует единственный путь. Деревья не содержат циклов и петель. Учителя Нач.кл. Ест-мат Гуман. Физич.воспитание Филол. Истор. Ин.яз. Горовая К.М. Рыжкова М.Я. Корень дерева Ветви Исходные вершины Порождённые вершины Листья Поддерево Династия Рюриковичей Рюрик 879 Игорь945 Святослав972 Олег977 Владимир1014 Ярополк980 МстиславТмутараканский1036 Глеб1015 Ярослав1054 Борис1015 Святополк1018 ИзяславПолоцкий1001 ИЕРАРХИЧЕСКАЯ МОДЕЛЬ Таблицы Строки Столбцы Ячейки Таблицы типа «объект – свойство»Каждая строка относится к конкретному объекту. Таблицы типа «объект – объект»Отражаются взаимосвязи между различными объектами. Двоичная матрица - отображает качественную связь между объектами: есть связь или нет связи. Таблицы Элементы таблицы:Строки, столбцы, ячейки ТИПЫ ТАБЛИЦ«объект-свойство»«объект-объект» «объект-свойство» С помощью таблиц устанавливается связь между несколькими элементами. Каждая строка относится к конкретному объекту, а столбцы отражают свойства объекта «объект-объект» Таблицы Связь между объектами двух типов: учениками и изучаемыми дисциплинами Двоичные матрицы- отражают качественную связь между объектами: есть связь или нет связи Автор Название Год издания Жанр А. Беляев «Человек-амфибия» 1990 г. Фантастика А. Пушкин «Сказка о царе Салтане» 1985 г. Поэтическая сказка Л. Толстой «Война и мир» 1972 г. Трагедия А. Конан-Дойль «Голубой карбункул» 1980 г. Детектив Фамилия Предмет Алгебра Русский Химия Иванов Рома 3 3 4 Петров Вася 4 4 3 Сидоров Иван 4 3 5 Андреев Коля 5 4 4 ТАБЛИЧНАЯ МОДЕЛЬ Любую структуру данных, в том числе и представленных в форме графа можно свести к табличной форме. Д Р К М Б Д Б К М Р Д 0 1 1 0 0 Б 1 0 1 1 0 К 1 1 0 0 1 М 0 1 0 0 0 Р 0 0 1 0 0 Матрица симметрична относительно главной диагонали для неориентированного графа Изобразите в виде графа систему, состоящую из четырех одноклассников, между которыми существуют следующие связи (взаимоотношения): дружат: Саша и Маша, Саша и Даша, Маша и Гриша, Гриша и Саша. Глядя на полученный граф, ответьте на вопрос: с кем Саша может поделиться секретом, не рискуя, что он станет известен кому-то другому?Нарисовать ориентированный граф (блок-схему) проверки учителем тетрадей. В систему команд входят команды : проверить работу; взять тетрадь из пачки; выставить оценку; выяснить, остались ли ещё не проверенные тетради.Нарисуйте два варианта графа системы «Компьютер», содержащего следующие вершины: процессор, оперативная память, внешняя память, клавиатура, монитор, принтер; а) линия связи обозначает отношение «передает информацию»; б) линия связи обозначает отношение «управляет».Нарисуйте блок-схему поиска фальшивой монеты среди 10 монет. Имеем чашечные весы и известно, что фальшивая монета всего одна , и она легче настоящих. Задания Двоичные матрицы удобно использовать для решения некоторых логических задач — головоломок. Попробуйте таким путем решить следующие задачи.Имена Иванова, Петрова, Семенова и Николаева — Иван, Петр, Семен и Николай, причем только у Николаева имя совпадает с фамилией, т. е. его зовут Николай. Семенова зовут не Петром. Определить фамилию и имя каждого человека.В Норильске, Москве, Ростове и Пятигорске живут четыре супружеские пары, причем в каждом городе — только одна пара. Имена этих супругов: Антон, Борис, Давид, Григорий, Ольга, Мария, Светлана, Екатерина. Антон живет в Норильске, Борис и Ольга — супруги, Григорий и Светлана не живут в одном городе, Мария живет в Москве, Светлана — ростовчанка. Кто на ком женат и кто где живет? Задания Задания 3. В школе учатся четыре талантливых мальчика: Иванов, Петров, Сидоров и Андреев. Один из них — будущий музыкант, другой преуспел в бальных танцах, третий — солист школьного хора, четвертый подает надежды как художник.О них известно следующее:Иванов и Сидоров присутствовали в зале консерватории, когда там солировал в хоре мальчиков певец.Петров и музыкант вместе позировали художнику.Музыкант раньше дружил с Андреевым, а теперь хочет познакомиться с Ивановым.Иванов не знаком с Сидоровым, так как они учатся в разных классах и в разные смены.Кто чем увлекается? ИВАН ПЕТР СЕМЁН НИКОЛАЙ ИВАНОВ ПЕТРОВ СЕМЁНОВ НИКОЛАЕВ ИВАН ПЕТР СЕМЁН НИКОЛАЙ ИВАНОВ 0 ПЕТРОВ 0 СЕМЁНОВ 0 НИКОЛАЕВ 0 0 0 1 Из условия задачи : Николаев НиколайСемёнов не ПётрУ остальных имя не совпадает с фамилией ИВАН ПЕТР СЕМЁН НИКОЛАЙ ИВАНОВ 0 ПЕТРОВ 0 СЕМЁНОВ 0 0 НИКОЛАЕВ 0 0 0 1 Из таблицы видим: Иванов - Пётр, следовательно он не может быть Семёном. Петров СемёнСемёнов Иван ИВАН ПЕТР СЕМЁН НИКОЛАЙ ИВАНОВ 0 0 ПЕТРОВ 0 0 СЕМЁНОВ 0 0 0 НИКОЛАЕВ 0 0 0 1 ИВАН ПЕТР СЕМЁН НИКОЛАЙ ИВАНОВ 0 1 0 0 ПЕТРОВ 0 0 СЕМЁНОВ 0 0 0 НИКОЛАЕВ 0 0 0 1 ИВАН ПЕТР СЕМЁН НИКОЛАЙ ИВАНОВ 0 1 0 0 ПЕТРОВ 0 0 1 0 СЕМЁНОВ 1 0 0 0 НИКОЛАЕВ 0 0 0 1 ОЛЬГА МАРИЯ СВЕТЛАНА ЕКАТЕРИНА АНТОН Н БОРИС П ДАВИД Р ГРИГОРИЙ М РЕШЕНИЕ ЗАДАЧИ 2 Решение задачи 3 1.Из первого пункта следует, что ни Иванов, ни Сидоров не могут быть певцами. В таблице занесем в соответствующие клетки знак «—».Петров — не художник и не музыкант (из пункта 2). Андреев и Иванов — не музыканты (из пункта 3).После этих рассуждений таблица выглядит так: Танцор Художник Солист Музыкант Иванов - — Петров - - Сидоров - Андреев - Следовательно, Сидоров — музыкант, он не может быть ни солистом, ни танцором, ни художником, что и зафиксируем знаками «—» и его строчке. Сопоставим теперь второй и третий пункты условия задачи. Петров и Сидоров вместе позировали художнику, но Иванов не знает Сидорова, значит художник — не Иванов. Отметим этот факт « —» в соответствующей клетке. Танцор Художник Солист Музыкант Иванов + - - - Петров - - + - Сидоров - - - + Андреев __ + — —