Алгоритмы и структуры данных на ПМИ (основной поток) — различия между версиями
.obj (обсуждение | вклад) (→Преподаватели и ассистенты) |
.obj (обсуждение | вклад) (→Преподаватели и ассистенты) |
||
Строка 75: | Строка 75: | ||
| 164-2 || [http://www.hse.ru/staff/iamakarov Илья Макаров] || [mailto:lera-bubnova@yandex.ru Валерия Бубнова] | | 164-2 || [http://www.hse.ru/staff/iamakarov Илья Макаров] || [mailto:lera-bubnova@yandex.ru Валерия Бубнова] | ||
|- | |- | ||
− | | 165-1 || [https://www.hse.ru/org/persons/137640594 Евгений Салагаев] || Юрий Баранов | + | | 165-1 || [https://www.hse.ru/org/persons/137640594 Евгений Салагаев] || [mailto:yuabaranov@edu.hse.ru Юрий Баранов] |
|- | |- | ||
− | | 165-2 || [https://www.hse.ru/org/persons/192085992 Иван Фефер] || Юрий Баранов | + | | 165-2 || [https://www.hse.ru/org/persons/192085992 Иван Фефер] || [mailto:yuabaranov@edu.hse.ru Юрий Баранов] |
|- | |- | ||
| 166-1 || Ярослав Кищенко || Дарья Вальтер | | 166-1 || Ярослав Кищенко || Дарья Вальтер |
Версия 19:03, 18 апреля 2017
Лектор: С. Объедков
Расписание лекций:
понедельник 10:30 – 11:50, ауд. 622
четверг 12:10 – 13:30, ауд. 622
Содержание
Рекомендуемая литература
- Дасгупта, Пападимитриу, Вазирани. Алгоритмы
- Клейнберг, Тардос. Алгоритмы. Разработка и применение
- Кормен, Лейзерсон, Ривест, Штайн. Алгоритмы: построение и анализ
- Также см. конспекты.
Лекции
Третий модуль
- 12 января. Постановка задачи поиска медианы. Простые решения этой задачи. Оценка сложности алгоритмов по времени и памяти. О-, o-, Ω-, ω-, Θ-обозначения. Время работы в худшем, лучшем и среднем случаях. Сортировка вставками.
- 19 января. Сортировка слиянием. Оценка времени работы алгоритма при помощи рекуррентного соотношения. Двоичный поиск. Примеры решения рекуррентных соотношений: решение с использованием дерева рекурсии и методом подстановки. Основная теорема.
- 26 января. Быстрая сортировка. Оптимальность сортировки слиянием.
- 2 февраля. Разделяй и властвуй: быстрое возведение в степень по модулю, выбор порядковой статистики за время O(n) — рандомизированный и детерминированный алгоритмы.
- 9 февраля. Структуры данных. Массив с операциями инициализации, чтения и записи, выполняемыми за время O(1). Структура данных для быстрого поиска и вставки на основе нескольких отсортированных массивов. Амортизационный анализ: групповой анализ и банковский метод (на примере двоичного счетчика).
- 16 февраля. Амортизационная стоимость операций в динамическом массиве. Реализация стека при помощи массива; нахождение максимального значения в стеке за константное время.
- 2 марта. Реализация очереди при помощи связного списка и при помощи массива; нахождение минимального элемента в очереди за константное время. Приоритетная очередь, ее реализация при помощи двоичной кучи. Сортировка кучей.
- 9 марта. Деревья поиска. Алгоритм построения двоичного дерева поиска. Сложность поиска в двоичном дереве поиска. Сортировка при помощи двоичного дерева поиска и ее связь с быстрой сортировкой. Сбалансированные деревья поиска. Определение красно-черного дерева.
- 16 марта. Красно-черные деревья. Удаление узла из двоичного дерева поиска.
- 23 марта. Деревья отрезков. Динамические порядковые статистики.
Четвертый модуль
- 3 апреля. Хеш-таблицы. Методы задания хеш-функций. Разрешение коллизий при помощи цепочек. Открытая адресация.
- 6 апреля. Сложность операций для открытой адресации в среднем случае. Универсальное хеширование. Двухуровневое идеальное хеширование.
- 10 апреля. Самоорганизующиеся списки и конкурентный анализ онлайн-алгоритмов.
- 13 апреля. Динамическое программирование: выравнивание абзаца по ширине. Свойства задач, эффективно решаемых при помощи динамического программирования: наличие полиномиального числа подзадач, выразимость исходной задачи в терминах подзадач, сводимость больших подзадач к полиномиальному числу меньших подзадач. Вычисление редакционного расстояния и выравнивание последовательностей.
- 17 апреля. Динамическое программирования на деревьях: нахождение независимого множества максимального веса в дереве. Задача о рюкзаке: жадный приближенный алгоритм; псевдополиномиальный алгоритм, основанный на динамическом программировании; приближенная схема полиномиального времени.
Домашние задания
Третий модуль
Сортировки — до 12 февраля. Для решения задачи F необязательно использовать именно алгоритм, реализованный в рамках решения задачи E.
Четвертый модуль
ДЗ 1-1: Деревья поиска — до 23:59:59 20 апреля. По техническим причинам посылки до вечера 10.04 более недоступны, большая просьба пересдать их. Дедлайн продлен до 20 апреля, приносим свои извинения.
ДЗ 1-2: Хеши и динамическое программирование — до 23:59:59 23 апреля.
Контрольные работы
Тренировочный вариант мартовской контрольной работы
В четвертом модуле контрольная работа пройдет в конце апреля.
Экзамен
В конце четвертого модуля пройдет письменный экзамен. На экзамене можно пользоваться бумажными материалами и нельзя — электронными.
Оценка
Накопленная оценка формируется на основе оценки за контрольную работу (20%), оценок за два домашних задания (по 30%) и оценки за аудиторную работу (20%). Накопленная оценка составляет 70% от итоговой оценки, остальное (30%) — экзамен. Все округления — на усмотрение преподавателя.
Страницы семинаров
Преподаватели и ассистенты
Подгруппа | Преподаватель | Учебные ассистенты |
---|---|---|
162-1 | Сергей Объедков | Петр Жижин |
162-2 | Филипп Синицын | Арсений Турышев |
164-1 | Федор Строк | Валерия Бубнова |
164-2 | Илья Макаров | Валерия Бубнова |
165-1 | Евгений Салагаев | Юрий Баранов |
165-2 | Иван Фефер | Юрий Баранов |
166-1 | Ярослав Кищенко | Дарья Вальтер |
166-2 | Михаил Густокашин | Дарья Вальтер |
167-1 | Алексей Умнов | Максим Рябинин |
167-2 | Михаил Чичварин | Максим Рябинин |
168-1 | Михаил Дектярев | Олег Найдин |
168-2 | Ольга Абакумова | Олег Найдин |