https://www.wikicshse.ru/index.php?action=history&feed=atom&title=%D0%90%D0%B8%D0%A1%D0%94-2_%D0%AD%D0%BA%D0%B7%D0%B0%D0%BC%D0%B5%D0%BDАиСД-2 Экзамен - История изменений2026-06-06T12:29:44ZИстория изменений этой страницы в викиMediaWiki 1.45.3https://www.wikicshse.ru/index.php?title=%D0%90%D0%B8%D0%A1%D0%94-2_%D0%AD%D0%BA%D0%B7%D0%B0%D0%BC%D0%B5%D0%BD&diff=790&oldid=previmported>Pankovamg: Migrated current public revision from wiki.cs.hse.ru2026-01-19T09:20:12Z<p>Migrated current public revision from wiki.cs.hse.ru</p>
<p><b>Новая страница</b></p><div>== Подробный план проведения экзамена 20 декабря ==<br />
<br />
'''Письменная часть с 12.00 до 13.30'''<br />
<br />
Все студенты заходят в zoom по ссылке и переходят в одну из 7 комнат<br />
<br />
1. БКНАД251 - 1 по алфавиту от A до И<br />
<br />
2. БКНАД251 - 2 по алфавиту от К до Т<br />
<br />
3. БКНАД252 - 1 по алфавиту от A до Л<br />
<br />
4. БКНАД252 - 2 по алфавиту от М до О<br />
<br />
5. БКНАД252 - 3 по алфавиту от П до Ч<br />
<br />
6. БКНАД253 - 1 по алфавиту от Г до Ф<br />
<br />
7. БКНАД253 - 2 по алфавиту от X до Ю<br />
<br />
Вам нужно <br />
<br />
1. включить камеру, которая показывает вас<br />
<br />
2. транслировать весь свой рабочий стол.<br />
<br />
Это нужно сделать до 12.00, в 12.00 стартует контест экзамена.<br />
<br />
<br />
Ссылки на вход в контест экзамена<br />
<br />
<br />
В экзаменационном наборе контеста у вас будет 25 заданий.<br />
Каждый верный ответ даёт 0,3 балла.<br />
Во время экзамена вам не будет доступна таблица результатов и вердикт проверяющей системы, т.е. если ваш ответ не совпадает по формату - будет сообщение, иначе он будет просто принят для рассмотрения.<br />
<br />
<br />
❗️Внимание! На проверку принимается ПОСЛЕДНИЙ посланный ответ для каждого задания.<br />
<br />
Во время экзамена разрешается использовать приложения «блокнот» (и аналоги) и «калькулятор», писать программы на Python, а также пользоваться чистой бумагой и ручкой. <br />
Нельзя использовать заранее написанный код и конспекты.<br />
<br />
Для выхода в устную часть экзамена вам необходимо верно решить '''15 заданий''' (набрать 4,5 балла)<br />
<br />
'''Устная часть с 14.00'''<br />
<br />
На каждый вопрос ожидается распространённый ответ.<br />
Преподаватель может задавать дополнительные вопросы по материалу вопроса.<br />
Оценка за каждый вопрос от 0 до 1,5 баллов.<br />
<br />
'''Критерии оценки'''<br />
<br />
0 нет ответа, или совсем неверный ответ<br />
<br />
0.5 студент владеет материалом, но допускает ошибки, не может привести примеры/пояснить асимптотику<br />
<br />
1 почти полный ответ, с незначительными ошибками<br />
<br />
1.5 полный ответ, с примерами, асимптотикой<br />
<br />
<br />
'''Итоговая оценка за экзамен:'''<br />
<br />
Итоговая оценка = min(10, контест + устный ответ(если студен допущен к устной части))<br />
<br />
<br />
-----------------------------------------<br />
<br />
'''с 12.00 до 13.30''' - письменная часть - контест из 5 теоретических вопросов по 5 заданий к каждом на Яндекс контесте.<br />
Каждое задание оценивается независимо в 0,3 балла.<br />
<br />
В набор задач войдут задачи из банка задач к экзамену.<br />
Экзамен проходит онлайн с подключением к zoom трансляции.<br />
<br />
'''с 14.00''' - устная часть экзамена. <br />
<br />
В устную часть приглашаются все, кто набрал хотя бы 4,5 балла (15 правильных ответов из 25)<br />
<br />
Вы записываетесь на один из доступных временных слотов и подключаетесь по ссылке к zoom. <br />
<br />
На устной части экзамена вам достаётся билет из 3-х вопросов. Вопросы формируются из банка вопросов к экзамену.<br />
По каждому вопросу билета экзаменующий может задавать дополнительные вопросы.<br />
<br />
'''Банк задач и вопросов к экзамену:'''<br />
<br />
Банк заданий и вопросов к экзамену состоит из открытой и закрытой части в отношении 80/20.<br />
Открытая часть размещается в свободном доступе не позднее 13 декабря.<br />
<br />
'''Оценка за экзамен:'''<br />
<br />
Каждое задание вопроса оценивается независимо в 0,3 балла (max = 7,5сза все задания)<br />
<br />
Ответ на каждый вопрос устной части оценивается в баллах от 0 до 1,5 с шагом 0,5 (max = 4,5)<br />
<br />
Итоговая оценка = min(10, контест + устный ответ)<br />
<br />
'''<big>Вопросы к устной части экзамена по АиСД, 2 модуль</big>'''<br />
<br />
1. Асимптотическая оценка сложности алгоритмов.<br />
Опишите общую идею асимптотической оценки сложности алгоритмов по времени и по памяти. Дайте определение асимптотической нотации Big-O. Сформулируйте основные правила вычисления асимптотической сложности алгоритма. Приведите примеры наиболее распространённых асимптотик и укажите алгоритмы, работающие с соответствующей сложностью.<br />
<br />
2. Бинарное возведение в степень.<br />
Опишите идею бинарного возведения в степень. Сформулируйте алгоритм и объясните принцип его работы. Приведите итеративную или рекурсивную реализацию алгоритма. Оцените временную сложность алгоритма.<br />
<br />
3. Факторизация целых чисел.<br />
Опишите постановку задачи разбиения числа на простые множители и основные методы её решения. Оцените асимптотическую сложность алгоритма факторизации. Объясните, как факторизация используется для нахождения количества делителей числа.<br />
<br />
4. Решето Эратосфена.<br />
Опишите алгоритм нахождения всех простых чисел от 2 до N с помощью решета Эратосфена. Объясните принцип его работы и оцените временную сложность. Поясните, как результаты работы алгоритма могут быть использованы для разложения числа на простые множители.<br />
<br />
5. Алгоритм Евклида.<br />
Опишите алгоритм Евклида для нахождения наибольшего общего делителя двух целых чисел. Объясните идею алгоритма, оцените его асимптотическую сложность и укажите возможные оптимизации.<br />
<br />
6. Метод двух указателей.<br />
Опишите идею метода двух указателей и объясните его применение для решения задачи поиска отрезков массива, в которых каждый элемент встречается ровно k раз. Раскройте принцип перемещения указателей, способ поддержания состояния текущего отрезка и используемые структуры данных. Оцените временную сложность алгоритма.<br />
<br />
7. Максимальная сумма подотрезка.<br />
Опишите алгоритм решения задачи о нахождении подотрезка числового массива с максимальной суммой. Объясните основную идею алгоритма, используемые методы линейной обработки данных и проанализируйте временную и пространственную сложность.<br />
<br />
8. Стек: ближайший меньший элемент слева.<br />
Опишите применение структуры данных «стек» на примере задачи о нахождении ближайшего меньшего элемента слева для каждого элемента массива. Объясните принцип работы алгоритма, правила добавления и удаления элементов из стека, а также обоснуйте корректность и сложность решения.<br />
<br />
9. Стек: проверка скобочной последовательности.<br />
Опишите применение структуры данных «стек» для проверки правильности скобочной последовательности, содержащей три вида скобок. Объясните, каким образом стек используется для контроля вложенности, какие условия определяют корректность последовательности, и оцените сложность алгоритма.<br />
<br />
10. Дек: минимум в скользящем окне.<br />
Опишите применение структуры данных «дек» на примере задачи нахождения минимума в скользящем окне фиксированной длины k. Объясните идею алгоритма, правила поддержания дека и оцените временную и пространственную сложность решения.<br />
<br />
11. Жадные алгоритмы.<br />
Опишите жадный принцип решения задач. Объясните основную идею жадных алгоритмов и условия, при которых жадный выбор приводит к оптимальному решению. Перечислите основные способы доказательства корректности жадных алгоритмов. Проиллюстрируйте жадный принцип на примере задачи составления оптимального расписания докладов.<br />
<br />
12. Покрытие отрезка на прямой.<br />
Опишите задачу покрытия заданного отрезка на числовой прямой минимальным количеством отрезков из заданного набора. Сформулируйте жадный алгоритм решения, объясните принцип выбора на каждом шаге, способ обработки событий и обоснуйте корректность алгоритма. Оцените сложность решения.<br />
<br />
13. События на прямой: максимум покрытий.<br />
Дайте определение понятию события в задачах на числовой прямой. Опишите типы событий, используемые при работе с отрезками и интервалами. Объясните процесс сортировки событий, роль компаратора и правила обработки событий с одинаковыми координатами. Опишите алгоритм нахождения точки, покрытой наибольшим количеством отрезков.<br />
<br />
14. Сортировка событий: ближайший непересекающийся отрезок.<br />
Опишите метод сортировки событий для работы с отрезками на числовой прямой. Объясните типы событий и правила их упорядочивания. На примере задачи поиска ближайшего слева отрезка, не пересекающегося с данным, поясните работу алгоритма и оцените его сложность.<br />
<br />
15. Бинарный поиск по ответу: верёвочки.<br />
Опишите идею бинарного поиска по ответу и её применение для нахождения последнего подходящего значения на примере задачи о получении из n верёвок не менее k верёвок максимально возможной длины. Объясните выбор границ поиска, проверку допустимости и оцените сложность алгоритма.<br />
<br />
16. Вещественный бинарный поиск.<br />
Опишите применение вещественного бинарного поиска для нахождения корней уравнения. Объясните условия применимости метода, выбор начального отрезка, критерии остановки и оцените временную сложность алгоритма.<br />
<br />
17. Обменные квадратичные сортировки.<br />
Опишите принцип работы обменных квадратичных сортировок на примере пузырьковой сортировки. На примере данного алгоритма объясните понятие устойчивости сортировки и критерии, по которым она определяется. Проанализируйте временную сложность алгоритма в лучшем, среднем и худшем случаях и укажите возможные оптимизации пузырьковой сортировки..<br />
<br />
18. Наибольшая общая подпоследовательность (НОП).<br />
Опишите решение задачи нахождения длины наибольшей общей подпоследовательности двух последовательностей с помощью динамического программирования. Укажите состояние, рекуррентное соотношение, базу, порядок вычислений и оценку сложности.<br />
<br />
19. Наибольшая возрастающая подпоследовательность (НВП).<br />
Опишите решение задачи нахождения длины наибольшей строго возрастающей подпоследовательности в массиве методом динамического программирования. Укажите состояние, рекуррентное соотношение, базу, порядок вычислений и оцените сложность алгоритма.<br />
<br />
20. Задача о рюкзаке (точное наполнение).<br />
Опишите решение задачи о рюкзаке с точным заполнением вместимости М методом динамического программирования. Определите состояние, базу, рекуррентный переход, порядок вычислений и оцените временную сложность алгоритма. Опишите решение с использованием линейной памяти. <br />
<br />
21. Задача о рюкзаке (максимальная стоимость).<br />
Опишите решение задачи о самом дорогом наполнении рюкзака вместимостью M предметами, у которых есть вес и стоимость методом динамического программирования. Определите состояние, базу, рекуррентный переход, порядок вычислений и оцените временную сложность алгоритма. Опишите процесс восстановления ответа <br />
<br />
22. Генерация перестановок.<br />
Опишите рекурсивный алгоритм генерации всех перестановок множества из N различных элементов. Объясните идею рекурсивного перехода, способ избежания повторений, базовый случай и оцените временную сложность.<br />
<br />
23. Разложения числа на слагаемые.<br />
Опишите рекурсивный алгоритм генерации всех разложений натурального числа N на натуральные слагаемые. Объясните, как обеспечивается уникальность разложений, структуру рекурсивных вызовов и базовый случай.<br />
<br />
24. Генерация сочетаний.<br />
Опишите рекурсивный алгоритм генерации всех сочетаний из N элементов по K. Укажите идею рекурсивного перехода, способ исключения повторений, базовый случай и оцените временную сложность.<br />
<br />
25. Структура данных «куча».<br />
Опишите идею построения структуры данных «куча». Дайте определение бинарной кучи и её основные свойства. Объясните алгоритм построения кучи из неупорядоченного массива. Опишите основные операции на куче и обоснуйте асимптотику их выполнения.<br />
<br />
26. Быстрая сортировка (Quick Sort).<br />
Опишите алгоритм быстрой сортировки и принцип «разделяй и властвуй». Объясните выбор опорного элемента, процесс разбиения массива и рекурсивную структуру алгоритма. Проанализируйте временную и пространственную сложность в лучшем, среднем и худшем случаях.<br />
<br />
27. Сортировка слиянием (Merge Sort).<br />
Опишите алгоритм рекурсивной сортировки слиянием. Объясните этапы разбиения и слияния подмассивов. Проанализируйте временную и пространственную сложность и сравните сортировку слиянием с быстрой сортировкой по устойчивости и потреблению памяти.<br />
<br />
<br />
<br />
'''<big>Вопросы к письменной части экзамена по АиСД, 2 модуль</big>''' <br />
<br />
<br />
'''Пример задания по теме "Теория чисел: Алгоритм Евклида'''<br />
<br />
# Какое минимальное количество шагов (делений с остатком) требуется алгоритму Евклида для вычисления НОД(34, 21)?<br />
# Напишите пропущенную строку в итеративной реализации алгоритма Евклида на Python:<br />
def gcd(a, b):<br />
while b != 0:<br />
pass<br />
return a<br />
# Напишите формулу нахождения НОК натуральных чисел a, b используя функцию нахождения НОД двух чисел - gcd(a, b).<br />
# Напишите оценку по времени в O нотации для алгоритма нахождения НОД для чисел a и b<br />
# Для решения задачи "Полоска бумаги имеет размеры A × B. Каждый раз от нее отрезается квадрат максимального размера до тех пор, пока не получится квадрат. Сколько квадратов получится?" Использовали реализацию алгоритма Евклида с вычитанием. Напишите условие, которое позволит сократить решение задачи для тестов, где одно из входных чисел очень велико, а другое равно 1.<br />
<br />
n, m = map(int, input().split())<br />
k = 1<br />
<br />
else:<br />
while n != m:<br />
k += 1<br />
if n > m:<br />
n-= m<br />
else:<br />
m-= n<br />
print(k)<br />
<br />
'''Банк заданий'''<br />
по другим темам размещён в [https://docs.google.com/document/d/1NwBe6dm1mZytZLTT5HkEpMm8Xco5ifHtvOi2BMG6-jo/edit?tab=t.0#bookmark=id.xeak5b2t4val отдельном google документе]</div>imported>Pankovamg