Практика 1. Организация курса и асимптотика

Первая практика по алгоритмам: как устроен курс и за что даются баллы, а во второй половине — первая тема семестра, асимптотика: почему время работы измеряют не в миллисекундах, что такое $O$, $\Omega$ и $\Theta$ и как оценивать код по кускам.

1. Формат практик

• Практику ведёт преподаватель, помогают менторы. К менторам можно обращаться так же, как к преподавателю.
• Практики не дублируют лекции: материал дают на лекции, на практику приходите с вопросами. Что не поняли — разбираем, если всё понятно — расширяем тему.
• Вопросы задавать не стесняясь, перебивать можно. Если совсем ничего не понятно — подходить на паре или писать в личку.
• Будут дополнительные необязательные лекции, тема анонсируется в канале заранее. Спрашивать их не будут.
• Группа сильная, преподаватель ожидает результат выше, чем от прежних потоков.

2. Балльно-рейтинговая система

• Все 100 можно набрать в семестре. Экзамен только для тех, кто не набрал 60.
• Средняя оценка в прошлогодних группах преподавателя — «четыре с лишним».

3. Лабораторные работы

• Формат олимпиадный: условие, входные данные, ограничения по времени и памяти. Решение отправляется на платформу Sort.me и автоматически гоняется по тестам; прошли все тесты — задача зачтена.
• Ориентировочно 6–7 лаб за семестр, в каждой 5–7 задач. Защищаются не все задачи из лабы.
• Лаба открыта две недели. Дедлайн защиты — следующая пара после закрытия; если не успели всех принять, разрешат прийти на следующую практику.
• Баллы не начисляются, пока лаба не защищена. Прошли тесты — получили право идти на защиту.
• Защита: открываете решение (желательно с ответами на тесты, включая неочевидные), рассказываете задачу и решение. Могут попросить минорную модификацию: сортировали по возрастанию — сделайте по убыванию. Кто писал сам, сделает без проблем.
• Пересдачи по лабе нет. Если на защите «плаваете», отправят готовиться. Пропустили защиту по болезни — есть отдельная активность «дозащита».
• Отправлять можно несколько решений одной задачи, но на защите открываете одно.
• Кто идёт впереди программы, может сдавать быстрее: как только лаба открылась, напишите преподавателю и договоритесь о защите, возможно дистанционно.
• Google и нейросети не запрещены, но понимать свой код обязаны. Два побуквенно идентичных решения — вопросы к обоим авторам.

4. Языки и что можно использовать

• Сдавать можно на любом языке платформы: C++, C, Java, Python, C#, Rust и другие. Гарантируется, что задачи заходят на C и C++. На Python решение может не пройти по времени.
• Главное правило: не использовать встроенные структуры данных и алгоритмы, пока тему не прошли. Лаба на сортировки со std::sort не считается. После защиты лабы по теме соответствующий класс использовать можно.
• vector и string использовать можно, но vector надо уметь объяснить. Преподаватель предпочитает vector сырым массивам: студенты путаются в указателях.
• Не уверены, можно ли что-то использовать — спросите в группе, чтобы все видели ответ, или напишите преподавателю или менторам. Если ночь перед дедлайном и спросить некого: залейте рабочий код, а при наличии времени — версию без спорного инструмента.

5. Тесты на практиках

• После каждой темы — тест на понимание, без кода. Пример: показать по шагам, как сортируется массив. Всего 18 баллов.
• Пропустили пару с тестом — тест не написан. Про болезнь см. раздел 9.

6. Командный коллоквиум

• Устный, в основном теория, код максимум на листочке. 10 баллов.
• Команды по 4–6 человек. Отвечает команда: могут остановить одного и сказать следующему продолжать с того же места.
• Балл один на всю команду и равен результату самого слабого. «Я всё учил, а тиммейт ничего не делал» — не аргумент: сильные подтягивают слабых.
• Первый коллоквиум ориентировочно в конце октября — начале ноября, по первой половине тем семестра.

7. Теормин

• Индивидуально: 10 вопросов, около 10 минут, сколько ответили — столько баллов из 10.
• Если работали в семестре и писали лабы, это простые баллы.

8. Лайвкодинг

• На паре вместо обычного занятия, 8 баллов. Открываются 2–3 задачи, решить нужно 2.
• Задачи несложные, по любой пройденной теме.
• Google нельзя. Можно свои конспекты и свои решённые задачи.

9. Экзамен и пропуски

• Экзамен только для тех, кто не набрал 60 баллов, и идти на него не стоит. На защите лабы могут подсказать, на экзамене никто не поможет: вопросы по всем темам, начали плавать на двух — комиссия.
• Чтобы попасть на экзамен, нужно «упорно, силой воли» не ходить на пары и ничего не сдавать.
• Посещаемость не отмечается. Но если заболели перед парой с тестом или защитой, напишите заранее, хотя бы утром: дадут дописать и досдать. Если «болезнь» станет еженедельной, потребуют справки.

10. Темы семестра

1. Асимптотика.
2. Сортировки: пузырьком, вставками, слиянием, быстрая, кучей, подсчётом, цифровая. Если пойдёт хорошо — introsort (используется в C++) и timsort (Python, Java).
3. Динамическое программирование: наибольшая возрастающая подпоследовательность, рюкзак, задача о сумме, расстановка знаков. Тема огромная, дальше — самостоятельно.
4. Куча и приоритетная очередь.
5. Деревья; возможно, другие структуры и кодирование.

11. Инструменты

• Sort.me: стартовый контест с задачей A «A+B», открыт до 1 октября. Он для знакомства с платформой; баллов за него скорее всего не будет, но возможен один балл, так что лучше порешать.
• Сайт капризный: не грузится — другой браузер, устройство, VPN, интернет получше (кампусный Wi-Fi слабый).
• Если контеста нет — писать преподавателю или менторам в личку: без этого лабу не защитить.
• IDE: CLion или VS Code, неважно. Гайд по установке скинул преподаватель.

12. Структуры, массив и vector

Структура — объявление нового типа данных:

struct Apple {
    int mass;
    std::string color;
};  // точка с запятой после закрывающей скобки обязательна
 
Apple a;        // переменная создаётся как обычная
a.mass = 100;   // доступ к полям через точку

• Массив — непрерывный участок памяти, по нему удобно ходить по индексам, индексы с нуля.
• vector: заводите на 8 элементов — под капотом выделяется вдвое больше (16), чтобы можно было добавлять. Когда запас кончился, массив пересоздаётся на 32 элемента и все элементы копируются. Если размер известен заранее, задайте его сразу: это дешевле постоянных пересозданий.

13. Асимптотика

• Почему не мерить время в миллисекундах: результат зависит от машины, нагрузки и стоимости одной операции. Нужен порядок роста.
• Асимптота из школьной математики — линия, к которой график стремится, но не пересекает. Асимптотика алгоритма — функция, которую время работы кода не превысит: ограничение сверху.
• Один цикл по массиву из $n$ элементов — $O(n)$. Формально можно ограничить и $n^2$, и $n!$, но берут самую близкую оценку, чтобы ограничить сильнее.
• Про $O(n)$ и $O(n^2)$ не говорят «быстрее» или «медленнее»: у $O(n)$ могут быть участки, где код работает дольше. Говорят «медленнее растущая» и «быстрее растущая» функция.

Три нотации. $O$ — ограничение сверху, $\Omega$ — снизу, $\Theta$ — когда верхняя и нижняя оценки совпали, точная оценка. Цикл по всем элементам ровно один раз: $O(n)$ и $\Omega(n)$, значит $\Theta(n)$.

Как считать: разбивать код на куски и оценивать каждый.

Пример с корнем: внутренний счётчик $j$ растёт, пока $j^2$ не превысит $i$. При $i = 9$ он доходит до 3, при $i = 10$ и $i = 16$ — до 4, при $i = 17$ — до 5, то есть внутренний цикл делает порядка $\sqrt{i}$ шагов; внешний до $n$, итого $O(n\sqrt{n})$.

Правила:

• Константы отбрасываются: $O(2n) = O(n)$. Важен порядок роста, не число операций; два цикла подряд по $n$ — всё равно линейная функция.
• Сложение для последовательных кусков: $O(n) + O(n) = O(n)$.
• Умножение для вложенных: $O(n) \cdot O(k) = O(nk)$. Вложенный цикл не всегда даёт умножение, с этим столкнётесь позже.
• Младшие члены отбрасываются: $O(n^2) + O(n) = O(n^2)$.

На что обратить внимание

1. Баллы за лабу только после защиты, а дедлайн защиты — следующая пара после закрытия лабы.
2. Нет пересдачи лабы. Готовьтесь к защите заранее, чтобы рассказать решение и внести правку.
3. Встроенные структуры и алгоритмы можно использовать только после защиты лабы по теме; vector и string можно всегда.
4. Коллоквиум командный, балл равен результату самого слабого.
5. Болезнь перед тестом или защитой — писать заранее, хотя бы утром.
6. Сумма баллов по записи 98, распределение сверить с правилами курса.

Чек-лист

• Зарегистрироваться на Sort.me и решить «A+B» в стартовом контесте до 1 октября.
• Если контест не появился — написать преподавателю или ментору.
• Поставить CLion или VS Code по гайду.
• Вспомнить struct и понять, как растёт vector.
• Уметь оценить простой код: цикл, два вложенных цикла, цикл с корнем.

Шпаргалка