Cтраница 3
Это очень важно с точки зрения конкретной реализации процедуры экономии памяти: направленный процесс получения однозначной информации о попарной несовместимости связок отделяется от сугубо неоднозначного, комбинаторного поиска наилучшей раскраски, которая к тому же сама по себе является известной математической задачей. Заметим, что к идее раскраски вершин графа как средства экономии памяти можно прийти, как говорится, с налета, без понятия информационных связей. Рассмотрим задачу экономии памяти как желание поместить в одну ячейку памяти побольше величин так, чтобы суммарный расход памяти оказался бы наименьшим. Две величины несовместимы, если их нельзя поместить в одну ячейку памяти, и совместимы в противном случае. Это отношение несовместимости можно представить в виде графа, вершинами которого являются величины, а ребра соединяют несовместимые величины. Как видно, это почти граф несовместимости с двумя существенными, однако, отличиями: во-первых, мы не подозреваем, что аргументы и результаты, обозначенные одной величиной, могут принадлежать разным связкам и быть поэтому соотнесенными разным ячейкам памяти и, во-вторых, у нас на этом уровне нет никакого подхода к фактическому определению несовместимости. [31]