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

Тест по курсу «Эффективные алгоритмы»

Вариант 2376654032.

Ваше имя*:

Является ли конкатенация двух разрешимых языков перечислимой?

Замкнутость по какой из операций выполнена как для разрешимых, так и для перечислимых языков?

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

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

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

Навигация