Презентация Роль теории графов в программировании и информатике онлайн

Содержание слайда: Роль теории графов в программировании и информатике Выполнила: Васюнцова Юлия Студентка группы 3641 Преподаватель: Симоненко Зинаида Григорьевна

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание слайда: Источники информации http://www.0zd.ru/programmirovanie_kompyutery_i/primenenie_teorii_grafov_v_informatike.html http://bourabai.ru/dm/graph.htm https://ru.wikipedia.org/wiki/ Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение.