Алгоритмы и структуры данных 2018/2019

2018-11-25T17:10:12Z

Cache-nez:

'''Лектор:''' [https://www.hse.ru/org/persons/obiedkov С.А. Объедков]

=Второй модуль=
==Лекции==
понедельник 10:30 – 11:50, ауд. 622

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


# '''29 октября.''' Задача сортировки. [https://www.dropbox.com/s/zc30m8ihxlde05d/algo1-sorting.pdf?dl=0 Сортировка вставками:] анализ корректности с использованием инварианта цикла и времени работы. Асимптотические обозначения. Циклическая сортировка.
# '''31 октября.''' Стратегия "Разделяй и властвуй". [https://www.dropbox.com/s/5anaz9kwebqcrlw/algo2-mergesort.pdf?dl=0 Сортировка слиянием.] Доказательство корректности рекурсивных алгоритмов по индукции. Оценка времени работы рекурсивных алгоритмов при помощи рекуррентных соотношений: дерево рекурсии, итерационный метод, основная теорема.
# '''7 ноября.''' Решение рекуррентных соотношений методом подстановки. Линейный алгоритм поиска k-ой порядковой статистики.
# '''12 ноября.''' Нижние оценки для сортировки сравнениями. Сортировка подсчетом, блочная сортировка, поразрядная сортировка.
# '''14 ноября.''' Рандомизированные алгоритмы. Лас-Вегас и Монте-Карло. Краткое введение в теорию вероятностей: вероятностные пространства, события, случайные переменные, математическое ожидание и его линейность, геометрические случайные переменные. Алгоритмы Bogosort и Quicksort.
# '''19 ноября.''' Таблицы с прямой адресацией. Хеш-таблицы. Хеш-функции. Универсальные семейства хеш-функций. Открытая адресация.
# '''21 ноября.''' Двоичные деревья поиска. Семейства сбалансированных деревьев. Красно-черные деревья.

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Подгруппа !! Преподаватель !! Учебные ассистенты !! Консультация
|-
| 182-1 || [https://www.hse.ru/org/persons/210587824 София Техажева] || [mailto:alatysheva@edu.hse.ru Александра Латышева] || вт 10:30 – 11:50
|-
| 182-2 || [https://www.hse.ru/org/persons/207902879 Сергей Брагин] || [mailto:alatysheva@edu.hse.ru Александра Латышева] || вт 10:30 – 11:50
|-
| 184-1 || [https://www.hse.ru/staff/kharvd Валерий Харитонов] || [mailto:ispogodaev@edu.hse.ru Илья Погодаев] ||
|-
| 184-2 || [mailto:cache-nez+hse@yandex.ru Екатерина Гольцова] || [mailto:ispogodaev@edu.hse.ru Илья Погодаев] ||
|-
| 185-1 || [https://www.hse.ru/staff/samonenko Илья Самоненко], <br>([http://to-edu.ru сайт для семинаров], [http://to-edu.ru/ask <br> задать вопрос]) || [mailto:aarodionov_1@edu.hse.ru Антон Родионов] || вт 9:00 – 10:20, ауд. 306
|-
| [[АиСД_185-2|185-2]] || [http://www.hse.ru/staff/obiedkov Сергей Объедков] || [mailto:aarodionov_1@edu.hse.ru Антон Родионов] || вт 9:00 – 10:20, ауд. 306
|-
| 186-1 || [https://www.hse.ru/org/persons/210175892 Антон Филиппов] || [mailto:khasanovaaliya19@gmail.com Алия Хасанова] || пн 13:40 – 15:00
|-
| 186-2 || Святослав Фельдшеров || [mailto:khasanovaaliya19@gmail.com Алия Хасанова] || пн 13:40 – 15:00
|-
| 187-1 || [https://www.hse.ru/org/persons/225218888 Вильям Саакян] || [mailto:achulkov2@gmail.com Андрей Чулков] ||
|-
| 187-2 || [https://www.hse.ru/org/persons/133408680 Михаил Густокашин] || [mailto:achulkov2@gmail.com Андрей Чулков] ||
|-
| 188-1 || [https://www.hse.ru/org/persons/224067475 Владислав Вершинин] || [mailto:mailto:Amtursunkhodzhaev@edu.hse.ru Агзамходжа Турсунходжаев] ||
|-
| 188-2 || [https://www.hse.ru/staff/fstrok Федор Строк] || [mailto:mailto:Amtursunkhodzhaev@edu.hse.ru Агзамходжа Турсунходжаев] ||
|-
| 189-1 || [https://www.hse.ru/org/persons/224876053 Дмитрий Светличный] || [mailto:khasanovaaliya19@gmail.com Алия Хасанова] || пн 13:40 – 15:00
|-
| 189-2 || [https://www.hse.ru/org/persons/205298385 Ярослав Кищенко] || [mailto:achulkov2@gmail.com Андрей Чулков] ||
|-
|}

==Домашние задания==
# [https://official.contest.yandex.ru/contest/9692/problems/ Простые сортировки, бинарный поиск] — с 29 октября по 4 ноября (со штрафом 50% — с 5 по 11 ноября).
# [https://official.contest.yandex.ru/contest/9823/problems/ Рекурсия, сортировка слиянием] — с 5 по 13 ноября (со штрафом 50% — с 14 по 18 ноября).
# [https://www.dropbox.com/s/a3pnmisrnbe8j6m/algo-ex-1.pdf?dl=0 Задачи на асимптотику и рекуррентные соотношения] — с 7 по 20 ноября. UPDATE: Задание в пункте 4 несколько упрощено.
# [https://official.contest.yandex.ru/contest/10120/problems/ Сортировка подсчетом, поразрядная и др.] — с 12 по 18 ноября (со штрафом 50% — с 19 по 25 ноября).
# [https://official.contest.yandex.ru/contest/10511/problems/ Быстрая сортировка, порядковые статистики, хеши] — с 19 по 25 ноября (со штрафом 50% — с 26 ноября по 2 декабря).

=Литература=

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

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

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

Студенческие конспекты: [http://t-arxiv.appspot.com 2015 г.], [https://www.dropbox.com/s/3y6hmfv3t7fe14d/Mini-Kormen.pdf?dl=0 2016 г.], [https://www.dropbox.com/sh/5lxaheg89isd6h9/AACOa50ihgNiu46YqhguwmDBa/algo_16-17_1course_standart.pdf 2017 г.]

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

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

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

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

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

Wiki - Факультет компьютерных наук - Вклад [ru]

Алгоритмы и структуры данных 2018/2019