Молодежь и наука - третье тысячелетие: Материалы студенческой научно-практической конференции с международным участием

4 Данная проблема была решена в статье [3]. В результате улучшилось быст- родействие программы и компилятора. Идея решения заключалась в декомпози- ции вычисляемых выражений и учете уже находящихся в регистре значений, по которым строился специальный граф. Для этого сначала использовалось прибли- жение Хайтина, а затем демонстрировалась доработанная авторами статьи эври- стика. После чего происходила генерация кода. Для программы строится граф несовместимости: вершины графа представ- ляют диапазоны данных, ребра – наложения двух соединенных диапазонов (име- ется в виду зависимости между ними). Затем из получившегося графа удаляются вершины, мешающие его окраски не более чем в цветов (по количеству реги- стров процессора), а затем граф раскрашиваться. Каждый цвет соответствует од- ному из регистров процессора. Раскраска позволяет избежать выполнения двух несовместимых операций, так как само определения правильной раскраски ис- ключает возможность раскрасить одним цветом две смежные вершины. Тем са- мым достигается такое состояние регистров, что они остаются плотно (исполь- зуется максимально возможное число регистров) заполнены во время всего жиз- ненного цикла программы, если операции, содержащиеся в коде программы, поз- воляют это сделать. В приведенной проблеме видна специфика применения раскраски графов при решении задач. Действительно, каждый из цветов рассматривается как от- дельный элемент, который можно использовать для совершения определенных вычислений. Если обобщить приведенное решение, то раскраски графов могут быть использованы для распределения каких-либо операций или работы между несколькими исполнителями. Некоторые задачи о составления расписаний также могут быть решены с применением раскраски графов [2]. Льюис описывает алгоритмы разработки плана рассадки людей, составления расписания для университета, а также реше- ния латинских квадратов и головоломок судоку [1]. Дальнейшие исследования в области раскраски графов таких, как нахожде- ние лучшей эвристики, возможно нахождения быстрого алгоритма раскраски (равенство классов P и NP пока не опровергнуто) дадут возможность в поиске быстрых и качественных решений в уже указанных областях, а также возмож- ность применения раскраски графов в малоизученных областях. Литература 1. Lewis, R. M. R. A Guide to Graph Colouring Algorithms and Applications [Электронный ресурс] / R. M. R. Lewis. – Springer. – 2015. – URL: https://doc.lagout.org/ science/0_Computer%20Science/2_Algorithms/A%20Guide%20to%20Graph%20Colour- ing_%20Algorithms%20and%20Applications%20%5BLewis%202015-10-27%5D.pdf (дата обращения: 01.03.2020). 2. Marx, D. Graph Coloring Problems And Their Applications In Scheduling [Электронный ресурс] / D. Marx. – Department of Computer Science and Infor- mation Theory Budapest University of Technology and Economics. –