Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

7) оптимальный раскрой (бумага, стальной прокат, отливка), оптимизация маршрутов в воздушном пространстве, инвестиций, станочного парка; 8) составление расписаний, учитьтваютттих определённые условия; 9) оптимальная загрузка ёмкости (рюкзак, поезд, корабль, самолёт) при не­ которых условиях; 10) динамическое распределение памяти. Раскроем эту проблему. Пусть заданы - множество элементов данных, размер s(a)eZ^, Z^={ 1,2,3,...}, каждо­ го элемента данных аеА, время поступления г(а)е2д , = {0,1,2,3,...} и время d(a)EZ^ окончания работы с элементом данных аеА, положительное целое число D - размер области памяти. Вопрос. Суш,ествует ли для множества эле­ ментов данных допустимое распределение памяти? Иначе говоря, суш,ествует ли такая функция о: А^{1,2,3,... }, что для каждого элемента интервал 1(а)=[а(а), <7(a )+s (a)-l] содержится в [1, D], причём для любых а, а*^А, если 1(а)п 1(а^^)^0, то ли­ бо d(a)<r(a^), либо d(a^)<r(a). В случае, когда размеры всех элементов данных одинаковы, задача реша­ ется за полиномиальное время [12]; 11) организация памяти в виде корневого дерева. Задача состоит в сле­ дующем [12]. Заданы конечное множество X, набор C={Xi,X2,... ,Х„} подмно­ жеств множества X, положительное целое число К. Вопрос. Суш,ествует ли та­ кой набор C={Xi^\ Х2* ...,XnV подмножеств множествах, чтоX i ^X i ^ при всех п i, l<i <п, X \ Xi^\Xi \ <К и суш,ествует ли ориентированное корневое дерево i=l Т(х,А), в котором элементы каждого из подмножеств Х/*, 1< i < п, образуют ориентированный путь? 12) достаточность числа регистров для реализации циклов. Задача состоит в следующем. Заданы множество V параметров циклов, длина цикла NeZ'^, для каждого параметра v начальное время sfvJeZg , продолжительность 1(V)EZ^ И целое положительное число К. Вопрос. Достаточно ли К регистров для запоми­ нания параметров циклов? Иными словами, существует ли такое назначение ре­ гистров /• V^L,2,3,... ,К}, что если f(u)=f(v) для некоторых U,VEV, ТО ИЗ нера­ венства ^(v) следует, что s(u)+l(u) <s(v) я s(v)+l(v)(modN) <s(u)? Если число К заранее фиксировано, то задача разрешима за полиномиаль­ ное время [12]. Интуитивно класс Р можно представлять себе как класс задач, которые можно быстро решить, а класс NP - как класс задач, решение которых может быть быстро проверено. На практике решить задачу часто намного труднее, чем проверить уже готовое решение. Например, выяснить, является ли граф с п вершинами гамильтоновым, не просто, но если задана последовательность из п 227