«Применение ит при решении задач теории графов»

Вид материала

Содержание

Список обозначений ко всей выпускной работе
Реферат на тему «Применение ИТ при решении задач теории графов» Введение
Глава 1 Базовые понятия теории графов
V — непустое множество, V
G, смежных с некоторой вершиной v
V двухэлементных подмножеств заменяется декартовым квадратом V
Глава 2 Анализ GraphMagic: системы работы с графовыми моделями и алгоритмами
2.1.3 Открытость и бесплатность
2.2 Архитектура системы GraphMagic
Глава 3 Плагин для системы GraphMagic
3.2 Используемые технологии 3.2.1 Java
Основные особенности языка Java
3.3 Результаты работы плагина
Список литературы к реферату
Предметный указатель к реферату.
Интернет ресурсы в предметной области исследования
Действующий личный сайт в WWW .narod.ru Граф научных интересов
01.01.07 — вычислительная математика.
01.01.09 – дискретная математика и математическая кибернетика
05.12.13 — системы, сети и устройства телекоммуникаций
...
Полное содержание

Подобный материал:

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Выпускная работа по
«Основам информационных технологий»

Магистрант кафедры численных методов и программирования

Жигмонт Андрей Владимирович

Руководители:

кандидат физ.-мат. наук Суздаль С.В.

доцент Кожич Павел Павлович

Минск – 2010 г.

Оглавление 2

Список обозначений ко всей выпускной работе 4

Реферат на тему «Применение ИТ при решении задач теории графов» 5

Введение 5

Глава 1 Базовые понятия теории графов 6

1.1 Основные определения 6

Глава 2 Анализ GraphMagic: системы работы с графовыми моделями и алгоритмами 9

2.1 Основные преимущества системы GraphMagic 9

Глава 3 Плагин для системы GraphMagic 19

3.1 Описание плагина 19

3.2 Используемые технологии 19

3.2.1 Java 19

3.2.2 Swing 22

3.3 Результаты работы плагина 24

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

24

25

На двух следующих рисунках ниже можно увидеть результаты работы плагина по нахождению K(K>2) кратчайшего множества реберно-непересекающихся путей между двумя вершинами 1 и 5. К вводиться пользователем (K=3,K=4). 25

25

26

Заключение 26

Список литературы к реферату 27

Предметный указатель к реферату. 28

Интернет ресурсы в предметной области исследования 29

Действующий личный сайт в WWW 30

Граф научных интересов 31

Тестовые вопросы по Основам информационных технологий 33

Презентация магистерской диссертации 34

Список литературы к выпускной работе 35

Приложение 36

Список обозначений ко всей выпускной работе

AI – искусственный интеллект

ИТ – информационные технологии.

СВГ – системы визуализации графов

ТГ – теория графов

ЭВМ – электронная вычислительная машина

Реферат на тему «Применение ИТ при решении задач теории графов»

Введение

Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждение о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины 19 века и был сосредоточен главным образом в Англии. Имелось много причин для такого оживленного изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул.

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

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

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

Построение кратчайшей пары реберно-непересекающихся путей между двумя вершинами;
Построение K(K>2) кратчайшего множества реберно-непересекающихся путей между двумя вершинами.

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

Глава 1 Базовые понятия теории графов

1.1 Основные определения

Термин «граф» впервые появился в книге выдающегося венгерского математика Д. Кёнига в 1936г.

Пусть V — непустое множество, V⁽²⁾ — множество всех его двухэлементных подмножеств. Пара (V, Е), где Е — произвольное подмножество множества V⁽²⁾, называется графом (неориентированным графом).

В этой работе рассматриваются только конечные графы, т. е. множество V предполагается конечным, хотя в определении графа конечность этого множества не требуется. Элементы множества V называются вершинами графа, а элементы множества E — ребрами. Итак, граф — это конечное множество V вершин и множество E ребер, EV⁽²⁾. Множества вершин и ребер графа G обозначаются символами VG и EG соответственно. Вершины и ребра графа называются его элементами. Число |VG| вершин графа G называется его порядком и обозначается через |G|. Если |G| = n, |EG| = m, то G называют (n, m)-графом.

Говорят, что две вершины u и v графа смежны, если множество {и, v} является ребром, и не смежны в противном случае. Если e = {и, v} — ребро, то вершины u и v называют его концами. В этой ситуации говорят также, что ребро e соединяет вершины u и v. Такое ребро обозначается символом uv.

Два ребра называются смежными, если они имеют общий конец.

Вершина u и ребро e называются инцидентными, если v является концом ребра e (т. е. e = иv), и не инцидентными в противном случае.

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

Множество всех вершин графа G, смежных с некоторой вершиной v, называется окружением вершины v и обозначается через N_G(v) или просто N(v).

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

Иногда приведенное выше определение графа оказывается недостаточным и приходится рассматривать более общие объекты, в которых две вершины могут соединяться более чем одним ребром. Так возникает понятие «мультиграф». Мультиграф — это пара (V, E), где V — непустое множество (вершин), а E — семейство подмножеств множества V⁽²⁾ (ребер). Употребление термина «семейство» вместо «множество» означает, что элементы множества V⁽²⁾ могут в E повторяться, т. е. допускаются кратные ребра.

Дальнейшее обобщение состоит в том, что кроме кратных ребер допускаются еще петли, т. е. ребра, соединяющие вершину саму с собой. Псевдограф — это пара (V, E), где V — непустое множество (вершин), а E —некоторое семейство неупорядоченных пар вершин (ребер), не обязательно различных. На следующих рисунках изображены мультиграф и псевдограф.

Изучаются также ориентированные графы. Тогда множество V⁽²⁾ двухэлементных подмножеств заменяется декартовым квадратом V², состоящим из упорядоченных пар элементов множества V. Итак, ориентированный граф (или орграф) — это пара (V, A), где V — множество вершин, A — множество ориентированных ребер, которые называются дугами, AV². Если a = (v₁, v₂) — дуга, то вершины v₁ и v₂ называются ее началом и концом соответственно. На рисунке дуги отмечаются стрелками, указывающими направление от начала к концу. Аналогично определяется ориентированный мультиграф. Рассматриваются также смешанные графы, у которых есть и дуги, и неориентированные ребра.

Простой граф, в котором каждая пара вершин смежна называется полным. Полные графы обозначаются K_n. На рисунке ниже изображены полные графы K₁, K₂, K₃, K₄.

Граф называется двудольным, если существует такое разбиение его вершин на две части (доли) такие, что концы каждого ребра принадлежат разным частям. Полный двудольный граф, доли которого состоят из p и q вершин, обозначается символом K_p_,_q. На рисунке ниже изображены полные двудольные графы K_1,4, K_3,3.

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

Глава 2 Анализ GraphMagic: системы работы с графовыми моделями и алгоритмами

2.1 Основные преимущества системы GraphMagic

2.1.1 Дополняемость

Ключевым моментом в системе GraphMagic является возможность лёгкого расширения и дополнения новыми модулями – «плагинами». Плагины могут быть разработаны и использованы без участия разработчиков самой системы, так как система предоставляет для этого интерфейс. Более подробно интерфейс будет описан в разделе Архитектура системы Примерный процесс включения дополнения в приложение определяется так:

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

2.1.2 Кроссплатформенность

Второй основной особенностью системы является возможность её использования под различными операционными системами, используемыми целевой аудиторией пользователей. Как основные, поддерживаються следующие семейства операционных систем с графическим интерфейсом: Linux, Windows, Mac OS X последних версий.

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

2.1.3 Открытость и бесплатность

Третьей, особенностью системы является её разработка по модели open-source, которая позволяет использовать, распространять, изменять, распространять изменения любому заинтересованному лицу на бесплатной основе.

В связи с этим для разработки, тиражирования, передачи и изменения была принята лицензия GPLv2 (General Public License version 2) – стандартной общественной лицензии версии 2 разработанной Free Software Foundation в 1991 году.

2.2 Архитектура системы GraphMagic

Система GraphMagic логически разделена на несколько модулей, по функциям, ими выполняемым. Каждый модуль при сборке системы собирается в один архивный файл с именем модуля, версией модуля и общепринятым расширением .jar. Например, модуль gm-core версии 0.2, при сборке запакуется в файл gm-core-0.2.jar.

Проект разделён на 3 модуля: ядро, оболочка, и плагины. Ядро – центральный модуль системы, не зависит от других. Модуль оболочки – зависит от ядра. Плагины также зависят от ядра, причем изменения в визуализации графа «слушаются» модулем оболочки и автоматически отображаются на экране пользователя. Эта отображена на диаграмме ниже:

Зависимости между модулями

Первый модуль – gm-core, ядро системы. Содержит основные интерфейсы необходимые остальным модулям и плагинам, а также базовые их базовые реализации. Стоить отметить, что разработчикам плагинов рекомендуется создавать собственные форматы хранения данных графа, так как базовые реализации не могут удовлетворить всех потребностей всех алгоритмов на графах. Таким образом, естесственно предположить что каждый алгоритм по возможности должен отделять свою логику от логики базовой реализации структуры графа. Например, граф в базовой реализации интерфейса Graph – BasicGraph задаётся множеством вершин и множеством рёбер. Но для многих алгоритмов гораздо удобнее было бы пользоваться матричным представлением графа, особенно если элементами матрицы могут являться различные числовые значения, метки, стрелки и т. п. Поэтому плагин, реализующий такой алгоритм должен сам создавать структуру хранения графа используя предоставленный интерфейс, а после выполнения алгоритма возвращать полученный результат обратно в граф через этот же интерфейс.

На следующей диаграмме изображены некоторые основные интерфейсы и базовые реализации ядра системы.

Диаграмма одного из основных интерфейсов – Graph

Диаграммы интерфейсов вершины и ребра графа.

Разберём подробнее эти интерфейсы. У каждой вершины есть внутренний идентификатор (см. getId()), который используется для уникального идентифицирования вершины в графе. На данный момент система отображает этот идентификатор как метки вершин в визуализации графа, но в дальнейшем можно будет изменять визуализацию вершины произвольно.

Каждая вершина и ребро имеют смысл только в контексте некоторого графа. Поэтому в базовых реализациях нельзя создать объект вершины напрямую, а только через методы графа. Каждая вершина и ребро имеют ссылку на граф которому они принадлежат и используют её во внутренних реализациях. Например возьмём ребро, имеющее своей начальной вершиной (getTail()) вершину 1, и своей конечной вершиной (getHead()) вершину 2. Стандартный Java метод equals(), определяющий равенство этих объектов работает в зависимости от того, направлен наш граф или нет. Таким образом метод equals() для ребра (2,1) вернет значение «истина», если граф ненаправленный, и значение «ложь» если граф направленный.

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

Диаграмма интерфейса визуальной части вершины или ребра.

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

значение координаты равное 0 соответствует середине видимой на экране части визуализации графа,
значение координаты равное 1 соответствует правому/нижнему краю видимой на экране части визуализации графа,
значение координаты равное -1 соответствует левому/верхнему краю видимой на экране части визуализации графа,
остальные значения пропорционально расчитываются по формулам:

X = (2x – 2Rx – Rw)/Rw;

Y = (2y – 2Ry – Rh)/Rh;

Где

X – дробная координата в интерфейсе Visual,

x – целочисленная координата, выводимая на экране (в пикселах)

Rx – сдвиг вправо видимой части экрана относительно холста визуализации графа (в пикселах)

Rw – ширина видимой части экрана (в пикселах)

Аналогично для координаты y (высоты).

Такое преобразование позволяет абстрагироваться от размеров экрана, видимой части и смещения видимой части относительно холста отрисовки графа, что упрощает разработку плагинов.

Второй модуль – gm-shell, графическая оболочка. Этот модуль отвечает за визуализацию системы на экран пользователя и пользовательский интерфейс для работы.
На данный момент в системе реализованы как пример два плагина: gm-dijkstra (реализующий алгоритм Дейкстры поиска кратчайшего пути из одной вершины) и gm-graphmaker (строящий некоторые типы графов (циклический, двудольный, полный итд и размещающий вершины соответственно). Каждый из плагинов оформлен как отдельный логический модуль в системе. На диаграмме ниже представлены связи между плагинами и основным модулем:

Как видно из диаграммы, модуль gm-core требует реализации своего интерфейса GraphMagicPlugin для любого плагина, подключаемого к системе:

Плагин, реализующий этот интерфейс получает себе:

Объект типа GraphMagicAPI, через который он может получить граф, с которым в данный момент работает пользователь.
Объект типа Locale – язык и региональные настройки пользователя.

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

Глава 3 Плагин для системы GraphMagic

3.1 Описание плагина

Мой плагин edge-Disjoint-Algorithms для системы GraphMagic поможет специалистам, студентам и другим заинтересованным в теории графов людям работать с графовыми моделями и алгоритмами и решать две следующие задачи:

Построение кратчайшей пары реберно-непересекающихся путей между двумя вершинами;
Построение K(K>2) кратчайшего множества реберно-непересекающихся путей между двумя вершинами.

При реализации были использованы следующие технологии:

Java
Swing
JUnit
EasyMock
Maven

В основе работы данного плагина лежат два алгоритма:

Алгоритм Дейкстры (Dijkstra’s algorithm).
Модифицированный aлгоритм Дейкстры (Modified Dijkstra’s algorithm.

3.2 Используемые технологии

3.2.1 Java

Java — ссылка скрыта, разрабатываемый компанией ссылка скрыта и официально выпущенный ссылка скрыта ссылка скрыта.

Java — так называют не только сам язык, но и платформу для создания приложений уровня предприятий на основе данного языка.

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

Основные особенности языка Java

Начальным этапом является написание программы на языке высокого уровня (на языке Java). Далее, с помощью компилятора Java создается промежуточный код, или так называемый байт-код (bytecodes) для некой абстрактной виртуальной машины Java (Java Virtual Machine - JVM). Реальная же виртуальная машина устанавливается на той платформе, на которой предполагается выполнение написанной программы. Так, компания Sun совместно с рядом независимых разработчиков создала программную версию JVM для большинства известных платформ: Solaris, Linux, Mac OS, Windows (подробности см. com). Когда на компьютер загружается файл, содержащий байт-коды (так называемый файл класса - class file), он интерпретируется виртуальной машиной Java на данном компьютере, которая считывает файл класса и выполняет команды, написанные на языке Java. Поскольку ядро виртуальной машины легко переносится с одного типа компьютера на другой, можно ожидать, что для каждого нового типа процессора и для каждой новой операционной системы вскоре появится своя реализация JVM. Поэтому Java-программа сможет работать на любой известной платформе, для которой существует реализация JVM.

Кроме отмеченного главного преимущества Java (переносимость), следует привести еще ряд достоинств этой технологии:

Совершенство языка. Java сочетает в себе положительные стороны многих языков, особенно C++. Являясь принципиально объектно-ориентированным языком, Java "приучает" программиста мыслить современными программистскими парадигмами ООП.
Безопасность. В частности, в Java устранены некоторые небезопасные языковые средства, такие как указатели в C. Хотя на первый взгляд кажется, что использование указателей дает некоторую гибкость и свободу для программиста, но на практике это часто приводит к мучительной отладке больших и сложных программ, особенно, когда программа что-то пишет по ошибочному адресу. Следует отметить также повышенную безопасность апплетов (специальных Java программ для web-броузера).
Широкий спектр возможностей. В Java реализованы мощные средства для разработки расчетных программ, GUI-интерфейсов, сетевых и web приложений, программ для работы с базами данных и графикой. Некоторые программы, реализующие сложную графику для web, по мнению автора вообще могут эффективно быть написаны только на Java.
Открытая технология. Каждому, кто хочет работать на Java, не нужно платить для того, чтобы приобрести легальный пакет разработчика. Компания Sun предоставляет возможность всем приобрести его совершенно свободно (коммерческими могут быть лишь какие-то узкоспециальные программы и средства).
Высокое качество документации и учебных материалов. Это достоинство на самом деле является немаловажным. Во "всемирной паутине" можно найти немало различных библиотек, поддерживаемых группами энтузиастов, документация которых часто страдает неполнотой и ошибочностью. Java же является государственным стандартом (в США) и поддерживается официально разработчиком (компанией Sun), а также постоянно увеличивающимся международным сообществом Java программистов.
Возможность интеграции в Java откомпилированных кодов с других языков. Эта возможность реализована с помощью т.н. интерфейса JNI (Java Native Interface).

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

50 %. Поэтому такая замена заметно увеличивает скорость работы JVM. Стремительность прогресса вычислительной техники также уменьшает значимость этого недостатка.

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

3.2.2 Swing

Swing – это набор графических компонентов для создания пользовательских интерфейсов приложений и апплетов, а также вспомогательные классы и инструменты для работы с этими компонентами. Swing является на данный моменд де-факто стандартом создания пользовательского интерфейса приложения, работающим под многими платформами и обладающий достаточной функциональностью для большинства приложений. Также Swing можно расширять своими компонентами, реализовывать собственные менеджеры расположения компонетов в контейнерах и т.д. Например, в системе GraphMagic было создано несколько таких компонентов, например GraphPanel для отображения графа, VertexPanel для отображения вершины, EdgePanel для отображения ребра и некоторые другие.

Основой библиотеки Swing, тем тонким слоем, что лежит между ней и зависящим от платформы кодом, является библиотека AWT (Abstract Window Toolkit — инструментарий для работы с различными оконными средами). В отличие от библиотеки Swing, которая появилась в Java версии 1.1 как нестандартное дополнение и стала частью платформы только с выходом Java 2, пакет java.awt входил в Java с самого первого выпуска. Поначалу именно он предназначался для создания пользовательских интерфейсов. [5]

Swing был разработан как полное замещение AWT и исправления многих архитектурных ошибок устаревшего AWT.

Во-первых, в Swing было введено такое понятие как «легковесный компонент» (lightweight component), то есть компонент который может быть отрисован на экране без помощи операционной системы, то есть перехода на уровень ядра, что само по себе является дорогой операцией (сотни процессорных тактов). Легковесные компоненты значительно увеличили скорость реакции и отрисовки графических приложений.

Во-вторых, была полностью переработана модель обработки событий. Разработчикам теперь не пришлось отлавливать события через огромный оператор switch (или if) в перегруженном методе handleEvent() класса Component.

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

В-четвёртых, был проработан стандарт создания собственных компонентов. В AWT было достаточно сложно создавать собственные компоненты, так как приходилось следить за совместимостью компонента с другими компонентами, а также встроенные менеджеры расположения были либо очень простыми, либо очень сложными.

3.3 Результаты работы плагина

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

На двух следующих рисунках ниже можно увидеть результаты работы плагина по нахождению K(K>2) кратчайшего множества реберно-непересекающихся путей между двумя вершинами 1 и 5. К вводиться пользователем (K=3,K=4).

Заключение

В данной работе я расширил систему GraphMagic, полезную для специалистов, студентов и других заинтересованных в теории графов людей. Мной был разработан плагин edge-Disjoint-Algorithms, который позволяет решать следующие задачи:

Построение кратчайшей пары реберно-непересекающихся путей между двумя вершинами;
Построение K(K>2) кратчайшего множества реберно-непересекающихся путей между двумя вершинами.

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

Список литературы к реферату

«Лекции по теории графов» / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - М.:Наука,1990. - 384с.
«Элементы теории графов» / В.Н. Бурков, Д.А. Новиков
«Алгоритмы: построение и анализ» = «Introduction to Algorithms» — 2-е изд. / Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн — М.: ссылка скрыта, 2006. — С. 1296. — ссылка скрыта
Thinking in Java, 2nd edition, Revision 11©2000 by Bruce Eckel.
«Swing: Эффектные пользовательские интерфейсы» / И. А. Портнякин – Санкт-Петербург, 2005. – 523с.
ссылка скрыта
Survivable Networks: Algorithms for Diverse Routing (The Springer International Series in Engineering and Computer Science) (Hardcover) / Ramesh Bhandari, Ph.D. AT&T Laboratories, New Jersey, 1999.
ссылка скрыта
ссылка скрыта
ссылка скрыта
ссылка скрыта
ссылка скрыта
ссылка скрыта
ссылка скрыта

Предметный указатель к реферату.

граф

визуализация 4

программы

визуализации графов 4

теория графов 4

технологии

информационные 4

Интернет ресурсы в предметной области исследования

ссылка скрыта – сайт предоставляет полезную информацию по математике для всех категорий пользователей. Для студентов является помощником при решении математических задач. Преподавателям помогает использовать математические пакеты для поддержки курса лекций. Всем заинтересованным пользователям доступны разделы Mathcad, Matlab, Mathematica, Maple, Statistica, где можно найти электронные учебники, справочники, статьи.
ссылка скрыта – ScienceDirect содержит около 25% мировой текстовой и библиографической информации по проблемам науки, технологии и медицины. Кроме предоставления доступа к электронным книгам, справочникам и сериям книг ScienceDirect предлагает доступ к коллекции из более чем 2000 журналов.
ссылка скрыта - сайт отделения дискретных наук университета Саскачевана, Канада. На сайте представлена полезная информация о деятельности отделения, доступна электронная библиотека. Эксклюзивным наполнением сайта является информация и результаты проектов, проводимых в отделении.
ссылка скрыта - официальный сайт разработчика пакета Mathematica. На сайте можно ознакомиться с возможностями пакета, приобрести пакет. Также с сайта доступен широкий круг теоретического материала. Сайт содержит ссылки на общедоступные сервесы предоставляемые компанией.

Действующий личный сайт в WWW

ссылка скрыта

Граф научных интересов

Механико-математический факультет

Специальность дискретная математика и математическая кибернетика

Смежные специальности

01.01.05 — теория вероятностей и математическая статистика

1. Вероятностные пространства и случайные элементы

2. Статистические выводы и анализ данных

3. Вероятностно-статистическое моделирование

01.01.07 — вычислительная математика.

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

2. Теория и методы параллельных вычислений

3. Численные методы и алгоритмы решения прикладных задач

Основная специальность

01.01.09 – дискретная математика и математическая кибернетика

1. Теоpия гpафов и комбинатоpный анализ.

2. Теория сложности вычислений.

Сопутствующие

05.12.13 — системы, сети и устройства телекоммуникаций

1. Создание или развитие теоретических основ сетей

2. Анализ, синтез и оптимизация сетей, систем и устройств телекоммуникаций.

3. Разработка и исследование методов достижения предельной пропускной способности систем связи.

05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

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

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

05.13.13 — телекоммуникационные системы и компьютерные сети, физ.-мат.

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

05.13.17 — теоретические основы информатики

1. Разработка и исследование математических методов (моделей) представления и обработки информации, анализа информационных структур. Выявление и математическое моделирование информационных процессов и логических слабо формализованных структур и методов управления ими.

2. Разработка теоретических основ технологий программной реализации информационных методов и моделей.

Тестовые вопросы по Основам информационных технологий

(Жигмонт Андрей) Идентификатор (параметр id) тега HTML должен быть уникальным на странице и обязательно указывается для каждого тега

верно

нет такого параметра

не обязательно указывается

не должен быть уникальным

>(Жигмонт Андрей) CSS: значение аттрибута display не может быть равным

cascade

none

inline

block

Презентация магистерской диссертации