Просмотр исходного текста страницы Алгоритмы и структуры данных (Русскоязычные иностранцы) 2023 a

= Общие сведения =
* Семестр: 3/5 (второй/третий курсы)
* Формат: очный
* Форма контроля: дифференцированный зачет + экзамен

== Важные ссылки ==

[https://t.me/+5fY3QdRpOkQzZGIy Чат курса] - там можно задавать вопросы по курсу, задачам, изредка флудить

[https://t.me/+63m-6WSqJgljYzIy Канал курса] - там будут все важные объявления (домашние задания, оргвопросы, etc.)

[https://drive.google.com/drive/folders/11NVf33MEu8NMsUj4BDiWhpGxK_5FjETi?usp=sharing Папка с теоретическими заданиями]

[https://docs.google.com/spreadsheets/d/1KyBFzhkzI3vV9voGntrxmb_dSwsYjXfPdSjsNdM9ETg/edit?usp=sharing Ведомость курса]

[https://forms.gle/7qxBb6BdmAFd3mXE6 Форма для регистрации на курс]

== Требования ==
* Физтех-почта (домен phystech.edu)
* Аккаунт на [https://contest.yandex.ru Я.Контесте] (можно на физтех-почту)
* Аккаунт на [https://gitlab.com гитлабе]

Обязательно заполнить [https://forms.gle/7qxBb6BdmAFd3mXE6 форму регистрации на курс] до 1 ноября! В противном случае считается, что курс вы сдавать не планируете или вы согласны на добровольную пересдачу по обоим предметам.

== План курса ==

 1. Базовые алгоритмы
  - Бинарный поиск: классический, вещественный, по ответу
  - Префиксные суммы. Обобщение на произвольную ассоциативную и обратимую операцию
  - Основы теории чисел:
    * Модульная арифметика
    * Решето Эратосфена
    * Поиск обратного по модулю: с использованием функции Эйлера, с использованием расширенного алгоритма Евклида
  - Амортизационный анализ: метод монеток, метод потенциалов
  - Линейные контейнеры
    * Динамически расширяющийся буффер
    * Списки: односвязный, двусвязный
    * Адаптеры: стек, очередь, дек
    * Очередь с минимумом
 2. Сортировки
  - Сортировка слиянием (MergeSort). Подсчет числа инверсий
  - Бинарная пирамида (Binary heap). Пирамидальная сортировка (HeapSort)
  - Быстрая сортировка (QuickSort)
  - Поиск k-й порядковой статистики
 3. Деревья поиска
  - Наивное дерево поиска. Поддержка lower_bound, k-й порядковой статистики
  - AVL-дерево
  - Декартово дерево
  - Splay дерево
 4. Хеш-таблицы
  - Метод цепочек
  - Универсальное семейство хеш-функций
 5. Динамическое программирование (ДП)
  - Постановка задачи ДП
  - Задачи НВП (наибольшая возрастающая подпоследовательность), НОП (наибольшая общая подпоследовательность)
  - ДП по подотрезкам: подсчет числа подпоследовательностей палиндромов, задача о перемножении матриц
 6. Структуры для работы с непрерывными данными
  - Постановка задач static/dynamic offline/online RMQ/RSQ
  - Дерево отрезков с групповыми операциями
  - Дерево Фенвика. Обобщение на многомерный случай
 7. Вычислительная геометрия на плоскости
  - Взаимное расположение геометрических примитивов: точек, прямых, отрезков, окружностей
  - Работа с многоугольниками: подсчет площади, принадлежность точки
  - Выпуклая оболочка. Алгоритмы Джарвис, Грехема
  - Построение огибающих
  - Динамическая выпуклая оболочка, случай только с добавлением
  - Сумма Минковского. Построение для двух выпуклых многоугольников
  - Две ближайшие точки на плоскости
  - Две самые удаленные точки на плоскости

== Оценивание ==
За курс ставятся сразу две оценки: дифференцированный зачет за "Практикум по алгоритмам и структурам данных", экзамен по дисциплине "Алгоритмы и структуры данных".

'''Оценивание дифференцированного зачета'''

Оценка состоит из следующих компонент:

1. Баллы за контесты (далее ''A''): до 7 баллов

Пусть X - число набранных баллов студентом, S - число набранных ''идеальным студентом'' баллов. Тогда баллы за контесты определяются как ''A = round(X / S, 2) * 7''

2. Баллы за теоретические задания (далее ''B''): до 3 баллов

Пусть X - число набранных баллов студентом, S - число набранных ''идеальным студентом'' баллов. Тогда баллы за теоретические задания определяются как ''B = round(X / S, 2) * 3''

3. Бонус от преподавательского состава (далее ''B''): до 1 балла. Ставится семинаристом или лектором с шагом 0.1

Последняя компонента. Пусть F - число задач, в решениях которых студент был уличен в плагиате. 

Итоговая оценка: ''clamp(round(A + B + C - F), 2, 10)'', однако если F > 2, то итоговая оценка неуд(2).



'''Оценивание экзамена'''

[https://drive.google.com/file/d/1fswi8A-7BijuL8aaPfFRHMJvaxsEJPF6/view?usp=sharing Программа и правила проведения экзамена]

== Команда курса ==

Лектор курса [http://t.me/KulArt Кулапин Артур]

Семинаристы:

Филатенков Артур - семинарист Б05-251

Смолин Александр - семинарист Б05-252

Долта Артем - семинарист Б05-253

Козловский Владислав - семинарист Б05-(153-155)

== Дополнительные материалы ==

[https://www.youtube.com/playlist?list=PL4_hYwCyhAvZtI5h-e2FBGLiygrGDWji0 Записи лекций 2022-2023 года]