Алгоритмы 5ML осень 2019

Материал из CSC Wiki
Перейти к:навигация, поиск

Правила сдачи курса

Оценка курса выставляется по 10-балльной шкале и состоит из 3 компонентов:

  1. Теоретические домашние задания. Балл — доля всех сданных обязательных задач.
  2. Контесты. Балл за контесты — доля всех сданных обязательных задач.
  3. Экзамен (только во втором модуле)

Каждый компонент также оцениватся по 10-балльной шкале. Оценки в модулях независимы между собой и являются взвешенной суммой:

  • 1 модуль: 0.6 дз + 0.4 контест
  • 2 модуль: 0.5 экзамен + 0.3 дз + 0.2 контесты

Кроме обязательныз задач бывают дополнительные. Отличия:

  1. Их не разбирают, поэтому их можно решать долго (месяц с момента выдачи, чтобы все не занялись ими 30 декабря)
  2. Они не учитываюся в теоретическом максимуме при расчёте итогового балла

Балл за контест является блокирующим границе 0.4, то есть набрав меньше, вы получаете назачёт за курс. Домашние задания и экзамен таких ограничений не имеют.

Лекции

Лекторы:

  1. Данил Сагунов (лекции 1 – 4)
    • danilka.pro[at]gmail.com
    • Telegram: dsagunov
  2. Пётр Смирнов
    • comradepetr+hse_19fall_algo@gmail.com

Программа

(1) 3 сентября. Асимптотика, рекуррентные соотношения.

  • Введение. Алгоритм. Память и время как ресурсы.
  • Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ.
  • O-символика как инструмент оценки ресурсов, различные асимптотики (логарифм, полином, экспонента). Примеры: простые сортировки, бинарный поиск.
  • Метод разделяй и властвуй. Сортировка слиянием.
  • Рекуррентные соотношения: основная теорема.

(2) 10 сентября. Сортировки.

  • Алгоритмы сортировки. Квадратичные сортировки.
  • Нижняя оценка Ω(n log n) для сортировки сравнениями.
  • Сортировка подсчётом, стабильность. Цифровая сортировка.
  • Интерфейс «очередь с приоритетами». Куча: определение, просеивание вниз, извлечение максимального элемента.

(3) 17 сентября. Анализ быстрой сортировки, порядковые статистики.

  • Куча: просеивание вверх, добавление нового элемента. Построение кучи за линейное время.
  • Сортировка кучей. Частичная сортировка кучей.
  • Быстрая сортировка: понятие вероятностного алгоритма, время работы в среднем.
  • Быстрая сортировка: элиминация хвостовой рекурсии, IntroSort.
  • Анализ среднего времени работы.
  • Массивы с малым количеством различных элементов, QuickSort3.
  • [На практике] Порядковые статистики. Порядковые статистики, нахождение за линейное в среднем время. Частичная сортировка.
---> вы находитесь здесь <---
  • Анализ средней глубины рекурсии быстрой сортировки

Литература

Онлайн-курсы

Практика

Telegram-чат для обсуждений лекций и практик: https://t.me/joinchat/AA2G2xTf_DQL1lfqOqS_hA

Задачи

Условия задач

Артур Рязанов

Контакты:

  • tunyash[at]gmail.com
  • Telegram: tunyash

Дедлайны по теоретическому ДЗ в 23:59 в день до занятия, после него работы не принимаются

Таблица с результатами

Михаил Слабодкин

Контакты:

  • slabodkin.m[at]gmail.com
  • Telegram: slabod

Дедлайны по теоретическому ДЗ:

  • мягкий дедлайн в субботу в 23:59, после него преподаватель один раз проверяет работу до пары
  • жёсткий дедлайн в 23:59 в день до занятия, после него работы не принимаются

Таблица с результатами