Алгоритмы и структуры данных 2018/2019 (пилотный поток) — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(не показана одна промежуточная версия этого же участника)
Строка 1: Строка 1:
 
'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]
 
'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]
  
[https://drive.google.com/file/d/14AXuM8dnNni2SIEmDXf60IHH6fnWOlG3/view?usp=sharing Программа курса]
+
[https://drive.google.com/open?id=1gy2tOjNQxuPZT9y9lAF3H19SIKLgdjZ5 Программа курса]
  
[https://docs.google.com/spreadsheets/d/10S9jQmnOEsw5gr_nTDK0rOU4rwBMPTqpbUxRQ1cPZwY/edit?usp=sharing Текущая успеваемость]
+
[https://docs.google.com/spreadsheets/d/1k08UuABQPh00ffKSegm_--MnHWONqPRXt0IQKdjflQ0/edit?usp=sharing Текущая успеваемость]
  
 
== Формула выставления итоговой оценки ==
 
== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2018-19 учебного года будет использоваться следующая формула определения оценки:
 
 
 
0.3 * Контесты + 0.25 * Листки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус
 
0.3 * Контесты + 0.25 * Листки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус
  
Строка 16: Строка 14:
 
* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.
 
* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.
  
* Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листок был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (кол-во решенных задач) / (общее число задач - поправка).
+
* Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листок был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (кол-во решенных задач) / (общее число задач - поправка). '''Кроме того, кол-во баллов, полученных за сдачу задач в электронном виде по почте (суммарно за весь модуль) должно не более чем в два раза превышать кол-во баллов, полученных за сдачу устно.''' Формально, если вы получили x баллов за устную сдачу и y баллов за сдачу по почте, то ваше суммарное кол-во баллов равняется x + min(2x, y).
  
 
* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.
 
* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.
Строка 32: Строка 30:
 
! Дата лекции !! Темы
 
! Дата лекции !! Темы
 
|-
 
|-
| 30 октября || Знакомство со структурой курса и системой выставления оценок. <br />Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.  
+
| 30 октября || Знакомство со структурой курса и системой выставления оценок. <br />Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность  
 +
|-
 +
| 31 октября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства
 +
|-
 +
| 6 ноября || RAM-модель, схемы доказательства корректности алгоритмов и времени их работы
 +
|-
 +
| 13 ноября || Сортировки сравнениями, подсчётом и поразрядная
 +
|-
 +
| 14 ноября || Корзинная сортировка и сортировка во внешней памяти
 +
|-
 +
| 20 ноября || Простые структуры данных, двоичные кучи
 +
|-
 +
| 27 ноября || Амортизационный анализ, k-ичные кучи
 +
|-
 +
| 28 ноября || Биномиальные и фибоначчиевы кучи
 +
|-
 +
| 4 декабря || Введение в хеширование, свойства хеш-функций, парадокс дней рождений и полиномиальный хеш
 +
|-
 +
| 11 декабря || Хеш-таблицы, методы сканирования при использовании открытой адресации, идеальное хеширование
 +
|-
 +
| 12 декабря || Фильтры блума, стратегии масштабирования таблиц, деамортизация
 +
|-
 +
| 18 декабря || Бинарные деревья поиска. Сбалансированные деревья. Декартово дерево.
 +
|-
 +
| 10 января || 2-3 деревья и B-деревья.
 +
|-
 +
| 15 января || Частичные суммы, разреженные таблицы, деревья отрезков. Метод сканирующей прямой.
 +
|-
 +
| 22 января || Задачи LCA и LA. Сведение LCA к RMQ и наоборот. Метод четырёх русских.
 +
|-
 +
| 24 января || Персистентность и персистентные структуры данных.
 +
|-
 +
| 29 января || Перебор комбинаторных объектов. Динамическое программирование. Генерация комбинаторных объектов.
 +
|-
 +
| 5 февраля || Динамическое программирование по подотрезкам, поддеревьям, подмаскам. Meet-in-the-middle.
 +
|-
 +
| 7 февраля || Ускорение вычислений с помощью битовых операций. Эффективное использование памяти в задачах динамического программирования.
 +
|-
 +
| 12 февраля || Перебор в задаче вершинного покрытия и в антагонистических играх (в том числе альфа-бета)
 +
|-
 +
| 19 февраля || Минимальные остовные деревья: алгоритмы поиска и критерии оптимальности
 +
|-
 +
| 21 февраля || СНМ, обход в глубину, поиск мостов и точек сочленения
 +
|-
 +
| 26 февраля || Поиск компонент реберной и вершинной двусвязности, сильной связности
 +
|-
 +
| 5 марта || Кратчайшие пути в графах: алгоритмы Форда-Беллмана, Флойда-Уоршелла и Дейкстры
 +
|-
 +
| 7 марта || Паросочетания, лемма Холла, алгоритм Куна и теорема Кёнига
 +
|-
 +
| 19 марта || Введение в теорию потоков, теорема Форда-Фалкерсона
 +
|-
 +
| 21 марта || Эйлеров цикл и list ranking
 +
|-
 +
| 2 апреля || Полиномиальные алгоритмы решения задачи о максимальном потоке. Алгоритм Эдмондса-Карпа, техника масштабирования, алгоритм Диница.
 +
|-
 +
| 4 апреля || Стоимостной поток. Определения и жадный алгоритм. Алгоритм Дейкстры с потенциалами Джонсона.
 +
|-
 +
| 9 апреля || Вычислительная геометрия. Основные примитивы (точка, прямая, окружность) и базовые операции работы с ними.
 +
|-
 +
| 16 апреля || Проверка принадлежности точки невыпуклому многоугольнику. Алгоритм Грэхема построения выпуклой оболочки. Некоторые алгоритмы быстрой геометрии.
 +
|-
 +
| 18 апреля || Задача поиска двух ближайших точек. Задача поиска двух наиболее удалённых точек. Пересечение полуплоскостей.
 +
|-
 +
| 23 апреля || Алгоритм Чана
 +
|-
 +
| 30 апреля || Построение трехмерной выпуклой оболочки за O(n^2)
 +
|-
 +
| 14 мая || Быстрое преобразование Фурье
 +
|-
 +
| 21 мая || Продвинутые алгоритмы ТЧ, алгоритм Полларда, алгоритм Миллера-Рабина
 +
|-
 +
| 23 мая || Введение в криптографию, шифрование RSA
 +
|-
 +
| 28 мая || Строковые алгоритмы, обзор задач, префикс-функция и z-функция
 +
|-
 +
| 4 июня || Бор и сжатый бор, алгоритм Ахо-Корасик
 +
|-
 +
| 6 июня || Cуффиксный массив и связанные задачи
 +
|-
 +
| 11 июня || Cуффиксное дерево, алгоритм Укконена
 
|}
 
|}
  
Строка 41: Строка 119:
 
! Дата семинара !! Темы !! Листок
 
! Дата семинара !! Темы !! Листок
 
|-
 
|-
| 30 октября || Понятие асимптотического времени работы алгоритма. <br /> Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω || [https://drive.google.com/file/d/1t8mHek9NBzRNtAWHib02C0mcY_x_nAzc/view?usp=sharing тык]
+
| 30 октября || Понятие асимптотического времени работы алгоритма <br /> Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω || [https://drive.google.com/file/d/1t8mHek9NBzRNtAWHib02C0mcY_x_nAzc/view?usp=sharing тык]
 +
|-
 +
| 31 октября || Совместное решение задач по теории вероятностей || [https://drive.google.com/file/d/1nxeLwcV11h7VqmSgYGKpIYlXJHpxSfst/view?usp=sharing тыц]
 +
|-
 +
| 6 ноября || Совместное решение задач на матожидание || [https://drive.google.com/open?id=1fq0KHmFU2pwVp9jw5mkFoV4vijPpUNmp туц]
 +
|-
 +
| 13 ноября || Обсуждение методов тестирования || не было
 +
|-
 +
| 14 ноября || Совместное решение задач на сортировки и порядковые статистики || [https://drive.google.com/open?id=1BzVe_foct6Yd31wlQWoXIrj3j8qJqYCg тыц]
 +
|-
 +
| 20 ноября || Сортировки и порядковые статистики наносят ответный удар || [https://drive.google.com/open?id=1DvAwBoc44Eb1vv-uX4QbEjDe0fr-UGHi туц]
 +
|-
 +
| 27 ноября || Разбор домашнего листка по теории вероятностей || [https://drive.google.com/open?id=13avmP9yw7GdrCO7d8mWfNTP3DMiP-Rc1 тык]
 +
|-
 +
| 28 ноября || Совместное решение задач на простые структуры данных || [https://drive.google.com/open?id=19z1ZXRICjwNMGRiJDGjqtGTc69LNWqt9 тыц]
 +
|-
 +
| 4 декабря || Подготовка к контрольной и совместное решение задач || [https://drive.google.com/open?id=13hIr9P5xB6NJcyTWqVOah4V6Nb1W0gWi туц]
 +
|-
 +
| 11 декабря || Разбор контрольной, второго листка и длинного контеста || не было
 +
|-
 +
| 12 декабря || Разбор контрольной, второго листка и длинного контеста || не было
 +
|-
 +
| 18 декабря || Хеши || ¯\_(ツ)_/¯
 +
|-
 +
| 10 января || ¯\_(ツ)_/¯ || ¯\_(ツ)_/¯
 +
|-
 +
| 15 января || Деревья поиска || [https://drive.google.com/open?id=18hDHLuuma99io4gOK-FzhszIek-6ON5L тык]
 +
|-
 +
| 22 января || Запросы на отрезках || [https://drive.google.com/open?id=1WRTAFYJ3Cb0drgc8lIyhfH9ZuTa-sjZG тыц]
 +
|-
 +
| 24 января || Splay-дерево || [https://drive.google.com/open?id=1FnYO6eB3m_TBoFnHYnXZpFQ6JSTt09CB туц]
 +
|-
 +
| 29 января || Запросы на деревьях и персистентность || [https://drive.google.com/open?id=1XxT8rLoG0yjBX7tXkGHP5ZGM6g7oqxut тыц]
 +
|-
 +
| 5 февраля || Разговоры про неасимптотические оптимизации || Не было
 +
|-
 +
| 7 февраля || Разбор листка про деревья и запросы на отрезках || не было
 +
|-
 +
| 12 февраля || Динамическое программирование || [https://drive.google.com/open?id=1_f9xCgYHDCr01gOtvaPvUvlnpIh5TsEt тыц]
 +
|-
 +
| 19 февраля || Динамическое программирование, перебор и meet-in-the-middle || [https://drive.google.com/open?id=1LyNoxd7Qu0XHbAiL-jMhYXZWV-kSpNBf туц]
 +
|-
 +
| 21 февраля || Динамическое программирование и остовные деревья || [https://drive.google.com/open?id=1lzwmO2Y5zICH19hMo51tKLJNj0ZxJO7R тык]
 +
|-
 +
| 26 февраля || Подготовка к контрольной || [https://drive.google.com/open?id=1ylJLPvSd4C6rdXDrHyUPLkY0nleLhUBE тыц]
 +
|-
 +
| 5 марта || Разбор листка про персистентность и запросы на деревьях || не было
 +
|-
 +
| 7 марта || Графы || [https://drive.google.com/open?id=1vTGaG3Egl5YgYvGk9Fo6pg7v9jDXG4h_ тык]
 +
|-
 +
| 19 марта || Двудольные графы || [https://drive.google.com/open?id=1j_V6UP3tnMleHfSDNewpqDER5qDzqz9F тыц]
 +
|-
 +
| 21 марта || Разбор листка про перебор и динамическое программирование || не было
 +
|-
 +
| 2 апреля || Разбор листка про остовы, графы и СНМ || не было
 +
|-
 +
| 4 апреля || Потоки и двудольные паросочетания || [https://drive.google.com/open?id=1j0IiiMbRVNT8vonoSqLNlHznF4Gn2kYx тык]
 +
|-
 +
| 9 апреля || Максимальные потоки и минимальные разрезы || [https://drive.google.com/open?id=1XflyS6JfESqpp5ML2T51cMUJeIk8B9tM туц]
 +
|-
 +
| 16 апреля || MapReduce || [https://drive.google.com/open?id=16HqoMdOy_t1yYTUWjll5-dKrxvJ0-sJD тыц]
 +
|-
 +
| 18 апреля || Геометрия || [https://drive.google.com/open?id=1rjOFMizSKqBRRbPTi6mhXcyQ55MJvoFN тык]
 +
|-
 +
| 23 апреля || Еще геометрия || [https://drive.google.com/open?id=1kA26ERuAOKxfYv8_ez3uXXaPBMQONp6P тыц]
 +
|-
 +
| 30 апреля || Разбор листка про паросочетания и потоки || не было
 +
|-
 +
| 14 мая || Алгоритм Карацубы и мастер-теорема || [https://drive.google.com/open?id=1cJcoh6sVT8xAvCO6X6_xpe1N23on7Mo9 туц]
 +
|-
 +
| 21 мая || Базовая теория чисел || [https://drive.google.com/open?id=1s7874Vo_wjiYW_XhQ2-roxL8PtU7qOGf тык]
 +
|-
 +
| 23 мая || Быстрое преобразование Фурье || [https://drive.google.com/open?id=1-33a7Y3whkEgMaTn0KBc9uT7_8l9r4sY тыц]
 +
|-
 +
| 28 мая || Разбор листка про геометрию || не было
 +
|-
 +
| 4 июня || Немного строк вам в ленту || [https://drive.google.com/open?id=1ESNGVSBy3s-mQWolhwAqbYVV7YO1ptaA тык]
 +
|-
 +
| 6 июня || Эх, щука! (Ахо-Корасик) || [https://drive.google.com/open?id=19F5TBVBUqDtQ4R_GfLZNFnbksVzutBVv туц]
 +
|-
 +
| 11 июня || Суффиксный массив и суффиксное дерево || [https://drive.google.com/open?id=1iK9pn4J6B5HP5JeoTtrA1Z-8OegF3ks5 тык]
 
|}
 
|}
  
 
== Листки ==
 
== Листки ==
  
Устно листки сдаются преподавателям и асситентам в присутственные часы.
+
Устно листки сдаются преподавателям и ассистентам в присутственные часы.
  
 
Листки в электронном виде отправляются на почту hse.algo@gmail.com. Принимается только TeX — нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки); решения, написанные в MS Word и подобных программах и т.д. Решения отправляются ровно один раз — нельзя отправить что-то, а потом через неделю прислать исправленную версию (небольшие исправления и уточнения разрешаются, если сделаны в течение нескольких часов после отправки листка и строго до дедлайна).   
 
Листки в электронном виде отправляются на почту hse.algo@gmail.com. Принимается только TeX — нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки); решения, написанные в MS Word и подобных программах и т.д. Решения отправляются ровно один раз — нельзя отправить что-то, а потом через неделю прислать исправленную версию (небольшие исправления и уточнения разрешаются, если сделаны в течение нескольких часов после отправки листка и строго до дедлайна).   
 +
 +
{| class="wikitable"
 +
|-
 +
! Дедлайн !! Темы !! Листок
 +
|-
 +
| полночь с 20 на 21 ноября || Вероятности и математическое ожидание || [https://drive.google.com/open?id=13avmP9yw7GdrCO7d8mWfNTP3DMiP-Rc1 тык]
 +
|-
 +
| полночь с 5 на 6 декабря || Сортировки и простые структуры данных || [https://drive.google.com/open?id=1L2Aky2D_w_yguPYwcwaOLTISVQphX3dq тыц]
 +
|-
 +
| полночь с 17 на 18 декабря || Кучи, хеши и амортизационный анализ || [https://drive.google.com/open?id=1vEwYzlA_kz9sIJPKMLwFfdMRZr4F6KnR туц]
 +
|-
 +
| полночь с 6 на 7 февраля || Деревья и запросы на отрезках || [https://drive.google.com/open?id=1KYceCdGxi9Ry-LaF4Gb9pWvffQUP1pdx тык]
 +
|-
 +
| полночь с 27 на 28 февраля || Персистентность, запросы на деревьях и прочее || [https://drive.google.com/open?id=1dD_u07RUvOHGRnOw091-8D158LioC6Oh тыц]
 +
|-
 +
| полночь с 13 на 14 марта || Динамическое программирование, перебор и meet-in-the-middle || [https://drive.google.com/open?id=1t4cYg1MmwhqSRs38-6iImy2gzKjTpIMj тык]
 +
|-
 +
| полночь с 27 на 28 марта || Остовы, графы и СНМ || [https://drive.google.com/open?id=1MC078Vxp688qNN3e67L7SgnHrNJI8GK- тыц]
 +
|-
 +
| полночь с 29 на 30 апреля || Потоки и паросочетания || [https://drive.google.com/open?id=167LE0CGmSWQFlavfuWAzKCPeAO-NcQEa туц]
 +
|-
 +
| полночь с 27 на 28 мая || Геометрия || [https://drive.google.com/open?id=1274FzjJHBZg__2SAcZG4qPsBl0W_seY8 тык]
 +
|-
 +
| полночь с 10 на 11 июня || Теория чисел и БПФ || [https://drive.google.com/open?id=1it4NpaGVo5qwfyptSbx7uB1Td4olWpCw тыц]
 +
|-
 +
| полночь с 25 на 26 июня || Строки || [https://drive.google.com/open?id=116ttmU33W26vx1hpGwsJuOFS1x4_d67M тык]
 +
|}
  
 
== Короткие контесты ==
 
== Короткие контесты ==
 +
 +
Если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
 +
 +
{| class="wikitable"
 +
|-
 +
! Дата !! Ссылка !! Дорешивать
 +
|-
 +
| 7 ноября || [https://official.contest.yandex.ru/contest/10023/enter/ тык] || Можно
 +
|-
 +
| 21 ноября || [https://official.contest.yandex.ru/contest/10727/enter/ тыц] || Можно
 +
|-
 +
| 19 декабря || [https://official.contest.yandex.ru/contest/11322/enter/ туц] || Нельзя (бонусный)
 +
|-
 +
| 17 января || [https://official.contest.yandex.ru/contest/11611/enter/ тыц] || Можно
 +
|-
 +
| 31 января || [https://official.contest.yandex.ru/contest/11867/enter/ тык] || Можно
 +
|-
 +
| 14 февраля ❤️ || [https://official.contest.yandex.ru/contest/11986/enter/ туц] || Нельзя (необычный)
 +
|-
 +
| 14 марта || [https://official.contest.yandex.ru/contest/12294/enter/ тык] || Нельзя (бонусный)
 +
|-
 +
| 11 апреля || [https://official.contest.yandex.ru/contest/12564 тыц] || Можно
 +
|-
 +
| 25 апреля || [https://official.contest.yandex.ru/contest/12693/enter/ тыц] || Можно
 +
|-
 +
| 16 мая || [https://official.contest.yandex.ru/contest/12799 туц] || Нельзя
 +
|-
 +
| 13 июня || [https://official.contest.yandex.ru/contest/13013/enter/ тык] || Нельзя (бонусный)
 +
|}
  
 
== Длинные контесты ==
 
== Длинные контесты ==
 +
 +
{| class="wikitable"
 +
|-
 +
! Дедлайн !! Темы !! Ссылка
 +
|-
 +
| Полночь с 6 на 7 декабря || Сортировки, порядковые статистики, простые структуры данных || [https://official.contest.yandex.ru/contest/10785/enter/ тык]
 +
|-
 +
| Полночь с 17 на 18 декабря || Хеширование и другие темы || [https://official.contest.yandex.ru/contest/11210/enter/ тыц]
 +
|-
 +
| Полночь с 4 на 5 марта || Структуры данных || [https://official.contest.yandex.ru/contest/11654/enter/ тык]
 +
|-
 +
| Полночь с 28 на 29 марта || Динамическое программирование и перебор || [https://official.contest.yandex.ru/contest/12344/enter/ тыц]
 +
|-
 +
| Полночь с 2 на 3 июня || Графы, геометрия || [https://official.contest.yandex.ru/contest/12783/enter/ тык]
 +
|-
 +
| Полнчь с 26 на 27 июня || Геометрия, теория чисел, БПФ, строки || [https://official.contest.yandex.ru/contest/12917/enter/ тыц]
 +
|}
  
 
== Преподаватели и ассистенты ==  
 
== Преподаватели и ассистенты ==  
Строка 60: Строка 291:
 
! Преподаватель !! Подгруппа !! Присутственные часы
 
! Преподаватель !! Подгруппа !! Присутственные часы
 
|-
 
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||  Вторник, с 13:40 до 15:00
+
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 181-1 ||   
 
|-
 
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||  
+
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 181-2 ||  
 
|-
 
|-
| Дмитрий Иващенко  || 173-1 ||  
+
| Дмитрий Иващенко  || 183-1 ||  
 
|-
 
|-
| Иван Смирнов || 173-2 ||   
+
| Иван Смирнов || 183-2 ||   
 
|-
 
|-
| Александр Курилкин ||  || Среда, с 12.10 до 13.30
+
| Александр Курилкин ||  || Среда, с 12:10 до 13:30, ауд. 416
 
|-
 
|-
| Глеб Третьяков ||  || Вторник, с 12:10 до 13:30
+
| Глеб Третьяков ||  || Вторник, с 12:10 до 13:30, ауд. 300
 
|}
 
|}
 +
 +
== Полезные материалы ==
 +
 +
[https://drive.google.com/file/d/1K2hRjwDEsHIWduJ1p5IPqYVmdHuahCVS/view?usp=sharing Памятка по теорверу]
 +
 +
[https://docs.google.com/spreadsheets/d/10S9jQmnOEsw5gr_nTDK0rOU4rwBMPTqpbUxRQ1cPZwY/edit?usp=sharing Успеваемость во втором модуле]
 +
 +
[https://docs.google.com/spreadsheets/d/15aD-80OjMLnCY1I2Y7TByYhrHQZovX_izxX16ItkHcw/edit#gid=1463151260 Успеваемость за третий модуль]

Версия 03:06, 26 июня 2019

Лектор: Глеб Олегович Евстропов

Программа курса

Текущая успеваемость

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

0.3 * Контесты + 0.25 * Листки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус

  • Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
  • Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные.
  • Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.
  • Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листок был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (кол-во решенных задач) / (общее число задач - поправка). Кроме того, кол-во баллов, полученных за сдачу задач в электронном виде по почте (суммарно за весь модуль) должно не более чем в два раза превышать кол-во баллов, полученных за сдачу устно. Формально, если вы получили x баллов за устную сдачу и y баллов за сдачу по почте, то ваше суммарное кол-во баллов равняется x + min(2x, y).
  • В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.
  • За экзамен студент получает оценку от 0 до 10.
  • Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.
  • Итоговая оценка округляется арифметически (то есть при дробной части меньше 0.5 округление производится вниз, иначе вверх).

Лекции

Дата лекции Темы
30 октября Знакомство со структурой курса и системой выставления оценок.
Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность
31 октября Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства
6 ноября RAM-модель, схемы доказательства корректности алгоритмов и времени их работы
13 ноября Сортировки сравнениями, подсчётом и поразрядная
14 ноября Корзинная сортировка и сортировка во внешней памяти
20 ноября Простые структуры данных, двоичные кучи
27 ноября Амортизационный анализ, k-ичные кучи
28 ноября Биномиальные и фибоначчиевы кучи
4 декабря Введение в хеширование, свойства хеш-функций, парадокс дней рождений и полиномиальный хеш
11 декабря Хеш-таблицы, методы сканирования при использовании открытой адресации, идеальное хеширование
12 декабря Фильтры блума, стратегии масштабирования таблиц, деамортизация
18 декабря Бинарные деревья поиска. Сбалансированные деревья. Декартово дерево.
10 января 2-3 деревья и B-деревья.
15 января Частичные суммы, разреженные таблицы, деревья отрезков. Метод сканирующей прямой.
22 января Задачи LCA и LA. Сведение LCA к RMQ и наоборот. Метод четырёх русских.
24 января Персистентность и персистентные структуры данных.
29 января Перебор комбинаторных объектов. Динамическое программирование. Генерация комбинаторных объектов.
5 февраля Динамическое программирование по подотрезкам, поддеревьям, подмаскам. Meet-in-the-middle.
7 февраля Ускорение вычислений с помощью битовых операций. Эффективное использование памяти в задачах динамического программирования.
12 февраля Перебор в задаче вершинного покрытия и в антагонистических играх (в том числе альфа-бета)
19 февраля Минимальные остовные деревья: алгоритмы поиска и критерии оптимальности
21 февраля СНМ, обход в глубину, поиск мостов и точек сочленения
26 февраля Поиск компонент реберной и вершинной двусвязности, сильной связности
5 марта Кратчайшие пути в графах: алгоритмы Форда-Беллмана, Флойда-Уоршелла и Дейкстры
7 марта Паросочетания, лемма Холла, алгоритм Куна и теорема Кёнига
19 марта Введение в теорию потоков, теорема Форда-Фалкерсона
21 марта Эйлеров цикл и list ranking
2 апреля Полиномиальные алгоритмы решения задачи о максимальном потоке. Алгоритм Эдмондса-Карпа, техника масштабирования, алгоритм Диница.
4 апреля Стоимостной поток. Определения и жадный алгоритм. Алгоритм Дейкстры с потенциалами Джонсона.
9 апреля Вычислительная геометрия. Основные примитивы (точка, прямая, окружность) и базовые операции работы с ними.
16 апреля Проверка принадлежности точки невыпуклому многоугольнику. Алгоритм Грэхема построения выпуклой оболочки. Некоторые алгоритмы быстрой геометрии.
18 апреля Задача поиска двух ближайших точек. Задача поиска двух наиболее удалённых точек. Пересечение полуплоскостей.
23 апреля Алгоритм Чана
30 апреля Построение трехмерной выпуклой оболочки за O(n^2)
14 мая Быстрое преобразование Фурье
21 мая Продвинутые алгоритмы ТЧ, алгоритм Полларда, алгоритм Миллера-Рабина
23 мая Введение в криптографию, шифрование RSA
28 мая Строковые алгоритмы, обзор задач, префикс-функция и z-функция
4 июня Бор и сжатый бор, алгоритм Ахо-Корасик
6 июня Cуффиксный массив и связанные задачи
11 июня Cуффиксное дерево, алгоритм Укконена

Семинары

Дата семинара Темы Листок
30 октября Понятие асимптотического времени работы алгоритма
Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω
тык
31 октября Совместное решение задач по теории вероятностей тыц
6 ноября Совместное решение задач на матожидание туц
13 ноября Обсуждение методов тестирования не было
14 ноября Совместное решение задач на сортировки и порядковые статистики тыц
20 ноября Сортировки и порядковые статистики наносят ответный удар туц
27 ноября Разбор домашнего листка по теории вероятностей тык
28 ноября Совместное решение задач на простые структуры данных тыц
4 декабря Подготовка к контрольной и совместное решение задач туц
11 декабря Разбор контрольной, второго листка и длинного контеста не было
12 декабря Разбор контрольной, второго листка и длинного контеста не было
18 декабря Хеши ¯\_(ツ)_/¯
10 января ¯\_(ツ)_/¯ ¯\_(ツ)_/¯
15 января Деревья поиска тык
22 января Запросы на отрезках тыц
24 января Splay-дерево туц
29 января Запросы на деревьях и персистентность тыц
5 февраля Разговоры про неасимптотические оптимизации Не было
7 февраля Разбор листка про деревья и запросы на отрезках не было
12 февраля Динамическое программирование тыц
19 февраля Динамическое программирование, перебор и meet-in-the-middle туц
21 февраля Динамическое программирование и остовные деревья тык
26 февраля Подготовка к контрольной тыц
5 марта Разбор листка про персистентность и запросы на деревьях не было
7 марта Графы тык
19 марта Двудольные графы тыц
21 марта Разбор листка про перебор и динамическое программирование не было
2 апреля Разбор листка про остовы, графы и СНМ не было
4 апреля Потоки и двудольные паросочетания тык
9 апреля Максимальные потоки и минимальные разрезы туц
16 апреля MapReduce тыц
18 апреля Геометрия тык
23 апреля Еще геометрия тыц
30 апреля Разбор листка про паросочетания и потоки не было
14 мая Алгоритм Карацубы и мастер-теорема туц
21 мая Базовая теория чисел тык
23 мая Быстрое преобразование Фурье тыц
28 мая Разбор листка про геометрию не было
4 июня Немного строк вам в ленту тык
6 июня Эх, щука! (Ахо-Корасик) туц
11 июня Суффиксный массив и суффиксное дерево тык

Листки

Устно листки сдаются преподавателям и ассистентам в присутственные часы.

Листки в электронном виде отправляются на почту hse.algo@gmail.com. Принимается только TeX — нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки); решения, написанные в MS Word и подобных программах и т.д. Решения отправляются ровно один раз — нельзя отправить что-то, а потом через неделю прислать исправленную версию (небольшие исправления и уточнения разрешаются, если сделаны в течение нескольких часов после отправки листка и строго до дедлайна).

Дедлайн Темы Листок
полночь с 20 на 21 ноября Вероятности и математическое ожидание тык
полночь с 5 на 6 декабря Сортировки и простые структуры данных тыц
полночь с 17 на 18 декабря Кучи, хеши и амортизационный анализ туц
полночь с 6 на 7 февраля Деревья и запросы на отрезках тык
полночь с 27 на 28 февраля Персистентность, запросы на деревьях и прочее тыц
полночь с 13 на 14 марта Динамическое программирование, перебор и meet-in-the-middle тык
полночь с 27 на 28 марта Остовы, графы и СНМ тыц
полночь с 29 на 30 апреля Потоки и паросочетания туц
полночь с 27 на 28 мая Геометрия тык
полночь с 10 на 11 июня Теория чисел и БПФ тыц
полночь с 25 на 26 июня Строки тык

Короткие контесты

Если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

Дата Ссылка Дорешивать
7 ноября тык Можно
21 ноября тыц Можно
19 декабря туц Нельзя (бонусный)
17 января тыц Можно
31 января тык Можно
14 февраля ❤️ туц Нельзя (необычный)
14 марта тык Нельзя (бонусный)
11 апреля тыц Можно
25 апреля тыц Можно
16 мая туц Нельзя
13 июня тык Нельзя (бонусный)

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

Дедлайн Темы Ссылка
Полночь с 6 на 7 декабря Сортировки, порядковые статистики, простые структуры данных тык
Полночь с 17 на 18 декабря Хеширование и другие темы тыц
Полночь с 4 на 5 марта Структуры данных тык
Полночь с 28 на 29 марта Динамическое программирование и перебор тыц
Полночь с 2 на 3 июня Графы, геометрия тык
Полнчь с 26 на 27 июня Геометрия, теория чисел, БПФ, строки тыц

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

Преподаватель Подгруппа Присутственные часы
Глеб Евстропов 181-1
Станислав Артюхин 181-2
Дмитрий Иващенко 183-1
Иван Смирнов 183-2
Александр Курилкин Среда, с 12:10 до 13:30, ауд. 416
Глеб Третьяков Вторник, с 12:10 до 13:30, ауд. 300

Полезные материалы

Памятка по теорверу

Успеваемость во втором модуле

Успеваемость за третий модуль