Билеты теории
Контейнеры
1. Как устроен массив непостоянной длины (массив постоянной длины можно использовать)
2. Как устроена Хеш-таблица? Что делать если произошла коллизия.
Одномерное ДП
1. Основная идея динамического программирования? Как построить правильное ДП (5 пунктов)?
2 Как решать задачу поиска НВП (по 5 пунктам).
Двумерное ДП
1. Отличие одномерного ДП от двумерного? Как решать задачу о черепашке?
2. Как решать задачу НОП (по 5 пунктам).
Функция и Рекурсия
1. Что такое рекурсия? Что такое рекурсивный перебор?
2. Что такое функция? Что такое именованный параметр? В чём разница между глобальной и локальной областью?
Сортировки-1
1. Что такое сортировка массива? Когда сортировка устойчива? Расскажите любые 2 алгоритма квадратичной сортировки.
2. Как устроен radix-sort (Цифровая сортировка).
Сортировки-2
1. Расскажите, как устроен merge-sort (Сортировка слиянием).
2. Расскажите, как устроен quick-sort (Быстрая сортировка Хоара).
Двоичный поиск
1. Расскажите, как устроен двоичный поиск, какие условия необходимы для его корректной работы.
2. Что такое вещественный двоичный поиск? Что такое двоичный поиск по ответу?
Арифметика-1
1. Сформулируйте и докажите алгоритм Евклида.
2. Сформулируйте и докажите критерий существование обратного по произвольному модулю.
Арифметика-2
1. Сформулируйте и докажите МТФ (малую теорему Ферма).
2. Общий принцип работы битовых операций, а также как производятся операции: "И", "ИЛИ", "НЕ", "XOR", "Сдвиг влево", "Сдвиг вправо".
Графы - 1
1. Что такое неориентированный граф? Что такое степень вершины? Что такое компонента связанности графа? Что такое цикл?
2. Когда граф называется деревом? Сформулируйте и докажите формулу количества рёбер в дереве?
Стек, Дек, Очередь
1. Что такое стек? Как реализовать стек с поддержкой максимума?
2. Что такое очередь? Как реализовать очередь с помощью двух стеков?
DFS, BFS
1. Что такое DFS?
2. Что такое BFS?
Правила зачёта
Практика
9:00-13:30 - решение практики. 4 часа на практику + 30 минут в запасе.
Формирование оценки за практику: 3 набора задач (если из группы решаешь больше максимума, то баллы за них не учитываются).
1 балл (3 задачи максимум) : будет указано общее количество задач.
2 балла (2 задачи максимум) :
3 балла (2 задачи максимум) :
Каждый из 12 контестов можно "закрыть", решив условно 2/3 задач. За каждый "закрытый" контест дается 0.25 бонусных балла, потом сумма округляется по математическим правилам. В итоге получаешь от 0 до 3 баллов, которые позволяют тебе не решать соответствующее количество задач из группы на 1 балл.
Максимум за практику - 10 баллов.
Как "закрыть" контест?
- Контейнеры : решить 4 из 5
- Одномерное ДП : 4 из 6
- Двумерное ДП : 4 из 6
- Функции и Рекурсия : 5 из 6
- Сортировки-1 : 6 из 8
- Сортировки-2 : 6 из 8
- Двоичный поиск : 7 из 8
- Арифметика-1 : 6 из 8
- Арифметика-2 : 6 из 7
- Простые графы : 7 из 8
- Стек, очередь : 4 из 7
Теория
14:00 - до победного 4 преподавателя, 16 человек. У каждого человека по 2 теор билета.
Группа из 4 человек заходит в аудиторию. Делим на 2 подгруппы по 2 человека.
Есть два пула билетов с независимыми темами. Сначала тянется билет из первого пула, подготовка, сдача одному из 2ух прикрепленных к соответсвующему пулу преподавателей. Swap групп, повторение действия.
Разбиваем группы по 4 человека.
14:30 - первая группа.
15:10 - вторая группа.
15:50 - третья группа.
16:30 - четвертая группа.
Оценка: От 0 до 4. Преподаватель ставит за билет оценку от 0 до 2. Оценка за теорию - сумма оценок за 2 билета.
Гарантированная тройка - : В итоге формируется одна оценка, так как теоретический зачет не полноценный. Суммарно надо набрать 5 баллов. Практика + теория.
- Статус проверки
OK
1057RJ
539CV
692PR
7