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

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

2019-04-22T13:10:26Z

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

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

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

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


# '''29 октября.''' Задача сортировки. [https://www.dropbox.com/s/zc30m8ihxlde05d/algo1-sorting.pdf?dl=0 Сортировка вставками:] анализ корректности с использованием инварианта цикла и времени работы. Асимптотические обозначения. Циклическая сортировка.
# '''31 октября.''' Стратегия "Разделяй и властвуй". [https://www.dropbox.com/s/5anaz9kwebqcrlw/algo2-mergesort.pdf?dl=0 Сортировка слиянием.] Доказательство корректности рекурсивных алгоритмов по индукции. Оценка времени работы рекурсивных алгоритмов при помощи рекуррентных соотношений: дерево рекурсии, итерационный метод, основная теорема.
# '''7 ноября.''' Решение рекуррентных соотношений методом подстановки. Линейный алгоритм поиска ''k''-ой порядковой статистики.
# '''12 ноября.''' Нижние оценки для сортировки сравнениями. Сортировка подсчетом, блочная сортировка, поразрядная сортировка.
# '''14 ноября.''' Рандомизированные алгоритмы. Лас-Вегас и Монте-Карло. Краткое введение в теорию вероятностей: вероятностные пространства, события, случайные переменные, математическое ожидание и его линейность, геометрические случайные переменные. Алгоритмы Bogosort и Quicksort.
# '''19 ноября.''' Таблицы с прямой адресацией. Хеш-таблицы. Хеш-функции. Универсальные семейства хеш-функций. Открытая адресация.
# '''21 ноября.''' Двоичные деревья поиска. Семейства сбалансированных деревьев. Красно-черные деревья.
# '''26 ноября.''' Вставка элемента в красно-черное дерево. Ориентированные и неориентированные графы. Представление графов в памяти компьютера: матрицы смежности и списки смежности. Поиск в ширину и в глубину.
# '''28 ноября.''' Вычисление расстояний при помощи обхода в ширину. Вычисление компонент связности в неориентированном графе и компонент сильной связности в ориентированном графе. Топологическая сортировка.
# '''3 декабря''' Кратчайшие пути во взвешенных графах. Алгоритм Дейкстры.
# '''5 декабря''' Динамическое программирование: алгоритмы Беллмана – Форда и Флойда – Уоршелла.
# '''10 декабря.''' ''Контрольная работа'' по материалам осенних лекций (29 октября – 28 ноября). В частности, в контрольной работе могут быть даны задачи на рекуррентные соотношения, хеш-таблицы, рандомизированные алгоритмы, а также задачи, похожие на [https://www.dropbox.com/s/jp2p6ugv9jqnesw/sample-quiz.pdf?dl=0 задачи для подготовки]. С собой можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. Контрольная состоится 10 декабря в 10:30 – 11:50 в ауд. 402 (группы 182 и 184) и в ауд. 622 (группы 185, 186, 187, 188 и 189). [https://docs.google.com/document/d/1S23E1XyRn0CrzOhjTRKhCaOHt1eIubnPOMDTDE-qYcY/edit?usp=sharing Те, кто пропустил контрольную работу по уважительной причине], смогут ее написать '''17 декабря''' в 16:40-18:00 в ауд. 622.
# '''12 декабря.''' Динамическое программирование: задача о рюкзаке, независимое множество максимального веса в дереве.
# '''17 декабря.''' Жадные алгоритмы, способы доказательства их корректности. Минимальные основные деревья. Алгоритм Прима.

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

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

==Экзамен==
Экзамен состоится 19 декабря в 15:10 – 18:00. На экзамене нужно будет решить несколько задач в системе Яндекс.Контест. Желательно прийти со своим ноутбуком. Если у вас нет такой возможности, отметьтесь, пожалуйста, [https://docs.google.com/document/d/1J4CEWPki0EcG0t4e31_NW13rzR168yO3Z8AMeLsbSHI/ здесь].

Те, кто собирается писать экзамен на своем ноутбуке, приходят в ауд. 317 (группы 182, 184, 185, 186) и в ауд. 205 (группы 187, 188, 189). Те, кому нужны компьютеры, приходят в ауд. 311.

=Третий модуль=
==Лекции==
понедельник, четверг 15:10 – 16:30, ауд. 622

# '''[https://www.dropbox.com/s/ybxc0ox2i1tniou/algo-2018-04-01-heap.pdf?dl=0 1 апреля.]''' Приоритетные очереди и их применение в алгоритмах Дейкстры и Прима. Реализация приоритетной очереди при помощи двоичной кучи.
# '''4 апреля.''' Три подхода к амортизационному анализу: групповой анализ, банковский метод и метод потенциалов (на примере двоичного счетчика и очереди на основе двух стеков).
# '''[https://www.dropbox.com/s/s7qlhopuewumwki/algo-2018-04-08-binomial-heap.pdf?dl=0 8 апреля.]''' Биномиальные кучи.
# '''11 апреля.''' Кучи Фибоначчи.
# '''16 апреля.''' Алгоритм Крускала и система непересекающихся множеств.
# '''18 апреля.''' Наименьшее значение в подмассиве: простые алгоритмы (линейный поиск, предподсчет всех возможных ответов), разбиение на блоки, разреженные таблицы, комбинирование структур данных для вычисления наименьших значений внутри блоков и наименьшего значения в массиве минимумов в блоках.

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

==Домашние задания==
# [https://official.contest.yandex.ru/contest/12530/problems/ Двоичная куча и ее применение] — с 8 по 14 апреля (со штрафом 50% — с 15 по 21 апреля). Требуется реализовать и использовать двоичную кучу при решении хотя бы двух задач.
# Домашнее задание состоит из [https://official.contest.yandex.ru/contest/12631/problems/ четырех задач контеста] и [https://www.dropbox.com/s/37qsinren5upywn/algo-hw-2.pdf?dl=0 шести задач], которые нужно решить письменно. Срок выполнения — 30 апреля.

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

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

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

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

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

=Оценки=
[https://docs.google.com/spreadsheets/d/13h-S-7rbMMMAnB0kWjlL9Qlo4CVBRIhq0wynAU1xiiE/edit?usp=sharing Таблицы с оценками]
==Второй модуль==
Текущая оценка: контрольная работа — 40%, домашние задания — 60%.

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

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

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

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

Цифровая грамотность(востоковедение)

2018-09-07T18:46:01Z

NicePizza:

== О курсе ==
Курс читается на 1 курсе ОП "Востоковедение", в 1 модуле. 
Литературу по курсу можно найти в программе учебной дисциплины [https://www.hse.ru/data/2018/08/28/1150116725/program-2183554889-JRUQA5DRea.pdf (ПУДе)]

=== Программные средства===
Для успешного освоения дисциплины, студент использует следующие программные средства:
* MS Excel
* MS Word
* MS PowerPoint
* [https://www.zotero.org/download/ Zotero]
* [https://www.mendeley.com/download-desktop/ Mendeley]

Студенты НИУ ВШЭ имеют право бесплатно использовать Microsoft Office 365 для образования, в том числе Word, Excel, PowerPoint, OneNote, Microsoft Teams и дополнительные учебные средства. У каждого студента есть корпоративная почта, при помощи которой открывается доступ к скачиванию офисных приложений.
Подробнее о том, как скачать Office 365 на свой компьютер, читайте в [https://www.hse.ru/data/2018/01/24/1163180977/%D0%90%D0%BA%D1%82%D0%B8%D0%B2%D0%B0%D1%86%D0%B8%D1%8F%20%D0%BF%D0%BE%D0%B4%D0%BF%D0%B8%D1%81%D0%BA%D0%B8%20MS%20Office365.pdf (инструкции)]

==Преподаватели==
===Лекции ведут:===
Бурова Маргарита Борисовна

* [mailto:mbburova@gmail.com E-mail]
* [https://vk.com/burrita VK Маргарита Бурова]
* telegram: @burritas

Курмуков Анвар Илдарович

*
*
*

===Семинары ведут:===
{| class="wikitable"
|-
! Группа !! Семинарист !! Ассистент
|-
| БВВ181 || Кротова Елена Борисовна, @Lena_Kr, [mailto:kroelebor@gmail.com mail] || Саломатин Юрий Владимирович, @Drizir, [mailto:yuvsalomatin@edu.hse.ru mail] ||
|-
| БВВ182|| Кротова Елена Борисовна, @Lena_Kr, [mailto:kroelebor@gmail.com mail] || Вельдяйкин Николай Олегович, @NickVeld, [mailto:noveldyaykin@edu.hse.ru mail]
|-
| БВВ183|| Кириллов Алексей Павлович, [mailto:KirillovAl@yandex.ru mail] ||
|-
| БВВ184|| Волосникова Марина Сергеевна, @marinamarina123, [mailto:mvolosnikova@gmail.com mail] || Черных Татьяна Олеговна, @tanicher, [mailto:tanufa2010@yandex.ru mail]
|-
| БВВ185|| Степанов Артём Алексеевич, @arstep, [mailto:stepartm@gmail.com mail]|| Турсунходжаев Агзамходжа Махсудхужаевич, @agzamg, [mailto:amtursunkhodzhaev@edu.hse.ru mail]
|}

== Материалы курса ==
===Лекции===

{| class="wikitable"
|-
! № !! Дата лекции!! Тема !! Презентация
|-
| 1 || || Структура курса, введение в анализ данных ||
|-
| 2 || || Поиск информации, виды данных ||
|-
| 3 || || Введение в статистический анализ данных ||
|-
| 4 || || Введение в статистический анализ данных ||
|-
| 5 || || Введение в статистический анализ данных ||
|-
| 6 || || Визуализация данных ||
|-
| 7 || || Визуализация данных ||
|-
| 8 || || Разбор кейсов ||
|-
| 9 || || Защита проекта ||

|}

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

==Критерии оценки знаний, навыков==
Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале. В диплом выставляется результирующая оценка по учебной дисциплине.

Оценка по курсу формируется из следующих составляющих:
* Домашнее задание 1 (оценивается от 0 до 10) – Одз1
* Домашнее задание 2 (оценивается от 0 до 10) – Одз2
* Домашнее задание 3 (оценивается от 0 до 10) – Одз3
* Самостоятельные работы (оцениваются от 0 до 10, вычисляется среднее арифметическоепо всем самостоятельным) – Оср
* Защита проекта (оценивается от 0 до 10) – Опроект

Результирующая оценка рассчитывается следующим образом:
Орез=0,15* Одз1 + 0,15* Одз2+ 0,15* Одз3+ 0,15* Опроект+ 0,4* Оср

Способ округления результирующей оценки по учебной дисциплине - арифметический. Проведение итогового экзамена не предусматривается.

=== Дедлайны===
Все домашние задания, самостоятельные работы и проект имеют жесткий дедлайн, который объявляется заранее. По решению преподавателя работы после дедлайна могут приниматься с понижением оценки.
Дедлайн по самостоятельным работам по решению преподавателя может быть продлен.

== Ведомости ==
* БВВ181
* БВВ182
* БВВ183
* БВВ184
* БВВ185