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

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


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


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


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


Первая книга по теории графов появилась в 1935 г., однако, началом широкого внедрения методов теории графов в практику научных и технических исследований следует считать 50-е годы XX века. В те годы были опубликованы отчёты американской корпорации RAND по математическим исследованиям в военной области, которые проводились в США во время и после окончания Второй мировой войны. Книги по теории графов (К. Берж, Р. Басакер и Т. Саати), вышедшие в начале 60-х годов, уже содержали материалы, относящиеся к приложениям теории графов в исследовании операций, дискретной оптимизации, электротехнике и пр. Затем последовали книги, посвящённые алгоритмическим проблемам теории графов и вопросам применения теории графов в отдельных областях знаний, в том числе в программировании. Среди них нужно назвать ``Введение в теоретическое программирование. Беседы о методе'' А.П. Ершова (1977 г.), ``Применение теории графов в программировании'' В.А. Евстигнеева (1985 г.), ``Оптимизирующие преобразования программ'' В.Н. Касьянова (1988 г.), ``Комбинаторика для программистов'' В. Липского (1988 г.).  
Первая книга по теории графов появилась в 1935 г., однако, началом широкого внедрения методов теории графов в практику научных и технических исследований следует считать 50-е годы XX века. В те годы были опубликованы отчёты американской корпорации RAND по математическим исследованиям в военной области, которые проводились в США во время и после окончания Второй мировой войны. Книги по теории графов (К. Берж, Р. Басакер и Т. Саати), вышедшие в начале 60-х годов, уже содержали материалы, относящиеся к приложениям теории графов в исследовании операций, дискретной оптимизации, электротехнике и пр. Затем последовали книги, посвящённые алгоритмическим проблемам теории графов и вопросам применения теории графов в отдельных областях знаний, в том числе в программировании. Среди них нужно назвать "Введение в теоретическое программирование. Беседы о методе" А.П. Ершова (1977 г.), "Применение теории графов в программировании" В.А. Евстигнеева (1985 г.), "Оптимизирующие преобразования программ" В.Н. Касьянова (1988 г.), "Комбинаторика для программистов" В. Липского (1988 г.).  


Заметим, что любая из книг, содержащих теоретико-графовые алгоритмы, оставалась либо книгой по теории графов, либо книгой по основной предметной области, использующей теоретико-графовые методы. Развивая эту тематику, мы решили объединить в одной книге графовые алгоритмы решения для графовых задач, и задачи по программированию вместе со специфическими алгоритмами их решения, основанными или использующими теоретико-графовые методы и алгоритмы. Этот подход подсказал нам идею разбить всё множество графов, которые наиболее часто встречаются в практике решения задач программирования, на классы, объединив вокруг каждого такого класса соответствующие задачи из информатики и программирования. Такими классами выступили классы деревьев, бесконтурных (или ациклических) графов и сводимых (или регуляризуемых) графов. Заметим, что последние два класса относятся к ориентированным графам, а из класса деревьев используется подкласс корневых деревьев, что также относится к ориентированным графам. Данный подход был успешно реализован нами в книгах ``Теория графов: алгоритмы обработки деревьев'' (1994 г.), ``Теория графов: алгоритмы обработки бесконтурных графов'' (1998 г.), ``Сводимые графы и граф-модели в программировании'' (1999 г.) и ``Толковый словарь по теории графов и ее применению в информатике и программировании'' (1999 г.). Однако небольшой тираж этих книг сделал их недоступными студентам и специалистам по программированию.  
Заметим, что любая из книг, содержащих теоретико-графовые алгоритмы, оставалась либо книгой по теории графов, либо книгой по основной предметной области, использующей теоретико-графовые методы. Развивая эту тематику, мы решили объединить в одной книге графовые алгоритмы решения для графовых задач, и задачи по программированию вместе со специфическими алгоритмами их решения, основанными или использующими теоретико-графовые методы и алгоритмы. Этот подход подсказал нам идею разбить всё множество графов, которые наиболее часто встречаются в практике решения задач программирования, на классы, объединив вокруг каждого такого класса соответствующие задачи из информатики и программирования. Такими классами выступили классы деревьев, бесконтурных (или ациклических) графов и сводимых (или регуляризуемых) графов. Заметим, что последние два класса относятся к ориентированным графам, а из класса деревьев используется подкласс корневых деревьев, что также относится к ориентированным графам. Данный подход был успешно реализован нами в книгах "Теория графов: алгоритмы обработки деревьев" (1994 г.), "Теория графов: алгоритмы обработки бесконтурных графов" (1998 г.), "Сводимые графы и граф-модели в программировании" (1999 г.) и "Толковый словарь по теории графов и ее применению в информатике и программировании" (1999 г.). Однако небольшой тираж этих книг сделал их недоступными студентам и специалистам по программированию.  


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


Часть III содержит справочный материал и состоит из двух приложений. Приложение 1 посвящено ``переборным'' (NP-полным) задачам, в котором наряду с введением понятия NP-полноты и рассмотрением списков NP-полных задач из различных областей программирования и информатики, описываются РАМ и ВУ-язык, используемые в книге для представления и анализа алгоритмов. В приложении 2 приведены характеристики размещений графов, включая размер области размещения, оценки величины углов, число сгибов и пр.  
Часть III содержит справочный материал и состоит из двух приложений. Приложение 1 посвящено "переборным" (NP-полным) задачам, в котором наряду с введением понятия NP-полноты и рассмотрением списков NP-полных задач из различных областей программирования и информатики, описываются РАМ и ВУ-язык, используемые в книге для представления и анализа алгоритмов. В приложении 2 приведены характеристики размещений графов, включая размер области размещения, оценки величины углов, число сгибов и пр.  


Формулировки основных свойств получают буквенные обозначения (А, Б, В, Г и т.д.) внутри каждого раздела, и ссылка на свойство в тексте образуется из номера раздела и его буквенного обозначения, например, свойство 1.2.3, А указывает на свойство А из раздела 1.2.3. Если производится ссылка на свойство в том же разделе, то номер раздела может опускаться.  
Формулировки основных свойств получают буквенные обозначения (А, Б, В, Г и т.д.) внутри каждого раздела, и ссылка на свойство в тексте образуется из номера раздела и его буквенного обозначения, например, свойство 1.2.3, А указывает на свойство А из раздела 1.2.3. Если производится ссылка на свойство в том же разделе, то номер раздела может опускаться.  
Строка 48: Строка 49:
Монография основывается на работах авторов в рамках проектов, которые выполнялись в лаборатории конструирования и оптимизации программ Института систем информатики Сибирского отделения Российской академии наук (ИСИ СО РАН) и на кафедре программирования Новосибирского государственного университета (НГУ) при финансовой поддержке Российского фонда фундаментальных исследований (РФФИ) и Минобразования. Авторы благодарны всем коллегам, принимавшим участие в выполнении этих проектов, в первую очередь И.А. Лисицыну, Е.С. Мердишевой, Т.С. Мердишевой, В.Е. Казанцеву, Д.Е. Бабурину и И.Л. Мирзуитовой.  
Монография основывается на работах авторов в рамках проектов, которые выполнялись в лаборатории конструирования и оптимизации программ Института систем информатики Сибирского отделения Российской академии наук (ИСИ СО РАН) и на кафедре программирования Новосибирского государственного университета (НГУ) при финансовой поддержке Российского фонда фундаментальных исследований (РФФИ) и Минобразования. Авторы благодарны всем коллегам, принимавшим участие в выполнении этих проектов, в первую очередь И.А. Лисицыну, Е.С. Мердишевой, Т.С. Мердишевой, В.Е. Казанцеву, Д.Е. Бабурину и И.Л. Мирзуитовой.  


Нельзя не назвать и тех, кто своими работами, советами и поддержкой способствовал появлению этой книги. Прежде всего -- это А.П. Ершов, С.С. Лавров, А.А. Летичевский, Э.З. Любимский, В.Е. Котов, В.К. Попков и А.А. Берс. Всем им, а также И.П. Мелинг и Л.К. Грушецкой, оказавшим большую помощь в технической подготовке рукописи, авторы выражают искреннюю признательность.  
Нельзя не назвать и тех, кто своими работами, советами и поддержкой способствовал появлению этой книги. Прежде всего - это А.П. Ершов, С.С. Лавров, А.А. Летичевский, Э.З. Любимский, В.Е. Котов, В.К. Попков и А.А. Берс. Всем им, а также И.П. Мелинг и Л.К. Грушецкой, оказавшим большую помощь в технической подготовке рукописи, авторы выражают искреннюю признательность.  


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

Навигация