4 группа/

Материал из Saratov FIO Wiki
Перейти к: навигация, поиск

==Достижения в теории графов

Графы и информация

Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана. Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось. Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.GriffPktiM953147.jpg

Графы и химия

Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:

          CnH2n+2           

Все атомы углеводорода четырехвалентны, все атомы водорода одновалентны. Структурные формулы простейших углеводородов показаны на рисунке 6.1 (а – метан CH4, б – этан C2H6). (РИСУНОК 6.1) Молекула каждого предельного углеводорода представляет собой дерево. Если удалить все атомы водорода, то оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина которого имеет степень не выше 4. Следовательно, число возможных структур предельных углеводородов, т. е. число гомологов данного вещества, равно числу деревьев с вершинами степени не больше четырех. Таким образом, подсчет числа гомологов предельных углеводородов также приводит к задаче о перечислении деревьев определенного типа. Эту задачу и ее обобщения рассмотрел Д. Пойа.

Графы и биология

Деревья играют большую роль в биологической теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся процессов – размножение бактерий. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево. Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.

Графы и физика

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

Алгоритмы на графах

Задачи теории графов хорошо моделируются средствами NP-языка. При использовании NP-языка от пользователя не требуется знаний алгоритмов из области теории графов, что позволяет снизить требования к его квалификации. И наоборот, если встроить алгоритмы теории графов в NP-систему, то методы теории графов будут применяться в задачах, которые и не ставились как задачи теории графов. Можно поставить следующие цели: 1.В постановке задачи «программирования в ограничениях» распознавать задачи, эффективное решение которых изучено в теории графов. В этом случае система сможет эффективно решить задачу, используя известный алгоритм. 2.Чаще всего, задачи теории графов возникает как подзадачи. Точнее говоря, если в программе распознана задачи из теории графов, то остаются еще дополнительные ограничения. В этом случае прямое применение алгоритмов из теории графов невозможно. Однако, если алгоритмы теории графов специальным образом модифицировать, то они могут применяться для отсечения дерева поиска, оценок границ переменных и критериев оптимальности. В предельном случае будет достигнута эффективность, как в пункте 1. Многие иностранные источники рекомендуют в процессе работы систем «программирования в ограничениях» особые случаи выражений или их частей переносить в графовое представление, а именно: Линейные ограничения двух переменных (в том числе неравенства) или векторов переменных (например, c(x1) <= c(x2), где x1 и x2 – переменные, c – вектор) Любые ограничения двух переменных, если комбинаций не очень много Биективные, сюръективные и инъективные отображения переменных Разъединения группы выражений (все указанные в ограничении выражения должны иметь различные значения). Особенно интересны случаи линейных выражений. Линейные уравнения Сериализация работ И так далее. Таким образом, встраивание структур и алгоритмов теории графов в NP-систему, приведет к «накоплению знаний» и общей интеллектуализации системы. Достижения теории графов станут доступны широкому кругу пользователей. Алгоритм накопления знаний известен в программировании в ограничениях: берем некоторый пример и добиваемся эффективного его решения. Берем второй пример, добиваемся его эффективного решения. После этого проверяем, хорошо ли решается первый пример, и если нет, то добивается эффективного решения обоих примеров. Далее берем третий пример и так далее. С каждым примером система становится (по вероятности) все более и более интеллектуальной. Если исходить из указанного алгоритма, то построение интеллектуальных систем – это кропотливый труд большого количества ученых из различных областей знаний (по крайней мере, математики), а не создание сверхгениального алгоритма решения NP-полной задачи. Jhyfndgkdfhj.jpg