|
|
Прак раб №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
|
|
|
|
|
Скачать 0.52 Mb.