Автореферат диссертации на соискание ученой степени кандидата
физико-математических наук. Специальность 05.13.11 – Математическое
и программное обеспечение вычислительных машин, комплексов и
компьютерных сетей.
- М.: Институт системного программирования РАН, 2006. – 26 с. Графы являются естественным и наглядным средством представления сложных структур и процессов. Это позволяет широко использовать их в компьютерных системах при решении различных задач. Во многих из этих задач графы используются для представления данных неоднородной структуры. К таким задачам относятся представление деревьев абстрактного синтаксиса программ в трансляторах языков программирования, описание структуры и обработки объектных моделей документов, обработка сложных структур данных предметной области в прикладных задачах и т.п.
Хорошо исследованы методы решения широкого класса задач на графах, изучены алгоритмы обработки графов, обеспечивающие эффективное решение этих задач. Однако для успешного решения задач на графах необходим не только правильный выбор алгоритма, но и такое представление графа в компьютерной системе, которое обеспечивает эффективную реализацию выбранного алгоритма обработки графа.
Алгоритм оказывает наибольшее влияние на эффективность решения задачи, а представление графа и способ реализации алгоритма определяют трудоемкость реализации и сопровождения. Естественно, возникает необходимость создания таких методов представления графов и реализации операций над ними, которые облегчают разработку и сопровождение программ, использующих графовые структуры данных.
- М.: Институт системного программирования РАН, 2006. – 26 с. Графы являются естественным и наглядным средством представления сложных структур и процессов. Это позволяет широко использовать их в компьютерных системах при решении различных задач. Во многих из этих задач графы используются для представления данных неоднородной структуры. К таким задачам относятся представление деревьев абстрактного синтаксиса программ в трансляторах языков программирования, описание структуры и обработки объектных моделей документов, обработка сложных структур данных предметной области в прикладных задачах и т.п.
Хорошо исследованы методы решения широкого класса задач на графах, изучены алгоритмы обработки графов, обеспечивающие эффективное решение этих задач. Однако для успешного решения задач на графах необходим не только правильный выбор алгоритма, но и такое представление графа в компьютерной системе, которое обеспечивает эффективную реализацию выбранного алгоритма обработки графа.
Алгоритм оказывает наибольшее влияние на эффективность решения задачи, а представление графа и способ реализации алгоритма определяют трудоемкость реализации и сопровождения. Естественно, возникает необходимость создания таких методов представления графов и реализации операций над ними, которые облегчают разработку и сопровождение программ, использующих графовые структуры данных.