Полезные ссылки

Два указателя

1. Что такое метод двух указателей? Асимптотика. Когда его можно использовать? Какая должна быть функция.

2. Определить инвариант и переходы в двух указателях. Два способа написать два указателя.

3. Найти сумму, которая равна X в массиве натуральных целых чисел. Асимптотика.

4. Найти сумму, которая равна X в массиве целых чисел. Асимптотика.

DFS+

1. DFS, дерево обхода, виды рёбер и их определения, свойства дерева обхода

2. Топологическая сортировка, алгоритмы с доказательством

3. Диаметр дерева с доказательством. Понятие времени входа и выхода, предки в дереве

Кратчайшие пути

1. Дейкстра, рассказать, что делает. Дейкстра за квадрат. На каких весах работает? Почему?

2. Дейкстра, рассказать, что делает. Дейкстра за логарифм. На каких весах работает? Почему?

3. Форд-Беллман. Асимптотика, код, что делает. На каких весах работает? Почему?

4. Флойд. Асимптотика, код, что делает. На каких весах работает? Почему?

Регулярные выражения

1. Синтаксис регулярных выражений (основные конструкции).

2. Написание регулярного выражения для заданных объектов: чисел, номеров телефонов, даты или времени и т.д

Рекурсивный перебор

1. Перебор чисел в k-ичной системе счисления. Перебор перестановок. Асимптотика по времени и памяти

2. Перебор с отсечением на каком-нибудь примере. Виды отсечений

3. Применение рекурсивного перебора в играх, задача судоку

Геометрия

1. Декартова система координат, геометрические примитивы и как их задать, уравнения прямой по двум точкам и коэффициентам. sin, cos, единичная окружность. Посчитать значение триг. функ. от разных углов.

2. Произведения векторов, определить, что угол прямой, тупой, острый, развёрнутый. Определить, что вектора коллинеарны, сонаправлены. Функции с векторами.

3. Площадь треугольника. Определить, что точка лежит на луче, прямой, внутри угла. Площадь многоугольника

Обработка изображений

1. Представление изображений в компьютере, яркость, контрастность, баланс белого.

2. Преобразования “серый мир”, “автоконтраст”.

Общие правила:

Оценка за зачёт вычисляется по формуле: \(Oценка = 0.5\cdot O_{дорешка} + 0.25\cdot O_{теория} + 0.25\cdot O_{практика}\), где \(O_{дорешка}\) - оценка за дорешку, которая вычисляется по формуле: \(O_{дорешка}=10\cdot \frac{\sum_{i=1}^{n} \sqrt{\frac{solved_i}{total_i}}}{n}\), где \(n, solved_i, total_i\) - это число контестов, число задач, решенных участником в \(i\)-ом контесте, и общее число задач в этом контесте соответственно.

\(O_{теория}\) - оценка за теорию получается за теоретические билеты, которые нужно сдавать преподавателям.

\(O_{практика}\) - оценка за практический зачёт.

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