Презентация "Графы в информатике"

Роль теории графов в программировании и информатике

Цель:
Показать важность изучения дискретной математики на специальностях, связанных с информационными технологиями
Задачи:
Описать функции теории графов в информационных технологиях
Проиллюстрировать, какие основы теории графов используются в сфере информационных технологий

Постановка задачи

Термин «дискретный» произошел от латинского слова discretus – прерывистый, состоящий из отдельных частей
Дискретная математика изучает дискретные величины, а так же объекты, их свойства, состояния и связи между ними при помощи дискретных величин
Разделы дискретной математики:
- комбинаторика
- теория чисел
- теория множеств
- математическая логика
- теория алгебраических систем
- теория графов и сетей
- теория кодирования и т.д.

Дискретная математика

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

Граф — совокупность непустого множества вершин и связей между вершинами
Модели графов часто используются в тех случаях, когда рассматриваются системы каких-либо объектов, между которыми существуют определенные связи а также в тех случаях, когда изучается структура системы, возможности ее функционирования.
В информатике графы используются в следующих разделах:
- операционные системы;
- алгоритмизация;
- структуры данных;
- моделирование и др.

Теория графов

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

Наиболее часто в информатике используются следующие понятия о графах:

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

Графы в программировании

Решение задачи о кратчайшем пути в графе позволяет найти наиболее эффективный и удобный путь в коммуникационных системах.
Например, для проектирования кратчайшей сети
Оптимизации структуры ПЗУ
Анализа надёжности сетей связи

Графы в сетевом планировании

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

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

Раскраска графов

Двоичные деревья позволяют удобно представить нужную информацию.
Например, интерпретация деревьев в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось.
Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.

Двоичные деревья

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

Структура дерева

Сегментация — процесс разделения цифрового изображения на несколько сегментов. Цель сегментации заключается в упрощении и/или изменении представления изображения, чтобы его было проще и легче анализировать
При сегментации применяются методы разреза. Изображение представляется как взвешенный неориентированный граф. Обычно пиксель или группа пикселей ассоциируется вершиной, а веса рёбер определяют похожесть соседних пикселей. Затем граф разрезается согласно заданному критерию. Каждая получаемая часть вершин получаемая считается объектом на изображении.

Графы в компьютерной графике. Сегментация изображения

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

Вывод