АиСД-2 Экзамен

с 12.00 до 13.30 - письменная часть - контест из 5 теоретических вопросов по 5 заданий к каждом на Яндекс контесте. Каждое задание оценивается независимо в 0,3 балла.

В набор задач войдут задачи из банка задач к экзамену. Экзамен проходит онлайн с подключением к zoom трансляции.

с 14.00 - устная часть экзамена.

В устную часть приглашаются все, кто набрал хотя бы 4,5 балла (15 правильных ответов из 25)

Вы записываетесь на один из доступных временных слотов и подключаетесь по ссылке к zoom На устной части экзамена вам достаётся билет из 3-х вопросов. Вопросы формируются из банка вопросов к экзамену. По каждому вопросу билета экзаменующий может задавать дополнительные вопросы.

Банк задач и вопросов к экзамену:

Банк заданий и вопросов к экзамену состоит из открытой и закрытой части в отношении 80/20. Открытая часть размещается в свободном доступе не позднее 13 декабря.

Оценка за экзамен:

Каждое задание вопроса оценивается независимо в 0,3 балла (max = 7,5сза все задания)

Ответ на каждый вопрос устной части оценивается в баллах от 0 до 1,5 с шагом 0,5 (max = 4,5)

Итоговая оценка = min(10, контест + устный ответ)

Вопросы к устной части экзамена по АиСД, 2 модуль

1. Асимптотическая оценка сложности алгоритмов. Опишите общую идею асимптотической оценки сложности алгоритмов по времени и по памяти. Дайте определение асимптотической нотации Big-O. Сформулируйте основные правила вычисления асимптотической сложности алгоритма. Приведите примеры наиболее распространённых асимптотик и укажите алгоритмы, работающие с соответствующей сложностью.

2. Бинарное возведение в степень. Опишите идею бинарного возведения в степень. Сформулируйте алгоритм и объясните принцип его работы. Приведите итеративную или рекурсивную реализацию алгоритма. Оцените временную сложность алгоритма.

3. Факторизация целых чисел. Опишите постановку задачи разбиения числа на простые множители и основные методы её решения. Оцените асимптотическую сложность алгоритма факторизации. Объясните, как факторизация используется для нахождения количества делителей числа.

4. Решето Эратосфена. Опишите алгоритм нахождения всех простых чисел от 2 до N с помощью решета Эратосфена. Объясните принцип его работы и оцените временную сложность. Поясните, как результаты работы алгоритма могут быть использованы для разложения числа на простые множители.

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

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

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

8. Стек: ближайший меньший элемент слева. Опишите применение структуры данных «стек» на примере задачи о нахождении ближайшего меньшего элемента слева для каждого элемента массива. Объясните принцип работы алгоритма, правила добавления и удаления элементов из стека, а также обоснуйте корректность и сложность решения.

9. Стек: проверка скобочной последовательности. Опишите применение структуры данных «стек» для проверки правильности скобочной последовательности, содержащей три вида скобок. Объясните, каким образом стек используется для контроля вложенности, какие условия определяют корректность последовательности, и оцените сложность алгоритма.

10. Дек: минимум в скользящем окне. Опишите применение структуры данных «дек» на примере задачи нахождения минимума в скользящем окне фиксированной длины k. Объясните идею алгоритма, правила поддержания дека и оцените временную и пространственную сложность решения.

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

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

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

14. Сортировка событий: ближайший непересекающийся отрезок. Опишите метод сортировки событий для работы с отрезками на числовой прямой. Объясните типы событий и правила их упорядочивания. На примере задачи поиска ближайшего слева отрезка, не пересекающегося с данным, поясните работу алгоритма и оцените его сложность.

15. Бинарный поиск по ответу: верёвочки. Опишите идею бинарного поиска по ответу и её применение для нахождения последнего подходящего значения на примере задачи о получении из n верёвок не менее k верёвок максимально возможной длины. Объясните выбор границ поиска, проверку допустимости и оцените сложность алгоритма.

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

17. Обменные квадратичные сортировки. Опишите принцип работы обменных квадратичных сортировок на примере пузырьковой сортировки. На примере данного алгоритма объясните понятие устойчивости сортировки и критерии, по которым она определяется. Проанализируйте временную сложность алгоритма в лучшем, среднем и худшем случаях и укажите возможные оптимизации пузырьковой сортировки..

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

19. Наибольшая возрастающая подпоследовательность (НВП). Опишите решение задачи нахождения длины наибольшей строго возрастающей подпоследовательности в массиве методом динамического программирования. Укажите состояние, рекуррентное соотношение, базу, порядок вычислений и оцените сложность алгоритма.

20. Задача о рюкзаке (точное наполнение). Опишите решение задачи о рюкзаке с точным заполнением вместимости М методом динамического программирования. Определите состояние, базу, рекуррентный переход, порядок вычислений и оцените временную сложность алгоритма. Опишите решение с использованием линейной памяти.

21. Задача о рюкзаке (максимальная стоимость). Опишите решение задачи о самом дорогом наполнении рюкзака вместимостью M предметами, у которых есть вес и стоимость методом динамического программирования. Определите состояние, базу, рекуррентный переход, порядок вычислений и оцените временную сложность алгоритма. Опишите процесс восстановления ответа

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

23. Разложения числа на слагаемые. Опишите рекурсивный алгоритм генерации всех разложений натурального числа N на натуральные слагаемые. Объясните, как обеспечивается уникальность разложений, структуру рекурсивных вызовов и базовый случай.

24. Генерация сочетаний. Опишите рекурсивный алгоритм генерации всех сочетаний из N элементов по K. Укажите идею рекурсивного перехода, способ исключения повторений, базовый случай и оцените временную сложность.

25. Структура данных «куча». Опишите идею построения структуры данных «куча». Дайте определение бинарной кучи и её основные свойства. Объясните алгоритм построения кучи из неупорядоченного массива. Опишите основные операции на куче и обоснуйте асимптотику их выполнения.

26. Быстрая сортировка (Quick Sort). Опишите алгоритм быстрой сортировки и принцип «разделяй и властвуй». Объясните выбор опорного элемента, процесс разбиения массива и рекурсивную структуру алгоритма. Проанализируйте временную и пространственную сложность в лучшем, среднем и худшем случаях.

27. Сортировка слиянием (Merge Sort). Опишите алгоритм рекурсивной сортировки слиянием. Объясните этапы разбиения и слияния подмассивов. Проанализируйте временную и пространственную сложность и сравните сортировку слиянием с быстрой сортировкой по устойчивости и потреблению памяти.

Вопросы к письменной части экзамена по АиСД, 2 модуль

Тема B "Теория чисел"

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

1. Какое минимальное количество шагов (делений с остатком) требуется алгоритму Евклида для вычисления НОД(34, 21)?
2. Напишите пропущенную строку в итеративной реализации алгоритма Евклида на Python:

   def gcd(a, b):
       while b != 0:
           pass
       return a

1. Напишите формулу нахождения НОК натуральных чисел a, b используя функцию нахождения НОД двух чисел - gcd(a, b).
2. Напишите оценку по времени в O нотации для алгоритма нахождения НОД для чисел a и b
3. Для решения задачи "Полоска бумаги имеет размеры A × B. Каждый раз от нее отрезается квадрат максимального размера до тех пор, пока не получится квадрат. Сколько квадратов получится?" Использовали реализацию алгоритма Евклида с вычитанием. Напишите условие, которое позволит сократить решение задачи для тестов, где одно из входных чисел очень велико, а другое равно 1.

   n, m = map(int, input().split())
   k = 1

   else:
       while n != m:
           k += 1
           if n > m:
              n-= m
           else:
               m-= n
       print(k)