Граф залежностей — орієнтований граф, що відображає співвідношення множини елементів деякої сукупності відповідно до вибраних транзитивних відношень над нею.
Такі графи часто застосовують в інформатиці та цифровій електроніці, зокрема, за графом залежностей визначають порядок обчислень або невідповідність порядку залежностям, заданим графом.
Визначення
Нехай дано множину об'єктів і відношення транзитивності де , що моделює залежність «для обчислення потрібно спочатку обчислити », тоді граф залежностей — це граф де і є транзитивним замиканням .
Наприклад, деякий калькулятор підтримує запис константи в деяку змінну і додавання двох змінних із записом результату в деяку третю змінну. Нехай дано кілька виразів, наприклад, . Тоді і . Можна явно вивести всі відношення: залежить від і , тому що дві змінні можна додати тоді й лише тоді, коли відомі значення обох змінних. Таким чином, і слід обчислити перед . Однак, значення відоме зразу, тому що це числова константа.
Виявлення неможливих обчислень
в графі залежностей призводять до ситуації, в якій немає доступного порядку обчислень, тому що жоден з об'єктів циклу не можна вважати першим. Якщо циклічних залежностей немає, то ми маємо спрямований ациклічний граф, і порядок обчислень можна визначити за допомогою топологічного сортування. Більшість алгоритмів топологічного сортування здатні виявляти цикли на вході, однак, бажано виявляти цикли окремо від топологічного сортування, щоб забезпечити належне їх опрацювання.
У прикладі на основі калькулятора, система виразів містить циклічну залежність. слід обчислити перед , слід обчислити перед , слід обчислити перед .
Визначення порядку обчислень
Коректний порядок обчислень — це нумерація об'єктів, яка впорядковує вузли графа залежностей так, що виконується рівність: , де . Це означає, що якщо нумерацією визначено, що обчислюється перед , то не може залежати від . Більш того, може існувати більше ніж один коректний порядок обчислень. По суті, коректна нумерація є топологічним сортуванням, і будь-яке топологічне сортування є коректною нумерацією. Насправді, будь-який алгоритм, що виконує коректне топологічне сортування, одночасно визначає коректний порядок обчислень.
Для системи (в прикладі з калькулятором) коректний порядок: , однак, також є коректним порядком обчислень.
Моноїдна структура
Ациклічний граф залежностей відповідає сліду слідового моноїда так:12:
- Функція позначає кожну вершину символом з алфавіту
- Ребро або існує тоді й лише тоді, коли перебуває у відношенні залежності .
- Два графи вважаються рівними, за умови відповідності їхніх міток та ребер.
Тоді рядок, що складається з міток вершин, упорядкованих правильним порядком оцінки, відповідає рядку сліду.
Моноїдна операція приймає диз'юнктне об'єднання множин вершин двох графів, зберігає наявні в кожному графі ребра та малює нові ребра від першого до другого, де це дозволяє відношення залежності:14
Тотожністю є порожній граф.
Приклади
Граф залежностей використовують у:
- Автоматизованому встановленні програмного забезпечення. Рухом по графу знаходять пакунки програм, які потрібні, але ще не встановлені. Залежності визначаються зв'язками між пакунками.
- В компілятор і формальних мовах:
- Планування інструкцій. Граф залежностей обчислюється для операндів асемблера або проміжних інструкцій і використовується для визначення оптимального порядку інструкцій.
- Видалення мертвого коду: якщо жодна побічна операція не залежить від змінної, ця змінна вважається мертвою і її можна видалити.
Графи залежностей це одне з питань:
- Теорії обмежень: початкові дані перероблюються в кінцеві в ході декількох залежних етапів.
- Теорії розкладів — набір взаємопов'язаних теоретичних проблем у галузі комп'ютерних наук.
Див. також
Примітки
- Наприклад, в утилітах make
Джерела
- Mazurkiewicz, Antoni (1995). Introduction to Trace Theory. У Rozenberg, G.; Diekert, V. (ред.). The Book of Traces (англ.). Singapore: World Scientific. ISBN .
{{}}
:|access-date=
вимагає|url=
()
Література
- Balmas, Francoise (2001) , [1] wcre, p. 261, Eighth Working Conference on Reverse Engineering (WCRE'01)
Посилання
- Compiler research project. Граф залежностей [ 4 березня 2016 у Wayback Machine.] (рос.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет