Вариант 1593823524.
Цикл, проходящий через все вершины графа, называется
Цикл, проходящий через все ребра графа по одному разу, называется
В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке полиномиальность в среднем доказана для следующего распределения входных данных:
С какой точностью работает «чисто» жадный алгоритм для задачи о рюкзаке («хватать предметы по убыванию удельной стоимости, пока не кончится место в рюкзаке»)?
Как называется задача оптимизации со следующей формулировкой:
Гамильтонов цикл в графе:
Какова точность, гарантируемая жадным алгоритмом в задаче о k-покрытии?
Какой из этих тестов на простоту не является рандомизированным:
Сложность алгоритма динамического программирования для задачи о рюкзаке, который «помнит» о наиболее «легких» допустимых решениях: