VOPR02 (811102), страница 2
Текст из файла (страница 2)
69. Доказать, что задача ²упаковка в контейнеры² является NP- полной в сильном смысле.
70. Сводимость по Тьюрингу. NP-трудные задачи.
71. Доказать, что задача ²К-е по порядку множество² является NP-трудной.
72. Доказать, что оптимизационные варианты семи основных NP-полных задач являются NP-эквивалентными.
73. Доказать, что оптимизационная задача коммивояжера является NP-эквивалентной.
74. Приближенный полиномиальный алгоритм решения задачи ²упаковка в контейнеры² с оценкой RA <2.
75. Доказать, что если P ¹ NP, то не существует полиномиального приближенного алгоритма решения задачи о рюкзаке с оценкой ½A(I) - OPT(I)½ £ K.
76. Доказать, что если P ¹ NP, то не существует полиномиального приближенного алгоритма решения задачи о максимальном независимом множестве с оценкой ½A(I)- - OPT(I)½ £ K.
77. Приближенный полиномиальный алгоритм решения задачи коммивояжера (с неравенством треугольника) с оценкой RA < 1.5.
78. Приближенный полиномиальный алгоритм решения задачи ²многопроцессорное расписание без прерываний² с оценкой RA <2.
79. Приближенный полиномиальный алгоритм решения задачи ²вершинное покрытие² с оценкой RA <2.
80. Доказать, что если P ¹ NP, то не существует полиномиального приближенного алгоритма решения задачи коммивояжера с оценкой A(I)/OPT(I) £ K.
81. Метод ²ветвей и границ² для решения задачи ²многопроцессорное расписание без прерываний (случай различных процессоров)².
82. Метод ²ветвей и границ² для решения задачи распределения нескладируемых ресурсов на сети.
83. Метод ²ветвей и границ² для решения задачи коммивояжера.
84. Метод ²ветвей и границ² для решения задачи ²самый длинный путь².
85. Приближенный алгоритм решения задачи о рюкзаке с временной сложностью O(n3/e).
86. Сети Петри. Построение конечного дерева достижимости.
87. Матричная форма представления сетей Петри. Решение задачи о достижимости маркировки.
88. Моделирование вычислительных систем с помощью сетей Петри.
89. Представление конечных автоматов и графов вычислений сетями Петри.
90. Лемма Шварца. Рандомизированный алгоритм решения задачи об идентичности полиномов и задачи о паросочетаниях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
