Практическая работа "Информационные модели"

Практическая работа

изучить информационные модели в виде таблицы, графа, дерева;

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

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

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

Пример 1. Представлены две таблицы из базы данных. Каждая строка Таблицы 2 содержит информацию о ребенке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке Таблицы 1. Определите на основании приведенных данных суммарное количество прямых потомков (т.е. детей, внуков, правнуков) Иоли А.Б.

1. В первой таблице находим Иоли А.Б, ей соответствует ID 84

2. Все остальное решение будет связано со второй таблицей: будем в ней искать ID родителя и соответствующего ему ID ребенка.

3. Выполним задание при помощи дерева, подробно рассматривая каждый уровень иерархии: сначала детей родителя 84, затем по полученным ID найдем внуков Иоли А.Б, затем правнуков и т.д.

4. Посчитаем общее количество потомков: 7.

Ответ: 7 прямых потомков.

Пример 2. Между населенными пунктами A, B, C, D, E, F построены дороги, протяженность которых приведена в таблице. Передвигаться можно только по дорогам, указанным в таблице. Определите длину кратчайшего пути между пунктами A и F.

1. Построим граф: точками A, B, C, D, E, F, расположенными по кругу, обозначим населенные пункты.

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

3. Отмечаем конечный пункт (в нашем случае это F) и рассматриваем пункты, из которых можно в него попасть (в нашем случае это A, E, D). В свою очередь в пункт E можно попасть из D, а в пункт D – из C и B. В пункты C и B попадаем из A. Получили начальный пункт. Изобразим дерево всех возможных путей из A в F.

4. Вычислим длины полученных дорог.

5) AF=15, ACDEF=5+1+2+1=9, ABDEF=3+4+2+1=10, ACDF=5+1+6=12, ABDF=3+4+6=13.

6) Выбираем длину кратчайшего пути – 9.

Ответ: 9 - длина кратчайшего пути между пунктами A и F.

Пример 3. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

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

Ответ: 10 различных путей.

ЗАДАЧА 1. Представлены две таблицы из базы данных, в которых собраны сведения о сотрудниках некоторой организации. Каждая строка Таблицы 2 содержит информацию о сотруднике структурного подразделения и о его непосредственном руководителе, который, в свою очередь, является непосредственным подчиненным руководителя более высокого уровня. Информация представлена значением поля ID в соответствующей строке Таблицы 1. Определите на основании приведенных данных суммарное количество подчиненных (непосредственных и через руководителей более низкого уровня) Сидорова Т.И.

ЗАДАЧА 2. На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

ЗАДАЧА 3. На рисунке приведена весовая матрица графа. Постройте граф и определите, сколько рёбер имеет такой граф и суммарный вес всех ребер графа.

ЗАДАЧА 1. Представлены две таблицы из базы данных. Фрагмент базы данных содержит сведения о родственных отношениях. Информация представлена значением поля ID в соответствующей строке Определите на основании приведенных данных, сколько всего внуков и внучек есть у Левитана И.И.

ЗАДАЧА 2. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?

ЗАДАЧА 3. На рисунке приведена весовая матрица графа. Постройте граф и определите, сколько рёбер имеет такой граф и суммарный вес всех ребер графа.

ЗАДАЧА 1. В фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите. Сколько внуков у Паненко Б.Л. упомянуты в таблице 1.

ЗАДАЧА 2. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?

ЗАДАЧА 3. На рисунке приведена весовая матрица графа. Постройте граф и определите, сколько рёбер имеет такой граф и вес ребра, соединяющего вершины C и E.