Заглавная страница: различия между версиями

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

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

Теория графов из академической дисциплины все более превращается в средство, владение которым становится решающим для успешного применения компьютеров во многих прикладных областях. Несмотря на наличие обширной специальной литературы по решению задач на графах, широкое применение в практике программирования полученных математических результатов затруднено в силу отсутствия систематического их описания, ориентированного на программистов. Поэтому значительный класс практических задач, по существу сводящихся к простому выбору подходящего способа решения и к построению конкретных формулировок абстрактных алгоритмов, для многих программистов все еще остается полем для интеллектуальной деятельности по ``переоткрытию'' методов. Даже известный фундаментальный труд Д. Кнута ``Искусство программирования для ЭВМ'', если бы он и продолжился, как планировалось, не сможет решить эту проблему в силу ориентации Д. Кнута на низкоуровневое (в терминах машины MIX) описание алгоритмов. В изданных же трех томах серии излагается достаточно узкий класс используемых в программировании граф-моделей (фактически Д. Кнут ограничился рассмотрением деревьев и уже не планирует продолжать работу над серией).  

Предлагаемая вниманию читателя книга является одной из первых попыток систематизации знаний по алгоритмам теории графов для программиста.  

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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