Публикации Роль дискретной математики в профессии Компьютерные системы и комплексы

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

Язык издания: русский
Периодичность: ежедневно
Вид издания: сборник
Версия издания: электронное сетевое
Публикация: Роль дискретной математики в профессии Компьютерные системы и комплексы
Автор: Анна Александровна Свиридова

Роль дискретной математикив профессии Компьютерные системы и комплексы.Аннотация. Дискретная математика - область математики, занимающаяся изучением свойств структур конечного характера, которые возникают как внутри математики, так и в её приложениях. К числу таких конечных структур могут быть отнесены, например, конечные группы, конечные графы, а также некоторые математические модели преобразователей информации, конечные автоматы, машина Тьюринга и т. п.Дискретная математика имеет широкий спектр приложений, прежде всего в областях, связанных с информационными технологиями и компьютерами (компьютер - цифровая вычислительная машина, следовательно, имеет дискретный характер работы).Ключевые слова. Дискретная математика, информационные технологии, граф, теория графов, функции графов.Введение. Целью данной работы является доказать важность изучения дисциплины Дискретная математика в профессии Компьютерные системы и комплексы. Основные задачи:

Описать функции теории графов в информационных технологиях

Проиллюстрировать, какие основы теории графов используются в сфере информационных технологий

Основная часть.Термин «дискретный» произошел от латинского слова discretus – прерывистый, состоящий из отдельных частей.Дискретная математика изучает дискретные величины, а так же объекты, их свойства, состояния и связи между ними при помощи дискретных величин. Разделы дискретной математики: комбинаторика, теория чисел, теория множеств, математическая логика, теория алгебраических систем, теория графов и сетей, теория кодирования и т.д.Наиболее значимой областью применения методов дискретной математики является область компьютерных технологий. Дискретная математика помогает описывать данные с различной структурой и предлагает алгоритмы для их обработки, применяется при оптимизации поисковых алгоритмов в сети Интернет, конструировании баз данных, широко используется в программировании.Современные ученые подтверждают: подготовка специалиста в области информатики невозможна без освоения курса дискретной математики. Рассмотрим роль дискретной математики в профессии "Компьютерные системы и комплексы" на примере "Теории графов".Граф — совокупность непустого множества вершин и связей между вершинами. Модели графов часто используются в тех случаях, когда рассматриваются системы каких-либо объектов, между которыми существуют определенные связи а также в тех случаях, когда изучается структура системы, возможности ее функционирования.В информатике графы используются в следующих разделах:- операционные системы;- алгоритмизация;- структуры данных;- моделирование и др.Наиболее часто в информатике используются следующие понятия о графах: маршрут (путь) – упорядоченная последовательность вершин и рёбер (дуг) графа; граф связный, если для любых двух его вершин существует маршрут, соединяющий их; дерево – связный граф, не имеющий циклов; сеть – связный ориентированный граф без ориентированного цикла. Роль графов в программировании.Визуализация информации – это процесс преобразования больших и сложных видов абстрактной информации в интуитивно понятную визуальную форму. Универсальным средством такого представления структурированной информации являются графы.При описании большинства алгоритмов решения задачи в программировании, они визуализируются построением графов Графы в сетевом планированииРешение задачи о кратчайшем пути в графе позволяет найти наиболее эффективный и удобный путь в коммуникационных системах.Например для :- проектирования кратчайшей сети- оптимизации структуры ПЗУ- анализа надёжности сетей связи При помощи графа можно: изобразить маршрутизацию данных в сетях; решить задачу о максимальном потоке, который позволяет определить пропускную способность сети; организовать движение в сети; распределить интенсивность выполнения работ.Раскраска графовПри раскраске элементам графа ставятся в соответствие цветные метки с учетом определенных ограничений. Для улучшения времени выполнения результирующего кода, одной из техник компиляторной оптимизации, является распределение регистров, в которой наиболее часто используемые переменные компилируемой программы хранятся в быстродействующих регистрах процессора.Один из подходов к этой задаче состоит в построении модели раскраски графов. Компилятор строит граф, где вершины соответствуют регистрам, а грань соединяет две из них, если они нужны в один и тот же момент времени. Двоичные деревьяДвоичные деревья позволяют удобно представить нужную информацию. Например, интерпретация деревьев в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось.Каталоги, папки и прочая информация в компьютере хранится в виде дерева. Чтобы открыть какой-то каталог, надо прописать маршрут (путь) к нему из корневого каталога. Графы в компьютерной графике. Сегментация изображения.Сегментация — процесс разделения цифрового изображения на несколько сегментов. Цель сегментации заключается в упрощении и/или изменении представления изображения, чтобы его было проще и легче анализировать.При сегментации применяются методы разреза. Изображение представляется как взвешенный неориентированный граф. Обычно пиксель или группа пикселей ассоциируется вершиной, а веса рёбер определяют похожесть соседних пикселей. Затем граф разрезается согласно заданному критерию. Каждая получаемая часть вершин получаемая считается объектом на изображении. Заключение.Теория графов позволяет упростить решение многих задач в сфере компьютерных технологий. Благодаря графам можно наглядно проиллюстрировать многие процессы в компьютере и лучше понять их.Изучение теории графов, как и всей дискретной математики очень важно для студентов, обучающихся на компьютерных специальностях.Литература.

Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение.