- •Информатика Учебное пособие
- •Содержание
- •Предисловие
- •Тема 1. Введение
- •1.1. Цель и задачи курса «Информатика»
- •1.2. Объекты и составные части информатики
- •1.3. Информатика как единство науки и технологии
- •Контрольные вопросы
- •Тема 2. Основные понятия информатики
- •2.1. Место информатики в системе наук
- •2.2. Основные понятия курса «Информатика»
- •Предмет информатики составляют следующие понятия:
- •Информация классифицируется по видам. (рис. 2.4.)
- •Тема 3. Основы дискретной математики.
- •3.2. Основы логики
- •Элементарные булевые функции
- •Из них выделим функцию "отрицание X" (обозначается -X). Эта функция представлена в таблице
- •3.3. Графы и деревья
- •А) граф g; б) остов графа g; в) другой остов графа g
- •Тема 4. Основные понятия архитектуры эвм
- •Для представления числовых данных в эвм используются естественная и нормальная формы записи чисел.
- •4.2. Системы счисления. Правила перевода чисел из одной системы счисления в другую
- •3. Арифметические операции
- •4.3. Логические элементы компьютера
- •В качестве важных последовательностных схем, выполняемых на одной ис, можно отметить счетчики, сдвиговые регистры, элементы памяти и др.
- •Структурная схема базовой модели мп фирмы Intel представлена на рисунке 4.15.
- •4.5. Организация памяти компьютера
- •Используется два основных типа оперативной памяти:
- •Контрольные вопросы
- •Тема 5. Алгоритмическое решение задач, анализ алгоритмической сложности.
- •5.1. Стратегия решения задач.
- •5.2. Алгоритмы (свойства, реализация алгоритмов)
- •5.3. Структуры данных
- •5.4. Основные вычислительные алгоритмы.
- •5.5. Анализ алгоритмов
- •1. Сравнительные оценки алгоритмов
- •2. Система обозначений в анализе алгоритмов
- •3. Классификация алгоритмов по виду функции трудоёмкости
- •4. Асимптотический анализ алгоритмов
- •Контрольные вопросы
- •Тема 6. Знакомство с языками программирования.
- •6.1. Обзор языков программирования
- •6.2. Основные конструкции программирования
- •Внутри программы значение свойств можно изменять как угодно часто.
- •Константы.
- •На практике наибольшее распространение получили язык функционального программирования lisp и два его диалекта: язык Common lisp и язык Scheme.
- •Наиболее распространенным языком логического программирования является язык Prolog (Пролог).
- •Контрольные вопросы
- •Тема 7. Основы операционных систем
- •7.1. Основные концепции операционных систем
- •7.4. Файловые системы
- •7.6. Обзор современного прикладного программного обеспечения
- •Контрольные вопросы
- •Тема 8. Сети и телекоммуникации
- •Компоненты сети
- •По программной совместимости эвм: однородные (гомогенные) и неоднородные (гетерогенные);
- •8.3. Системы телекоммуникаций
- •Типы телекоммуникационных систем
- •Системы телевещания
- •Системы подвижной связи
- •Сети сотовой подвижной связи
- •Сети транкинговой связи
- •Сети персонального радиовызова
- •Сети мобильной спутниковой связи
- •Волоконно-оптические сети
- •Контрольные вопросы:
- •Тема 9. Сеть Internet
- •9.1. Теоретические основы Internet
- •9.2. Основные понятия (сайт, сокет, сервер, клиент). Web как пример архитектуры «клиент-сервер»
- •9.3. Службы Internet
- •Контрольные вопросы:
- •Тема 10. Графическое программное обеспечение
- •10.1. Иерархия графического программного обеспечения. Графические коммуникации. Графические системы.
- •10.2. Системы растровой и векторной графики
- •Описание объекта является простым и занимает мало памяти;
- •10.3. Графические редакторы
- •Контрольные вопросы
- •Тема 11. Основы защиты информации
- •11.1. Информационная безопасность и ее составляющие
- •11.2. Угрозы безопасности информации и их классификация
- •11.3. Сетевая безопасность
- •11.4. Антивирусные программы
- •Контрольные вопросы
3.3. Графы и деревья
Такая структура, как граф (в качестве синонима используется также термин «сеть»), имеет самые различные применения в информатике и в смежных прикладных областях, поэтому познакомимся с основными понятиями теории графов.
Граф G = (V, Е) задается парой конечных множеств V и Е. Элементы первого множества v1, v2,..., vM называются вершинами графа (при графическом представлении им соответствуют точки). Элементы второго множества e1, e2, ..., eN называют ребрами. Каждое ребро определяется парой вершин (при графическом представлении ребро соединяет две вершины графа). Если ребра графа определяются упорядоченными парами вершин, то такой граф называют ориентированным – орграфом (на чертеже при изображении ориентированного графа на каждом ребре ставят стрелку, указывающую его направление). Ориентированный граф с пятью вершинами и семью ребрами изображен на рис. 3.2.
Рис. 3.2. Пример ориентированного графа
Если порядок ребер не имеет значения, то граф называется неориентированным.
Если две вершины соединены двумя или более ребрами, то эти ребра называют параллельными (например, ребра е4 и е5). Если начало и конец ребра совпадают, то такое ребро называется петлей (например, ребро e7).
Граф без петель и параллельных ребер называется простым.
Если ребро ек определяется вершинами vi и vj (будем обозначать этот факт следующим образом: еk = (vi, vj), то говорят, что ребро ек инцидентно вершинам vi и vj.
Граф G(E,U) называется конечным, если множество Е вершин конечно. Граф G(E,U), у которого любые две вершины соединены ребром, называется полным. Если хотя бы две вершины соединены несколькими ребрами, то такой граф называется мультиграфом. Две вершины еi, еj Е называются смежными, если они соединены ребром. Число ребер, инцидентных данной вершине еi, называется локальной степенью этой вершины р(еi). Число ребер r графа G(E,U) определяется выражением
где n — количество вершин в графе.
Рассмотрим граф, изображенный на рис. 3.3.
Рис. 3.3. Ориентированный граф
Множество вершин графа состоит из пяти элементов: Е = {1, 2, 3, 4, 5}, а множество ребер U = {(1, 2), (1, 4), (1, 5), (2, 3), (3, 4), (5, 3)}. Ребро (5, 3) — является ориентированным ребром или дугой. Число ребер в графе определяется по значению локальных степеней для каждой вершины:
р(1) = 3; р(2) = 2; р(3) = 3; р(4) = 2; р(5) = 2; р = (3+2+3+2+2)/2=6.
Важным в теории графов является понятие части графа G(E,U), который обозначается G'(E',U') G(E,U).
Множества вершин и ребер части графа являются подмножествами вершин и ребер исходного графа Е'Е, U' U. Многие задачи на графах состоят в определении частей графа с заданными свойствами. Часть графа G'(E',U')G(E,U) называется подграфом графа G(E,U), если Е'Е, а подмножество U'U образовано только ребрами, инцидентными вершинам множества Е'.
Полным графом называется граф G(E,U), у которого каждая вершина соединена ребрами с остальными вершинами (рис.3.4).
Рис. 3.4. Полный граф
Обязанность графов
Маршрутом графа G называется последовательность ребер S=(u1,u2, ... un), в которой каждые два соседних ребра имеют общую вершину, т.е. u1= (e1, e2); u2= (e2, е3); ... un= (en, еn+1). Не исключено, что одно и то же ребро может встречаться несколько раз на одном маршруте.
Две вершины еi и еj называются связанными, если существует маршрут из еi в еj.
Компонентой связности графа называется подмножество его вершин с инцидентными им ребрами, такое, что любая вершина связана с любой другой вершиной маршрута. Например, из графа на рис. 3.5 можно выделить следующие две компоненты связанности, показанные сплошной линией.
Рис. 3.5. Компоненты связанности графа
Простой цепью, или простым путем, называется маршрут, в котором ни одно ребро не повторяется дважды. Элементарной цепью или элементарным путем называется маршрут, в котором ни одна вершина не повторяется дважды. Циклом в графе называется маршрут, у которого начальная вершина совпадает с конечной. Например, следующий граф имеет цикл S = (1, 2, 3, 5, 4, 1) (рис. 3.6).
Рис. 3.6. Цикл в графе
Цикл, проходящий по всем ребрам графа только один раз, называется эйлеровым циклом. В теории графов доказывается теорема, определяющая, содержит ли граф эйлеров цикл. Оказывается, конечный граф содержит эйлеров цикл тогда и только тогда, когда он связан, и все его локальные степени вершин четные. Важной прикладной задачей теории графов является задача поиска в графе цикла, проходящего через каждую вершину только один раз. Такие циклы называются гамильтоновыми циклами.
Задание графа
Граф может задаваться в виде рисунка, аналитически, в виде матрицы. Выше приводилось задание графа в виде рисунка. Аналитическое задание состоит в задании элементов множества вершин Е={е1, е2, ... еn} и множества ребер U = {u1, u2, ... um}.
Для выполнения различного рода формальных преобразований над графами удобно использовать их матричные задания. Матрица А размерностью n ´ n называется матрицей смежности графа G(E,U), если ее элементы образованы по правилу: элемент матрицы аij= m, если вершины еi и еj соединены m ребрами, и аij=0, если эти вершины не связаны ребрами. Матрица смежности имеет число строк и столбцов, равное количеству вершин графа.
Матрица А размерностью n m называется матрицей инцидентности графа G(E,U), если ее элементы образованы по правилу: элемент матрицы bij=1, если вершина еi инцидентна ребру uj и bij=0 в противном случае. Так как каждое ребро инцидентно двум вершинам, то в каждой строке этой матрицы ровно два ненулевых элемента.
Построим матрицы смежности и инцидентности для графа, изображенного на рис. 3.7.
Рис. 3.7. Пример графа.
Матрица смежности будет состоять из пяти строк и пяти столбцов.
|
1 |
2 |
3 |
4 |
5 |
1 |
0 |
1 |
0 |
1 |
0 |
2 |
1 |
0 |
1 |
1 |
0 |
3 |
0 |
1 |
0 |
0 |
1 |
4 |
1 |
1 |
0 |
0 |
1 |
5 |
0 |
0 |
1 |
1 |
0 |
Матрица инцидентности будет состоять из пяти строк и шести столбцов.
|
а |
b |
с |
d |
е |
f |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
2 |
1 |
0 |
1 |
0 |
1 |
0 |
3 |
0 |
0 |
1 |
1 |
0 |
0 |
4 |
0 |
1 |
0 |
0 |
1 |
1 |
5 |
0 |
0 |
0 |
1 |
0 |
1 |
Анализ приведенных здесь понятий и определений показывает, что в качестве моделей графы удобно использовать в тех случаях, когда рассматривается система каких-либо объектов, между которыми существуют определенные связи, отношения, когда изучается структура системы, возможности ее функционирования. В информатике графы используются в разделах: операционные системы, алгоритмизация, структуры данных, информационное моделирование и др.
Весьма важным является связанный граф, не имеющий циклов, он называется деревом. В дереве любые две вершины связаны единственным путем. Вершина называется концевой, если ей инцидентно не более одного ребра; одна из концевых вершин может быть выбрана в качестве корня.
Лес - это любой граф без циклов. На рис. 3.8 показаны возможные деревья с пятью вершинами.
Рис. 3.8. Примеры деревьев
Деревья бывают также ориентированные и неориентирование.
Нижеследующие определения неориентированного дерева, как легко показать, эквивалентны друг другу. Неориентированное дерево есть связный граф, содержащий п вершин и n-1 ребер, либо связный граф, не имеющий циклов, либо граф, в котором каждая пара вершин соединена одной и только одной простой цепью.
Если G = (X, А) - неориентированный граф с n вершинами, то остовным деревом (или, короче, остовом) графа G называется всякий остовный подграф графа G, являющийся деревом (в смысле приведенного выше определения). Например, если G - граф, показанный на рисунке (а), то граф на рисунке (б) является остовом графа G, как и граф, изображенный на рисунке (в). Из сформулированных выше определений вытекает, что остов графа G можно также рассматривать как минимальный связный остовный подграф графа G, где «минимальность» понимается в том смысле, что никакое собственное подмножество ребер этого остова не образует связный остовный подграф графа G.