Алгоритмы 5ML осень 2020 — различия между версиями

Материал из CSC Wiki
Перейти к:навигация, поиск
((7) 30 октября. Кратчайшие пути в графах.)
((7) 30 октября. Кратчайшие пути в графах.)
Строка 99: Строка 99:
 
* Поиск в ширину (BFS), доказательство корректности. <!--Лучевой поиск (beam search).-->
 
* Поиск в ширину (BFS), доказательство корректности. <!--Лучевой поиск (beam search).-->
 
* Алгоритм Дейкстры, доказательство корректности. Реализации для плотных и разреженных графов.
 
* Алгоритм Дейкстры, доказательство корректности. Реализации для плотных и разреженных графов.
* Алгоритм Флойда. Оптимизация памяти до квадратичной, доказательство корректности. Проверка на наличие отрицательного цикла.
+
* Алгоритм Флойда — Уоршелла. Оптимизация памяти до квадратичной, доказательство корректности. Проверка на наличие отрицательного цикла.
* Алгоритм Форда-Беллмана, оптимизация памяти до линейной. Проверка на наличие отрицательного цикла, его нахождение.
+
* Алгоритм Форда Беллмана, оптимизация памяти до линейной. Проверка на наличие отрицательного цикла, его нахождение.
  
 
=== Литература ===
 
=== Литература ===

Версия 08:27, 28 октября 2020

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

Оценка курса выставляется по 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 сентября. Быстрая сортировка, порядковые статистики.
  • Изменение элемента в куче. Построение кучи за линейное время. Частичная сортировка кучей.
  • Быстрая сортировка: понятие вероятностного алгоритма, время работы в среднем.
  • Анализ среднего времени работы.
  • Массивы с малым количеством различных элементов, QuickSort3.
  • [На практике] Порядковые статистики. Нахождение за линейное в среднем время и детерминированно.
(4) 28 сентября. Быстрая сортировка — 2. Динамическое программирование — 1.
  • Быстрая сортировка. Корректность inplace-версии. Частичная сортировка.
  • Средняя глубины рекурсии (без доказательства).
  • Элиминация хвостовой рекурсии. IntroSort.

Динамическое программирование:

  • Общие принципы динамического программирования. Кратчайшие пути в ациклических ориентированных графах.
  • Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач; нахождение не только длины, но и самой подпоследовательности.

На практике:

  • Быстрое возведение матрицы в степень для динамического программирования.
  • Паросочетание максимального веса на деревьях.
(5) 5 октября. Динамическое программирование — 2. Жадные алгоритмы.

Динамическое-программирование — 2:

  • Дискретная задача о рюкзаке с повторениями.
  • Дискретная задача о рюкзаке без повторений.
  • Редакционное расстояние.
  • Задача коммивояжёра.

Жадные алгоритмы:

  • Покрытие точек единичными отрезками.
  • Задача о выборе заявок.
  • Непрерывная задаче о рюкзаке.
(6) 12 октября. Код Хаффмана. Алгоритмы на графах — 1.

Жадные алгоритмы:

  • Непрерывная задаче о рюкзаке — доказательство
  • Код Хаффмана.

Графы:

  • Определения, способы хранения (матрица смежности и списки смежности).
  • Поиск в глубину (DFS), доказательство корректности. Компоненты связности.
  • DFS: поиск цикла, три цвета вершин.
  • Топологическая сортировка, два подхода: с очередью, с помощью DFS (на практике).

25 октября. Экзамен.

Список вопросов

---> вы находитесь здесь <---
(7) 30 октября. Кратчайшие пути в графах.
  • Поиск в ширину (BFS), доказательство корректности.
  • Алгоритм Дейкстры, доказательство корректности. Реализации для плотных и разреженных графов.
  • Алгоритм Флойда — Уоршелла. Оптимизация памяти до квадратичной, доказательство корректности. Проверка на наличие отрицательного цикла.
  • Алгоритм Форда — Беллмана, оптимизация памяти до линейной. Проверка на наличие отрицательного цикла, его нахождение.

Литература

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

Практика

Задачи

Условия задач | Разборы | Разборы контестов

Технические советы для написании кода

TeX-шаблон для домашек

Сергей Копелиович

Контакты:

  • Почта для домашек: burunduk30@gmail.com, в теме письма должна быть подстрока SPb HSE HW

Правила сдачи:

  • Решения нужно присылать в виде pdf-ки на почту для домашек, указанную выше. Под ссылкой на условия лежит ссылка на удобный и простой шаблон, рекомендую им пользоваться, если у вас нет собственных разработок.

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

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

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

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

Контакты:

  • vladislav.korablinov+hse_20_algo@gmail.com
  • Telegram: ladine0n

Правила сдачи:

  • Решения нужно присылать в виде pdf-ки на почту, указанную выше. Под ссылкой на условия лежит ссылка на удобный и простой шаблон, рекомендую им пользоваться, если у вас нет собственных разработок.

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

  • мягкий дедлайн в пятницу в 22:00, задачи, присланные до него, гарантированно проверяются как минимум 1 раз до жесткого дедлайна
  • жёсткий дедлайн в воскресенье в 23:59, после него до начала занятия можно присылать только исправления по задачам, по которым было написано что-то разумное (в ваших интересах прислать пораньше, чтобы я успел посмотреть и было понятно, что исправлять)

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