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