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

ППО Социология 1 курс 2019/2020

2020-03-06T12:24:12Z

Biryuk:

== О курсе ==
"Прикладное программное обеспечение" читается на 1 курсе, в 3 модуле.

[https://www.hse.ru/ba/soc/courses/292663779.html Карточка курса и программа]

Чат в Telegram (для всего потока): https://t.me/joinchat/BVSknBUMVI2R1KUlL7Udlg

==Преподаватели==
'''Группы 191, 192''' 
Преподаватель: Рогович Татьяна Владимировна 
E-mail: rogovich@gmail.com 
Ассистент: Егор Файн 
Telegram: @feinegor 
Чат в Telegram: для всего потока (см. выше).
Канал в телеграм с объявлениями: https://t.me/joinchat/AAAAAEVEzfWsdko1_Mc10w

'''Группы 193, 194''' 
Преподаватель: Рогович Татьяна Владимировна 
E-mail: rogovich@gmail.com 
Ассистент: Инсан-Александр Латыпов 
Telegram: @Le_Figaro

Чат в Telegram: для всего потока (см. выше).
Канал в телеграм с объявлениями: https://t.me/joinchat/AAAAAEVEzfWsdko1_Mc10w

'''Группы 195, 196''' 
Преподаватель: Валентина Лебедева 
E-mail: valentine96leb@gmail.com 
VK, Telegram: lalentine96 
Ассистент: Василиса Дёмина 
Почта: vasilyoook@mail.ru 
VK: https://vk.com/id30526342 
Чат в Telegram: https://t.me/joinchat/BVSknBUMVI2R1KUlL7Udlg

'''Группы 197, 198''' 
Преподаватель: Валентин Бирюков 
E-mail: valentin.biryukov@gmail.com 
Telegram: biryuk_v 
VK: https://vk.com/valentin.biryukov 
Ассистент: Дмитрий Кузнецов 
Telegram: eldmitro 
Чат в Telegram: https://t.me/joinchat/BVSknBUMVI2R1KUlL7Udlg

==Как установить Jupyter на свой ноутбук?==
Для этого нужно пройти по ссылке https://www.anaconda.com/distribution/ и выбрать дистрибутив пакета Anaconda для '''Python 3.7''', в который входит Jupyter, для вашей операционной системы. Скачайте дистрибутив и запустите, дальше следуйте промтам установщика. Мы будем работать с Jupyter Notebook (не Jupyter Lab).

== Формула оценки ==
Оценка =
0.25 * Домашние задания (Power Point) + 0.35 * Контрольная работа (Word, Excel) + '''0.1 * Оценка за прохождение онлайн-курса (Python)''' + '''0.2 * Самостоятельные работы на семинарах (Python)''' + 0.1 * Финальная презентация (Power Point)

Самостоятельные работы оцениваются по 10-балльной шкале и в формулу оценки идет их среднее арифметическое.

== Онлайн курс (дедлайны) ==
В понедельник 20 января вам должна была прийти ссылка на новую сессию онлайн курса на платформе openedu.ru.
В сессии установлено три дедлайна. Задания из соответствующих тем принимаются только до своего дедлайн. Проходить курс вперед можно.
{| class="wikitable"
|-
! Тема !! Дедлайн
|-
| Ввод, вывод, целочисленная арифметика || ДО 11 ФЕВР. 2020 Г. 23:59 MSK
|-
| Условный оператор и цикл while || ДО 11 ФЕВР. 2020 Г. 23:59 MSK
|-
| Вещественные числа и строки || ДО 11 ФЕВР. 2020 Г. 23:59 MSK
|-
| Цикл for, списки и функции || ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| Сортировки, множества, словари || ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| Текстовые файлы и таблицы|| ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| Обработка web-страниц || ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| XML и обработка геоданных || ДО 29 МАР. 2020 Г. 23:59 MSK
|-
| JSON и визуализация геоданных || ДО 29 МАР. 2020 Г. 23:59 MSK
|-
| Диаграммы || ДО 29 МАР. 2020 Г. 23:59 MSK
|}

== Онлайн курс (перевод процента выполнения в оценку) ==
{| class="wikitable"
|-
! Процент выполнения онлайн-курса !! Оценка
|-
| 76% + || 10
|-
| 68 – 75% || 9
|-
| 60 – 67% || 8
|-
| 52 – 59% || 7
|-
| 44 – 51% || 6
|-
| 36 – 43% || 5
|-
| 28 – 35% || 4
|-
| 20 – 27% || 3
|-
| 12 – 19% || 2
|-
| 4 – 11% || 1
|-
| < 4% || 0
|}

== Самостоятельные ==
{| class="wikitable"
|-
! Группа !! СР1 !! СР2 !! СР3
|-
| 191 (Рогович) || 7 февраля 12.10 || 28 февраля 12.10 || 13 марта 12.10
|-
| 192 (Рогович) || 7 февраля 13.40 || 28 февраля 13.40 || 13 марта 13.40
|-
| 193 (Рогович) || 6 февраля 12.10 || 27 февраля 12.10 || 12 марта 12.10
|-
| 194 (Рогович) || 6 февраля 13.40|| 27 февраля 13.40 || 12 марта 13.40
|-
| 195 (Лебедева) || 5 февраля 9.00 || 4 марта 9.00 || 18 марта 9.00
|-
| 196 (Лебедева) || 5 февраля 10.30 || 4 марта 10.30 || 18 марта 10.30
|-
| 197 (Бирюков) || 3 февраля 9.00 || 28 февраля 9.00 || 23 марта 9.00
|-
| 198 (Бирюков) || 3 февраля 10.30 || 28 февраля 10.30 || 23 марта 10.30
|}

== Материалы ==
[https://docs.google.com/presentation/d/1DutZmawzXyTFJUrjScoLHbaUs8XeDoV2gAqVrCUwDGY Семинар 1 Презентация]

Материалы семинаров лежат в репозитории Github:

[https://github.com/rogovich/2020_HSE_SOC_PPO Ссылка на весь репозиторий]

[https://nbviewer.jupyter.org/github/rogovich/2020_HSE_SOC_PPO/blob/master/1%20Seminar/2020_SOC_PPO_1_Seminar.ipynb Семинар 1 на nbviewer. Ввод и вывод (input(), print()). Целые числа и арифметические операции. Строки.]

[https://nbviewer.jupyter.org/github/rogovich/2020_HSE_SOC_PPO/blob/master/2%20Seminar/2020_SOC_PPO_2_Seminar.ipynb Семинар 2 на nbviewer. Логические переменные. Условный оператор if (if else, elif). Цикл while (критерии остановки break, continue]

[https://nbviewer.jupyter.org/github/rogovich/2020_HSE_SOC_PPO/blob/master/3%20Seminar/2020_SOC_PPO_3_Seminar.ipynb Семинар 3 на nbviewer. Вещественные числа, строки: срезы, методы строк.]

[https://nbviewer.jupyter.org/github/rogovich/2020_HSE_SOC_PPO/blob/master/4%20Seminar/2020_SOC_PPO_4_Seminar.ipynb Семинар 4 на nbviewer. Списки и кортежи, цикл for, функции.]

[https://nbviewer.jupyter.org/github/rogovich/2020_HSE_SOC_PPO/blob/master/5%20Seminar/2020_SOC_PPO_5_Seminar.ipynb Семинар 5 на nbviewer. Сортировки, словари, множества.]

[https://github.com/VaDyomina/2020_HSE_SOC_PPO/blob/master/6_Seminar/2020_SOC_PPO_6_Intro_html.ipynb Семинар 6 Введение в html]

[https://github.com/rogovich/2020_HSE_SOC_PPO/blob/master/6_Seminar/2020_SOC_PPO_3Test_Explanation.ipynb Семинар 6 Скрэйпинг и парсинг таблиц (он же пробный вариант контрольной 3)]

[https://github.com/rogovich/2020_HSE_SOC_PPO/blob/master/6_Seminar/2020_SOC_PPO_6_Bonus_Web_Scraping.ipynb Дополнительный материал: скрэйпинг новостного сайта]

== Файлики для задачек ==
http://www.py4inf.com/code/romeo-full.txt
http://www.py4inf.com/code/mbox.txt

== Ссылки для семинара 6 ==
https://www.w3schools.com/
https://en.wikipedia.org/wiki/List_of_nuclear_weapons_tests

== Самостоятельные работы ==
[https://nbviewer.jupyter.org/github/rogovich/2020_HSE_SOC_PPO/blob/master/1_Test/2020_HSE_SOC_PPO_Test1_Mock.ipynb Пробный вариант СР1] [https://github.com/rogovich/2020_HSE_SOC_PPO/blob/master/1_Test/2020_HSE_SOC_PPO_Test1_Mock_Solution.ipynb Решение пробного варианта]

[https://github.com/rogovich/2020_HSE_SOC_PPO/blob/master/2_Test/2020_HSE_Test2_Mock.ipynb Пробный вариант КР2]
===Как работать с Github?===
Для скачивания файлов с Github необязательно иметь аккаунт, достаточно кликнуть на зеленую кнопку Clone or download в правом верхнем углу, выбрать Download ZIP и распаковать архив. В папке 2020_HSE_SOC_PPO будут все файлы, загруженные на Github на момент скачивания.

Если нужно скачать ipynb-файл с конкретной лекцией, можно пройти по ссылке на эту лекцию на NBviewer (ссылки указаны в перечне материалов в файле README в каждой папке) и в правом верхнем углу кликнуть на значок-стрелочку для скачивания.

Если файл .ipynb сохраняется как текст или с лишним расширением (например, .txt), то нужно выбрать при сохранении тип файла все файлы, а не текст, или после сохранения убрать вручную расширение, переименовав файл.

Основы программирования в Python (Мирэк)

2020-02-03T10:54:59Z

Biryuk: /* Преподаватели */

== О курсе ==
"Основы программирования в Python" читается на 2 курсе, в 3 и 4 модуле.
3 модуль - самостоятельное прохождение студентами онлайн-курса.
4 модуль - лекционные и семинарские занятия.

[https://www.hse.ru/ba/we/courses/292691621.html Карточка курса и программа]

Чат в Telegram (для всего потока): https://t.me/hse_mirec_python_2020 или hse_mirec_python_2020 в поиске.

== Преподаватели ==
Лектор: Рогович Татьяна Владимировна 
E-mail: rogovich@gmail.com 

'''Группы 181, 182'''

Семинарист: Рогович Татьяна Владимировна 
E-mail: rogovich@gmail.com 

Ассистент: Инсан-Александр Латыпов
E-mail: insanaleksandr@yandex.ru 
Telegram: @Le_Figaro 

'''Группы 183, 184'''

Семинарист: Карпов Максим Евгеньевич 
E-mail: mekarpov@hse.ru 

Ассистент: Сергей Петрович
E-mail: serg.petrovich2000@gmail.com 
Telegram: @serp404 

'''Группа 185'''

Семинарист: Рогович Татьяна Владимировна 
E-mail: rogovich@gmail.com 

Ассистент: Михаил Филатов
E-mail: mihfil1998@yandex.ru 
Telegram: @mihfil 

'''Группа 186'''
Семинарист: Бирюков Валентин Андреевич 
E-mail: valentin.biryukov@gmail.com 
Telegram: @biryuk_v 

Ассистент: Дмитрий Кузнецов
Telegram: @eldmitro 

==Как установить Jupyter на свой ноутбук?==
Для этого нужно пройти по ссылке https://www.anaconda.com/distribution/ и выбрать дистрибутив пакета Anaconda для '''Python 3.7''', в который входит Jupyter, для вашей операционной системы. Скачайте дистрибутив и запустите, дальше следуйте промтам установщика. Мы будем работать с Jupyter Notebook (не Jupyter Lab).

== Формула оценки ==
'''!!! Обратите внимание, формула может незначительно измениться !!! (официальное объявление формулы - 1 лекция)''' 
Оценка =
0.2 * Домашнее задание + 0.2 * Мини-самостоятельные + '''0.2 * Онлайн-курс'''* + 0.2 * Проект + 0.2 * Самостоятельная работа + Доп. Баллы

*онлайн-курс выполняется на платформе openedu в течение 3 модуля.

== Онлайн курс (дедлайны) ==
В понедельник 20 января вам должна была прийти ссылка на новую сессию онлайн курса на платформе openedu.ru.
В сессии установлено три дедлайна. Задания из соответствующих тем принимаются только до своего дедлайн. Проходить курс вперед можно.
{| class="wikitable"
|-
! Тема !! Дедлайн
|-
| Ввод, вывод, целочисленная арифметика || ДО 11 ФЕВР. 2020 Г. 23:59 MSK
|-
| Условный оператор и цикл while || ДО 11 ФЕВР. 2020 Г. 23:59 MSK
|-
| Вещественные числа и строки || ДО 11 ФЕВР. 2020 Г. 23:59 MSK
|-
| Цикл for, списки и функции || ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| Сортировки, множества, словари || ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| Текстовые файлы и таблицы|| ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| Обработка web-страниц || ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| XML и обработка геоданных || ДО 31 МАР. 2020 Г. 23:59 MSK
|-
| JSON и визуализация геоданных || ДО 31 МАР. 2020 Г. 23:59 MSK
|-
| Диаграммы || ДО 31 МАР. 2020 Г. 23:59 MSK
|}

== Онлайн курс (перевод процента выполнения в оценку) ==
{| class="wikitable"
|-
! Процент выполнения онлайн-курса !! Оценка
|-
| 76% + || 10
|-
| 68 – 75% || 9
|-
| 60 – 67% || 8
|-
| 52 – 59% || 7
|-
| 44 – 51% || 6
|-
| 36 – 43% || 5
|-
| 28 – 35% || 4
|-
| 20 – 27% || 3
|-
| 12 – 19% || 2
|-
| 4 – 11% || 1
|-
| < 4% || 0
|}

ППО Социология 1 курс 2019/2020

2020-02-01T16:17:42Z

Biryuk: /* Преподаватели */

== О курсе ==
"Прикладное программное обеспечение" читается на 1 курсе, в 3 модуле.

[https://www.hse.ru/ba/soc/courses/292663779.html Карточка курса и программа]

Чат в Telegram (для всего потока): https://t.me/joinchat/BVSknBUMVI2R1KUlL7Udlg

==Преподаватели==
'''Группы 191, 192''' 
Преподаватель: Рогович Татьяна Владимировна 
E-mail: rogovich@gmail.com 
Ассистент: Егор Файн 
Telegram: @feinegor 
Чат в Telegram: для всего потока (см. выше).
Канал в телеграм с объявлениями: https://t.me/joinchat/AAAAAEVEzfWsdko1_Mc10w

'''Группы 193, 194''' 
Преподаватель: Рогович Татьяна Владимировна 
E-mail: rogovich@gmail.com 
Ассистент: Инсан-Александр Латыпов 
Telegram: @Le_Figaro

Чат в Telegram: для всего потока (см. выше).
Канал в телеграм с объявлениями: https://t.me/joinchat/AAAAAEVEzfWsdko1_Mc10w

'''Группы 195, 196''' 
Преподаватель: Валентина Лебедева 
E-mail: valentine96leb@gmail.com 
VK, Telegram: lalentine96 
Ассистент: Василиса Дёмина 
Почта: vasilyoook@mail.ru 
VK: https://vk.com/id30526342 
Чат в Telegram: https://t.me/joinchat/BVSknBUMVI2R1KUlL7Udlg

'''Группы 197, 198''' 
Преподаватель: Валентин Бирюков 
E-mail: valentin.biryukov@gmail.com 
Telegram: biryuk_v 
VK: https://vk.com/valentin.biryukov 
Ассистент: Дмитрий Кузнецов 
Telegram: eldmitro 
Чат в Telegram: https://t.me/joinchat/BVSknBUMVI2R1KUlL7Udlg

==Как установить Jupyter на свой ноутбук?==
Для этого нужно пройти по ссылке https://www.anaconda.com/distribution/ и выбрать дистрибутив пакета Anaconda для '''Python 3.7''', в который входит Jupyter, для вашей операционной системы. Скачайте дистрибутив и запустите, дальше следуйте промтам установщика. Мы будем работать с Jupyter Notebook (не Jupyter Lab).

== Формула оценки ==
Оценка =
0.25 * Домашние задания (Power Point) + 0.35 * Контрольная работа (Word, Excel) + '''0.1 * Оценка за прохождение онлайн-курса (Python)''' + '''0.2 * Самостоятельные работы на семинарах (Python)''' + 0.1 * Финальная презентация (Power Point)

Самостоятельные работы оцениваются по 10-балльной шкале и в формулу оценки идет их среднее арифметическое.

== Онлайн курс (дедлайны) ==
В понедельник 20 января вам должна была прийти ссылка на новую сессию онлайн курса на платформе openedu.ru.
В сессии установлено три дедлайна. Задания из соответствующих тем принимаются только до своего дедлайн. Проходить курс вперед можно.
{| class="wikitable"
|-
! Тема !! Дедлайн
|-
| Ввод, вывод, целочисленная арифметика || ДО 11 ФЕВР. 2020 Г. 23:59 MSK
|-
| Условный оператор и цикл while || ДО 11 ФЕВР. 2020 Г. 23:59 MSK
|-
| Вещественные числа и строки || ДО 11 ФЕВР. 2020 Г. 23:59 MSK
|-
| Цикл for, списки и функции || ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| Сортировки, множества, словари || ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| Текстовые файлы и таблицы|| ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| Обработка web-страниц || ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| XML и обработка геоданных || ДО 29 МАР. 2020 Г. 23:59 MSK
|-
| JSON и визуализация геоданных || ДО 29 МАР. 2020 Г. 23:59 MSK
|-
| Диаграммы || ДО 29 МАР. 2020 Г. 23:59 MSK
|}

== Онлайн курс (перевод процента выполнения в оценку) ==
{| class="wikitable"
|-
! Процент выполнения онлайн-курса !! Оценка
|-
| 76% + || 10
|-
| 68 – 75% || 9
|-
| 60 – 67% || 8
|-
| 52 – 59% || 7
|-
| 44 – 51% || 6
|-
| 36 – 43% || 5
|-
| 28 – 35% || 4
|-
| 20 – 27% || 3
|-
| 12 – 19% || 2
|-
| 4 – 11% || 1
|-
| < 4% || 0
|}

== Самостоятельные ==
{| class="wikitable"
|-
! Группа !! СР1 !! СР2 !! СР3 !! Оценки
|-
| 191 (Рогович) || 7 февраля 12.10 || TBA || TBA || [Здесь будет ссылка]
|-
| 192 (Рогович) || 7 февраля 13.40 || TBA || TBA || [Здесь будет ссылка]
|-
| 193 (Рогович) || 6 февраля 12.10 || TBA || TBA || [Здесь будет ссылка]
|-
| 194 (Рогович) || 6 февраля 13.40|| TBA || TBA || [Здесь будет ссылка]
|-
| 195 (Лебедева) || 5 февраля 9.00 || TBA || TBA || [Здесь будет ссылка]
|-
| 196 (Лебедева) || 5 февраля 10.30 || TBA || TBA || [Здесь будет ссылка]
|-
| 197 (Бирюков) || 3 февраля 9.00 || TBA || TBA || [Здесь будет ссылка]
|-
| 198 (Бирюков) || 3 февраля 10.30 || TBA || TBA || [Здесь будет ссылка]
|}

== Материалы ==
[https://docs.google.com/presentation/d/1DutZmawzXyTFJUrjScoLHbaUs8XeDoV2gAqVrCUwDGY Семинар 1 Презентация]

Материалы семинаров лежат в репозитории Github:

[https://github.com/rogovich/2020_HSE_SOC_PPO Ссылка на весь репозиторий]

[https://nbviewer.jupyter.org/github/rogovich/2020_HSE_SOC_PPO/blob/master/1%20Seminar/2020_SOC_PPO_1_Seminar.ipynb Семинар 1 на nbviewer. Ввод и вывод (input(), print()). Целые числа и арифметические операции. Строки.]

[https://nbviewer.jupyter.org/github/rogovich/2020_HSE_SOC_PPO/blob/master/2%20Seminar/2020_SOC_PPO_2_Seminar.ipynb Семинар 2 на nbviewer. Логические переменные. Условный оператор if (if else, elif). Цикл while (критерии остановки break, continue]

[https://nbviewer.jupyter.org/github/rogovich/2020_HSE_SOC_PPO/blob/master/3%20Seminar/2020_SOC_PPO_3_Seminar.ipynb Семинар 3 на nbviewer. Вещественные числа, строки: срезы, методы строк.]

== Самостоятельные работы ==
[https://nbviewer.jupyter.org/github/rogovich/2020_HSE_SOC_PPO/blob/master/1_Test/2020_HSE_SOC_PPO_Test1_Mock.ipynb Пробный вариант СР1]

===Как работать с Github?===
Для скачивания файлов с Github необязательно иметь аккаунт, достаточно кликнуть на зеленую кнопку Clone or download в правом верхнем углу, выбрать Download ZIP и распаковать архив. В папке 2020_HSE_SOC_PPO будут все файлы, загруженные на Github на момент скачивания.

Если нужно скачать ipynb-файл с конкретной лекцией, можно пройти по ссылке на эту лекцию на NBviewer (ссылки указаны в перечне материалов в файле README в каждой папке) и в правом верхнем углу кликнуть на значок-стрелочку для скачивания.

Если файл .ipynb сохраняется как текст или с лишним расширением (например, .txt), то нужно выбрать при сохранении тип файла все файлы, а не текст, или после сохранения убрать вручную расширение, переименовав файл.

ППО Социология 1 курс 2019/2020

2020-02-01T16:15:27Z

Biryuk: /* Преподаватели */

== О курсе ==
"Прикладное программное обеспечение" читается на 1 курсе, в 3 модуле.

[https://www.hse.ru/ba/soc/courses/292663779.html Карточка курса и программа]

Чат в Telegram (для всего потока): https://t.me/joinchat/BVSknBUMVI2R1KUlL7Udlg

==Преподаватели==
'''Группы 191, 192''' 
Преподаватель: Рогович Татьяна Владимировна 
E-mail: rogovich@gmail.com 
Ассистент: Егор Файн 
Telegram: @feinegor 
Чат в Telegram: для всего потока (см. выше).
Канал в телеграм с объявлениями: https://t.me/joinchat/AAAAAEVEzfWsdko1_Mc10w

'''Группы 193, 194''' 
Преподаватель: Рогович Татьяна Владимировна 
E-mail: rogovich@gmail.com 
Ассистент: Инсан-Александр Латыпов 
Telegram: @Le_Figaro

Чат в Telegram: для всего потока (см. выше).
Канал в телеграм с объявлениями: https://t.me/joinchat/AAAAAEVEzfWsdko1_Mc10w

'''Группы 195, 196''' 
Преподаватель: Валентина Лебедева 
E-mail: valentine96leb@gmail.com 
VK, Telegram: lalentine96 
Ассистент: Василиса Дёмина 
Почта: vasilyoook@mail.ru 
VK: https://vk.com/id30526342 
Чат в Telegram: https://t.me/joinchat/BVSknBUMVI2R1KUlL7Udlg

'''Группы 197, 198''' 
Преподаватель: Валентин Бирюков 
E-mail: valentin.biryukov@gmail.com 
VK, Telegram: biryuk_v 
Ассистент: Дмитрий Кузнецов 
Telegram: eldmitro
VK: https://vk.com/valentin.biryukov 
Чат в Telegram: https://t.me/joinchat/BVSknBUMVI2R1KUlL7Udlg

==Как установить Jupyter на свой ноутбук?==
Для этого нужно пройти по ссылке https://www.anaconda.com/distribution/ и выбрать дистрибутив пакета Anaconda для '''Python 3.7''', в который входит Jupyter, для вашей операционной системы. Скачайте дистрибутив и запустите, дальше следуйте промтам установщика. Мы будем работать с Jupyter Notebook (не Jupyter Lab).

== Формула оценки ==
Оценка =
0.25 * Домашние задания (Power Point) + 0.35 * Контрольная работа (Word, Excel) + '''0.1 * Оценка за прохождение онлайн-курса (Python)''' + '''0.2 * Самостоятельные работы на семинарах (Python)''' + 0.1 * Финальная презентация (Power Point)

Самостоятельные работы оцениваются по 10-балльной шкале и в формулу оценки идет их среднее арифметическое.

== Онлайн курс (дедлайны) ==
В понедельник 20 января вам должна была прийти ссылка на новую сессию онлайн курса на платформе openedu.ru.
В сессии установлено три дедлайна. Задания из соответствующих тем принимаются только до своего дедлайн. Проходить курс вперед можно.
{| class="wikitable"
|-
! Тема !! Дедлайн
|-
| Ввод, вывод, целочисленная арифметика || ДО 11 ФЕВР. 2020 Г. 23:59 MSK
|-
| Условный оператор и цикл while || ДО 11 ФЕВР. 2020 Г. 23:59 MSK
|-
| Вещественные числа и строки || ДО 11 ФЕВР. 2020 Г. 23:59 MSK
|-
| Цикл for, списки и функции || ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| Сортировки, множества, словари || ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| Текстовые файлы и таблицы|| ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| Обработка web-страниц || ДО 10 МАР. 2020 Г. 23:59 MSK
|-
| XML и обработка геоданных || ДО 29 МАР. 2020 Г. 23:59 MSK
|-
| JSON и визуализация геоданных || ДО 29 МАР. 2020 Г. 23:59 MSK
|-
| Диаграммы || ДО 29 МАР. 2020 Г. 23:59 MSK
|}

== Онлайн курс (перевод процента выполнения в оценку) ==
{| class="wikitable"
|-
! Процент выполнения онлайн-курса !! Оценка
|-
| 76% + || 10
|-
| 68 – 75% || 9
|-
| 60 – 67% || 8
|-
| 52 – 59% || 7
|-
| 44 – 51% || 6
|-
| 36 – 43% || 5
|-
| 28 – 35% || 4
|-
| 20 – 27% || 3
|-
| 12 – 19% || 2
|-
| 4 – 11% || 1
|-
| < 4% || 0
|}

== Самостоятельные ==
{| class="wikitable"
|-
! Группа !! СР1 !! СР2 !! СР3 !! Оценки
|-
| 191 (Рогович) || 7 февраля 12.10 || TBA || TBA || [Здесь будет ссылка]
|-
| 192 (Рогович) || 7 февраля 13.40 || TBA || TBA || [Здесь будет ссылка]
|-
| 193 (Рогович) || 6 февраля 12.10 || TBA || TBA || [Здесь будет ссылка]
|-
| 194 (Рогович) || 6 февраля 13.40|| TBA || TBA || [Здесь будет ссылка]
|-
| 195 (Лебедева) || 5 февраля 9.00 || TBA || TBA || [Здесь будет ссылка]
|-
| 196 (Лебедева) || 5 февраля 10.30 || TBA || TBA || [Здесь будет ссылка]
|-
| 197 (Бирюков) || 3 февраля 9.00 || TBA || TBA || [Здесь будет ссылка]
|-
| 198 (Бирюков) || 3 февраля 10.30 || TBA || TBA || [Здесь будет ссылка]
|}

== Материалы ==
[https://docs.google.com/presentation/d/1DutZmawzXyTFJUrjScoLHbaUs8XeDoV2gAqVrCUwDGY Семинар 1 Презентация]

Материалы семинаров лежат в репозитории Github:

[https://github.com/rogovich/2020_HSE_SOC_PPO Ссылка на весь репозиторий]

[https://nbviewer.jupyter.org/github/rogovich/2020_HSE_SOC_PPO/blob/master/1%20Seminar/2020_SOC_PPO_1_Seminar.ipynb Семинар 1 на nbviewer. Ввод и вывод (input(), print()). Целые числа и арифметические операции. Строки.]

[https://nbviewer.jupyter.org/github/rogovich/2020_HSE_SOC_PPO/blob/master/2%20Seminar/2020_SOC_PPO_2_Seminar.ipynb Семинар 2 на nbviewer. Логические переменные. Условный оператор if (if else, elif). Цикл while (критерии остановки break, continue]

[https://nbviewer.jupyter.org/github/rogovich/2020_HSE_SOC_PPO/blob/master/3%20Seminar/2020_SOC_PPO_3_Seminar.ipynb Семинар 3 на nbviewer. Вещественные числа, строки: срезы, методы строк.]

== Самостоятельные работы ==
[https://nbviewer.jupyter.org/github/rogovich/2020_HSE_SOC_PPO/blob/master/1_Test/2020_HSE_SOC_PPO_Test1_Mock.ipynb Пробный вариант СР1]

===Как работать с Github?===
Для скачивания файлов с Github необязательно иметь аккаунт, достаточно кликнуть на зеленую кнопку Clone or download в правом верхнем углу, выбрать Download ZIP и распаковать архив. В папке 2020_HSE_SOC_PPO будут все файлы, загруженные на Github на момент скачивания.

Если нужно скачать ipynb-файл с конкретной лекцией, можно пройти по ссылке на эту лекцию на NBviewer (ссылки указаны в перечне материалов в файле README в каждой папке) и в правом верхнем углу кликнуть на значок-стрелочку для скачивания.

Если файл .ipynb сохраняется как текст или с лишним расширением (например, .txt), то нужно выбрать при сохранении тип файла все файлы, а не текст, или после сохранения убрать вручную расширение, переименовав файл.

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

2018-02-27T15:53:05Z

Biryuk: /* Формула выставления итоговой оценки */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/AF-Sst0u3S2R6u Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable sortable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно) !! материалы
|-
| Листочек || Введение в теорвер и анализ алгоритмов || 8 ноября || 21 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац]
|-
| Листочек || Упорядоченные данные || 22 ноября || 5 декабря || [https://yadi.sk/i/lspn_0Sk3QbYWw клац]
|-
| Листочек || Кучи, амортизационный анализ || 30 ноября || 13 декабря || [https://yadi.sk/i/JNFXns9f3QbYX2 клац]
|-
| Листочек || Хеши || 14 декабря || 28 декабря || [https://yadi.sk/i/_yJhrJ4q3QbYX6 клац]
|-
| Листочек || Деревья поиска || 11 января || 25 января || [https://yadi.sk/i/deaTYJhu3S2R6S клац]
|-
| Листочек || Запросы на отрезках || 24 января || 7 января || [https://yadi.sk/i/Zc0TzliL3S2R6H клац]
|-
| Листочек || Различные структуры || 31 января || 14 января || [https://yadi.sk/i/mikgwtQ23S2R75 клац]
|-
| Контест || [https://contest.yandex.ru/contest/5856/standings/ Короткий контест 1] || 9 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6216/standings/ Короткий контест 2] || 23 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6946/standings/ Необычный контест 1] || 20 декабря || только на паре ||
|-
| Контест || [https://contest.yandex.ru/contest/6475/standings/ Длинный контест 1] || 30 ноября || 25 декабря ||
|-
| Контест || [https://contest.yandex.ru/contest/7123/standings/ Короткий контест 3] || 18 января || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/7353/standings/ Короткий контест 4] || 1 февраля || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/7355/standings/ Длинный контест 2] || 1 февраля || 26 февраля ||
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 декабря || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|-
| 11 || 10 января || Бинарные деревья поиска, декартово дерево
|-
| 12 || 11 января || Декартово дерево по неявному ключу. Задачи на отрезках, префиксные суммы и разреженные таблицы. Дерево отрезков, групповые модификации.
|-
| 13 || 17 января || Многомерные деревья отрезков. Задачи LCA и LA, двоичные подъёмы, преобразование LCA к RMQ и наоборот, алгоритм Фарака-Колтона и Бендера
|-
| 14 || 24 января || Задача LCA за O(n log n) \ O(1), понятие персистентной структуры данных, виды персистентности. Персистентные стек, массив и дерево отрезков.
|-
| 15 || 25 января || Персистентные деревья поиска и персистентные деревья с неявным ключом. Примеры решаемых с помощью этих структур данных задач. Простые алгоритмы сборки мусора.
|}

== Семинары ==
{| class="wikitable"
|-
! Дата !! Материалы !! Тема
|-
| 1 ноября || [https://yadi.sk/i/J_j0Pcmn3QbYWm клац] || Понятие асимптотического времени работы алгоритма. Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω
|---
| 2 ноябр || [https://yadi.sk/i/eqF6qtJb3QbYWq клац] || Совместное решение задач по теории вероятностей.
|-
| 8 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац] || Теоретическое домашнее задание по теме "Вероятности и математическое ожидание", приём задач.
|-
| 9 ноября || [https://contest.yandex.ru/contest/5856/standings/ сурс] || Первый короткий контест.
|-
| 15 ноября || None || Обсуждение методов тестирования программ.
|-
| 16 ноября || [https://yadi.sk/i/Cc69A0pf3QbYWu клац] || Совместное решение задач на алгоритмы сортировки и поиска порядковой статистики.
|-
| 22 ноября || [https://yadi.sk/i/lspn_0Sk3QbYWw клац] || Теоретическое домашнее задание по теме "Упорядоченные данные, элементарные стурктуры данных", приём задач.
|-
| 23 ноября || [https://contest.yandex.ru/contest/6216/standings/ сурс] || Второй короткий контест.
|-
| 29 ноября || [https://yadi.sk/i/1H-uuwNz3QbYWy клац] || Разбор задач первого теоретического домашнего задания. Совместное решение задач на элементарные структуры данных и двоичные кучи.
|-
| 30 ноября || [https://yadi.sk/i/JNFXns9f3QbYX2 клац] || Теоретическое домашнее задание по теме "Кучи, амортизационный анализ", приём задач.
|-
| 6 декабря || [https://yadi.sk/i/Ix221PIa3QbYX4 клац] || Подготовка к контрольной, совместное решение задач на различные темы.
|-
| 7 декабря || None || Контрольная работа за текущий модуль на две пары.
|-
| 13 декабря || None || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|-
| 14 декабря || [https://yadi.sk/i/_yJhrJ4q3QbYX6 клац] || Хеши
|-
| 20 декабря || [https://contest.yandex.ru/contest/6946/standings/ сурс] || Бонусный контест на две пары
|-
| 10 января || None || Разбор третьего домашнего задания и задач первого длинного контеста.
|-
| 11 января || [https://yadi.sk/i/deaTYJhu3S2R6S клац] || Разбор четвёртого домашнего задания. Приём задач листочка по теме "Деревья поиска"
|-
| 17 января || [https://yadi.sk/i/0_Mbhw5p3S2R5x клац] || Совместное решение задач на тему "Деревья отрезков"
|-
| 18 января || [https://contest.yandex.ru/contest/7123/standings/ сурс] || Третий короткий контест
|-
| 24 января || [https://yadi.sk/i/Zc0TzliL3S2R6H клац] || Приём домашнего задания по теме "запросы на отрезках и связанные задачи"
|-
| 25 января || [https://yadi.sk/i/qiaJdYUn3S2R6g/ клац] || Разбор домашнего задания по теме "Деревья поиска", совместное решение задач на персистентные деревья отрезков
|-
| 31 января || [https://yadi.sk/i/mikgwtQ23S2R75 клац] || Приём домашнего задания по теме "Последнее ДЗ по структурам данных, задачи на разные темы."
|-
| 1 февраля || [https://contest.yandex.ru/contest/7353/standings/ сурс] || Короткий контест 4

|}

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Вторник, 12.10-13.30 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 12.10-13.30 + офис Яндекса по договоренности
|-
| Глеб Третьяков || || Вторник, с 13:40 до 15:00 в аудитории 503
|}

== Учебные контесты ==

==Листики==
[https://yadi.sk/d/Spaj2IdG3QbYTG Все листки на Яндекс.Диске]

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

2018-02-02T08:14:22Z

Biryuk:

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/AF-Sst0u3S2R6u Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable sortable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно) !! материалы
|-
| Листочек || Введение в теорвер и анализ алгоритмов || 8 ноября || 21 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац]
|-
| Листочек || Упорядоченные данные || 22 ноября || 5 декабря || [https://yadi.sk/i/lspn_0Sk3QbYWw клац]
|-
| Листочек || Кучи, амортизационный анализ || 30 ноября || 13 декабря || [https://yadi.sk/i/JNFXns9f3QbYX2 клац]
|-
| Листочек || Хеши || 14 декабря || 28 декабря || [https://yadi.sk/i/_yJhrJ4q3QbYX6 клац]
|-
| Листочек || Деревья поиска || 11 января || 25 января || [https://yadi.sk/i/deaTYJhu3S2R6S клац]
|-
| Листочек || Запросы на отрезках || 24 января || 7 января || [https://yadi.sk/i/Zc0TzliL3S2R6H клац]
|-
| Листочек || Различные структуры || 31 января || 14 января || [https://yadi.sk/i/mikgwtQ23S2R75 клац]
|-
| Контест || [https://contest.yandex.ru/contest/5856/standings/ Короткий контест 1] || 9 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6216/standings/ Короткий контест 2] || 23 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6946/standings/ Необычный контест 1] || 20 декабря || только на паре ||
|-
| Контест || [https://contest.yandex.ru/contest/6475/standings/ Длинный контест 1] || 30 ноября || 25 декабря ||
|-
| Контест || [https://contest.yandex.ru/contest/7123/standings/ Короткий контест 3] || 18 января || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/7353/standings/ Короткий контест 4] || 1 февраля || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/7355/standings/ Длинный контест 2] || 1 февраля || 26 февраля ||
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 декабря || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|-
| 11 || 10 января || Бинарные деревья поиска, декартово дерево
|-
| 12 || 11 января || Декартово дерево по неявному ключу. Задачи на отрезках, префиксные суммы и разреженные таблицы. Дерево отрезков, групповые модификации.
|-
| 13 || 17 января || Многомерные деревья отрезков. Задачи LCA и LA, двоичные подъёмы, преобразование LCA к RMQ и наоборот, алгоритм Фарака-Колтона и Бендера
|-
| 14 || 24 января || Задача LCA за O(n log n) \ O(1), понятие персистентной структуры данных, виды персистентности. Персистентные стек, массив и дерево отрезков.
|-
| 15 || 25 января || Персистентные деревья поиска и персистентные деревья с неявным ключом. Примеры решаемых с помощью этих структур данных задач. Простые алгоритмы сборки мусора.
|}

== Семинары ==
{| class="wikitable"
|-
! Дата !! Материалы !! Тема
|-
| 1 ноября || [https://yadi.sk/i/J_j0Pcmn3QbYWm клац] || Понятие асимптотического времени работы алгоритма. Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω
|---
| 2 ноябр || [https://yadi.sk/i/eqF6qtJb3QbYWq клац] || Совместное решение задач по теории вероятностей.
|-
| 8 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац] || Теоретическое домашнее задание по теме "Вероятности и математическое ожидание", приём задач.
|-
| 9 ноября || [https://contest.yandex.ru/contest/5856/standings/ сурс] || Первый короткий контест.
|-
| 15 ноября || None || Обсуждение методов тестирования программ.
|-
| 16 ноября || [https://yadi.sk/i/Cc69A0pf3QbYWu клац] || Совместное решение задач на алгоритмы сортировки и поиска порядковой статистики.
|-
| 22 ноября || [https://yadi.sk/i/lspn_0Sk3QbYWw клац] || Теоретическое домашнее задание по теме "Упорядоченные данные, элементарные стурктуры данных", приём задач.
|-
| 23 ноября || [https://contest.yandex.ru/contest/6216/standings/ сурс] || Второй короткий контест.
|-
| 29 ноября || [https://yadi.sk/i/1H-uuwNz3QbYWy клац] || Разбор задач первого теоретического домашнего задания. Совместное решение задач на элементарные структуры данных и двоичные кучи.
|-
| 30 ноября || [https://yadi.sk/i/JNFXns9f3QbYX2 клац] || Теоретическое домашнее задание по теме "Кучи, амортизационный анализ", приём задач.
|-
| 6 декабря || [https://yadi.sk/i/Ix221PIa3QbYX4 клац] || Подготовка к контрольной, совместное решение задач на различные темы.
|-
| 7 декабря || None || Контрольная работа за текущий модуль на две пары.
|-
| 13 декабря || None || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|-
| 14 декабря || [https://yadi.sk/i/_yJhrJ4q3QbYX6 клац] || Хеши
|-
| 20 декабря || [https://contest.yandex.ru/contest/6946/standings/ сурс] || Бонусный контест на две пары
|-
| 10 января || None || Разбор третьего домашнего задания и задач первого длинного контеста.
|-
| 11 января || [https://yadi.sk/i/deaTYJhu3S2R6S клац] || Разбор четвёртого домашнего задания. Приём задач листочка по теме "Деревья поиска"
|-
| 17 января || [https://yadi.sk/i/0_Mbhw5p3S2R5x клац] || Совместное решение задач на тему "Деревья отрезков"
|-
| 18 января || [https://contest.yandex.ru/contest/7123/standings/ сурс] || Третий короткий контест
|-
| 24 января || [https://yadi.sk/i/Zc0TzliL3S2R6H клац] || Приём домашнего задания по теме "запросы на отрезках и связанные задачи"
|-
| 25 января || [https://yadi.sk/i/qiaJdYUn3S2R6g/ клац] || Разбор домашнего задания по теме "Деревья поиска", совместное решение задач на персистентные деревья отрезков
|-
| 31 января || [https://yadi.sk/i/mikgwtQ23S2R75 клац] || Приём домашнего задания по теме "Последнее ДЗ по структурам данных, задачи на разные темы."
|-
| 1 февраля || [https://contest.yandex.ru/contest/7353/standings/ сурс] || Короткий контест 4

|}

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Вторник, 12.10-13.30 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 12.10-13.30 + офис Яндекса по договоренности
|-
| Глеб Третьяков || || Вторник, с 13:40 до 15:00 в аудитории 503
|}

== Учебные контесты ==

==Листики==
[https://yadi.sk/d/Spaj2IdG3QbYTG Все листки на Яндекс.Диске]

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

2018-02-02T08:12:19Z

Biryuk:

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/AF-Sst0u3S2R6u Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable sortable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно) !! материалы
|-
| Листочек || Введение в теорвер и анализ алгоритмов || 8 ноября || 21 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац]
|-
| Листочек || Упорядоченные данные || 22 ноября || 5 декабря || [https://yadi.sk/i/lspn_0Sk3QbYWw клац]
|-
| Листочек || Кучи, амортизационный анализ || 30 ноября || 13 декабря || [https://yadi.sk/i/JNFXns9f3QbYX2 клац]
|-
| Листочек || Хеши || 14 декабря || 28 декабря || [https://yadi.sk/i/_yJhrJ4q3QbYX6 клац]
|-
| Листочек || Деревья поиска || 11 января || 25 января || [https://yadi.sk/i/deaTYJhu3S2R6S клац]
|-
| Листочек || Запросы на отрезках || 24 января || 7 января || [https://yadi.sk/i/Zc0TzliL3S2R6H клац]
|-
| Листочек || Различные структуры || 31 января || 14 января || https://yadi.sk/i/mikgwtQ23S2R75
|-
| Контест || [https://contest.yandex.ru/contest/5856/standings/ Короткий контест 1] || 9 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6216/standings/ Короткий контест 2] || 23 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6946/standings/ Необычный контест 1] || 20 декабря || только на паре ||
|-
| Контест || [https://contest.yandex.ru/contest/6475/standings/ Длинный контест 1] || 30 ноября || 25 декабря ||
|-
| Контест || [https://contest.yandex.ru/contest/7123/standings/ Короткий контест 3] || 18 января || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/7353/standings/ Короткий контест 4] || 1 февраля || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/7355/standings/ Длинный контест 2] || 1 февраля || 26 февраля ||
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 декабря || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|-
| 11 || 10 января || Бинарные деревья поиска, декартово дерево
|-
| 12 || 11 января || Декартово дерево по неявному ключу. Задачи на отрезках, префиксные суммы и разреженные таблицы. Дерево отрезков, групповые модификации.
|-
| 13 || 17 января || Многомерные деревья отрезков. Задачи LCA и LA, двоичные подъёмы, преобразование LCA к RMQ и наоборот, алгоритм Фарака-Колтона и Бендера
|-
| 14 || 24 января || Задача LCA за O(n log n) \ O(1), понятие персистентной структуры данных, виды персистентности. Персистентные стек, массив и дерево отрезков.
|-
| 15 || 25 января || Персистентные деревья поиска и персистентные деревья с неявным ключом. Примеры решаемых с помощью этих структур данных задач. Простые алгоритмы сборки мусора.
|}

== Семинары ==
{| class="wikitable"
|-
! Дата !! Материалы !! Тема
|-
| 1 ноября || [https://yadi.sk/i/J_j0Pcmn3QbYWm клац] || Понятие асимптотического времени работы алгоритма. Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω
|---
| 2 ноябр || [https://yadi.sk/i/eqF6qtJb3QbYWq клац] || Совместное решение задач по теории вероятностей.
|-
| 8 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац] || Теоретическое домашнее задание по теме "Вероятности и математическое ожидание", приём задач.
|-
| 9 ноября || [https://contest.yandex.ru/contest/5856/standings/ сурс] || Первый короткий контест.
|-
| 15 ноября || None || Обсуждение методов тестирования программ.
|-
| 16 ноября || [https://yadi.sk/i/Cc69A0pf3QbYWu клац] || Совместное решение задач на алгоритмы сортировки и поиска порядковой статистики.
|-
| 22 ноября || [https://yadi.sk/i/lspn_0Sk3QbYWw клац] || Теоретическое домашнее задание по теме "Упорядоченные данные, элементарные стурктуры данных", приём задач.
|-
| 23 ноября || [https://contest.yandex.ru/contest/6216/standings/ сурс] || Второй короткий контест.
|-
| 29 ноября || [https://yadi.sk/i/1H-uuwNz3QbYWy клац] || Разбор задач первого теоретического домашнего задания. Совместное решение задач на элементарные структуры данных и двоичные кучи.
|-
| 30 ноября || [https://yadi.sk/i/JNFXns9f3QbYX2 клац] || Теоретическое домашнее задание по теме "Кучи, амортизационный анализ", приём задач.
|-
| 6 декабря || [https://yadi.sk/i/Ix221PIa3QbYX4 клац] || Подготовка к контрольной, совместное решение задач на различные темы.
|-
| 7 декабря || None || Контрольная работа за текущий модуль на две пары.
|-
| 13 декабря || None || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|-
| 14 декабря || [https://yadi.sk/i/_yJhrJ4q3QbYX6 клац] || Хеши
|-
| 20 декабря || [https://contest.yandex.ru/contest/6946/standings/ сурс] || Бонусный контест на две пары
|-
| 10 января || None || Разбор третьего домашнего задания и задач первого длинного контеста.
|-
| 11 января || [https://yadi.sk/i/deaTYJhu3S2R6S клац] || Разбор четвёртого домашнего задания. Приём задач листочка по теме "Деревья поиска"
|-
| 17 января || [https://yadi.sk/i/0_Mbhw5p3S2R5x клац] || Совместное решение задач на тему "Деревья отрезков"
|-
| 18 января || [https://contest.yandex.ru/contest/7123/standings/ сурс] || Третий короткий контест
|-
| 24 января || [https://yadi.sk/i/Zc0TzliL3S2R6H клац] || Приём домашнего задания по теме "запросы на отрезках и связанные задачи"
|-
| 25 января || [https://yadi.sk/i/qiaJdYUn3S2R6g/ клац] || Разбор домашнего задания по теме "Деревья поиска", совместное решение задач на персистентные деревья отрезков
|-
| 31 января || [https://yadi.sk/i/mikgwtQ23S2R75 клац] || Приём домашнего задания по теме "Последнее ДЗ по структурам данных, задачи на разные темы."
|-
| 1 февраля || [https://yadi.sk/i/qiaJdYUn3S2R6g/ клац] || Разбор домашнего задания по теме "Деревья поиска", совместное решение задач на персистентные деревья отрезков

|}

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Вторник, 12.10-13.30 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 12.10-13.30 + офис Яндекса по договоренности
|-
| Глеб Третьяков || || Вторник, с 13:40 до 15:00 в аудитории 503
|}

== Учебные контесты ==

==Листики==
[https://yadi.sk/d/Spaj2IdG3QbYTG Все листки на Яндекс.Диске]

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

2018-01-17T22:01:24Z

Biryuk: /* Семинары */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable sortable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно) !! материалы
|-
| Листочек || Введение в теорвер и анализ алгоритмов || 8 ноября || 21 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац]
|-
| Листочек || Упорядоченные данные || 22 ноября || 5 декабря || [https://yadi.sk/i/lspn_0Sk3QbYWw клац]
|-
| Листочек || Кучи, амортизационный анализ || 30 ноября || 13 декабря || [https://yadi.sk/i/JNFXns9f3QbYX2 клац]
|-
| Листочек || || is comming || ||
|-
| Контест || [https://contest.yandex.ru/contest/5856/standings/ Короткий контест 1] || 9 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6216/standings/ Короткий контест 2] || 23 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6946/standings/ Необычный контест 1] || 20 декабря || только на паре ||
|-
| Контест || [https://contest.yandex.ru/contest/6475/standings/ Длинный контест 1] || 30 ноября || 25 декабря ||
|-
| Контест || [https://contest.yandex.ru/contest/7123/standings/ Короткий контест 3] || 18 января || день до экзамена (дорешка) ||
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 декабря || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|-
| 11 || 10 января || Бинарные деревья поиска, декартово дерево
|-
| 12 || 11 января || Декартово дерево по неявному ключу. Задачи на отрезках, префиксные суммы и разреженные таблицы. Дерево отрезков, групповые модификации.
|}

== Семинары ==
{| class="wikitable"
|-
! Дата !! Материалы !! Тема
|-
| 1 ноября || [https://yadi.sk/i/J_j0Pcmn3QbYWm клац] || Понятие асимптотического времени работы алгоритма. Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω
|---
| 2 ноябр || [https://yadi.sk/i/eqF6qtJb3QbYWq клац] || Совместное решение задач по теории вероятностей.
|-
| 8 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац] || Теоретическое домашнее задание по теме "Вероятности и математическое ожидание", приём задач.
|-
| 9 ноября || [https://contest.yandex.ru/contest/5856/standings/ сурс] || Первый короткий контест.
|-
| 15 ноября || None || Обсуждение методов тестирования программ.
|-
| 16 ноября || [https://yadi.sk/i/Cc69A0pf3QbYWu клац] || Совместное решение задач на алгоритмы сортировки и поиска порядковой статистики.
|-
| 22 ноября || [https://yadi.sk/i/lspn_0Sk3QbYWw клац] || Теоретическое домашнее задание по теме "Упорядоченные данные, элементарные стурктуры данных", приём задач.
|-
| 23 ноября || [https://contest.yandex.ru/contest/6216/standings/ сурс] || Второй короткий контест.
|-
| 29 ноября || [https://yadi.sk/i/1H-uuwNz3QbYWy клац] || Разбор задач первого теоретического домашнего задания. Совместное решение задач на элементарные структуры данных и двоичные кучи.
|-
| 30 ноября || [https://yadi.sk/i/JNFXns9f3QbYX2 клац] || Теоретическое домашнее задание по теме "Кучи, амортизационный анализ", приём задач.
|-
| 6 декабря || [https://yadi.sk/i/Ix221PIa3QbYX4 клац] || Подготовка к контрольной, совместное решение задач на различные темы.
|-
| 7 декабря || None || Контрольная работа за текущий модуль на две пары.
|-
| 13 декабря || None || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|-
| 14(?) декабря || клац || Хеши
|-
| 20 декабря || [https://contest.yandex.ru/contest/6946/standings/ сурс] || Бонусный контест на две пары
|-
| 10 января || None || Разбор третьего домашнего задания и задач первого длинного контеста.
|-
| 11 января || клац || Разбор четвёртого домашнего задания. Приём задач листочка по теме "Деревья поиска"
|-
| 17 января || клац || Листок "Решаем вместе"
|-
| 18 января || [https://contest.yandex.ru/contest/7123/standings/ сурс] || Третий короткий контест
|}

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Вторник, 12.10-13.30 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 12.10-13.30 + офис Яндекса по договоренности
|-
| Глеб Третьяков || || Вторник, с 13:40 до 15:00 в аудитории 503
|}

== Учебные контесты ==

==Листики==
[https://yadi.sk/d/Spaj2IdG3QbYTG Все листки на Яндекс.Диске]

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

2018-01-17T22:00:45Z

Biryuk: /* Преподаватели и ассистенты */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable sortable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно) !! материалы
|-
| Листочек || Введение в теорвер и анализ алгоритмов || 8 ноября || 21 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац]
|-
| Листочек || Упорядоченные данные || 22 ноября || 5 декабря || [https://yadi.sk/i/lspn_0Sk3QbYWw клац]
|-
| Листочек || Кучи, амортизационный анализ || 30 ноября || 13 декабря || [https://yadi.sk/i/JNFXns9f3QbYX2 клац]
|-
| Листочек || || is comming || ||
|-
| Контест || [https://contest.yandex.ru/contest/5856/standings/ Короткий контест 1] || 9 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6216/standings/ Короткий контест 2] || 23 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6946/standings/ Необычный контест 1] || 20 декабря || только на паре ||
|-
| Контест || [https://contest.yandex.ru/contest/6475/standings/ Длинный контест 1] || 30 ноября || 25 декабря ||
|-
| Контест || [https://contest.yandex.ru/contest/7123/standings/ Короткий контест 3] || 18 января || день до экзамена (дорешка) ||
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 декабря || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|-
| 11 || 10 января || Бинарные деревья поиска, декартово дерево
|-
| 12 || 11 января || Декартово дерево по неявному ключу. Задачи на отрезках, префиксные суммы и разреженные таблицы. Дерево отрезков, групповые модификации.
|}

== Семинары ==
{| class="wikitable"
|-
! Дата !! Материалы !! Тема
|-
| 1 ноября || [https://yadi.sk/i/J_j0Pcmn3QbYWm клац] || Понятие асимптотического времени работы алгоритма. Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω
|---
| 2 ноябр || [https://yadi.sk/i/eqF6qtJb3QbYWq клац] || Совместное решение задач по теории вероятностей.
|-
| 8 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац] || Теоретическое домашнее задание по теме "Вероятности и математическое ожидание", приём задач.
|-
| 9 ноября || [https://contest.yandex.ru/contest/5856/standings/ сурс] || Первый короткий контест.
|-
| 15 ноября || None || Обсуждение методов тестирования программ.
|-
| 16 ноября || [https://yadi.sk/i/Cc69A0pf3QbYWu клац] || Совместное решение задач на алгоритмы сортировки и поиска порядковой статистики.
|-
| 22 ноября || [https://yadi.sk/i/lspn_0Sk3QbYWw клац] || Теоретическое домашнее задание по теме "Упорядоченные данные, элементарные стурктуры данных", приём задач.
|-
| 23 ноября || [https://contest.yandex.ru/contest/6216/standings/ сурс] || Второй короткий контест.
|-
| 29 ноября || [https://yadi.sk/i/1H-uuwNz3QbYWy клац] || Разбор задач первого теоретического домашнего задания. Совместное решение задач на элементарные структуры данных и двоичные кучи.
|-
| 30 ноября || [https://yadi.sk/i/JNFXns9f3QbYX2 клац] || Теоретическое домашнее задание по теме "Кучи, амортизационный анализ", приём задач.
|-
| 6 декабря || [https://yadi.sk/i/Ix221PIa3QbYX4 клац] || Подготовка к контрольной, совместное решение задач на различные темы.
|-
| 7 декабря || None || Контрольная работа за текущий модуль на две пары.
|-
| 13 декабря || None || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|-
| 14(?) декабря || клац || Хеши
|-
| 20 декабря || [https://contest.yandex.ru/contest/6946/standings/ сурс] || Бонусный контест на две пары
|-
| 13 декабря || None || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|-
| 10 января || None || Разбор третьего домашнего задания и задач первого длинного контеста.
|-
| 11 января || клац || Разбор четвёртого домашнего задания. Приём задач листочка по теме "Деревья поиска"
|-
| 17 января || клац || Листок "Решаем вместе"
|-
| 18 января || [https://contest.yandex.ru/contest/7123/standings/ сурс] || Третий короткий контест
|}

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Вторник, 12.10-13.30 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 12.10-13.30 + офис Яндекса по договоренности
|-
| Глеб Третьяков || || Вторник, с 13:40 до 15:00 в аудитории 503
|}

== Учебные контесты ==

==Листики==
[https://yadi.sk/d/Spaj2IdG3QbYTG Все листки на Яндекс.Диске]

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

2018-01-17T21:57:50Z

Biryuk: /* Семинары */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable sortable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно) !! материалы
|-
| Листочек || Введение в теорвер и анализ алгоритмов || 8 ноября || 21 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац]
|-
| Листочек || Упорядоченные данные || 22 ноября || 5 декабря || [https://yadi.sk/i/lspn_0Sk3QbYWw клац]
|-
| Листочек || Кучи, амортизационный анализ || 30 ноября || 13 декабря || [https://yadi.sk/i/JNFXns9f3QbYX2 клац]
|-
| Листочек || || is comming || ||
|-
| Контест || [https://contest.yandex.ru/contest/5856/standings/ Короткий контест 1] || 9 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6216/standings/ Короткий контест 2] || 23 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6946/standings/ Необычный контест 1] || 20 декабря || только на паре ||
|-
| Контест || [https://contest.yandex.ru/contest/6475/standings/ Длинный контест 1] || 30 ноября || 25 декабря ||
|-
| Контест || [https://contest.yandex.ru/contest/7123/standings/ Короткий контест 3] || 18 января || день до экзамена (дорешка) ||
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 декабря || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|-
| 11 || 10 января || Бинарные деревья поиска, декартово дерево
|-
| 12 || 11 января || Декартово дерево по неявному ключу. Задачи на отрезках, префиксные суммы и разреженные таблицы. Дерево отрезков, групповые модификации.
|}

== Семинары ==
{| class="wikitable"
|-
! Дата !! Материалы !! Тема
|-
| 1 ноября || [https://yadi.sk/i/J_j0Pcmn3QbYWm клац] || Понятие асимптотического времени работы алгоритма. Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω
|---
| 2 ноябр || [https://yadi.sk/i/eqF6qtJb3QbYWq клац] || Совместное решение задач по теории вероятностей.
|-
| 8 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац] || Теоретическое домашнее задание по теме "Вероятности и математическое ожидание", приём задач.
|-
| 9 ноября || [https://contest.yandex.ru/contest/5856/standings/ сурс] || Первый короткий контест.
|-
| 15 ноября || None || Обсуждение методов тестирования программ.
|-
| 16 ноября || [https://yadi.sk/i/Cc69A0pf3QbYWu клац] || Совместное решение задач на алгоритмы сортировки и поиска порядковой статистики.
|-
| 22 ноября || [https://yadi.sk/i/lspn_0Sk3QbYWw клац] || Теоретическое домашнее задание по теме "Упорядоченные данные, элементарные стурктуры данных", приём задач.
|-
| 23 ноября || [https://contest.yandex.ru/contest/6216/standings/ сурс] || Второй короткий контест.
|-
| 29 ноября || [https://yadi.sk/i/1H-uuwNz3QbYWy клац] || Разбор задач первого теоретического домашнего задания. Совместное решение задач на элементарные структуры данных и двоичные кучи.
|-
| 30 ноября || [https://yadi.sk/i/JNFXns9f3QbYX2 клац] || Теоретическое домашнее задание по теме "Кучи, амортизационный анализ", приём задач.
|-
| 6 декабря || [https://yadi.sk/i/Ix221PIa3QbYX4 клац] || Подготовка к контрольной, совместное решение задач на различные темы.
|-
| 7 декабря || None || Контрольная работа за текущий модуль на две пары.
|-
| 13 декабря || None || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|-
| 14(?) декабря || клац || Хеши
|-
| 20 декабря || [https://contest.yandex.ru/contest/6946/standings/ сурс] || Бонусный контест на две пары
|-
| 13 декабря || None || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|-
| 10 января || None || Разбор третьего домашнего задания и задач первого длинного контеста.
|-
| 11 января || клац || Разбор четвёртого домашнего задания. Приём задач листочка по теме "Деревья поиска"
|-
| 17 января || клац || Листок "Решаем вместе"
|-
| 18 января || [https://contest.yandex.ru/contest/7123/standings/ сурс] || Третий короткий контест
|}

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Четверг 16.40-18.00 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 15.10-16.30 + офис Яндекса по договоренности
|-
|}

== Учебные контесты ==

==Листики==
[https://yadi.sk/d/Spaj2IdG3QbYTG Все листки на Яндекс.Диске]

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

2018-01-17T21:48:35Z

Biryuk: /* Лекции */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable sortable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно) !! материалы
|-
| Листочек || Введение в теорвер и анализ алгоритмов || 8 ноября || 21 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац]
|-
| Листочек || Упорядоченные данные || 22 ноября || 5 декабря || [https://yadi.sk/i/lspn_0Sk3QbYWw клац]
|-
| Листочек || Кучи, амортизационный анализ || 30 ноября || 13 декабря || [https://yadi.sk/i/JNFXns9f3QbYX2 клац]
|-
| Листочек || || is comming || ||
|-
| Контест || [https://contest.yandex.ru/contest/5856/standings/ Короткий контест 1] || 9 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6216/standings/ Короткий контест 2] || 23 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6946/standings/ Необычный контест 1] || 20 декабря || только на паре ||
|-
| Контест || [https://contest.yandex.ru/contest/6475/standings/ Длинный контест 1] || 30 ноября || 25 декабря ||
|-
| Контест || [https://contest.yandex.ru/contest/7123/standings/ Короткий контест 3] || 18 января || день до экзамена (дорешка) ||
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 декабря || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|-
| 11 || 10 января || Бинарные деревья поиска, декартово дерево
|-
| 12 || 11 января || Декартово дерево по неявному ключу. Задачи на отрезках, префиксные суммы и разреженные таблицы. Дерево отрезков, групповые модификации.
|}

== Семинары ==
{| class="wikitable"
|-
! Дата !! Материалы !! Тема
|-
| 1 ноября || [https://yadi.sk/i/J_j0Pcmn3QbYWm клац] || Понятие асимптотического времени работы алгоритма. Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω
|---
| 2 ноябр || [https://yadi.sk/i/eqF6qtJb3QbYWq клац] || Совместное решение задач по теории вероятностей.
|-
| 8 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац] || Теоретическое домашнее задание по теме "Вероятности и математическое ожидание", приём задач.
|-
| 9 ноября || сурс || Первый короткий контест.
|-
| 15 ноября || None || Обсуждение методов тестирования программ.
|-
| 16 ноября || [https://yadi.sk/i/Cc69A0pf3QbYWu клац] || Совместное решение задач на алгоритмы сортировки и поиска порядковой статистики.
|-
| 22 ноября || [https://yadi.sk/i/lspn_0Sk3QbYWw клац] || Теоретическое домашнее задание по теме "Упорядоченные данные, элементарные стурктуры данных", приём задач.
|-
| 23 ноября || сурс || Второй короткий контест.
|-
| 29 ноября || [https://yadi.sk/i/1H-uuwNz3QbYWy клац] || Разбор задач первого теоретического домашнего задания. Совместное решение задач на элементарные структуры данных и двоичные кучи.
|-
| 30 ноября || [https://yadi.sk/i/JNFXns9f3QbYX2 клац] || Теоретическое домашнее задание по теме "Кучи, амортизационный анализ", приём задач.
|-
| 6 декабря || [https://yadi.sk/i/Ix221PIa3QbYX4 клац] || Подготовка к контрольной, совместное решение задач на различные темы.
|-
| 7 декабря || None || Контрольная работа за текущий модуль на две пары.
|-
| 13 декабря || None || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|}

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Четверг 16.40-18.00 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 15.10-16.30 + офис Яндекса по договоренности
|-
|}

== Учебные контесты ==

==Листики==
[https://yadi.sk/d/Spaj2IdG3QbYTG Все листки на Яндекс.Диске]

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

2018-01-17T21:45:38Z

Biryuk: /* Сроки выполнения заданий */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable sortable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно) !! материалы
|-
| Листочек || Введение в теорвер и анализ алгоритмов || 8 ноября || 21 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац]
|-
| Листочек || Упорядоченные данные || 22 ноября || 5 декабря || [https://yadi.sk/i/lspn_0Sk3QbYWw клац]
|-
| Листочек || Кучи, амортизационный анализ || 30 ноября || 13 декабря || [https://yadi.sk/i/JNFXns9f3QbYX2 клац]
|-
| Листочек || || is comming || ||
|-
| Контест || [https://contest.yandex.ru/contest/5856/standings/ Короткий контест 1] || 9 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6216/standings/ Короткий контест 2] || 23 ноября || день до экзамена (дорешка) ||
|-
| Контест || [https://contest.yandex.ru/contest/6946/standings/ Необычный контест 1] || 20 декабря || только на паре ||
|-
| Контест || [https://contest.yandex.ru/contest/6475/standings/ Длинный контест 1] || 30 ноября || 25 декабря ||
|-
| Контест || [https://contest.yandex.ru/contest/7123/standings/ Короткий контест 3] || 18 января || день до экзамена (дорешка) ||
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 ноября || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|}

== Семинары ==
{| class="wikitable"
|-
! Дата !! Материалы !! Тема
|-
| 1 ноября || [https://yadi.sk/i/J_j0Pcmn3QbYWm клац] || Понятие асимптотического времени работы алгоритма. Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω
|---
| 2 ноябр || [https://yadi.sk/i/eqF6qtJb3QbYWq клац] || Совместное решение задач по теории вероятностей.
|-
| 8 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац] || Теоретическое домашнее задание по теме "Вероятности и математическое ожидание", приём задач.
|-
| 9 ноября || сурс || Первый короткий контест.
|-
| 15 ноября || None || Обсуждение методов тестирования программ.
|-
| 16 ноября || [https://yadi.sk/i/Cc69A0pf3QbYWu клац] || Совместное решение задач на алгоритмы сортировки и поиска порядковой статистики.
|-
| 22 ноября || [https://yadi.sk/i/lspn_0Sk3QbYWw клац] || Теоретическое домашнее задание по теме "Упорядоченные данные, элементарные стурктуры данных", приём задач.
|-
| 23 ноября || сурс || Второй короткий контест.
|-
| 29 ноября || [https://yadi.sk/i/1H-uuwNz3QbYWy клац] || Разбор задач первого теоретического домашнего задания. Совместное решение задач на элементарные структуры данных и двоичные кучи.
|-
| 30 ноября || [https://yadi.sk/i/JNFXns9f3QbYX2 клац] || Теоретическое домашнее задание по теме "Кучи, амортизационный анализ", приём задач.
|-
| 6 декабря || [https://yadi.sk/i/Ix221PIa3QbYX4 клац] || Подготовка к контрольной, совместное решение задач на различные темы.
|-
| 7 декабря || None || Контрольная работа за текущий модуль на две пары.
|-
| 13 декабря || None || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|}

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Четверг 16.40-18.00 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 15.10-16.30 + офис Яндекса по договоренности
|-
|}

== Учебные контесты ==

==Листики==
[https://yadi.sk/d/Spaj2IdG3QbYTG Все листки на Яндекс.Диске]

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

2017-12-14T02:53:26Z

Biryuk: /* Семинары */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable sortable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно) !! материалы
|-
| Листочек || Введение в теорвер и анализ алгоритмов || 8 ноября || 21 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац]
|-
| Листочек || Упорядоченные данные || 22 ноября || 5 декабря || [https://yadi.sk/i/lspn_0Sk3QbYWw клац]
|-
| Листочек || Кучи, амортизационный анализ || 30 ноября || 13 декабря || [https://yadi.sk/i/JNFXns9f3QbYX2 клац]
|-
| Листочек || || is comming || ||
|-
| Контест || Короткий контест 1 || 9 ноября || день до экзамена (дорешка) ||
|-
| Контест || Короткий контест 2 || 23 ноября || день до экзамена (дорешка) ||
|-
| Контест || Необычный контест 1 || ??? || только на паре ||
|-
| Контест || Длинный контест 1 || || ||
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 ноября || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|}

== Семинары ==
{| class="wikitable"
|-
! Дата !! Материалы !! Тема
|-
| 1 ноября || [https://yadi.sk/i/J_j0Pcmn3QbYWm клац] || Понятие асимптотического времени работы алгоритма. Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω
|---
| 2 ноябр || [https://yadi.sk/i/eqF6qtJb3QbYWq клац] || Совместное решение задач по теории вероятностей.
|-
| 8 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац] || Теоретическое домашнее задание по теме "Вероятности и математическое ожидание", приём задач.
|-
| 9 ноября || сурс || Первый короткий контест.
|-
| 15 ноября || None || Обсуждение методов тестирования программ.
|-
| 16 ноября || [https://yadi.sk/i/Cc69A0pf3QbYWu клац] || Совместное решение задач на алгоритмы сортировки и поиска порядковой статистики.
|-
| 22 ноября || [https://yadi.sk/i/lspn_0Sk3QbYWw клац] || Теоретическое домашнее задание по теме "Упорядоченные данные, элементарные стурктуры данных", приём задач.
|-
| 23 ноября || сурс || Второй короткий контест.
|-
| 29 ноября || [https://yadi.sk/i/1H-uuwNz3QbYWy клац] || Разбор задач первого теоретического домашнего задания. Совместное решение задач на элементарные структуры данных и двоичные кучи.
|-
| 30 ноября || [https://yadi.sk/i/JNFXns9f3QbYX2 клац] || Теоретическое домашнее задание по теме "Кучи, амортизационный анализ", приём задач.
|-
| 6 декабря || [https://yadi.sk/i/Ix221PIa3QbYX4 клац] || Подготовка к контрольной, совместное решение задач на различные темы.
|-
| 7 декабря || None || Контрольная работа за текущий модуль на две пары.
|-
| 13 декабря || None || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|}

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Четверг 16.40-18.00 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 15.10-16.30 + офис Яндекса по договоренности
|-
|}

== Учебные контесты ==

==Листики==
[https://yadi.sk/d/Spaj2IdG3QbYTG Все листки на Яндекс.Диске]

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

2017-12-14T02:50:25Z

Biryuk: /* Формула выставления итоговой оценки */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable sortable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно) !! материалы
|-
| Листочек || Введение в теорвер и анализ алгоритмов || 8 ноября || 21 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац]
|-
| Листочек || Упорядоченные данные || 22 ноября || 5 декабря || [https://yadi.sk/i/lspn_0Sk3QbYWw клац]
|-
| Листочек || Кучи, амортизационный анализ || 30 ноября || 13 декабря || [https://yadi.sk/i/JNFXns9f3QbYX2 клац]
|-
| Листочек || || is comming || ||
|-
| Контест || Короткий контест 1 || 9 ноября || день до экзамена (дорешка) ||
|-
| Контест || Короткий контест 2 || 23 ноября || день до экзамена (дорешка) ||
|-
| Контест || Необычный контест 1 || ??? || только на паре ||
|-
| Контест || Длинный контест 1 || || ||
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 ноября || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|}

== Семинары ==
{| class="wikitable"
|-
! Дата !! Материалы !! Тема
|-
| 1 ноября || [https://yadi.sk/i/J_j0Pcmn3QbYWm клац] || Понятие асимптотического времени работы алгоритма. Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω
|---
| 2 ноябр || [https://yadi.sk/i/eqF6qtJb3QbYWq клац] || Совместное решение задач по теории вероятностей.
|-
| 8 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац] || Теоретическое домашнее задание по теме "Вероятности и математическое ожидание", приём задач.
|-
| 9 ноября || сурс || Первый короткий контест.
|-
| 15 ноября || None || Обсуждение методов тестирования программ.
|-
| 16 ноября || [https://yadi.sk/i/Cc69A0pf3QbYWu клац] || Совместное решение задач на алгоритмы сортировки и поиска порядковой статистики.
|-
| 22 ноября || [https://yadi.sk/i/lspn_0Sk3QbYWw клац] || Теоретическое домашнее задание по теме "Упорядоченные данные, элементарные стурктуры данных", приём задач.
|-
| 23 ноября || сурс || Второй короткий контест.
|-
| 29 ноября || [https://yadi.sk/i/1H-uuwNz3QbYWy клац] || Разбор задач первого теоретического домашнего задания. Совместное решение задач на элементарные структуры данных и двоичные кучи.
|-
| 30 ноября || [https://yadi.sk/i/JNFXns9f3QbYX2 клац] || Теоретическое домашнее задание по теме "Кучи, амортизационный анализ", приём задач.
|-
| 6 декабря || [https://yadi.sk/i/Ix221PIa3QbYX4 клац] || Подготовка к контрольной, совместное решение задач на различные темы.
|-
| 7 декабря || None || Контрольная работа за текущий модуль на две пары.
|-
| 13 декабря || [https://yadi.sk/i/_yJhrJ4q3QbYX6 клац] || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|}

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Четверг 16.40-18.00 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 15.10-16.30 + офис Яндекса по договоренности
|-
|}

== Учебные контесты ==

==Листики==
[https://yadi.sk/d/Spaj2IdG3QbYTG Все листки на Яндекс.Диске]

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

2017-12-14T02:47:03Z

Biryuk: /* Сроки выполнения заданий */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable sortable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно) !! материалы
|-
| Листочек || Введение в теорвер и анализ алгоритмов || 8 ноября || 21 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац]
|-
| Листочек || Упорядоченные данные || 22 ноября || 5 декабря || [https://yadi.sk/i/lspn_0Sk3QbYWw клац]
|-
| Листочек || Кучи, амортизационный анализ || 30 ноября || 13 декабря || [https://yadi.sk/i/JNFXns9f3QbYX2 клац]
|-
| Листочек || || is comming || ||
|-
| Контест || Короткий контест 1 || 9 ноября || день до экзамена (дорешка) ||
|-
| Контест || Короткий контест 2 || 23 ноября || день до экзамена (дорешка) ||
|-
| Контест || Необычный контест 1 || ??? || только на паре ||
|-
| Контест || Длинный контест 1 || || ||
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 ноября || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|}

== Семинары ==
{| class="wikitable"
|-
! Дата !! Материалы !! Тема
|-
| 1 ноября || [https://yadi.sk/i/J_j0Pcmn3QbYWm клац] || Понятие асимптотического времени работы алгоритма. Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω
|---
| 2 ноябр || [https://yadi.sk/i/eqF6qtJb3QbYWq клац] || Совместное решение задач по теории вероятностей.
|-
| 8 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац] || Теоретическое домашнее задание по теме "Вероятности и математическое ожидание", приём задач.
|-
| 9 ноября || сурс || Первый короткий контест.
|-
| 15 ноября || None || Обсуждение методов тестирования программ.
|-
| 16 ноября || [https://yadi.sk/i/Cc69A0pf3QbYWu клац] || Совместное решение задач на алгоритмы сортировки и поиска порядковой статистики.
|-
| 22 ноября || [https://yadi.sk/i/lspn_0Sk3QbYWw клац] || Теоретическое домашнее задание по теме "Упорядоченные данные, элементарные стурктуры данных", приём задач.
|-
| 23 ноября || сурс || Второй короткий контест.
|-
| 29 ноября || [https://yadi.sk/i/1H-uuwNz3QbYWy клац] || Разбор задач первого теоретического домашнего задания. Совместное решение задач на элементарные структуры данных и двоичные кучи.
|-
| 30 ноября || [https://yadi.sk/i/JNFXns9f3QbYX2 клац] || Теоретическое домашнее задание по теме "Кучи, амортизационный анализ", приём задач.
|-
| 6 декабря || [https://yadi.sk/i/Ix221PIa3QbYX4 клац] || Подготовка к контрольной, совместное решение задач на различные темы.
|-
| 7 декабря || None || Контрольная работа за текущий модуль на две пары.
|-
| 13 декабря || [https://yadi.sk/i/_yJhrJ4q3QbYX6 клац] || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|}

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Четверг 16.40-18.00 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 15.10-16.30 + офис Яндекса по договоренности
|-
|}

== Учебные контесты ==

==Листики==
[https://yadi.sk/d/Spaj2IdG3QbYTG Все листки на Яндекс.Диске]

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

2017-12-14T02:35:56Z

Biryuk: /* Семинары */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно)
|-
| Теоретические задачи || Введение в теорвер и анализ алгоритмов || || ||
|-
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 ноября || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|}

== Семинары ==
{| class="wikitable"
|-
! Дата !! Материалы !! Тема
|-
| 1 ноября || [https://yadi.sk/i/J_j0Pcmn3QbYWm клац] || Понятие асимптотического времени работы алгоритма. Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω
|---
| 2 ноябр || [https://yadi.sk/i/eqF6qtJb3QbYWq клац] || Совместное решение задач по теории вероятностей.
|-
| 8 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац] || Теоретическое домашнее задание по теме "Вероятности и математическое ожидание", приём задач.
|-
| 9 ноября || сурс || Первый короткий контест.
|-
| 15 ноября || None || Обсуждение методов тестирования программ.
|-
| 16 ноября || [https://yadi.sk/i/Cc69A0pf3QbYWu клац] || Совместное решение задач на алгоритмы сортировки и поиска порядковой статистики.
|-
| 22 ноября || [https://yadi.sk/i/lspn_0Sk3QbYWw клац] || Теоретическое домашнее задание по теме "Упорядоченные данные, элементарные стурктуры данных", приём задач.
|-
| 23 ноября || сурс || Второй короткий контест.
|-
| 29 ноября || [https://yadi.sk/i/1H-uuwNz3QbYWy клац] || Разбор задач первого теоретического домашнего задания. Совместное решение задач на элементарные структуры данных и двоичные кучи.
|-
| 30 ноября || [https://yadi.sk/i/JNFXns9f3QbYX2 клац] || Теоретическое домашнее задание по теме "Кучи, амортизационный анализ", приём задач.
|-
| 6 декабря || [https://yadi.sk/i/Ix221PIa3QbYX4 клац] || Подготовка к контрольной, совместное решение задач на различные темы.
|-
| 7 декабря || None || Контрольная работа за текущий модуль на две пары.
|-
| 13 декабря || [https://yadi.sk/i/_yJhrJ4q3QbYX6 клац] || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|}

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Четверг 16.40-18.00 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 15.10-16.30 + офис Яндекса по договоренности
|-
|}

== Учебные контесты ==

==Листики==
[https://yadi.sk/d/Spaj2IdG3QbYTG Все листки на Яндекс.Диске]

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

2017-12-14T02:35:05Z

Biryuk: /* Семинары */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно)
|-
| Теоретические задачи || Введение в теорвер и анализ алгоритмов || || ||
|-
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 ноября || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|}

== Семинары ==
{| class="wikitable"
|-
! Дата !! Материалы !! Тема
|-
| 1 ноября || [https://yadi.sk/i/J_j0Pcmn3QbYWm клац] || Понятие асимптотического времени работы алгоритма. Сильно, слабо и псевдополиномиальное время работы. Обозначения $O$, $o$, $\Omega$, $\omega$
|---
| 2 ноябр || [https://yadi.sk/i/eqF6qtJb3QbYWq клац] || Совместное решение задач по теории вероятностей.
|-
| 8 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац] || Теоретическое домашнее задание по теме "Вероятности и математическое ожидание", приём задач.
|-
| 9 ноября || сурс || Первый короткий контест.
|-
| 15 ноября || None || Обсуждение методов тестирования программ.
|-
| 16 ноября || [https://yadi.sk/i/Cc69A0pf3QbYWu клац] || Совместное решение задач на алгоритмы сортировки и поиска порядковой статистики.
|-
| 22 ноября || [https://yadi.sk/i/lspn_0Sk3QbYWw клац] || Теоретическое домашнее задание по теме "Упорядоченные данные, элементарные стурктуры данных", приём задач.
|-
| 23 ноября || сурс || Второй короткий контест.
|-
| 29 ноября || [https://yadi.sk/i/1H-uuwNz3QbYWy клац] || Разбор задач первого теоретического домашнего задания. Совместное решение задач на элементарные структуры данных и двоичные кучи.
|-
| 30 ноября || [https://yadi.sk/i/JNFXns9f3QbYX2 клац] || Теоретическое домашнее задание по теме "Кучи, амортизационный анализ", приём задач.
|-
| 6 декабря || [https://yadi.sk/i/Ix221PIa3QbYX4 клац] || Подготовка к контрольной, совместное решение задач на различные темы.
|-
| 7 декабря || None || Контрольная работа за текущий модуль на две пары.
|-
| 13 декабря || [https://yadi.sk/i/_yJhrJ4q3QbYX6 клац] || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|}

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Четверг 16.40-18.00 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 15.10-16.30 + офис Яндекса по договоренности
|-
|}

== Учебные контесты ==

==Листики==
[https://yadi.sk/d/Spaj2IdG3QbYTG Все листки на Яндекс.Диске]

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

2017-12-14T02:32:42Z

Biryuk: /* Семинары */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно)
|-
| Теоретические задачи || Введение в теорвер и анализ алгоритмов || || ||
|-
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 ноября || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|}

== Семинары ==
{| class="wikitable"
|-
! Дата !! Материалы !! Тема
|-
| 1 ноября || [https://yadi.sk/i/J_j0Pcmn3QbYWm клац] || Понятие асимптотического времени работы алгоритма. Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, TODO: тут скопируй Омега большое, Омега малое и тета
|-
| 2 ноябр || [https://yadi.sk/i/eqF6qtJb3QbYWq клац] || Совместное решение задач по теории вероятностей.
|-
| 8 ноября || [https://yadi.sk/i/2O2EL5WV3QbYWs клац] || Теоретическое домашнее задание по теме "Вероятности и математическое ожидание", приём задач.
|-
| 9 ноября || сурс || Первый короткий контест.
|-
| 15 ноября || None || Обсуждение методов тестирования программ.
|-
| 16 ноября || [https://yadi.sk/i/Cc69A0pf3QbYWu клац] || Совместное решение задач на алгоритмы сортировки и поиска порядковой статистики.
|-
| 22 ноября || [https://yadi.sk/i/lspn_0Sk3QbYWw клац] || Теоретическое домашнее задание по теме "Упорядоченные данные, элементарные стурктуры данных", приём задач.
|-
| 23 ноября || сурс || Второй короткий контест.
|-
| 29 ноября || [https://yadi.sk/i/1H-uuwNz3QbYWy клац] || Разбор задач первого теоретического домашнего задания. Совместное решение задач на элементарные структуры данных и двоичные кучи.
|-
| 30 ноября || [https://yadi.sk/i/JNFXns9f3QbYX2 клац] || Теоретическое домашнее задание по теме "Кучи, амортизационный анализ", приём задач.
|-
| 6 декабря || [https://yadi.sk/i/Ix221PIa3QbYX4 клац] || Подготовка к контрольной, совместное решение задач на различные темы.
|-
| 7 декабря || None || Контрольная работа за текущий модуль на две пары.
|-
| 13 декабря || [https://yadi.sk/i/_yJhrJ4q3QbYX6 клац] || Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
|}

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Четверг 16.40-18.00 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 15.10-16.30 + офис Яндекса по договоренности
|-
|}

== Учебные контесты ==

==Листики==
[https://yadi.sk/d/Spaj2IdG3QbYTG Все листки на Яндекс.Диске]

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

2017-12-14T02:18:33Z

Biryuk: /* Листики */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно)
|-
| Теоретические задачи || Введение в теорвер и анализ алгоритмов || || ||
|-
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 ноября || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|}

== Семинары ==

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Четверг 16.40-18.00 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 15.10-16.30 + офис Яндекса по договоренности
|-
|}

== Учебные контесты ==

==Листики==
[https://yadi.sk/d/Spaj2IdG3QbYTG Все листки на Яндекс.Диске]

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

2017-12-14T01:29:52Z

Biryuk: /* Лекции */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно)
|-
| Теоретические задачи || Введение в теорвер и анализ алгоритмов || || ||
|-
|}

== Лекции ==

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 ноября || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|}

== Семинары ==

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Четверг 16.40-18.00 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 15.10-16.30 + офис Яндекса по договоренности
|-
|}

== Учебные контесты ==

==Листики==

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

2017-12-14T01:28:32Z

Biryuk: /* Сроки выполнения заданий */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно)
|-
| Теоретические задачи || Введение в теорвер и анализ алгоритмов || || ||
|-
|}

== Лекции ==

== Семинары ==

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Четверг 16.40-18.00 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 15.10-16.30 + офис Яндекса по договоренности
|-
|}

== Учебные контесты ==

==Листики==

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

2017-12-14T01:28:02Z

Biryuk: /* Лекции */

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно)
|-
| Теоретические задачи || Введение в теорвер и анализ алгоритмов || || ||
|-
|}

{| class="wikitable"
|-
! Номер !! Дата лекции !! Темы
|-
| 1 || 1 ноября || Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
|-
| 2 || 2 ноября || Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
|-
| 3 || 8 ноября || Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
|-
| 4 || 15 ноября || Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
|-
| 5 || 16 ноября || Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
|-
| 6 || 22 ноября || Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
|-
| 7 || 29 ноября || k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
|-
| 8 || 30 ноября || Биномиальный и фибоначчиевы пирамиды.
|-
| 9 || 6 декабря || Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
|-
| 10 || 13 ноября || Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
|}
== Лекции ==

== Семинары ==

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Четверг 16.40-18.00 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 15.10-16.30 + офис Яндекса по договоренности
|-
|}

== Учебные контесты ==

==Листики==

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

2017-11-15T16:22:23Z

Biryuk:

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1SdLZuYT-vNoYIYrG4bVSAPPipYMDNEM1nBC5qPfMjtY Текущая успеваемость]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно)
|-
| Теоретические задачи || Введение в теорвер и анализ алгоритмов || || ||
|-
|}

== Лекции ==

== Семинары ==

== Длинные контесты ==

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 171-1 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 171-2 ||
|-
| [https://www.hse.ru/org/persons/ Иван Смирнов] || 173-1 ||
|-
| [https://www.hse.ru/org/persons/ Артем Жук] || 173-2 ||
|-
| Данила Кутенин || || Четверг 16.40-18.00 + офис Яндекса по договоренности
|-
| Валентин Бирюков || || Вторник, 15.10-16.30 + офис Яндекса по договоренности
|-
|}

== Учебные контесты ==

==Листики==

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

2017-11-15T16:21:01Z

Biryuk: /* Преподаватели и ассистенты */

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

2017-11-15T16:20:25Z

Biryuk:

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

2017-11-15T15:53:04Z

Biryuk: Обновили по прошлому году

'''Лектор:''' [https://www.hse.ru/org/persons/164692936 Глеб Олегович Евстропов]

[https://yadi.sk/i/FI1FSYuSxx3LN Предполагаемая программа на 4 модуля]

[https://docs.google.com/spreadsheets/d/1reWEDjY6anDIkrcsq1uEYP2CSeofdQjnnuSuVMxiGQo/edit?usp=sharing Текущая успеваемость]

[https://contest.yandex.ru/hse_algo_pilot_2017 Результаты коротких контестов]

== Формула выставления итоговой оценки ==
В первый отчетный период, состоящий из 2 и 3 модулей 2016-17 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

* Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

* Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, '''но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные'''. Дорешивание длинных контестов доступно дополнительно в течение некоторого периода после его окончания (до двух недель), сданная в дорешивание задача оценивается в 0.5 балла.

* Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

* Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

* В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

* За экзамен студент получает оценку от 0 до 10.

* Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

== Сроки выполнения заданий ==

{| class="wikitable"
|-
! Тип задания !! Тема !! Дата выдачи !! Сроки выполнения до (включительно)
|-
| Длинный контест || Хеширование, сбалансированные деревья, прочие структуры данных || 23 января 2017 || 13 февраля 2017, дорешивание до 27 февраля 2017
|-
| Теоретические задачи || Деревья отрезков, LCA, разное || 19 января 2017 || 2 февраля 2017 ||
|-
| Короткий контест || Разное || 18 января 2017 || 25 марта 2017 (дорешивание)
|-
| Теоретические задачи || Сбалансированные деревья поиска || 11 января 2017 || 25 января 2017 ||
|-
| Теоретические задачи || Фиб. пирамиды, хеширование, амортизационный анализ || 7 декабря 2016 || 21 декабря 2016 ||
|-
| Короткий контест || Разное || 30 ноября 2016 || 25 марта 2017 (дорешивание)
|-
| Теоретические задачи || Элементарные структуры и пирамиды || 25 ноября 2016 || 9 декабря 2016 ||
|-
| Длинный контест || Разное || 22 ноября 2016 || 6 декабря 2016, дорешивание до 20 декабря 2016
|-
| Теоретические задачи || Сортировки и порядковые статистики || 18 ноября 2016 || 2 декабря 2016 ||
|-
| Короткий контест || Разное || 16 ноября 2016 || 25 марта 2017 (дорешивание)
|-
| Теоретические задачи || Введение в теорвер и анализ алгоритмов || 11 ноября 2016 || 25 ноября 2016 ||
|-
|}

== Лекции ==

* 2 ноября 2016. Структура курса, его концепция и задачи. Введение в теорию вероятностей, понятие вероятностного пространства для случая конечного множества элементарных исходов. Условная вероятность, полная группа события. Понятие геометрической вероятности. '''[https://yadi.sk/i/HE2uuFrpyHXXE Заметки.]'''

* 9 ноября 2016. Продолжение введения в теорию вероятностей. Понятие случайной величины и математического ожидания в случае конечно множества элементарных исходов. Индикаторные случайные величины. Математическое ожидание случайной величины и его линейность. Неравенства Маркова и Чебышёва. Примеры вероятностного анализа простых случайных структур.

* 11 ноября 2016. Методы доказательства корректности алгоритмов на примере квадратичных сортировок. Тривиальные методы оценки времени работы. Индуктивный метод доказательства рекуррентных оценок сложности. Сортировка слиянием и быстрая сортировка. Поиск порядковой статистики.

* 18 ноября 2016. Нижняя оценка на сложность сортировки, использующей только сравнение элементов. Сортировка подсчётом, цифровая (поразрядная) сортировка, карманная сортировка. Линейность времени работы карманной сортировки на случайных данных. Метод бинарного поиска.

* 23 ноября 2016. Элементарные структуры данных: массив, отсортированный массив, односвязный и двусвязный списки, стек, очередь, дек. Метод амортизационного анализа методом кредитов на примере сливаемых отсортированных массивов и реализации очереди через два стека. Двоичная и k-ичная кучи.

* 2 декабря 2016. Техника приливания меньшего к большему для объединения двух куч. Биномиальные деревья и сливаемые пирамиды на их основе. Амортизационный анализ методом потенциалов, расширяемый массив, дек с минимумом на трёх стеках.

* 7 декабря 2016. Фибоначчиевы пирамиды.

* 7 декабря 2016. Хеширование, парадокс дней рождений, полиномиальный хеш и его применения.

* 9 декабря 2016. Хеш-таблицы, открытая и закрытая адресация. Способы сканирования. Масштабирование размера и деамортизация оценок.

* 16 декабря 2016. Сбалансированные деревья поиска. Декартово дерево. Декартово дерево по неявному ключу.

* 11 января 2017. Задачи о запросах на отрезке. Префиксные суммы, разреженные таблицы, дерево отрезков.

* 12 января 2017. Групповые операции в деревьях отрезков. Двумерные деревья отрезков.

* 19 января 2017. Задача о наименьшем общем предке. Сведение к задаче минимума на отрезке. Алгоритм Фараха-Колтона и Бендера решения задачи минимума на отрезке.

* 25 января 2017. Персистентные структуры данных. Персистентный стек, персистентный массив на основе дерева отрезков, персистентное декартово дерево и его основные операции.

* 26 января 2017. Перебор комбинаторных объектов. Введение в динамическое программирование, построение объекта по номеру и получение номера по объекту. Динамическое программирование на подотрезках.

== Семинары ==

* 2 ноября 2016. Некоторые необходимые обозначения и термины для описания времени работы (и других используемых ресурсов) алгоритма. Совместное решение '''[https://yadi.sk/i/7ZcuFsSWyHXd7 задач.]'''

* 9 ноября 2016. Совместное решение комбинаторных и геометрических '''[https://yadi.sk/i/PvIzV8QRyiV9n задач]''' по теории вероятностей.

* 11 ноября 2016. Приём '''[https://yadi.sk/i/xVmmyboeyiW43 задач]''' первого теоретического домашнего задания, темы: введение в теорию вероятностей, анализ алгоритмов.

* 16 ноября 2016. Короткий личный '''[https://contest.yandex.ru/contest/3437/enter/ контест]'''.

* 18 ноября 2016. Приём '''[https://yadi.sk/i/ecgtjaRTzHyYc задач]''' второго теоретического домашнего задания, темы: сортировки и порядковые статистики.

* 23 ноября 2016. Теоретический семинар по методам тестирования и отладки программ.

* 25 ноября 2016. Приём '''[https://yadi.sk/d/ypNSmk2332eJ6N задач]''' третьего теоретического домашнего задания, темы: элементарные структуры данных, пирамиды.

* 30 ноября 2016. Короткий личный '''[https://contest.yandex.ru/contest/3518/enter/ контест]'''.

* 2 декабря 2016. Разбор задач первого теоретического домашнего задания. Совместное решение '''[https://yadi.sk/i/ksHHKXJ232eJhV задач]''' для подготовки к контрольной работе.

* 7 декабря 2016. Приём '''[https://yadi.sk/i/RoYQOe-032eJm9 задач]''' четвёртого теоретического домашнего задания, темы: фибоначчиевы пирамиды, хеширование, амортизационный анализ.

* 9 декабря 2016. Разбор задач второго теоретического домашнего задания. '''[https://yadi.sk/i/zyx8ffL_3C5aTd Тест]''' для подготовки к контрольной работе.

* 14 декабря 2016. Контрольная '''[https://yadi.sk/i/sAq04BzI3C5cRb работа]''' за второй модуль.

* 16 декабря 2016. Разбор задач контрольной работы и третьего теоретического домашнего задания.

* 21 декабря 2016. Показ работ первой контрольной, апелляции.

* 11 января 2017. Приём '''[https://yadi.sk/i/nQaxYYC53C5otj задач]''' пятого теоретического домашнего задания, темы: сбалансированные деревья поиска, декартовы деревья.

* 12 января 2017. Разбор задач четвёртого теоретического домашнего задания.

* 18 января 2017. Короткий личный '''[https://contest.yandex.ru/contest/3721/enter/ контест]'''.

* 19 января 2017. Приём '''[https://yadi.sk/i/nQaxYYC53C5otj задач]''' шестого теоретического домашнего задания, темы: запросы на отрезках, наименьший общий предок.

* 25 января 2017. Теоретический семинар по методам оптимизации программ.

* 26 января 2017. Разбор задач пятого теоретического домашнего задания. Совместное решение '''[https://yadi.sk/i/yph6ix7d3C5xir задач]''' на персистентные структуры.

== Длинные контесты ==

===Сортировки, порядковые статистики, элементарные структуры===

Ссылка на контест: [https://contest.yandex.ru/contest/3478/problems/ https://contest.yandex.ru/contest/3478/problems/].
Старт: 22 ноября в 21:00.

Контест идет 2 недели + 3 часа, после чего можно будет сдавать задачи еще 2 недели, но с коэффициентом 0.5. Это будет отражено в баллах
за задачу в контесте.

По первым двум задачам нужно пройти ревью. Это необходимое условие для получения баллов за остальные задачи. Ревью проводится
в системе [http://anytask.org/course/122 Anytask]. Перед отправкой задачи на ревью '''обязательно''' укажите в настройках свой логин в
контесте (тот, который вы зарегистрировали сами, а не тот, который был выдан в 1-ом модуле), если вы еще этого не сделали.

В задачах с ревью используется другая схема тестирования. Компилируется 2 варианта вашего решения --- с включенными санитайзерами
и без. На маленьких тестах будет запускаться решение с санитайзерами.

Полная строка компиляции (с санитайзерами):
clang++ -fsanitize=address,undefined -x c++ -std=c++14 -O2 -Wall -Werror

Обратите внимание на -Werror --- компилятор не должен выдавать никаких предупреждений при компиляции. Стандарт С++14.

===Хеши, сбалансированные деревья, деревья отрезков и прочие структуры===

Ссылка на контест: [https://contest.yandex.ru/contest/3744/enter/ https://contest.yandex.ru/contest/3744/enter/].
Старт: 23 января в 18:00.

Контест идет 3 недели + 6 часов, после чего можно будет сдавать задачи еще 2 недели, но с коэффициентом 0.5. Обратите внимание, что в контесте 9 задач, но оценку 10 можно получить и за 8 из них (одна бонусная).

По первым двум задачам необходимо пройти ревью в anytask, чтобы получить баллы за остальные задачи, как и в прошлом домашнем задании. Ревью должно быть зачтено к концу дорешивания контеста, т.е. за 5 недель, поэтому не затягивайте с его сдачей.

По второй задаче также необходимо сдать устную часть лично Глебу: описание используемого алгоритма (т.е. дерева) с доказательством.

Некоторые технические моменты по задачам:

1. В обеих задачах на ревью вам может потребоваться реализовать оператор =. Чтобы избежать распространенных ошибок, почитайте как это делать правильно здесь: [https://en.wikibooks.org/wiki/More_C++_Idioms/Copy-and-swap https://en.wikibooks.org/wiki/More_C++_Idioms/Copy-and-swap].

2. Если в первой задаче вы реализуете итераторы, то не нужно дублировать код для const и не-const итераторов, используйте шаблоны и/или наследование. Однако в этой задаче можно избежать необходимости писать свои итераторы, если правильно хранить данные.

3. Разберитесь в константности методов: [http://stackoverflow.com/questions/751681/meaning-of-const-last-in-a-c-method-declaration http://stackoverflow.com/questions/751681/meaning-of-const-last-in-a-c-method-declaration].

4. Разберитесь, в чем отличие списков инициализации конструктора от ининциализации в теле конструктора. А чтобы не дублировать код, ознакомьтесь с делегированием в конструкторах. Все это можно найти здесь: [http://en.cppreference.com/w/cpp/language/initializer_list http://en.cppreference.com/w/cpp/language/initializer_list].

5. В первых двух задачах запрещено использовать map/set, а также их unordered-аналоги. Все остальные контейнеры использовать можно. В остальных задачах разрешено все.

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

===Динамическое программирование, meet in the middle===

Ссылка на контест: [https://contest.yandex.ru/contest/4222/enter/ https://contest.yandex.ru/contest/4222/enter/].
Старт: 18 марта 15:00.
Этот контест идет в зачет 4 модуля.

Контест идет 18 дней + 9 часов, т.е. дедлайн ночью с 5 на 6 апреля. После этого как обычно можно сдавать задачи еще 2 недели
с коэффициентом 0.5. Задача G стоит в 2 раза дороже остальных и чтобы получить баллы за остальные, сдавать ее необязательно. Однако чтобы получить за нее баллы, необходимо пройти ревью. Ревью должно быть зачтено к концу дорешивания контеста, поэтому не затягивайте с его сдачей.

===Остовы, обходы графов, строковые алгоритмы===
Ссылка на контест: [https://contest.yandex.ru/contest/4528/problems/ https://contest.yandex.ru/contest/4528/problems/].
Старт: 7 мая в 16:00.

Контест идет 2 недели + 8 часов с дорешиванием еще 2 недели. По первой задаче необходимо пройти ревью в anytask, чтобы получить баллы за остальные задачи. Ревью должно быть зачтено к концу дорешивания.

===Потоки, геометрия, теория чисел===
Ссылка на контест: [https://contest.yandex.ru/contest/4605/problems/ https://contest.yandex.ru/contest/4605/problems/].
Старт: 6 июня в 00:00.

== Рекомендуемая литература ==
# Кормен, Лейзерсон, Ривест, Штайн. ''Алгоритмы: построение и анализ''
# [http://biblio.mccme.ru/node/5066/shop Дасгупта, Пападимитриу, Вазирани. ''Алгоритмы'']
# Корте, Фиген. ''Комбинаторная оптимизация. Теория и алгоритмы''

==Преподаватели и ассистенты==
{| class="wikitable"
|-
! Преподаватель !! Подгруппа !! Присутственные часы
|-
| [https://www.hse.ru/org/persons/164692936 Глеб Евстропов] || 161-1 || Среда, 13:40 - 15:10, ауд. 505
|-
| [https://www.hse.ru/org/persons/137640601 Павел Мельничук] || 161-2 ||
|-
| [https://www.hse.ru/org/persons/165212894 Станислав Артюхин] || 163-1 ||
|-
| [https://www.hse.ru/org/persons/144545940 Алексей Панов] || 163-2 ||
|-
| Александр Тиунов || ||
|-
| Александр Зойкин || || Среда, 14:20-15:40
|-
| Валентин Бирюков || || Среда, 12:00-13:00, ауд. 618
|-
|}

== Учебные контесты ==

==Листики==
https://yadi.sk/d/uN86f35WyeryR

==Тесты для командного контеста==
https://yadi.sk/d/0-YawHpC3Fqq2c

О факультете

2017-11-15T15:52:02Z

Biryuk: /* Курсы за 2017/18 учебный год */

__NOTOC__

== Учебные курсы факультета компьютерных наук==

=== Курсы за 2017/18 учебный год ===
{| class="wikitable"
|-
! 1 курс !! 2 курс !! 3 курс !! 4 курс !! майноры
|-
|

[[Математический_анализ_на_ПМИ_2017/2018_(пилотный_поток) | Математический анализ на ПМИ 2017/2018 (пилотный поток)]]

[[Математический_анализ_на_ПМИ_2017/2018_(основной_поток) | Математический анализ на ПМИ 2017/2018 (основной поток)]]

[[Основы_и_методология_программирования_на_ПМИ_2017/2018_(пилотный_поток,_1_модуль) | Основы и методология программирования на ПМИ 2017/2018 (пилотный поток, 1 модуль)]]

[[Основы_и_методология_программирования_на_ПМИ_2017/2018_(основной_поток,_2_модуль) | Основы и методология программирования на ПМИ 2017/2018 (основной поток, 2 модуль)]]

[[Линейная_алгебра_и_геометрия_на_ПМИ_2017/2018_(пилотный_поток) | Линейная алгебра и геометрия на ПМИ (пилотный поток)]]

[[Линейная_алгебра_и_геометрия_на_ПМИ_2017/2018_(основной_поток) | Линейная алгебра и геометрия на ПМИ (основной поток)]]

[[Дискретная_математика_1_2017/2018 | Дискретная математика-1 на ПМИ]]

[[Алгоритмы и структуры данных 1 | Алгоритмы и структуры данных – 1 (пилотный поток)]]

||
[[Теория_вероятностей_2017/2018_(основной_поток) | Теория вероятностей на ПМИ (основной поток)]]

[[Теория_вероятностей_2017/2018_(пилотный_поток) | Теория вероятностей на ПМИ (пилотный поток)]]

[[Математический анализ-3 на ПМИ_2017/2018_(основной_поток) | Математический анализ-3 на ПМИ (основной поток)]]

[[Математический анализ на ПМИ_2017/2018 | Математический анализ-3 на ПМИ (пилотный поток)]]

[[DM2-pilot2017/2018 | Дискретная математика-2 на ПМИ (пилотный поток)]]

[[DM_2_2017_2018 | Дискретная математика-2 на ПМИ (основной поток)]]

[[Алгоритмы и структуры данных_2_2017/2018 | Алгоритмы и структуры данных – 2 на ПМИ (основной поток)]]

[[Факультативы "Дополнительные главы линейной алгебры" и "Практическая линейная алгебра"_2017/2018 | Дополнительные главы линейной алгебры на ПМИ (факультатив)]]
||
[[Машинное_обучение_1 | Машинное обучение 1 на ПМИ]]

[[Численные_методы_2017 | Численные методы]]

[[Прикладная_статистика_в_машинном_обучении | Прикладная статистика в машинном обучении]]

[[Theory_of_Computing | Theory of Computing, AMI]]

[[Statistical_learning_theory | Introduction to statistical learning theory]]

[[Основные_методы_анализа_данных_(специализация_АДИС) | Основные методы анализа данных на ПМИ]]

[[Параллельные и распределенные вычисления 2017 | Параллельные и распределенные вычисления]]

[[Анализ неструктурированных данных]]

[[Безопасность компьютерных систем 2017 | Безопасность компьютерных систем]]

[[НИС_Распределенные_системы_(3_курс,_2017) | НИС Распределенные системы]]

[[НИС_Машинное_обучение_и_приложения_2017/2018 | НИС Машинное обучение и приложения]]
||

[[Безопасность компьютерных систем 2017 | Безопасность компьютерных систем]]

[[Философия_науки_2017 | Философия науки]]

[[НИС_Распределенные_системы_(4_курс,_2017) | НИС Распределенные системы]]

[[НИС_Машинное_обучение_и_приложения_2017/2018 | НИС Машинное обучение и приложения]]

[[Анализ неструктурированных данных]]

[[Байесовские методы машинного обучения 2017 | Байесовские методы машинного обучения]]

||

[[Современные методы машинного обучения (курс майнора) 2017/2018]]

[[Введение в программирование (курс майнора) 2017/2018]]

|}

== Курсы в рамках проекта [https://www.hse.ru/dataculture/ Data Culture]==

[[Цифровая_грамотность|Цифровая грамотность (факультет гуманитарных наук)]] 
[[Машинное обучение (факультет экономических наук)|Машинное обучение (факультет экономических наук)]] 
[[Программирование (python) для лингвистов | Программирование (python) для лингвистов (факультет гуманитарных наук)]] 
[[Извлечение и анализ интернет-данных | Извлечение и анализ интернет-данных (факультет экономических наук)]] 
[[Анализ больших данных в социальных науках (ФСН, 2017) | Анализ больших данных в социальных науках (ФСН, 2017)]] 
[[Информационные_технологии_в_деятельности_юриста|Информационные технологии в деятельности юриста (Факультет права)]] 
[[Машинное_обучение_для_лингвистов|Машинное обучение (магистратура Школы лингвистики)]]

=== Курсы за 2016/17 учебный год ===
{| class="wikitable"
|-
! 1 курс !! 2 курс !! 3-4 курс !! майноры
|-
|

[[Математический анализ на ПМИ_2016/2017 | Математический анализ на ПМИ (пилотный поток)]]

[[Линейная алгебра и геометрия_2016/2017 | Линейная алгебра и геометрия на ПМИ]]

[[Дискретная_математика_1_2016/2017 | Дискретная математика-1 на ПМИ]]

[[Основы и методология программирования_2016/2017_пилотный_поток | Основы и методология программирования на ПМИ (пилотный поток)]]

[[Основы и методология программирования_2016/2017 | Основы и методология программирования на ПМИ (основной поток)]]

[[Алгоритмы_и_структуры_данных_на_ПМИ_(пилотный_поток) | Алгоритмы и структуры данных на ПМИ (пилотный поток)]]

[[Алгоритмы_и_структуры_данных_на_ПМИ_(основной_поток) | Алгоритмы и структуры данных на ПМИ (основной поток)]]

[[Алгебра_на_ПМИ_2016/2017 | Алгебра на ПМИ]]

[http://hsealgebra17.wikidot.com/ Алгебра на ПИ]

||

[[Математический анализ_2016/2017 | Математический анализ-3 на ПМИ (основной поток)]]

[[Математически_анализ_3_на_ПМИ_(пилотный_поток) | Математический анализ-3 на ПМИ (пилотный поток)]]

[[DM_2_2016_2017 | Дискретная математика-2 на ПМИ (основной поток)]]

[[Дискретная математика_2_2016/2017 | Дискретная математика-2 на ПМИ (пилотный поток)]]

[[Алгоритмы и структуры данных_2_2016/2017 | Алгоритмы и структуры данных – 2 на ПМИ (основной поток)]]

[[Теория вероятностей_2016/2017 | Теория вероятностей на ПМИ (основной поток)]]

[[Теория_вероятностей_2016/2017_(пилотный_поток) | Теория вероятностей на ПМИ (пилотный поток)]]

[[Архитектура_компьютеров_и_операционные_системы_2016/2017 | Архитектура компьютеров и операционные системы]]

[[Факультатив_теория_вычислений_2016/2017 | Факультатив теория вычислений на ПМИ]]

[[Дополнительные_главы_теории_вероятностей_(факультатив,_2017) | Дополнительные главы теории вероятностей (факультатив)]]

[[Дифференциальные_уравнения_(2_курс,_2016/2017) | Дифференциальные уравнения]]

[[Математическая_статистика_2016/2017_(пилотный_поток) | Математическая статистика на ПМИ (пилотный поток)]]

[[Архитектура_компьютеров_и_операционные_системы_2016/2017 | Архитектура компьютеров и операционные системы ]]

||

[[НИС_Машинное_обучение_и_приложения_2016/2017 | НИС Машинное обучение и приложения на ПМИ]]

[[Машинное_обучение_1/2016_2017 | Машинное обучение 1 на ПМИ]]

[[Машинное_обучение_2 | Машинное обучение 2 на ПМИ]]

[[Прикладной_статистический_анализ_данных | Прикладной статистический анализ данных на ПМИ]]

[[Численные_методы_в_анализе_данных | Численные методы в анализе данных на ПМИ]]

[http://www.machinelearning.ru/wiki/index.php?title=Статистика_случайных_процессов_(курс_лекций,_ФКН_ВШЭ) Вероятностные модели и статистика случайных процессов на ПМИ]

[http://www.machinelearning.ru/wiki/index.php?title=Opt Методы оптимизации на ПМИ (специализации МОП и РС)]

[[Методы_оптимизации_(весна_2017)|Методы оптимизации 2 (дискретная оптимизация)]]

[[НИС_Распределенные_системы_(осень_2016) | НИС Распределенные системы]]

[[Анализ и верификация алгоритмов биржевой торговли | Анализ и верификация алгоритмов для систем биржевой торговли ]]

[[Программирование_на_графических_процессорах | Программирование на графических процессорах]]

[[ЯРПО | Языки разработки ПО (курс по выбору) на ПМИ]]

[[Data analysis (Software Engineering) 2017 | Data analysis на ПИ]]

[[Базы данных 2 | Базы данных 2 ]]

[[Компьютерные сети 2 | Компьютерные сети 2]]

[[Машинное_обучение_на_больших_данных | Машинное обучение на больших данных на ПМИ]]

||

[[Современные_методы_машинного_обучения_(курс_майнора) | Современные методы машинного обучения (курс майнора)]]

[[Майнор_Интеллектуальный_анализ_данных/Введение_в_программирование_2016/2017 | Введение в программирование (курс майнора)]]

[[Майнор Интеллектуальный анализ данных/Введение в анализ данных | Введение в анализ данных (курс майнора)]]

[[Майнор Интеллектуальный анализ данных/Прикладные задачи анализа данных| Прикладные задачи анализа данных (курс майнора)]]

|}

{|width=100%
|style="vertical-align:top;"|



=== Курсы за 2015/16 учебный год ===
{|
|-
| [[Технологии программирования|Технологии программирования на ПМИ]]
|-
|[[ОиМП-2015|Основы и методология программирования на ПМИ]]
|-
|[[Алгоритмы и структуры данных 2016]]
|-
|[[Линейная алгебра и геометрия_2015/2016 | Линейная алгебра и геометрия на ПМИ]]
|-
|[[Алгебра_2015/2016 | Алгебра на ПМИ]]
|-
|[http://hsealgebra.wikidot.com/ Алгебра на ПИ]
|-
|[[Компьютерные системы]]
|-
|[[Математический анализ на ПМИ_2015/2016 | Математический анализ на ПМИ]]
|-
|[[Факультатив_Матпрактикум | Матпрактикум (факультатив) на ПМИ]]
|-
|[[Data analysis (Software Engineering)]] 
|-
|[[Майнор Интеллектуальный анализ данных/Введение в программирование|Введение в программирование (курс майнора) на ПМИ]]
|-
|[[Майнор Интеллектуальный анализ данных/Введение в анализ данных/2015-2016|Введение в анализ данных (курс майнора) на ПМИ]]
|-
|[[НИС Машинное обучение и приложения|НИС Машинное обучение и приложения на ПМИ]]
|-
|[[Архитектура компьютеров и системное программирование (ПМИ_4, 2015/2016)|Архитектура компьютеров и системное программирование (4 курс)]]
|-
|[[Дифференциальные уравнения (2 курс, 2015/2016)| Дифференциальные уравнения]]
|-
|[[Введение в VBA|Введение в VBA]]
|}

|style="vertical-align:top;"|



=== Курсы за 2014/15 учебный год ===
{|
|-
|[[Основы и методологии программирования]] 
|-
|[[Алгоритмы и структуры данных 2015 | Алгоритмы и структуры данных]] 
|-
|[[Анализ данных (Программная инженерия)]] 
|-
|[[Алгебра_2014/2015 | Алгебра]] 
|-
|[[Magolego_sna_2015| MAGoLEGO Social Network Analysis]]
|}

==== Проектная работа ====
{|
|-
|[[Проектная работа]] 
|-
|[[Учебная практика 1 курс (2016)]]
|-
|[[Проектная работа 2 курс (2016)]]
|}


|}

== Мероприятия факультета компьютерных наук ==
=== Summer School 2015 ===
[[Introduction to Natural Language Processing|Introduction to Natural Language Processing]]
#[[Lecture 1. Introduction|Introduction]]
#[[Lecture 2. Tokenization and word counts|Tokenization and word counts]]
#[[Lecture 3. POS tagging. Key word and phrase extraction|POS tagging. Key word and phrase extraction]]
#[[Lecture 4. Parsing|Parsing]]
#[[Lecture 5. Language sources|Language sources]]
#[[Lecture 6. Synonyms and near-synonyms detection|Synonyms and near-synonyms detection]]
#[[Lecture 8. Suffix trees for NLP|Suffix trees for NLP]]
#[[NLP References|References]]

== Архив ==
* [[Учебная практика 1 курс (2015)]]