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

Материал из CSC Wiki
Версия от 21:04, 7 сентября 2020; P.u.smirnov (обсуждение | вклад) (Новая страница: «== Правила сдачи курса == Оценка курса выставляется по 10-балльной шкале и состоит из 3 комп…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

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

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

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

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

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

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

Балл за контест, балл за дз и оценка за экзамен являются блокирующими по оценке 4/10, то есть набрав меньше, вы не получите зачёт за курс.

Лекции

Лектор: Пётр Смирнов

Программа

(1) 7 сентября. Асимптотика, рекуррентные соотношения.
  • Введение. Алгоритм. Память и время как ресурсы.
  • Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ.
  • O-символика как инструмент оценки ресурсов, различные асимптотики (логарифм, полином, экспонента). Примеры: простые сортировки, бинарный поиск.
  • Метод разделяй и властвуй. Сортировка слиянием.
  • Рекуррентные соотношения: основная теорема.
(2) 14 сентября. Сортировки.
  • Алгоритмы сортировки. Квадратичные сортировки.
  • Нижняя оценка Ω(n log n) для сортировки сравнениями.
  • Сортировка подсчётом, стабильность. Цифровая сортировка.
  • Интерфейс «очередь с приоритетами». Куча: определение, просеивание вниз, извлечение максимального элемента.
(3) 21 сентября. Анализ быстрой сортировки, порядковые статистики.
  • Куча: просеивание вверх, добавление нового элемента. Построение кучи за линейное время.
  • Сортировка кучей. Частичная сортировка кучей.
  • Быстрая сортировка: понятие вероятностного алгоритма, время работы в среднем.
  • Быстрая сортировка: элиминация хвостовой рекурсии, IntroSort.
  • Анализ среднего времени работы.
  • Массивы с малым количеством различных элементов, QuickSort3.
  • [На практике] Порядковые статистики. Порядковые статистики, нахождение за линейное в среднем время. Частичная сортировка.
---> вы находитесь здесь <---

Список вопросов к экзаменам аналогичного курса в прошлом году: Список вопросов Список вопросов

Литература

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

Практика

Задачи

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

Антон Гардер

Контакты:

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

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

Владислав Кораблинов

Контакты:

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

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