Font size
WorksheetsАнализ и разработка алгоритмов
Total questions: 6
Worksheet time: 5mins
Обозначим количество вершин в графе через n. Что означает выражение O(n), описывающее временную сложность некоторого алгоритма на графах?
Алгоритм предполагает перебор всех рёбер один раз
Алгоритм предполагает перебор всех вершин один раз
Алгоритм предполагает перебор всех рёбер и вершин один раз
С чем связана необходимость усреднять по нескольким запускам замеры времени работы алгоритма при эмпирическом анализе временной сложности алгоритма?
Время работы алгоритма может варьироваться от запуска к запуску
При однократном запуске есть вероятность получить некорректный результат из-за особенностей работы компьютера
Чтобы исключить влияние сторонних факторов на результирующий замер
Дайте определение прямых методов оптимизации.
К задачам оптимизации относятся
Задача максимизации
Задача минимизации
Задача поиска корней многочлена
Задача построения минимального остовного дерева
Алгоритм Дейкстры, А*, алгоритм Беллмана-Форда - это алгоритмы
поиска кратчайшего пути в графе
построения дерева обхода графа
метаэвристической оптимизации
выделения сообществ в графе
Плотность полного графа равна
1
0
0.5
не определена
