Программы и графы

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

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

Характеристика связности графов часто описывается достижимостью из некоторой вершины графа всех других, а очевидное средство такой достижимости – проложенный между парой вершин путь. Наличие множества путей, покрывающих вершины и\или ребра (дуги) графа, обеспечивает часто решение целевых задач таких, например, как минимизация контрольных точек или тестирование программ. Затрагиваются вопросы и цикломатической сложности графа.

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

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

Представление графа в памяти компьютера

Представление матрицами

Матрицы. При работе с графами используются различные алгебраические средства, в частности матрицы. Матрицы используются для создания описания графов G (V, U), которые могут быть применены в формульных выражениях для вычислений различных характеристик графов. Простейшие матричные описания графов – это матрицы инциденций и смежностей.

Рисунок 1 a) размеченный граф, b) матрица смежностей, с) матрица инциденций

Матрицей смежностей А(G) графа G c n вершинами (без петель) называется квадратная матрица размера (порядка) n×n с элементами а_ij: а_ij = 1, если в графе существует дуга (ребро) (x_i, x_j); a_ij = 0 в противном случае. Эта матрица симметрична относительно главной диагонали для неориентированного графа.

В случае орграфа входу в вершины графа соответствует столбец из нулей, выходу из вершин графа – строка из нулей, число единиц в i –й строке равно полустепени исхода вершины x_i, число единиц в j-м столбце равно полустепени захода вершины x_j.

Матрицей инцидентности В(G) графа G c n вершинами, которые соответствуют строкам матрицы и m дугами, соответствующими столбцам, называется прямоугольная матрица размера n×m с элементами b_ij: b_ij =1, если в графе существует вершина x_i, начало дуги u_j; b_ij = –1, если вершина x_i есть конец дуги u_j; b_ij = 0 противном случае.

Так как сумма элементов каждого столбца равно нулю, ранг матрицы инциденций всегда меньше, чем число ее строк. Для этой матрицы известны теоремы, полезные при вычислительных операциях с матрицей.

Теорема 1. Ранг матрицы инциденций связного графа G (V, U) равен rank = |V| – 1.

Следствие. Ранг матрицы инциденций произвольного графа G (V, U) равен разности числа вершин и числа компонент связности.

Теорема 2. В матрице инциденций значение любого минора равно 0, 1 или – 1.

Матрицей достижимости R(G) графа G c n вершинами называется квадратная матрица размера (порядка) n×n с элементами r_ij: r_ij = 1, если в графе вершина x_j достижима из вершины x_i; r_ij = 0 в противном случае.

Представление графа списками смежности

Список смежности для вершины х – это множество смежных с ней вершин или концов дуг, исходящих из вершины х. На рис. 2 представлены два графа G₁ и G₂: ориентированный и неориентированный с шестью вершинами каждый и их матрицами смежности. Граф представляется числом |Х| списков смежности, по одному для каждой вершины (рис. 3).

Рисунок 2 – Графы ориентированный и неориентированный

Ниже приводится пример задания графов G₁ и G₂с помощью списков смежности. Такое представление графа удобно при решении ряда задач, например, при перечислении контуров в графе (алгоритм Джонсона). Предварительно в графе отыскиваются бикомпоненты

Эффективность алгоритма

Сложность программ и ее оценивание. В качестве оценок сложности часто используют общепринятые выражения, к которым можно относиться по разному. Дело в том, что теоретические оценки получаются при разных и многих допущениях, которые в свою очередь не оцениваются.

Традиционные соотношения, используемые в теории оценивания сложности объектов

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

Время, затрачиваемое алгоритмом на получение результата, в зависимости от размерности задачи, называют временной сложностью или трудоемкостью алгоритма. Асимптотической временной сложностью (трудоемкостью) алгоритма называют предельное значение сложности при неограниченном увеличении размерности.

Размер памяти, минимально необходимый для решения задачи алгоритмом, называется емкостной сложностью или сложностью по объему памяти. Асимптотической емкостной сложностью по аналогии с асимптотической временной сложностью называют предельно минимальное значение памяти необходимое для получения результатов.

При обработке алгоритмом входов размерностью n за время сn², где с – некоторая постоянная, определяемая реализацией алгоритма, то говорят, что временная сложность этого алгоритма есть О(n²).

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

Здесь цикломатическая сложность является одной, но важной компонентой общей сложности (не затрагивая проблему в целом) программ. Речь у нас пойдет о цикломатической сложности.

Определение. Цикломатическим числом l(G) графа G c n вершинами и m дугами называется величина

l(G) = m(G) – n(G) + k(G), где k– число компонент связности. Характеристика l(G) определена только для неориентированного графа. Для связного графа k = 1, l(G) = m – n + 1.

Теорема 3. В сильно связном графе цикломатическое число равно числу линейно независимых контуров.

Пример. Изображение управляющего графа G приведено на рис. 4. В графе G выявлено 5 независимых контуров (цикломатическое число графа l(G) = m – n +1): [s, v₁, v₄, t, s], [v₁, v₄, v₁], [s, v₁, v₄, s], [s, v₂, t, s], [s, v₃, v₂, t, s]. При этом путь [s, v₁, v₄, s, v₁, v₄, v₁, v₄, v₁, v₄, t] может быть представлен линейной комбинацией [s, v₁, v₄, t, s] + 2[v₁, v₄, v₁] + [s, v₁, v₄, t, s]. Вычисление числа всех линейно независимых путей может служить оценкой сложности программы через цикломатическое число.

Определение. Цикломатической сложностью программы называется величина v(G) = l(G) + 2, где l(G) – цикломатическое число соответствующего управляющего графа. Величина v(G) зависит только от логической структуры управляющего графа.

Цикломатической матрицей H = ||h_ij|| орграфа G называется прямоугольная (0, 1)–матрица размера c×n, где с – число контуров, а n – число вершин, а

Рисунок 5 – Для графа с цикломатической матрицей (рис. 5а), матрица вложенности (рис.5б) и граф вложенности (рис. 5в)

Матрицей бикомпонент М(G) = R×R^Тграфа G c n вершинами называется квадратная матрица размера (порядка) n×n с элементами r_ij: r_ij = 1, если в графе вершина x_j достижима из вершины x_i; r_ij = 0 в противном случае.

Рисунок 6 – Для графа (рис.6а) матрицы смежности и достижимости (рис. 6б)

Рисунок 7 – Для графа (рис.6а) матрица бикомпонент и список бикомпонент

Графы как модели программ, данных и процессов

Формулируя задачи, предназначенные для решения на ПК, мы используем различные средства, математические, языковые, логические и др. Например, при анализе программ, при оптимизации, трансляции, проверке правильности, тестировании и т.п. традиционно используются различные графы. При этом, как правило, сами задачи значительно упрощаются при их рассмотрении на теоретико-графовых моделях. В основе многих задач и их моделей лежат управляющий и\или информационный графы программы.

Будем представлять программу (код) некоторой задачи текстом в некотором языке программирования. В тексте выделяются входы и выходы не только для кода в целом, но и для каждого отдельного оператора. Такие входы объединяются в множество В⁺и выходы – в множество В^–, причем В⁺UВ^–=B, а В⁺∩ В ^–= ∅.

Определение. Орграф G = (X, U) называется управляющим графом (р-графом, графом переходов), если выполнены следующие условия:

граф G не содержит параллельных дуг;
в графе G выделена одна вершина s – вход графа;
в графе G выделена хотя бы одна вершина t – выход графа;
каждая вершина x ϵ X графа G достижима из входа s;
из каждой вершины x ϵ X графа G достигает выход t.

Управляющий граф – основная модель программы, представляющая в виде орграфа систему управляющих связей в программе; в которой сохраняется членение программы на операторы, а также информация о тождественности операторов и возможных передачах управления между операторами.

Поясним определение примером. Пусть задан небольшой текст (программа BUBBLE) в алголоподобном языке

Этот текст преобразуется в ориентированный граф G по определенным правилам. Каждый оператор языка программирования (машинной команды, строки или любого фрагмента, признаваемого единицей языка) представляется отдельной вершиной графа с номером. Две вершины являются смежными, если между соответствующими операторами есть передача управления. Каждая передача управления представляется дугой графа G.

Оператор, после исполнения которого производится передача управления, изображается началом дуги, а оператор, которому передается управление – концом дуги. Каждой дуге присваивается буквенное имя. Линейные участки (цепочки вершин) существенно увеличивают изображение графа, но такие фрагменты можно заменять и одной вершиной.

Рисунок 8 – Управляющий граф (рис.7a) программы BUBBLEA, редуцированный граф (рис.7b)

Каждая вершина графа G (рис. 7а)) соответствует одному оператору, а дугам – передачи управления.

Справа на рис. 7) приведен редуцированный граф G, в котором линейные участки управляющего графа G представлены одной вершиной. В управляющем графе G можно рассматривать пути различного уровня. Уровень отражает глубину вложенности оператора. Путь уровня 0 есть простой s – t путь; путь уровня 1 есть простой путь или контур, который начинается или заканчивается в вершинах путей уровня 0.

Путь уровня i есть простой путь или контур, который начинается или заканчивается в вершинах путей меньшего уровня, и у которого ни одна другая вершина или дуга не входит в путь меньшего уровня. Ниже в таблице приводится полный список путей i-го уровня, i = 0,1, 2, управляющего графа программы

Тестирование

Определение. Тестирование – это проверка правильности программы посредством множества контрольных примеров – тестов.

Определение. Тестом, проверяющим программу, называется тройка t = <x, μ(G), y >, где х ⊆ Х – подмножество значений входных данных; μ(G) – это
s – t путь в управляющем графе G, соответствующий входным данным х;
y ⊆Y – подмножество значений выходных данных при прохождении программой пути s – t.

Очевидно, что полное тестирование согласно определению, требует прохода программы по всем путям управляющего графа G. Это очень трудозатратное и времязатратное действие (мероприятие), которое фактически не реализуется. Заменой тотального тестирования является разработка и реализация различных стратегий.

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

Достаточно общий случай предполагает построение тестирующих путей, покрывающих или все требуемые пути (заданные отрезки путей в управляющем графе), или все дуги, или все вершины управляющего графа

Определение. Орграф без петель I = (B, U) называется информационным графом, если его вершинами являются входы и выходы операторов программы, а дуга (х, у) принадлежит множеству дуг U тогда и только тогда, когда х ϵ В ^– и у ϵ В ⁺. Дуги информационного графа называются информационными парами, сохраняя традиционное название «дуга» для дуг управляющего графа.

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

В общем случае предполагается, что каждой вершине сопоставлен вес w >0, который можно интерпретировать как сложность оператора (или отдельного блока) программы, изображаемого данной вершиной. Отыскание тестирующих данных для тестирующего пути тем проще, чем меньше вершин будет в нем содержаться из множества K вершин, не подлежащих проверке. Это соответствует задаче отыскания (s–t) -пути с наибольшим весом при условии, что вершинам из множества K приписан небольшой отрицательный вес.

В общем случае тестирования программ требуется построить тестирующие пути, или все требуемые пути (заданные отрезки путей в управляющем графе), или все дуги, или все вершины управляющего графа. Эти задачи сводятся к построению различного вида покрытий графа путями.

Задача о контрольных точках. Большую задачу и программу трудно охватитить единым взглядом. Возникает необходимость при отладке больших программ создавать в текстах вспомогательные точки, в которых можно было бы получать промежуточные результаты и выводы о процессе отладки. Это позволит обнаруживать в ходе отладки программ ошибки в функционировании циклических частей программы..

Число таких контрольных точек желательно иметь небольшим. Таким образом, задача состоит в нахождении наименьшего числа точек программы, в которые нужно поместить операторы выдачи контрольных распечаток для обнаружения ошибок.

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

Однако существует приближенное решение, при котором отыскивается множество дуг, принадлежащих как можно большему числу контуров, алгоритм его можно записать следующим образом. Пусть K – множество дуг, разрывающих все контуры. На вход алгоритма поступает множество простых контуров, заданных перечислением дуг, входящих в контуры.

Шаг 1. Построить матрицу H = ||h_ij|| , контуры-дуги которой определяются:
h_ij= 1, если дуга u_j принадлежит контуру С_i, в противном случае, h_ij= 0.

Шаг 2. Включить в множество K те дуги, которым в матрице H соответствуют строки, содержащие только одну единицу (тем самым в множество K включаются все петли графа).

Шаг 3. Удалить из H строки и столбцы, соответствующие этим петлям.

Шаг 4. Пока Н не пусто цикл.

Шаг 5. Исключить из H все мажорируемые столбцы, то есть те, для которых найдется хотя бы один столбец, имеющий единицу в тех же строках, что и рассматриваемые.

Шаг 6. Включить в множество K дугу u_r , соответствующую столбцу с наибольшим числом единиц.

Шаг 7. Вычеркнуть из H строки, соответствующие единицам в r-м столбце, и сам r-й столбец. Проверка условия H = Ø, если оно не выполняется, необходимо вернуться к шагу 4. Если условие выполнено, конец алгоритма, K – искомое множество дуг, принадлежащих как можно большему числу контуров

Заключение

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

Возникал вопрос к автору: в чем оригинальность публикации? Ответ: в том, что вы не можете назвать других статей и авторов, где эта задача решается. Другой вопрос: для какой цели нужны все пути? Ответ: для многих, хотя бы для обнаружения закладок, не удаленных (забытых) контрольных точек... Один из отзывов: ...думаю студенты будут вам благодарны.

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

Литература

1. Авондо-Бодино Дж. Применение в экономике теории графов –М.: Прогресс,1966. –160с.
2. Харари Ф., Палмер 3. Харари Ф. Теория графов. –М.: Мир, 1973. – 300 с. 4. Евстигнеев В.А. Применение теории графов в программировании. - М.: Наука,1985.- 352 с. 5. Стечкин Б. С., Матиясевич Ю. В. Сито Эратосфена // Труды международной школы С. Б. Стечкина по теории функций. — Екатеринбург, 1999. – с. 148.
6. Трост Э. Простые числа. — М.: ГИФМЛ, 1959. — 136 с.
7. Касселс Дж. В. С. Введение в геометрию чисел. – М.: МИР, 1965. – 430 с.
8. Кнут Д. Искусство программирования. Т.2. Получисленные алгоритмы. – М.: Вильямс, 2000. 3-е издание. – 280 с.
9. Коблиц Н. Курс теории чисел и криптографии. — М.: Научное издательство ТВП, 2001.— 254 с.
10. Коваленко Д. В., Сидоров Д. П. Факторизация больших чисел распределенными вычислениями // Материалы научной конференции «XXX Огаревские чтения» (естественные и технические науки), Саранск, 2001. — С. 230-232.
11. Коваленко Д. В., Сидоров Д. П., Федосин С.А. Применение распределенных вычислительных систем для факторизации больших чисел // Тезисы международного семинара «Супервычисления и математическое моделирование», Саров, 2002. – С. 53-56.
12. Манин Ю. Н., Панчишкин А.А. Введение в современную теорию чисел. -М.: МЦНМО, 2013.-552 с.

∨ ∧ ∍ ∌ ∊ ∉ ∄ ∃ ∀ ∪ ∩ ≣ ≢ ≠ ≤ ≥ ⊆ ⊇ ⊃ ⊂ ≡ τ σ φ ω ψ χ υ ρ π ξ μ λ ζ η α β γ δ ε ρ ά ℓ ∅ ∞ ∩ ∛ ∜ ± ≠ ~ × ÷ ≤ ≥ ≈ ∀ ℃ °∈∋∃∅ Ω

Графы и программирование