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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Материалы 3-го модуля)
Строка 206: Строка 206:
 
|}
 
|}
  
 +
=== 3 модуль ===
 +
 +
{| role="presentation" class="mw-collapsible wikitable"
 +
! Дата
 +
! Тип
 +
! Тема
 +
! Материалы
 +
! Видео
 +
|-
 +
| rowspan="2" | 10.01.2023 (вт)
 +
| Семинар
 +
| Антихештесты
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| [1] [Филипп]
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 12.01.2023 (чт)
 +
| Семинар
 +
| Деревья поиска
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| [2] [Филипп]
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 17.01.2023 (вт)
 +
| Семинар
 +
| Деревья поиска, запросы на отрезках
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| [3] ДД, доказательство высоты (?)
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 19.01.2023 (чт)
 +
| Семинар
 +
| Персистентность, запросы на отрезках
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| [4] Частичная персистентность
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 24.01.2023 (вт)
 +
| Семинар
 +
| Запросы на отрезках, персистентная очередь (бонус)
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| [5] List order maintenance (?)
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 26.01.2023 (чт)
 +
| Семинар
 +
| Задачи на деревья
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| [6] HLD (?)
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 31.01.2023 (вт)
 +
| Семинар
 +
| Простое ДП, задачи о рюкзаке
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| [7] Подсчёт количества клик в графе (?)
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 2.02.2023 (чт)
 +
| Семинар
 +
| Бонусный семинар — архитектура
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| Бонус (рассказ)
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 7.02.2023 (вт)
 +
| Семинар
 +
| ДП, переборы
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| [8] Переборы,альфа-бета отсечение
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 9.02.2023 (чт)
 +
| Семинар
 +
| ДП, альфа-бета отсечение
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| [9]
 +
|
 +
|
 +
|-
 +
| rowspan="1" | 14.02.2023 (вт)
 +
| Занятий не было
 +
|
 +
|
 +
|
 +
| 16.02.2023 (чт)
 +
| Бонусный семинар
 +
| Модель внешней памяти
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 21.02.2023 (вт)
 +
| Семинар
 +
| Пути в графах, кратчайшие и не очень
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| [10] Contraction Hierarchies: поиск кратчайших путей на практике
 +
|
 +
|
 +
| 23.02.2023 (чт)
 +
| Выходной
 +
|
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 28.02.2023 (вт)
 +
| Семинар
 +
| Разбор КР
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| [11] Линейный алгоритм поиска MST
 +
|
 +
|
 +
| 2.03.2023 (чт)
 +
| Бонусный контест
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 7.03.2023 (вт)
 +
| Семинар
 +
| Минимальные остовы
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| [12] Алгоритм Тарьяна для поиска КСС. Неудачное доказательство log* n для СНМ.
 +
|
 +
|
 +
|-
 +
| rowspan="2" | 9.03.2023 (чт)
 +
| Семинар
 +
| Задачи на графы, конденсация, 2-SAT
 +
|
 +
|
 +
|-
 +
| Лекция
 +
| [13] Доказательство log* n для СНМ. Введение в потоки.
 +
|
 +
|
 +
|}
  
 
== Ссылки на материалы ==
 
== Ссылки на материалы ==

Версия 22:07, 11 марта 2023

Лектор: Иван Фёдорович Смирнов


Важные ссылки
Google.Classroom
Текущая успеваемость 		Google.Classroom
Запись на консультации 		Google.Classroom
Сдача ДЗ

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

Формула оценивания пока предварительная и может поменяться!

Курс длится 4 модуля (со 2-го по 5-й) и предполагает две итоговые оценки: на первом курсе (2-4 модули) и на втором (5 модуль). Оценки за каждый модуль ставятся независимо. Итоговая оценка за первый курс составляется из оценок за 2-4 модули (точные правила будут сообщены позднее). Оценка за 5-й модуль является итоговой оценкой за второй курс.

После 3-го, 4-го и 5-го модулей будут экзамены.

Предварительные правила выставления оценок за модули:

2 модуль: Оитог = 0.4286 · Оконтесты + 0.3571 · Oлистки + 0.2143 · ОКР + Oбонус

3-4 модуль: Оитог = 0.3 · Оконтесты + 0.25 · Oлистки + 0.15 · ОКР + 0.3 · Оэкзамен + Oбонус

  • Олистки вычисляется по формуле:
    Олистки = 10 · количество решённых задач
    количество обязательных задач - поправка

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

  • В течение каждого очного модуля предполагается по одной контрольной работе. За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться ОКР. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.
  • За экзамен студент получает оценку от 0 до 10, эта оценка будет являться Оэкзамен.
  • Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

Итоговая оценка округляется арифметически (то есть при дробной части меньше 0.5 округление производится вниз, иначе вверх).

Теоретическое домашнее задание

Общие предположения, которыми можно пользоваться в задачах

1. Если в задаче говорится про запросы, то по умолчанию online

2. Если не оговорено иное, можно использовать столько же памяти, сколько времени

3. Если не оговорено иное, то можно ожидаемое амортизированное время с хешами


Правила сдачи письменных работ

1. Пожалуйста, убедитесь, что вашу работу можно идентифицировать (имя написано в файле, или ваш гугл-аккаунт подписан вашим именем).

2. При отправке убедитесь, что у вас появилась кнопка "отменить отправку" — это означает, что работа отправлена на проверку.

3. Домашние задания, сданные не в формате .pdf или набранные не с помощью системы вёрстки LaTeX не принимаются.

4. Нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки).

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

6. Списывание в работах повлечёт за собой обнуление баллов по работе.

7. Если вы не чувствуете себя уверено при работе с LaTeX, используйте шаблон https://www.overleaf.com/read/bpvmhqcvfgqq. В нём отражена основная функциональность системы вёрстки. Вы можете склонировать проект и использовать его.


Список заданий

№ Тема Листок Дедлайн
2 модуль

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

Все длинные контесты доступны по ссылке.

№ Дедлайн Темы
2 модуль
1 26.11.2022 Вероятности
2 10.12.2023 Простые структуры


Экзамены

Лекции и семинары

2 модуль

3 модуль

Ссылки на материалы

Основные источники:

  1. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: Построение и анализ, [2013, 3 издание]
  2. neerc.ifmo.ru

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

Преподаватель Подгруппа Присутственные часы Контакты
Преподаватели
Иван Смирнов 221-1 @ifsmirnov
Филипп Грибов 221-2
Иван Сафонов 222-1
Михаил Анопренко 222-2
Сергей Нечаев 225-1
Екатерина Фадеева 225-2
Источник — «http://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных_пилотный_поток_2022/2023&oldid=76960»