Алгоритмы и структуры данных, часть 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 Сортировки, основанные не на сравнениях
Динамическое программирование, часть 1

8 Динамическое программирование: теория и задачи

  • 8.1 Введение
  • 8.2 Наибольшая возрастающая подпоследовательность
  • 8.3 Расстояние редактирования
Динамическое программирование, часть 2

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 и LCA

Динамическая задача RMQ/RSQ: дерево отрезков, оценка \(O(\log n)\) для запросов суммы/минимума и изменения элемента.
Статический вариант задачи RMQ: полное предвычисление (\(O(n^2)\) на предобработку, \(O(1)\) на запрос), метод разреженной таблицы (\(O(n\log n)\) на предобработку, \(O(1)\) на запрос). Задача LCA: эйлеров обход дерева, сведение к задаче RMQ.

Числовые алгоритмы

Cложение, умножение, деление длинных чисел. Арифметика по модулю: сложение, умножение, возведение в степень, алгоритм Евклида, расширенный алгоритм Евклида, деление. Проверка чисел на простоту. Генерация случайных простых чисел. Криптография: схемы с закрытым ключом, RSA.