Алгоритмы решения нестандартных задач

Какой алгоритм наиболее эффективен для поиска кратчайшего пути в графе с неотрицательными весами?

• Жадный алгоритм
• Алгоритм Флойда-Уоршелла
• Алгоритм Дейкстры
• Алгоритм Беллмана-Форда

Что означает термин «жадный алгоритм»?

• Использование глобальной оптимальной стратегии на каждом шаге
• Поиск на глубину
• Поиск в ширину
• Выбор локально оптимального решения на каждом этапе

Что такое разветвление и отсечение в алгоритмах поиска?

• Определение ультиматумов для ветвлений
• Обход графа по уровням
• Использование буфера для хранения решений
• Отбрасывание ветвей, не ведущих к оптимальному решению

Что такое хэш-таблица?

• Структура данных для хранения последовательных элементов
• Структура, которая сортирует данные по ключу
• Структура данных для хранения пар ключ-значение с быстрым доступом
• Структура для быстрого поиска и вставки элементов по ключу

Что из перечисленного не является классической задачей жадных алгоритмов?

• Задача о кролике и моркови
• Задача о разложении числа на простые множители
• Задача о минимальном покрытии
• Задача о минимизации стоимости пути

Что такое жадный выбор?

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

Что характеризует задачу «нв» (незавершенной ветки) в алгоритмах поиска?

• Обследование всех вариантов
• Обнаружение уже посещённых вершин
• Область исследований, которая далее не будет расширяться
• Ветвь, которая больше не может быть расширена с учётом заданных условий

Что из перечисленного относится к жадным алгоритмам?

• Обход графа в глубину
• Динамическое программирование
• Обход графа в ширину
• Алгоритм Краскала для построения минимального остовного дерева

Что представляет собой алгоритм Гаусса?

• Решение систем линейных уравнений методом последовательных приближений
• Решение систем линейных уравнений методом выполнения элементарных преобразований
• Алгоритм поиска минимального пути
• Алгоритм сортировки массива

Что означает термин «отсечение» в контексте поиска решений?

• Исключение вариантов, не приводящих к оптимальному результату
• Обход графа в обратном порядке
• Расширение поиска в неизвестном направлении
• Исключение ветвей, не способных привести к лучшему решению

Для чего предназначен алгоритм Беллмана-Форда?

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

Что такое сортировка слиянием?

• Деление массива на части и их сортировка по отдельности
• Объединение двух отсортированных массивов в один отсортированный
• Медианная сортировка
• Рекурсивный алгоритм деления массива и их последующее слияние

Что такое рекурсия в алгоритмах?

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

Что такое динамическое программирование?

• Разбиение задачи на подзадачи с запоминанием решений для повторного использования
• Обход графа в глубину
• Поиск решений с использованием жадной стратегии
• Обработка задач путем разбиения их на более мелкие и использование решений для них

Что означает термин «сбалансированный граф»?

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

Что такое минимальное остовное дерево?

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

Что такое жадный выбор в алгоритмах?

• Выбор локального оптимума на каждом шаге
• Выбирается самый маленький или самый большой элемент
• Происходит полный перебор решений
• Выбор на основе локально оптимального решения на каждом шаге

Что обозначает сложность алгоритма «O(n log n)»?

• Что время выполнения растет пропорционально n
• Что время выполнения растет пропорционально логарифму n
• Что время выполнения растет пропорционально n, умноженному на логарифм n
• Что время выполнения растет пропорционально произведению n и логарифма n

Ключевая идея жадных алгоритмов заключается в выборе на каждом шаге:

• самого сложного элемента
• самого выгодного решения в текущий момент
• самого локально оптимального варианта
• наименьшей подзадачи

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

• Стек
• Очередь
• Двухсвязный список
• Дерево

Что из перечисленного является примером жадного подхода?

• Динамическое программирование
• Разделяй и властвуй
• Поиск минимального остовного дерева
• Обратный ход

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

• Флойда-Уоршелла
• Дейкстры
• Диукстры
• Беллмана-Форда

Какой алгоритм применяется для нахождения максимального потока в сети?

• Алгоритм Дейкстры
• Алгоритм Эдмондса-Карпа
• Алгоритм Куна-МакКарти
• Алгоритм Эдмондса-Карпа

Что такое коммивояжерская задача?

• Задача о минимальном покрытии
• Задача о нахождении максимальной подпоследовательности
• Задача о раскраске графа
• Задача о минимальной сумме путей, посещающих все города

Какое свойство характерно для динамического программирования?

• Жадность выбора
• Использование жадных решений
• Разбиение задачи на подзадачи, решения которых используют результаты более мелких задач
• Обратный ход

Что из перечисленного не относится к техникам решения нестандартных задач?

• Метод ветвей и границ
• Жадный алгоритм
• Динамическое программирование
• Батчевый обмен

Что такое эвристика в контексте решений сложных задач?

• Точный алгоритм
• Метод полного перебора
• Приближенное решение, основанное на интуиции
• Доказательство оптимальности

Какая сложность у метода ветвей и границ в худшем случае?

• Линейная
• Квадратичная
• Экспоненциальная
• Экспоненциальная

Что из ниже перечисленного является примером использования жадных алгоритмов?

• Распределение ресурсов
• Поиск в глубину
• Обратный ход
• Задача о рюкзаке с ограничениями

Что условие необходимости наличия «постоянных» компонент в графе для задачи о минимальном покрытии?

• Граф связен
• Граф неориентирован
• Граф должен быть связан
• Граф должен содержать циклы

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

• Мемо
• Таблицей
• Массивом
• Мемо

Что такое «грязная» жадность?

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

Что такое пример задачи о минимальном остовном дереве?

• Задача о нахождении кратчайшего пути
• Задача о раскраске вершин
• Задача о максимальном потоке
• Задача о соединении всех вершин графа минимальной суммой рёбер

Что из перечисленного является характерной чертой алгоритма поиска в глубину?

• Использование стека
• Рекурсивное погружение в граф
• Использование очереди
• Обход по уровням

При решении задачи о рюкзаке методом динамического программирования, основная идея заключается в:

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

Что из перечисленного представляет собой задачу о раскраске графа?

• Разделение графа на компоненты
• Минимизация количества цветов
• Максимизация связных компонент
• Назначение цветов вершинам так, чтобы смежные вершины имели разные цвета

Анна

Исследования ученых о взаимосвязи ума и красоты говорят о том, что умные люди – красивые!

Задать вопрос

Представленная информация была полезной?

ДА

87.1%

НЕТ

12.9%

Проголосовало: 248

или напишите нам прямо сейчас:

Написать в MAXНаписать в TelegramНаписать в WhatsApp

Отзывы наших клиентов

1 2 ... 12 ►