Еженедельный по «сложности алгоритмов» для 3 курса ИСПРАН — вопросы

Применение теории генетических алгоритмов
Построение эффективных вероятностных приближенных алгоритмов с оценками точности в худшем случае
Построение эффективных метаэвристик

Паросочетание, покрывающее все вершины графа, называется

Какова сложность вероятностного алгоритма Фрейвалда для проверки тождества AB=C для матриц ?

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

Построение эффективных алгоритмов методом ветвей и границ
Построение эффективных приближенных алгоритмов, использующих метод вероятностного округления решений релаксационных задач
Построение недетерминированных полиномиальных алгоритмов

Задача Коммивояжера, в которой для матрицы расстояний выполнено неравенство треугольника, называется:

Для чего применяется «метод условных вероятностей»:

Какой алгоритм используется в алгоритме Кристофидеса?

Гамильтонов цикл в графе:

Навигация