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

Вопрос 1

1.  Динамическое программирование
2.  Вероятностное округление
3.  Полный перебор
4.  Монте-Карло
5.  Дерандомизация вероятностного округления

Вопрос 2

1.  вершин
2.  ребер
3.  связных подграфов
4.  циклов

Вопрос 3

1.  Гамильтоновой
2.  Евклидовой
3.  Треугольной
4.  Метрической
5.  Эйлеровой

Вопрос 4

1.  Находит приближенное решение, с точностью
2.  Точность решения в среднем —
3.  Вероятностно подсчитывал число невыполненных наборов
4.  Вероятностно подсчитывал число выполненных наборов
5.  Заполнял таблицу «наиболее выполняющими» наборами
6.  Подсчитывал число невыполненных наборов

Вопрос 5

1.  проходит через все вершины и ребра по одному разу
2.  проходит через все вершины по одному разу
3.  проходит через все ребра по одному разу

Вопрос 6

1.  MIN-CUT
2.  MAX-SAT
3.  MAX-CUT
4.  Рюкзак-оптимизация
5.  TSP
6.  Рюкзак-выполнимость

Вопрос 7

1.  Поиск минимального разреза
2.  Поиск кратчайших путей
3.  Поиск минимального обхода вершин (TSP)
4.  Поиск минимального остовного дерева
5.  Рюкзак-оптимальность

Вопрос 8

1.  Демократизация
2.  Дератизация
3.  Метод Монте-Карло
4.  Дерандомизация
5.  Шервудские алгоритмы
6.  Метод Лас-Вегас
7.  Рандомизация

Вопрос 9

1.  Петля Нестерова
2.  Наполеонов цикл
3.  Гамильтонов цикл
4.  Эйлеров цикл
5.  Цикл Нельсона

Вопрос 10

1.  3
2.  2
3.  
4.  
5.  e
6.