Тест на тему Алгоритмы

Ниже готов тест по информатике на тему "Алгоритмы" для 10 класса. Формат – открытые вопросы. В конце приведены образцовые ответы с критериями оценивания.

Тест

1. Что такое алгоритм? Перечислите не менее четырех обязательных свойств алгоритма и кратко поясните каждое. Приведите простой пример алгоритма из повседневной жизни.
2. Опишите пошагово алгоритм нахождения наибольшего элемента в массиве A размерности n. Запишите в виде псевдокода и укажите сложность по времени и памяти.
3. Опишите алгоритм бинарного поиска в упорядоченном по неубыванию массиве. Объясните логику работы и приведите пример последовательности шагов для массива [1, 3, 4, 7, 9, 12] при поиске элемента 7.
4. Сравните пузырьковую сортировку и сортировку выбором:
   • принципы работы;
   • временную сложность в худшем, среднем и лучшем случаях;
   • устойчивость;
   • пример, когда каждую из них уместно использовать.
5. Напишите псевдокод Евклидова алгоритма для нахождения наибольшего общего делителя (НОД) двух чисел a и b. Объясните, почему этот алгоритм работает.
6. Объясните концепцию рекурсии и приведите пример: вычисление факториала n! с помощью рекурсивной функции. Укажите базовый случай и переход.
7. Что такое динамическое программирование? Приведите пример задачи и запишите типичный подход DP: определение состояния, переход и пример расчета для небольшого значения. Например, задача размена монет: минимальное число монет, чтобы составить заданную сумму, используя монеты заданного набора.
8. Опишите алгоритм обхода графа в глубину (DFS). Приведите псевдокод и объясните ситуации, когда DFS предпочтителен (например, обход компонент связности, поиск цикла, топологическая сортировка в DAG).
9. Что такое жадный алгоритм? Приведите пример задачи и объясните, почему жадное решение может быть неверным в общем случае. Приведите конкретный пример задачи по размену монет с неидеальной системой монет (например, монеты 1, 3, 4 для суммы 6) и сравните с оптимальным решением.
10. Напишите простой псевдокод решения задачи нахождения всех примитивных чисел до N с помощью решета Эратосфена. Объясните принцип работы и оценку сложности по времени и памяти.

Образец ответов (ключевые моменты и критерии оценивания)

1. Определение алгоритма и свойства

• Определение: конечная последовательность инструкций, преобразующая ввод в ожидаемый вывод.
• Свойства:
  • конечность: выполнение заканчивается за сколь угодно конечное число шагов;
  • детерминированность: в каждом шаге однозначно выбирается следующий шаг;
  • вход/выход: наличие входных данных и ожидаемого вывода;
  • определенность инструкций: шаги понятны и выполнимы однозначно;
  • корректность: решение задачи достигается для всех допустимых входов.
• Пример: рецепт приготовления блюда (словарь инструкции до готовности).

2. Поиск максимального элемента

• Псевдокод: max_element(A[1..n]): if n == 0: вернуть ошибка max <- A[1] for i = 2..n: если A[i] > max: max <- A[i] вернуть max
• Сложность: время O(n), память O(1).
• Пример применения: найти наибольший балл ученика в списке.

3. Бинарный поиск

• Псевдокод: binary_search(A[1..n], x): Л = 1, П = n while Л ≤ П: М = floor((Л + П) / 2) если A[М] == x: вернуть М если A[М] < x: Л = М + 1 иначе: П = М - 1 вернуть -1 (не найдено)
• Пример на массиве [1,3,4,7,9,12], ищем 7: Л=1, П=6 → М=3, A[3]=4 < 7 → Л=4 М=(4+6)/2=5, A[5]=9 > 7 → П=4 М=4, A[4]=7 → найдено на позиции 4.
• Сложность: O(log n) по времени.

4. Сравнение пузырьковой и сортировки выбором

• Пузырьковая: Swap соседних элементов; стабильна; худшее/среднее O(n^2); лучше при уже частично отсортированном массиве при оптимизированном варианте близко к O(n).
• Сортировка выбором: за итерацию выбирается минимальный/максимальный элемент и помещается на нужную позицию; время O(n^2) в любом случае; неустойчивость (можно сделать устойчивую версию, но обычно не используют).
• В каких случаях: малые массивы можно использовать обе; если нужна стабильность — пузырьковая (со специальной оптимизацией), если требуется простота реализации и нет требования к устойчивости — выбор.

5. Евклидов алгоритм

• Псевдокод: gcd(a,b): while b ≠ 0: r = a mod b a = b b = r вернуть a
• Почему работает: деление с остатком сохраняет НОД; повторяя замену аргументов, получаем НОД за счёт свойств делимости.
• Сложность: O(log min(a,b)) по количеству итераций.

6. Рекурсия и факториал

• Пример: factorial(n): если n <= 1: вернуть 1 иначе: вернуть n * factorial(n-1)
• Базовый случай: n <= 1.
• Переход: n → n-1.
• Проблема: глубина стека пропорциональна n; для больших n возможен переполнение стека.

7. Динамическое программирование

• Определение: метод решения задач разбиения на подзадачи с запоминанием результатов, чтобы не перепроизводить вычисления.
• Пример: размен монет Пусть есть монеты в наборе C = {c1, c2, ..., ck} и сумма M. dp[x] – минимальное число монет для суммы x (x от 0 до M). dp[0] = 0 для x = 1..M: dp[x] = min{ dp[x - ci] + 1 | ci ≤ x }
• Пример: для M=6 и C={1,3,4} dp[6] = 2 (3+3) вместо 4+1+1 (3 монеты).
• Сложность: O(M * k) по времени, O(M) по памяти.

8. DFS

• Псевдокод: DFS(G, v): пометить v посещённой для каждого соседа u в Adj[v]: если не посещён(u): DFS(G, u)
• Применение: обход всех вершин графа, поиск компонент связности, цикл в неориентированном графе, топологическая сортировка в DAG (после модификаций), планирование маршрутов.
• Примечание: может потребоваться стек в памяти и отслеживание посещённых.

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

• Идея: каждый шаг выбирает локально оптимальное решение, которое кажется лучшим на текущий момент.
• Ограничения: не гарантируют глобальную оптимальность во всех задачах.
• Пример: размен монет с монетами {1, 3, 4} и сумма 6: Жадно: 4 + 1 + 1 (3 монеты) → не оптимально. Оптимальное решение: 3 + 3 (2 монеты).
• Важная мысль для экзамена: иногда жадные работают, когда системы монет «каноничны», но не во всех случаях.

10. Решето Эратосфена

• Псевдокод: sieve(N): создать массив is_prime[2..N] и заполнить истинными для p от 2 до floor(sqrt(N)): если is_prime[p]: для m от p*p до N шагом p: is_prime[m] = ложь вернуть все i, у которых is_prime[i] истинно
• Принцип: вычеркиваем кратные простых чисел.
• Сложность: время O(N log log N), память O(N).

Если нужно, могу адаптировать тест под конкретный формат (например, добавить поле для рассуждений, ограничение времени на выполнение, шкалу баллов, или привести дополнительные примеры для каждого вопроса).