Вопросы для повторения темы

1 2

Колледж геодезии и картографии МИИГАиК

МЕТОДИЧЕСКИЙ КАБИНЕТ «22» февраля 2014 г. Рег. № 1618

Методические указания по «Информатике»

ИНФОРМАЦИОННЫЕ МОДЕЛИ СЛОЖНЫХ СИСТЕМ:

ТАБЛИЦЫ, ГРАФЫ, ДОРОЖНЫЕ СЕТИ, ИЕРАРХИЧЕСКИЕ СТРУКТУРЫ

для студентов 1 курса специальностей:

«Прикладная геодезия»,

«Аэрофотогеодезия»,

«Картография»

«Земельно-имущественные отношения»

среднего профессионального образования

(базовый уровень)

Москва 2014

ОДОБРЕНО Предметно-цикловой комиссией «Общеобразовательных и математических и естественно-научных дисциплин» Председатель: _____________ Слижевич Т.В. Протокол № ________________ 2014

Составлена в соответствии с примерной программой учебной дисциплины Информатика для всех специальностей Зам. директора по МР _____________ Воскресенская О.В.

Составитель – Коржавина Е.Р., преподаватель информатики

Рецензент – Трубникова Н.Ю., преподаватель физики и электротехники

Содержание

1. Аннотация 4

2. Введение 4

3. Таблицы 5

4. Графы 7

5. Иерархические структуры – деревья 13

6. Вопросы для повторения темы 15

7. Задачи для самоподготовки 16

8. Список литературы 20

Аннотация

Дисциплина «Информатика» изучается в соответствии с требованиями Федерального государственного образовательного стандарта (ФГОС 3) поколения согласно учебному плану на основе примерной программы, утвержденной в 2011 году.

Дисциплина относится к математическому и общего естественно-научному циклу.

Тема «Информационные модели сложных систем: таблицы, графы, дорожные сети, иерархические структуры» изучается после усвоения основных понятий – информация, объем информации, кодирование текстовой, числовой, звуковой и графической информации.

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

2. Введение

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

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

Также к категории информационных систем относятся:

· Экспертные системы

· Системы автоматизации научных исследований

· Автоматизированные системы управления (логистика)

· Автоматизированные системы составления расписаний

· Автоматизированные обучающие системы

· Системы автоматизации проектирования (САПР)

· Геоинформационные системы (ГИС)

уровни

Таблицы

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

Таблица (Table) – основная структура для хранения данных.

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

Пример таблицы:

Дата	Осадки	Температура, °С	Давление, мм ртст	Влажность, %
15.03.2013	Снег	-3,5
16.03.2013	Без осадков	-1,0
17.03.2013	Туман	1,0
18.03.2013	Дождь	3,4
19.03.2013	Без осадков	5,2

Таблица состоит из строк и столбцов.

В данной таблице – 5 столбцов и 6 строк.

В верхней строке – заголовки столбцов.

Пересечение строки и столбца образует ячейку таблицы.

По своей структуре таблицы могут различаться.

Данная таблица относится к типу «объект-свойство» (ОС).

В таких таблицах все свойства относятся к одному объекту.

В данном примере объект – определенный день, задается датой. Все остальные столбцы – свойства объекта (метеорологические данные).

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

Другой тип таблиц – «объект-объект» (ОО)

Рассматриваются пары объектов, то есть свойства характеризуют не один объект, а сразу два. Для каждой пары объектов описано только одно свойство. Таким образом, таблица типа «объект-объект» отражает взаимосвязь между различными объектами.

Пример таблицы:

Таблица 1. Успеваемости учеников

Ученик	Предмет
Русский	Алгебра	Химия	Физика
Иванов Сергей
Петров Андрей
Сидоренко Елена
Тимофеев Иван

Эта таблица отражает связь между объектами – учениками и предметами.

Оценка в баллах – характеристика связи.

Например:

Таблица 2. Расстояния между областными центрами.

	Владимир	Волоколамск	Гагарин	Дмитров	Егорьевск	Калуга
Владимир
Волоколамск
Гагарин
Дмитров
Егорьевск
Калуга

Такая таблица называется матрицей смежности – цифра расстояния между городами находится на пересечении столбцов и строк с названиями смежных городов.

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

4. Графы

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

Все части системы объединяются в единое целое в определенном порядке. Структура – это порядок связей между элементами системы, это внутренняя организация системы.

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

Граф отображает состав системы и структуру связей между элементами.

Графы являются мощной основой для построения информационных моделей, решения огромного числа задач моделирования.

Составные части графа:

1. вершины графа (обозначаются кружками) – обозначают элементы системы;

2. ребра (линии) – показывают связи между элементами

Вершины, соединенные ребрами, называются смежными.

Пример неориентированного графа:

В данном графе 4 вершины (A,B,C,D) и 5 ребер (линии, соединяющие вершины и указывающие взаимосвязи между ними)

Существует 3 способа задания графа:

1 способ - список всех ребер – указывается в круглых скобках через запятую:

(АС, AD, AB, BC, BD)

2 способ – матрица смежности. Матрица смежности - таблица типа «объект-объект», в названиях столбцов и строк – названия вершин графа

Правило заполнения ячеек таблицы:

1 – ребро между вершинами есть.

0 –ребра между вершинами нет

Таблица симметрична относительно главной диагонали матрицы смежности (диагональ выделена зеленым цветом).

3 способ – таблица инцидентности

Слово инцидент означает случай, происшествие, столкновение, пересечение интересов.

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

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

Для заполнения этой таблицы необходимо пронумеровать ребра графа:

Правило заполнения:

1 – вершина с ребром соединена

0 – вершина с ребром не соединяется

Названия строк таблицы инцидентности – названия вершин графа, названия столбцов – номера ребер графа. Эта таблица не является симметричной и не имеет главной диагонали.

Примером применения неориентированного графа служит дорожная сеть.

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

Пример:

Дано словесное описание:

«Район состоит из пяти поселков: Марьино, Прокшино, Софьино, Булатово и Лукино. Автомобильные дороги проложены между: Марьино и Прокшино, Марьино и Булатово, Прокшино и Лукино, Прокшино и Булатово, от Булатово до Софьино»

Пример схемы по этому описанию:

Поселки обозначены

первыми буквами названий:

М - Марьино

П - Прокшино

С - Софьино

Б - Булатово

Л - Лукино

Глядя на этот граф, можно ответить на вопрос – через какие поселки нужно проехать, чтобы добраться из Софьино в Лукино?

Возможно два пути:

1 вариант С – Б – П – Л (Софьино-Булатово-Прокшино-Лукино)

2 вариант С – Б – М – П – Л (Софьино-Булатово-Марьино-Прокшино-Лукино)

Для сетей характерно наличие замкнутых путей, которые называются циклами.

В примере цикл: Б – М – П – Б (Булатово-Марьино-Прокшино-Булатово).

Дорожную сеть можно представить и в табличном виде:

	Марьино	Прокшино	Софьино	Булатово	Лукино
Марьино
Прокшино
Софьино
Булатово
Лукино

Такая таблица – двоичная матрица, соответствующая структуре сети:

1 – дорога между поселками есть. 0 – дороги нет

Таблица – симметрична относительно главной диагонали.

Если на каждой линии, соединяющей две смежные вершины, выбрано направление, то такой граф называется ориентированным или сокращенно орграфом. Линии со стрелками, указывающие направления, называются дугами.

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

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

Пример способов задания орграфа

1 способ – список всех дуг (AE, AD, AC, AB, CB, ED, DE)

2 способ – двоичная матрица смежности

	A	B	C	D	E
A
B
C
D
E

Названия строк таблицы - вершины, из которых выходит дуга

Названия столбцов таблицы – вершины, в которые входит дуга

Правило заполнения:

1 – дуга между вершинами есть

0 – дуги между вершинами нет

Важно – учитывать направления дуг (в отличие от неориентированного графа).

Матрицасмежности для орграфа не является симметричной.

3 способ – таблица инцидентности

Строится аналогично неориентированному графу, но заполняется с учетом направления дуг орграфа.


A
B				-1	-1
C		-1				-1
D	-1						-1
E			-1

Правило заполнения:

1 – дуга выходит из вершины

-1 – дуга входит в вершину

0 – дуга с вершиной не соединена

5. Иерархические структуры – деревья

Иерархия - (греч. hierarchía, от hierós — священный и arche — власть), принцип структурной организации многоуровневых систем, состоящий в упорядочении взаимодействий между уровнями по закону от высшего к низшему.

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

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

Обычно у дерева, отображающего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. От нее идут ветви дерева. От корня начинается отсчет уровней дерева.

Вершины, связанные с корнем образуют первый уровень.

Вершины последнего уровня называются листьями.

Пример – граф административной структуры Российской Федерации

В приведенном примере: корень - РФ, первый уровень – округа, второй уровень - области, листья – города.

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

ВОПРОСЫ ДЛЯ ПОВТОРЕНИЯ ТЕМЫ

1. Что такое информация?

2. Что такое информационная система? Что такое структура системы?

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

4. Уметь различить по виду таблицы типа «объект-свойство» и «объект-объект», суметь их составить по данным.

5. Представлять, что такое строка таблицы, столбец таблицы, ячейка таблицы

6. Что такое главная диагональ таблицы?

7. Что означает симметричность таблицы?

8. Что такое граф? Что он отображает?

9. Составные части графа.

10. Уметь построить граф заданной системы.

11. Чем отличается ориентированный граф от неориентированного?