⚙️ Алгоритмы · 20 вопросов · ~45 мин · ⏱ Таймер 45:00 · Сложный ·

Жадные алгоритмы

Жадный выбор выглядит соблазнительно почти в любой задаче, но корректен лишь там, где локальный шаг можно встроить в оптимальное решение. Тест сочетает рабочие алгоритмы для интервалов, кодов и остовов с минимальными контрпримерами для монет, рюкзака и маршрутов.

Отвечено: 0 из 20

⏱ --:--

💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 45 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.

Вопрос 1 из 20

Какие интервалы выберет алгоритм?

intervals = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (7, 8)]
intervals.sort(key=lambda x: x[1])
chosen = []
end = float('-inf')
for start, finish in intervals:
    if start >= end:
        chosen.append((start, finish))
        end = finish
print(chosen)

[(0,6),(7,8)] [(1,4),(5,7),(7,8)] [(1,4),(3,5),(5,7),(7,8)] [(3,5),(5,7),(7,8)]

Вопрос 2 из 20

Какие монеты выберет правило «каждый раз брать крупнейший подходящий номинал»?

4+1+1=6

coins = [1, 3, 4]
amount = 6
used = []
for coin in sorted(coins, reverse=True):
    while amount >= coin:
        amount -= coin
        used.append(coin)
print(used)

[4,3] [3,3] [4,1,1] [1,1,1,1,1,1]

Вопрос 3 из 20

В дробном рюкзаке предметы можно делить. Какой локальный выбор оптимален?

\rho_i=\frac{v_i}{w_i}

Брать самый дешёвый предмет Брать наибольшую ценность на единицу веса Брать предмет с минимальной ценностью Брать предмет с наибольшим весом

Вопрос 4 из 20

Какие два символа будут объединены первыми и какой вес получит новый узел?

from heapq import heapify, heappop, heappush
heap = [(5, 'A'), (9, 'B'), (12, 'C'), (13, 'D')]
heapify(heap)
x = heappop(heap)
y = heappop(heap)
print(x[1], y[1], x[0] + y[0])

A C 17 C D 25 B C 21 A B 14

Вопрос 5 из 20

При построении минимального остова алгоритмом Краскала какой следующий шаг выполняется?

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

Вопрос 6 из 20

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

greedy_first = (1, 3)      # заканчивается раньше всех
optimal_first = (0, 5)     # первое событие в некотором оптимуме
rest = [(5, 7), (7, 9)]

# Нужно обосновать замену optimal_first на greedy_first,
# не уменьшая число мероприятий в расписании.

Удалить из расписания все мероприятия, начинающиеся после G, и оставить выбранный префикс Добавить G рядом с O без замены, даже если два мероприятия занимают одно время Заменить G самым длинным совместимым мероприятием, чтобы оставить меньше промежутков Заменить O на G; остальные мероприятия после O остаются совместимыми и после G

Вопрос 7 из 20

Что нужно доказать помимо свойства жадного выбора?

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

Вопрос 8 из 20

Почему выбор двух минимальных частот безопасен в коде Хаффмана?

from heapq import heapify, heappop, heappush

frequencies = [2, 3, 7, 9, 18]
heapify(frequencies)
while len(frequencies) > 1:
    x = heappop(frequencies)
    y = heappop(frequencies)
    heappush(frequencies, x + y)

# На каждом шаге объединяются две минимальные частоты.

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

Вопрос 9 из 20

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

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

Вопрос 10 из 20

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

from heapq import heappop

used = {0, 2}
frontier = [(3, 2, 1), (5, 0, 3), (8, 2, 4)]

weight, inside, outside = heappop(frontier)
used.add(outside)
# Затем в очередь добавляются рёбра новой вершины.

Самое лёгкое ребро разреза безопасно для некоторого минимального остова Любое ребро внутри S обязательно входит в остов Все рёбра разреза имеют одинаковый вес Самое тяжёлое ребро разреза безопасно

Вопрос 11 из 20

Какой результат даст жадный 0/1-рюкзак по плотности?

items = [(60, 10), (100, 20), (120, 30)]  # (value, weight)
capacity = 50
items.sort(key=lambda p: p[0] / p[1], reverse=True)
value = 0
for v, w in items:
    if w <= capacity:
        capacity -= w
        value += v
print(value)

160 220 280 180

Вопрос 12 из 20

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

Номиналы 1,5,10; сумма 20 Номиналы 1,3,4; сумма 6 Номиналы 1,10; сумма 30 Номиналы 1,2,4; сумма 7

Вопрос 13 из 20

Почему выбор ближайшей по весу ещё не посещённой вершины не гарантирует минимальный гамильтонов цикл?

# Произвольные стоимости переходов в полном взвешенном графе.
distance = [
    [0,   1,   2, 100],
    [1,   0,   1,   2],
    [2,   1,   0,   1],
    [100, 2,   1,   0],
]

current = 0
unvisited = {1, 2, 3}
route = [current]
while unvisited:
    current = min(unvisited, key=lambda v: distance[current][v])
    unvisited.remove(current)
    route.append(current)
route.append(route[0])

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

Вопрос 14 из 20

Почему правило «в лабиринте всегда идти в соседнюю клетку, ближайшую по прямой к выходу» может провалиться?

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

Вопрос 15 из 20

Что произойдёт, если первым выбрать самый короткий интервал \( (3,5) \)?

intervals = [(0, 4), (4, 8), (3, 5)]

Такой выбор совпадёт с правилом самого раннего окончания и даст оптимальные два интервала Он оставит расписание из одного интервала, хотя \( (0,4) \) и \( (4,8) \) совместимы и дают два После него удастся добавить оба остальных интервала и получить расписание из трёх Он исключит только интервал \( (0,4) \), но позволит затем выбрать \( (4,8) \)

Вопрос 16 из 20

Сколько комнат нужно?

meetings = [(0, 10), (5, 7), (6, 8), (9, 12)]
events = []
for s, e in meetings:
    events.append((s, 1))
    events.append((e, -1))
events.sort(key=lambda x: (x[0], x[1]))
current = best = 0
for _, delta in events:
    current += delta
    best = max(best, current)
print(best)

2 3 4 5

Вопрос 17 из 20

Какой суммарный вес получит лес Краскала?

edges = [(1,0,1),(2,1,2),(3,0,2),(4,2,3),(5,1,3)]
parent = list(range(4))
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x
total = 0
for w,u,v in sorted(edges):
    ru, rv = find(u), find(v)
    if ru != rv:
        parent[rv] = ru
        total += w
print(total)

6 9 8 7

Вопрос 18 из 20

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

Сначала задания с самым большим номером Выполнять по убыванию длительности Случайный порядок Выполнять задания по возрастанию длительности

Вопрос 19 из 20

Какую стоимость кода Хаффмана создаёт первый этап?

frequencies = [2, 3, 7, 9]
# объединяем 2 и 3 -> 5; затем 5 и 7 -> 12; затем 9 и 12 -> 21
cost = 5 + 12 + 21
print(cost)

21 38 26 42

Вопрос 20 из 20

Какой инструмент делает выбор следующего минимального элемента эффективным в Хаффмане и Приме?

O((V+E)\log V)

Стек Неупорядоченный массив с удалением последнего Множество без приоритета Мини-куча

Ответьте на все 20 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу