Проблемы представления графов в функциональном программировании: магистерская диссертация / Александра Анатольевна Рыжевич; БГУ, Факультет прикладной математики и информатики, Кафедра дискретной математики и алгоритмики; науч. рук. Котов В. М.

Abstract

Магистерская диссертация, 57 страниц, 8 иллюстраций, 7 листингов, 13 источников, 1 приложение. ГРАФЫ; ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ; HASKELL; БЕЗОПАСНОСТЬ ТИПОВ; БИБЛИОТЕКА ГРАФОВ; МАКСИМАЛЬНЫЙ ПОТОК. Объектом исследования являются представление графов в чистом функциональном окружении, а также проблемы, затрудняющие написание идиоматического кода без потери эффективности. Цель работы включает в себя анализ существующих подходов, определение проблем, которые встречаются при работе с ними, а также проектирование библиотеки в качестве решения данных проблем, которая предлагает безопасный интерфейс для конструирования и эффективной обработки графов в чистом функциональном стиле. Методы исследования, использованные в данной работе, включают анализ, проектирование, экспериментирование и тестирование. Результатом работы является библиотека для обработки графов, реализованная на языке программирования Haskell. Библиотека предлагает средства для безопасного с точки зрения типов построения графов и оперирования ими. Она предоставляет низкоуровневый интерфейс для написания эффективного кода в императивном стиле, а также высокоуровневые абстракции для разработки идиоматических чистых функциональных алгоритмов на их основе. Библиотека включает обширный набор тестов и встраивается в существующие системы тестирования производительности различных библиотек для работы с графами на языке Haskell. Область применения результатов работы покрывает различные области исследования, для которых необходима библиотека обработки графов общего назначения, например компьютерные сети, организация данных, анализ социальных сетей и др.