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

<big>Приветствуем вас на страницах «WEGA».</big>

 

 

«WEGA» создается сотрудниками [http://pco.iis.nsk.su лаборатории конструирования и оптимизации программ] [http://www.iis.nsk.su Института систем информатики им. А.П.Ершова СО РАН] при частичной финансовой поддержке [http://www.rfbr.ru Российского фонда фундаментальных исследований] (грант РФФИ 09-07-00012).

По всем вопросам, связанным со словарём «WEGA», можно обращаться с администратору словаря

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

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

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

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

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

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