А. М. Горького математико-механический факультет кафедра алгебры и геометрии Библиотека структур данных и алгоритмов для графов и множеств Диплом

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

Диплом

Содержание Допустить к защите 4. Структуры данных 7 5. Иерархия классов 15 7. Пример использования GRAPHLAB 25 Краткий реферат 1. Введение в проблему 2. Общая характеристика системы GRAPHLAB 3. Использование GRAPHLAB в разработках 4. Структуры данных 4.1. Скалярные структуры данных 4.2. Списковые структуры данных Item Head() - возвращает первый элемент списка; Item Item Eject() - возвращает последний элемент, удаляя его из cписка; Inject(Item Очередь (Queue) - это список, для которого разрешены лишь операции Head, Pop, Inject. Дек Дек с ограниченным выводом 4.3. Эффективные структуры данных 4.3.1 Семейства непересекающихся множеств Левацкие хипы O(1); время на findmin O 4.3.3 Бинарные деревья поиска ... Полное содержание

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

• Петербургский Государственный Университет Математико-Механический Факультет Кафедра, 596.99kb.
• Язык описания алгоритмов начертательной геометрии adgl, 70.57kb.
• «Применение информационный технологий в теории графов», 272.84kb.
• Петербургский Государственный Университет Математико-механический факультет Кафедра, 358.16kb.
• Петербургский Государственный Университет Математико-механический факультет Кафедра, 415.59kb.
• Петербургский Государственный Университет Математико-механический факультет Кафедра, 392.11kb.
• Рабочей программы дисциплины Структуры и алгоритмы обработки данных по направлению, 21.62kb.
• Примерная рабочая программа по дисциплине: «Дискретная математика» Факультет экономический, 134.71kb.
• Петербургский Государственный Университет Математико-механический факультет Кафедра, 390.77kb.
• Санкт-Петербургский государственный университет Математико-механический факультет Кафедра, 441.47kb.

Государственный комитет Российской Федерации

по высшему образованию

Уральский Государственный Университет им. А.М.Горького

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

кафедра алгебры и геометрии

Библиотека структур данных и алгоритмов для графов и множеств



Дипломная работа

студента 5 курса

Грина Григория Владимировича


Научный руководитель:

доктор математических наук

профессор

Баранский Виталий Анатольевич




Допустить к защите


Зав. кафедрой







Екатеринбург

1995

Содержание:

Краткий реферат

GRAPHLAB — это объектно-ориентированная библиотека структур данных и алгоритмов для множеств и графов. В GRAPHLAB’е реализованы основные структуры данных, необходимые при решении многочисленных задач по обработке графов. Использование этих структур делает программирование

• быстрым - библиотека содержит в себе большую часть повторяющегося кода;
  
• надежным - каждая процедура библиотеки тщательно отлажена;
  
• наглядным - активно применяемые принципы ООП предлагают интуитивно понятную иерархию классов;
  
• эффективным - реализованы очень эффективные алгоритмы поддержки разнообразных структур данных.
  
• По сути дела реализован язык — надмножество языка C++ — специально предназначенный для решения задач на графах. В работе приведен ряд примеров разработки алгоритмов на данном языке.
  

1. Введение в проблему

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

1. Написание процедур работы с простейшими объектами достаточно малоинтересное занятие.
   
2. Желание быстрее приступить к алгоритму приводит к тому, что основным структурам данных отводится недостаточно внимания и реализуются простейшие методы, часто наименее эффективные.
   
3. По той же причине в программах появляется много ошибок, не имеющих отношения к основной задаче.
   
4. Пользовательский интерфейс либо вообще не продумывается либо реализуется наиболее поверхностное решение.
   

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

Анализ программ, написанных студентами математико-механического факультета УрГУ показывает, что программы по курсам ВМП и САПР на 60-70% состоят из процедур, обеспечивающих поддержку структур данных и пользовательский интерфейс. При этом программы очень плохо читаемы и трудно модифицируемы.

2. Общая характеристика системы GRAPHLAB

GRAPHLAB - это объектно-ориентированная библиотека структур данных и алгоритмов для множеств и графов. В GRAPHLAB’е реализованы основные структуры данных, необходимые при решении многочисленных задач по обработке графов. Использование этих структур делает программирование

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