Алгоритмы и структуры данных пилотный поток 2022/2023

Лектор: Иван Фёдорович Смирнов

Важные ссылки
Текущая успеваемость	Запись на консультации		Сдача ДЗ

Формула выставления итоговой оценки

Формула оценивания пока предварительная и может поменяться!

Курс длится 4 модуля (со 2-го по 5-й) и предполагает две итоговые оценки: на первом курсе (2-4 модули) и на втором (5 модуль). Оценки за каждый модуль ставятся независимо. Итоговая оценка за первый курс составляется из оценок за 2-4 модули (точные правила будут сообщены позднее). Оценка за 5-й модуль является итоговой оценкой за второй курс.

После 3-го, 4-го и 5-го модулей будут экзамены.

Предварительные правила выставления оценок за модули:

2 модуль: О_итог = 0.4286 · О_{контесты} + 0.3571 · O_листки + 0.2143 · О_КР + O_бонус

3-4 модуль: О_итог = 0.3 · О_{контесты} + 0.25 · O_листки + 0.15 · О_КР + 0.3 · О_{экзамен} + O_бонус

• О_листки вычисляется по формуле:

  Олистки = 10 ·	количество решённых задач
  	количество обязательных задач - поправка

  Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно в электронном виде. Дополнительно предусматривается возможность сдать их во время присутственных часов на консультациях ассистентам.

• В течение каждого очного модуля предполагается по одной контрольной работе. За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться О_КР. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.
• За экзамен студент получает оценку от 0 до 10, эта оценка будет являться О_{экзамен}.
• Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

Итоговая оценка округляется арифметически (то есть при дробной части меньше 0.5 округление производится вниз, иначе вверх).

Теоретическое домашнее задание

Общие предположения, которыми можно пользоваться в задачах

1. Если в задаче говорится про запросы, то по умолчанию online

2. Если не оговорено иное, можно использовать столько же памяти, сколько времени

3. Если не оговорено иное, то можно ожидаемое амортизированное время с хешами

Правила сдачи письменных работ

1. Пожалуйста, убедитесь, что вашу работу можно идентифицировать (имя написано в файле, или ваш гугл-аккаунт подписан вашим именем).

2. При отправке убедитесь, что у вас появилась кнопка "отменить отправку" — это означает, что работа отправлена на проверку.

3. Домашние задания, сданные не в формате .pdf или набранные не с помощью системы вёрстки LaTeX не принимаются.

4. Нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки).

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

6. Списывание в работах повлечёт за собой обнуление баллов по работе.

7. Если вы не чувствуете себя уверено при работе с LaTeX, используйте шаблон https://www.overleaf.com/read/bpvmhqcvfgqq. В нём отражена основная функциональность системы вёрстки. Вы можете склонировать проект и использовать его.

Список заданий

№	Тема	Листок	Дедлайн
2 модуль

Длинные контесты

Все длинные контесты доступны по ссылке.

№	Дедлайн	Темы
2 модуль
1	26.11.2022	Вероятности
2	10.12.2023	Простые структуры

Лекции и семинары

2 модуль

Дата Тип Тема Материалы Видео 01.11.2022 Семинар Основные определения, асимптотический рост функций, виды полиномиальности Лекция Знакомство, обзор программы курса, введние в теорию вероятностей 03.11.2022 Семинар Задачи на теорию вероятностей, конечные вероятностные пространства, геометрическая вероятность Лекция Случайные величины. Математическое ожидание, дисперсия, линейность, индикаторные величины.

3 модуль

Дата Тип Тема Материалы Видео 10.01.2023 (вт) Семинар Антихештесты Лекция [1] [Филипп] 12.01.2023 (чт) Семинар Деревья поиска Лекция [2] [Филипп] 17.01.2023 (вт) Семинар Деревья поиска, запросы на отрезках Лекция [3] ДД, доказательство высоты (?) 19.01.2023 (чт) Семинар Персистентность, запросы на отрезках Лекция [4] Частичная персистентность 24.01.2023 (вт) Семинар Запросы на отрезках, персистентная очередь (бонус) Лекция [5] List order maintenance (?) 26.01.2023 (чт) Семинар Задачи на деревья Лекция [6] HLD (?) 31.01.2023 (вт) Семинар Простое ДП, задачи о рюкзаке Лекция [7] Подсчёт количества клик в графе (?) 2.02.2023 (чт) Семинар Бонусный семинар — архитектура Лекция Бонус (рассказ) 7.02.2023 (вт) Семинар ДП, переборы Лекция [8] Переборы,альфа-бета отсечение 9.02.2023 (чт) Семинар ДП, альфа-бета отсечение Лекция [9] 14.02.2023 (вт) Занятий не было 16.02.2023 (чт) Бонусный семинар Модель внешней памяти 21.02.2023 (вт) Семинар Пути в графах, кратчайшие и не очень Лекция [10] Contraction Hierarchies: поиск кратчайших путей на практике 23.02.2023 (чт) Выходной 28.02.2023 (вт) Семинар Разбор КР Лекция [11] Линейный алгоритм поиска MST 2.03.2023 (чт) Бонусный контест 7.03.2023 (вт) Семинар Минимальные остовы Лекция [12] Алгоритм Тарьяна для поиска КСС. Неудачное доказательство log* n для СНМ. 9.03.2023 (чт) Семинар Задачи на графы, конденсация, 2-SAT Лекция [13] Доказательство log* n для СНМ. Введение в потоки.

Ссылки на материалы

Основные источники:

1. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: Построение и анализ, [2013, 3 издание]
2. neerc.ifmo.ru

Преподаватели и ассистенты

Преподаватель	Подгруппа	Присутственные часы	Контакты
Преподаватели
Иван Смирнов	221-1		@ifsmirnov
Филипп Грибов	221-2
Иван Сафонов	222-1
Михаил Анопренко	222-2
Сергей Нечаев	225-1
Екатерина Фадеева	225-2