Алгоритмы и структуры данных (Русскоязычные иностранцы)
Содержание
Общие сведения
- Семестр: 3/5 (второй/третий курсы)
- Формат: очный
- Форма контроля: дифференцированный зачет + экзамен
Важные ссылки
Чат курса - там можно задавать вопросы по курсу, задачам, изредка флудить
Канал курса - там будут все важные объявления (домашние задания, оргвопросы, etc.)
Папка с теоретическими заданиями
Требования
- Физтех-почта (домен phystech.edu)
- Аккаунт на Я.Контесте (можно на физтех-почту)
- Аккаунт на гитлабе
Обязательно заполнить форму регистрации на курс до 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).
Оценивание экзамена
Программа и правила проведения экзамена
Команда курса
Лектор курса Кулапин Артур
Семинаристы:
Филатенков Артур - семинарист Б05-251
Смолин Александр - семинарист Б05-252
Долта Артем - семинарист Б05-253
Козловский Владислав - семинарист Б05-(153-155)
