Алгоритмы и структуры данных, часть 1
Санкт-Петербург, осень 2018
Описание
Первый семестр курса будет посвящён базовым идеям построения и анализа алгоритмов.
Мы начнём с того, что обсудим, как оценивать сложность алгоритмов, и применим это к алгоритмам, известным нам из курса математики.
Далее мы рассмотрим три основополагающих подхода к построению алгоритмов: жадные алгоритмы, разделяй и властвуй
и динамическое программирование.
Оставшееся время мы потратим на изучение структур данных.
Формат занятий
Занятия проводятся каждый вторник и состоят из лекции (18:30-19:50) и практики (20:00-21:20).
Формат лекций
Основной лекционный материал курса будет предложен для самостоятельного изучения в виде онлайн-курса. На лекциях мы будем обсуждать вопросы, которые возникли в связи с материалом онлайн-курса, и изучать дополнительный материал, который в онлайн-курсе отсутствует.
Онлайн-курс в этом семестре состоит из двух частей: https://stepik.org/course/217/syllabus и https://stepik.org/course/1547/syllabus.
Формат практик
Практика будет проводится в группах. На практиках будут решаться задачи и обсуждаться домашние задания. Разбиение на группы произойдет по результатам контеста на первой неделе.
Домашние задания
Будут состоять из двух типов задач:
Задачи на программирование будут приниматься в автоматическом режиме на системе для контестов.
Задачи на доказательство будет приниматься через сайт центра.
Критерии выставления оценки
Оценка будет выставляться по результатам решения домашних заданий и летучек. Летучки составляют 10% от общей оценки, теоретические домашние задания - 30%, задачи на программирование - 60%.
За 85% решённых задач выставляется оценка
отлично
,за 75% -
хорошо
,за 60% -
зачёт
.
Список литературы
- Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы.
- Т.Кормен, Ч.Лейзерсон, Р.Ривест, К.Штайн - Алгоритмы. Построение и анализ (есть в библиотеке).
- А. Шень. Программирование: теоремы и задачи.
- М. А. Бабенко, М. В. Левин. Введение в теорию алгоритмов и структур данных (есть в библиотеке).
- Вики-конспекты ИТМО.
Преподаватели
Список лекций
Числа Фибоначчи. Наибольший общий делитель. O-символика.
К лекции нужно самостоятельно просмотреть вторую неделю онлайн-курса.
К лекции нужно самостоятельно просмотреть четвёртую неделю онлайн-курса на stepik.
В онлайн курсе на степике нужно посмотреть материалы шестой недели Разделяй и властвуй
.
- 6.1 Двоичный поиск
- 6.2 Умножение чисел
- 6.3 Умножение матриц
- 6.4 Сортировка слиянием
- 6.9 Рекуррентные соотношения
Онлайн курс: «Разделяй и властвуй»
- 6.5 Быстрая сортировка
- 6.6 Порядковые статистики
- 6.7 Сортировка кучей
- 6.8 Сортировки, основанные не на сравнениях
8 Динамическое программирование: теория и задачи
- 8.1 Введение
- 8.2 Наибольшая возрастающая подпоследовательность
- 8.3 Расстояние редактирования
8 Динамическое программирование: теория и задачи
- 8.4 Рюкзак
- 8.5 Перемножение последовательности матриц
- 8.6 Независимые множества во взвешенных деревьях
- 8.7 Обзор
Онлайн курс: “Базовые структуры данных”
1.1 Базовые структуры данных
1.2 Задачи
Ссылка на курс: https://stepik.org/course/1547/syllabus
Онлайн курс: “Очереди с приоритетом и системы непересекающихся множеств”
- 2.1 Очереди с приоритетом
- 2.2 Системы непересекающихся множеств
- 2.3 Задачи
Онлайн курс: “Хеш-таблицы”
3.1 Хеш-таблицы
3.2 Задачи
Лекция: совершенное хеширование.
Онлайн курс: “Деревья поиска”
4.1 АВЛ-деревья
4.2 Дополнительные операции
Онлайн курс: “Сплей-деревья”
- 4.3 Сплей-деревья
- 4.4 Задачи
Динамическая задача RMQ/RSQ: дерево отрезков,
оценка $O(\log n)$ для запросов суммы/минимума и изменения элемента.
Статический вариант задачи RMQ: полное предвычисление
($O(n^2)$ на предобработку, $O(1)$ на запрос),
метод разреженной таблицы ($O(n\log n)$ на предобработку, $O(1)$ на
запрос).
Задача LCA: эйлеров обход дерева, сведение к задаче RMQ.
Cложение, умножение, деление длинных чисел. Арифметика по модулю: сложение, умножение, возведение в степень, алгоритм Евклида, расширенный алгоритм Евклида, деление. Проверка чисел на простоту. Генерация случайных простых чисел. Криптография: схемы с закрытым ключом, RSA.