Алгоритмы и структуры данных 2018/2019 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Домашние задания)
(Лекции)
Строка 22: Строка 22:
 
# '''5 декабря''' Динамическое программирование: алгоритмы Беллмана – Форда и Флойда – Уоршелла.
 
# '''5 декабря''' Динамическое программирование: алгоритмы Беллмана – Форда и Флойда – Уоршелла.
 
# '''10 декабря.''' ''Контрольная работа'' по материалам осенних лекций (29 октября – 28 ноября). В частности, в контрольной работе могут быть даны задачи на рекуррентные соотношения, хеш-таблицы, рандомизированные алгоритмы, а также задачи, похожие на [https://www.dropbox.com/s/jp2p6ugv9jqnesw/sample-quiz.pdf?dl=0 задачи для подготовки]. С собой можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. Контрольная состоится 10 декабря в 10:30 – 11:50 в ауд. 402 (группы 182 и 184) и в ауд. 622 (группы 185, 186, 187, 188 и 189).
 
# '''10 декабря.''' ''Контрольная работа'' по материалам осенних лекций (29 октября – 28 ноября). В частности, в контрольной работе могут быть даны задачи на рекуррентные соотношения, хеш-таблицы, рандомизированные алгоритмы, а также задачи, похожие на [https://www.dropbox.com/s/jp2p6ugv9jqnesw/sample-quiz.pdf?dl=0 задачи для подготовки]. С собой можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. Контрольная состоится 10 декабря в 10:30 – 11:50 в ауд. 402 (группы 182 и 184) и в ауд. 622 (группы 185, 186, 187, 188 и 189).
 +
# '''12 декабря.''' Динамическое программирование: задача о рюкзаке, независимое множество максимального веса в дереве.
  
 
==Преподаватели и ассистенты==
 
==Преподаватели и ассистенты==

Версия 18:36, 14 декабря 2018

Лектор: С.А. Объедков

Второй модуль

Лекции

понедельник 10:30 – 11:50, ауд. 622

среда 15:10 – 16:30, ауд. 622

  1. 29 октября. Задача сортировки. Сортировка вставками: анализ корректности с использованием инварианта цикла и времени работы. Асимптотические обозначения. Циклическая сортировка.
  2. 31 октября. Стратегия "Разделяй и властвуй". Сортировка слиянием. Доказательство корректности рекурсивных алгоритмов по индукции. Оценка времени работы рекурсивных алгоритмов при помощи рекуррентных соотношений: дерево рекурсии, итерационный метод, основная теорема.
  3. 7 ноября. Решение рекуррентных соотношений методом подстановки. Линейный алгоритм поиска k-ой порядковой статистики.
  4. 12 ноября. Нижние оценки для сортировки сравнениями. Сортировка подсчетом, блочная сортировка, поразрядная сортировка.
  5. 14 ноября. Рандомизированные алгоритмы. Лас-Вегас и Монте-Карло. Краткое введение в теорию вероятностей: вероятностные пространства, события, случайные переменные, математическое ожидание и его линейность, геометрические случайные переменные. Алгоритмы Bogosort и Quicksort.
  6. 19 ноября. Таблицы с прямой адресацией. Хеш-таблицы. Хеш-функции. Универсальные семейства хеш-функций. Открытая адресация.
  7. 21 ноября. Двоичные деревья поиска. Семейства сбалансированных деревьев. Красно-черные деревья.
  8. 26 ноября. Вставка элемента в красно-черное дерево. Ориентированные и неориентированные графы. Представление графов в памяти компьютера: матрицы смежности и списки смежности. Поиск в ширину и в глубину.
  9. 28 ноября. Вычисление расстояний при помощи обхода в ширину. Вычисление компонент связности в неориентированном графе и компонент сильной связности в ориентированном графе. Топологическая сортировка.
  10. 3 декабря Кратчайшие пути во взвешенных графах. Алгоритм Дейкстры.
  11. 5 декабря Динамическое программирование: алгоритмы Беллмана – Форда и Флойда – Уоршелла.
  12. 10 декабря. Контрольная работа по материалам осенних лекций (29 октября – 28 ноября). В частности, в контрольной работе могут быть даны задачи на рекуррентные соотношения, хеш-таблицы, рандомизированные алгоритмы, а также задачи, похожие на задачи для подготовки. С собой можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. Контрольная состоится 10 декабря в 10:30 – 11:50 в ауд. 402 (группы 182 и 184) и в ауд. 622 (группы 185, 186, 187, 188 и 189).
  13. 12 декабря. Динамическое программирование: задача о рюкзаке, независимое множество максимального веса в дереве.

Преподаватели и ассистенты

Подгруппа Преподаватель Учебные ассистенты Консультация
182-1 София Техажева Александра Латышева вт 10:30 – 11:50
182-2 Сергей Брагин Александра Латышева вт 10:30 – 11:50
184-1 Валерий Харитонов Илья Погодаев
184-2 Екатерина Гольцова Илья Погодаев
185-1 Илья Самоненко,
(сайт для семинаров,
задать вопрос
)
Антон Родионов вт 9:00 – 10:20, ауд. 306
185-2 Сергей Объедков Антон Родионов вт 9:00 – 10:20, ауд. 306
186-1 Антон Филиппов Алия Хасанова пн 13:40 – 15:00
186-2 Святослав Фельдшеров Алия Хасанова пн 13:40 – 15:00
187-1 Вильям Саакян Андрей Чулков пн 15:10 – 16:30
187-2 Михаил Густокашин Андрей Чулков пн 15:10 – 16:30
188-1 Владислав Вершинин Агзамходжа Турсунходжаев
188-2 Федор Строк Агзамходжа Турсунходжаев
189-1 Дмитрий Светличный Алия Хасанова пн 13:40 – 15:00
189-2 Ярослав Кищенко Андрей Чулков пн 13:40 – 15:00

Домашние задания

  1. Простые сортировки, бинарный поиск — с 29 октября по 4 ноября (со штрафом 50% — с 5 по 11 ноября).
  2. Рекурсия, сортировка слиянием — с 5 по 13 ноября (со штрафом 50% — с 14 по 18 ноября).
  3. Задачи на асимптотику и рекуррентные соотношения — с 7 по 20 ноября. UPDATE: Задание в пункте 4 несколько упрощено.
  4. Сортировка подсчетом, поразрядная и др. — с 12 по 18 ноября (со штрафом 50% — с 19 по 25 ноября).
  5. Быстрая сортировка, порядковые статистики, хеши — с 19 по 25 ноября (со штрафом 50% — с 26 ноября по 2 декабря).
  6. Бинарные деревья поиска — с 26 ноября по 2 декабря (со штрафом 50% — с 3 по 9 декабря).
  7. Задачи на сортировку, хеш-функции, структуры данных — с 27 ноября по 9 декабря. Для получения зачета по задачам из листка нужно решить их все письменно и защитить устно. UPDATE: Исправлена опечатка в задаче 2.
  8. Обход в глубину и ширину — с 3 по 10 декабря (со штрафом 50% — с 11 по 16 декабря).
  9. Алгоритм Дейкстры — с 10 по 16 декабря.
  10. Задачи на динамическое программирование — с 11 по 18 декабря. Для получения зачета по задачам из листка нужно решить 'обе задачи письменно и защитить устно.

Литература

Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. — М.: МЦНМО, 2014.

Клейнберг Дж., Тардос Е. Алгоритмы: разработка и применение. — СПб.: Питер, 2016.

Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. — 3-е издание — М.: Вильямс, 2013.

Студенческие конспекты: 2015 г., 2016 г., 2017 г.

Оценки

Таблицы с оценками

Второй модуль

Текущая оценка: контрольная работа — 40%, домашние задания — 60%.

Промежуточная оценка: экзамен — 40%, текущая оценка — 60%.

Четвертый модуль

Накопленная оценка: контрольная работа — 50%, домашние задания — 50%.

Итог

Завершающая накопленная оценка: среднее промежуточной оценки за второй модуль и накопленной оценки за четвертый модуль.

Итоговая оценка: экзамен — 25%, завершающая накопленная оценка — 75%.