Списки, графы, деревья.

Группа Т(О), ТГ(О), С(О)–24-02, 2025 год

Занятие по рабочей программе №02

Дисциплина: БД.08 «Информатика»

Раздел 3. Информационное моделирование.

Тема: Списки, графы, деревья.

1. Цель занятия:

   1. Дидактическая:

• сформулировать представление студентов о понятии списка, графа и деревьях;

• выяснить различные подходы к этапам моделирования;

• определения конфиденциальности и доступности информации;

• систематизировать и объяснить сущность проблемы Классификация моделей;

• углубить и закрепить знания по дисциплине «Информатика».

Воспитательная:

• развивать коммуникативные способности;

• развивать аналитические способности;

• развивать творческий подход к процессу обучения.

• воспитывать самостоятельность, дисциплинированность;

• стимулировать студентов к изучению дисциплины;

• побуждать к формированию активной жизненной позиции;

• прививать уважение и любовь к будущей профессии.

Вид занятия: лекция.

Тип занятия: обобщение и систематизация знаний.

Форма проведения занятия: репродуктивная и эвристическая беседа.

Междисциплинарные связи:

Обеспечивающие Математика, Охрана труда, Безопасность жизнедеятельности.

Обеспечиваемые

Информационные технологии в профессиональной деятельности, и др.

Методическое обеспечение: опорный конспект.

Литература:

1. Симонович, С. В. Информатика. Базовый курс : Учебник для вузов. 3 - е изд. Стандарт третьего поколения. – СПб., 2016., стр.

2. Электронный учебник по информатике и информационным технологиям - http://www.ctc.msiu.ru/

3. Галатенко, В. А. Стандарты информационной безопасности. – М : Интернет-Университет Информационных Технологий – ИНТУИТ. РУ, 2004.

ХОД ЗАНЯТИЯ

1. Ознакомление с темой, целью и планом занятия.

Тема: Списки, графы, деревья.

ПЛАН

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

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

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

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

1. Изложение и изучение нового материала.

ЛИТЕРАТУРА: [2], стр.

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

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

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

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

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

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

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

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

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

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

• модель - это новый объект, который имеет свойства данного объекта, существенные для определённого исследования;

• моделирование - метод познания, заключающийся в создании и исследовании моделей;

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

• информационная модель - описание объекта-оригинала на одном из языков кодирования информации;

• по форме представления можно выделить знаковые, образные и смешанные информационные модели;

• для создания информационной модели объекта необходимо:

1) выяснить цель моделирования;

2) выделить свойства объекта-оригинала, существенные с точки зрения цели моделирования;

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

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

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

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

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

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

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

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

• прогнозирование погоды и климатических изменений;

• конструирование транспортных средств и дизайн лекарственных препаратов;

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

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

• многие другие задачи.

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

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

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

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

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

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

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

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

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

• исследовать процессы в развитии, при необходимости ускоряя или замедляя их и проводя эксперименты многократно;

• находить оптимальные решения без затрат на изготовление пробных экземпляров;

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

• визуализировать получаемые результаты.

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

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

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

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

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

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

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

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

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

Почему стек является структурой типа LIFO (от англ. Last In, Firts Out - последним пришёл, первым ушёл)?

Почему очередь является структурой

Примеры нелинейных структур данных типа FIFO (от англ. First In, First Out - первым пришёл, первым ушёл)?вам также хорошо известны - это графы и деревья (рис.3).

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

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

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

1) на каждый элемент может быть произвольное количество ссылок;

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

3) каждая связка может иметь направление и вес.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) от исходного графа перейти к матрице смежности;

2) по матрице смежности построить дерево решений;

3) по дереву решений выбрать подходящий вариант.

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

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

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

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

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

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

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

Рис. 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. Можно считать число путей с начала маршрута. При этом процесс подсчёта удобно изображать на самом графе — рисунок 10.

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

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

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

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

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

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

Вопросы и задания

1. Создайте информационную модель одной из комнат вашей квартиры с целью оклейки её обоями. Представьте информационную модель в знаковой и графической формах.

2. Какие модели называются компьютерными информационными моделями?

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

4. Приведите примеры линейных структур данных. Чем очередь отличается от стека?

5. Муравьи идут друг за другом по неровной лесной тропе. На их пути встречаются ямки, в которые могут провалиться несколько Муравьёв. Когда ямка заполняется муравьями, остальные муравьи проходят через неё, а затем по одному вытаскивают провалившихся. Например, вот как четыре муравья проходят через ямку, вмещающую двух Муравьёв:

Пусть по тропе идут 8 Муравьёв. В каком порядке они будут идти после преодоления участка с четырьмя ямками, вмещающими 2, 4, 5 и 1 муравья соответственно?

Какую структуру данных иллюстрирует данный пример?

6. Что такое граф? Какой граф называется ориентированным? Какой граф называется неориентированным? Какой граф называется взвешенным? Приведите примеры.

7. Что такое дерево? Какое дерево называется бинарным? Приведите примеры.

8. Почему графы и деревья считаются многоуровневыми структурами данных?

9. В кладовке хранятся ёлочные игрушки - большие и маленькие красные и золотые шары и звёзды. При этом игрушки разного размера, цвета и формы хранятся в отдельных коробках. Например, в одной коробке - большие красные звёзды, в другой - маленькие красные звёзды и т. д. Известно, что среди игрушек нет ни маленьких шаров, ни маленьких золотых звёзд. Всего звёзд 25, а шаров - 17. Всего больших игрушек - 32; красных игрушек - 28. Золотых звёзд на 2 больше, чем золотых шаров. В скольких коробках хранятся игрушки? Сколько игрушек в каждой коробке?

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

10. Найдите кратчайший путь от вершины А до вершины F в ориентированном графе:

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

ДОМАШНЕЕ ЗАДАНИЕ

1. Изучить новый материал лекции. Дополнительно презентацию «Модели и моделирование».

2. Составить конспект лекции.

3. Ответить письменно на контрольные вопросы и задания.

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

Основные источники:

1. Симонович, С. В. Информатика. Базовый курс : Учебник для вузов. 3 - е изд. Стандарт третьего поколения. – СПб., 2016

2. Гохберг, Г.С. Информационные технологии : учебник для студ. сред. проф. Образования / Гохберг, Г.С, Зафиевский, А.В., Короткин, А.А.- 5-е изд., стер. – М. : Издательский центр «Академия», 2010. – 208с.

3. Филимонова, Е.В. Информационные технологии в профессиональной деятельности : учебник. – Изд-е 2-е, доп. и перераб. – Ростов н/Д : Феникс, 2008. – 381. – (СПО).

4. Е.В. Михеева, О.И. Титова Информатика Учебник 6-е издание М., Издательский центр «Академия», 2011 г

Дополнительные источники:

1. Колесниченко, О.В., Шишигин, И.В. Аппаратные средства PC. 5-е издание. СПб. БХВ - Петербург, 2006.

2. Ральф Вебер. Сборка, конфигурирование, настройка, модернизация и разгон ПК. - ДиаСофт, 2007.

3. Гребенюк, Е.И., Гребенюк, Н.А. Технические средства информатизации: учебник для студ. учреждений сред. проф. образования / Е. И. Гребенюк, Н.А.Гребенюк. – 9-е изд., перераб. и доп. – М. : Издательский центр «Академия», 2014. – 352 с.

4. Максимов, Н. В., Партыка, Т. JI., Попов, И. И. Технические средства информатизации : учебник / Н. В. Максимов, Т. JI. Партыка, И. И. Попов. — 3-е изд., перераб. и доп. — М. : ФОРУМ, 2010. — 608 с.

5. Гук, М. Аппаратные средства IBM PC. Энциклопедия. – СПб. : Питер, 2003. – 928 с.

6. Технические средства информатизации. Учебное пособие. / Составитель А.Н. Попов. – Нижневартовск : НГСГК, - 2007. – 331 с.

Интернет - источники:

1. Электронный учебник по информатике и информационным технологиям - http://www.ctc.msiu.ru/

2. Тесты по информатике - http://www.ege.ru/

Преподаватель: Владимир Александрович Волков