|
Прак раб №2 Информационные модели. Использование компьютерных моделей различных процессов
Цель работы: Практическая работа Использование компьютерных моделей различных процессов изучить информационные модели в виде таблицы, графа, дерева; научиться решать задачи поиска данных в базе данных, представленной в табличном виде; научиться строить графы, определять количество путей с использованием графов и таблиц. Краткие теоретические сведения Структурирование информации это установление главных элементов в информационных сообщениях и установление связей между ними. Структурирование выполняется с целью облегчения восприятия и поиска информации. Структурирование возможно при помощи следующих структур (информационных моделей): множество, линейный список, дерево, граф, таблица. Граф – набор вершин и связей между ними. Точки – это вершины графа, линии – ребра. Графы используют для структурирования информации, если «взаимоотношения» между объектами сложные. Связный граф – это граф, между любыми вершинами которого существует путь. Граф называется древовидным, если для каждой пары вершин существует только одно соединяющее ребро. У взвешенных графов указан «вес ребра» его числовое значение. Из взвешенных графов получается весовая матрица. Примеры решения задач Пример 1. Представлены две таблицы из базы данных. Каждая строка Таблицы 2 содержит информацию о ребенке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке Таблицы 1. Определите на основании приведенных данных суммарное количество прямых потомков (т.е. детей, внуков, правнуков) Иоли А.Б. Решение: В первой таблице находим Иоли А.Б, ей соответствует ID 84 Все остальное решение будет связано со второй таблицей: будем в ней искать ID родителя и соответствующего ему ID ребенка. Выполним задание при помощи дерева, подробно рассматривая каждый уровень иерархии: сначала детей родителя 84, затем по полученным ID найдем внуков Иоли А.Б, затем правнуков и т.д. Посчитаем общее количество потомков: 7.
Ответ: 7 прямых потомков.
Пример 2. Между населенными пунктами A, B, C, D, E, F построены дороги, протяженность которых приведена в таблице. Передвигаться можно только по дорогам, указанным в таблице. Определите длину кратчайшего пути между пунктами A и F.
Решение: Построим граф: точками A, B, C, D, E, F, расположенными по кругу, обозначим населенные пункты. Если в таблице есть число, соединяем точки отрезком и подписываем сверху это число. Отмечаем конечный пункт (в нашем случае это F) и рассматриваем пункты, из которых можно в него попасть (в нашем случае это A, E, D). В свою очередь в пункт E можно попасть из D, а в пункт D – из C и B. В пункты C и B попадаем из A. Получили начальный пункт. Изобразим дерево всех возможных путей из A в F. Вычислим длины полученных дорог.
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. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Решение: Подсчитаем количество путей, последовательно для каждой из вершин графа. Заполним таблицу:
Вершина
| Предшествующие вершины
| Количество путей
| Б
| А
| 1
| В
| А+Б
| 1+1=2
| Г
| А
| 1
| Д
| Б+В
| 1+2=3
| Е
| Г
| 1
| Ж
| Д+В+Е
| 3+2+1=6
| И
| Д
| 3
| К
| И+Ж+Е
| 3+6+1=10
|
Ответ: 10 различных путей. ЗАДАЧА 1. Представлены две таблицы из базы данных, в которых собраны сведения о сотрудниках некоторой организации. Каждая строка Таблицы 2 содержит информацию о сотруднике структурного подразделения и о его непосредственном руководителе, который, в свою очередь, является непосредственным подчиненным руководителя более высокого уровня. Информация представлена значением поля ID в соответствующей строке Таблицы 1. Определите на основании приведенных данных суммарное количество подчиненных (непосредственных и через руководителей более низкого уровня) Сидорова Т.И.
ЗАДАЧА 2. На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
ЗАДАЧА 3. На рисунке приведена весовая матрица графа. Постройте граф и определите, сколько рёбер имеет такой граф и суммарный вес всех ребер графа.
ЗАДАЧА 1. Представлены две таблицы из базы данных. Фрагмент базы данных содержит сведения о родственных отношениях. Информация представлена значением поля ID в соответствующей строке Определите на основании приведенных данных, сколько всего внуков и внучек есть у Левитана И.И.
ЗАДАЧА 2. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И?
ЗАДАЧА 3. На рисунке приведена весовая матрица графа. Постройте граф и определите, сколько рёбер имеет такой граф и суммарный вес всех ребер графа.
ЗАДАЧА 1. В фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите. Сколько внуков у Паненко Б.Л. упомянуты в таблице 1.
ЗАДАЧА 2. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
ЗАДАЧА 3. На рисунке приведена весовая матрица графа. Постройте граф и определите, сколько рёбер имеет такой граф и вес ребра, соединяющего вершины C и E.
| A
| B
| C
| D
| E
| A
|
|
| 4
|
| 6
| B
|
|
|
| 5
| 7
| C
| 4
|
|
| 2
| 8
| D
|
| 5
| 2
|
| 3
| E
| 6
| 7
| 8
| 3
|
|
|
|
|