Математическая логика и теория алгоритмов

10) динамическое распределение памяти. Раскроем эт>' пробле­ му. Пусть заданы А - множество элементов данных, размер s(d)eZ* 2^={1,2,3,...}, каждого элемента данных аеА, время поступления г(а)е ZQ , ZQ ={0,1,2,3,...} и время d(a)eZ' окончания работы с э ментом данных аеЛ, положительное целое число D - размер области памяти. Существует ли для множества элементов данных допустимое распределение памяти? Иначе говоря, существует ли такая функция ст. ^->{1,2,3,...}, что для каждого элемента аеЛ интервал /(а)=[а(<з), су(а)+5(а)-11 содержится в [1, D], причем для любых а, а*еА, если 1(а)п 1( то либо d(a)< г(а*), либо d{a'*)< г{а). В случае, когда размеры всех элементов данных одинаковы, задача решается за полиномиальное время [10]; 11) организация памяти в виде корневого дерева. Задача состоит в следующем [10]. Заданы конечное множество X, набор подмножеств множествах, положительное целое чис­ ло К. Существует ли такой набор С={Х|* Х2*,,..,Х„*} подмножеств множествах, что X сХ)* при всех г, Ы i ^ ^ 1 I < iT и суще- ствует ли ориентированное корневое дерево Г(ху4.), в котором элемен­ ты каждого из подмножеств Х^* 1< i < «, образуют ориентированный путь? 12) достаточность числа регистров для реализации циклов. За­ дача состоит в следующем. Заданы мнолсество V параметров циклов, длина цикла NeZ^, для каждого параметра v начальное время s(v)g Zq и продолжительность l{v)sZ\ целое положительное число Достаточно ли К регистров для запоминания параметров циклов? Иными словами, существует ли такое назначение регистров f. F->{l,2,3,...,Ar}, что еслиДгО=Ду) для некоторых u,veF, то из нера венства s(u) ^s(v) следует, что s(u)+l(u) < s{v) и j(v)+/(v)(modiV Если число К заранее фиксировано, то задача разрешима за полиномиальное время [10]. 288