http://wiki.atp-fivt.org/index.php?action=history&feed=atom&title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%28%D0%A0%D1%83%D1%81%D1%81%D0%BA%D0%BE%D1%8F%D0%B7%D1%8B%D1%87%D0%BD%D1%8B%D0%B5_%D0%B8%D0%BD%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%86%D1%8B%29_2023_%D0%BE%D1%81%D0%B5%D0%BD%D1%8C 2026-04-10T21:50:13Z История изменений этой страницы в вики MediaWiki 1.30.0 http://wiki.atp-fivt.org/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_(%D0%A0%D1%83%D1%81%D1%81%D0%BA%D0%BE%D1%8F%D0%B7%D1%8B%D1%87%D0%BD%D1%8B%D0%B5_%D0%B8%D0%BD%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%86%D1%8B)_2023_%D0%BE%D1%81%D0%B5%D0%BD%D1%8C&diff=2956&oldid=prev 2024-04-18T19:07:00Z

<p>Новая страница: «= Общие сведения = * Семестр: 3/5 (второй/третий курсы) * Формат: очный * Форма контроля: диффе…»</p> <p><b>Новая страница</b></p><div>= Общие сведения =<br /> * Семестр: 3/5 (второй/третий курсы)<br /> * Формат: очный<br /> * Форма контроля: дифференцированный зачет + экзамен<br /> <br /> == Важные ссылки ==<br /> <br /> [https://t.me/+5fY3QdRpOkQzZGIy Чат курса] - там можно задавать вопросы по курсу, задачам, изредка флудить<br /> <br /> [https://t.me/+63m-6WSqJgljYzIy Канал курса] - там будут все важные объявления (домашние задания, оргвопросы, etc.)<br /> <br /> [https://drive.google.com/drive/folders/11NVf33MEu8NMsUj4BDiWhpGxK_5FjETi?usp=sharing Папка с теоретическими заданиями]<br /> <br /> [https://docs.google.com/spreadsheets/d/1KyBFzhkzI3vV9voGntrxmb_dSwsYjXfPdSjsNdM9ETg/edit?usp=sharing Ведомость курса]<br /> <br /> [https://forms.gle/7qxBb6BdmAFd3mXE6 Форма для регистрации на курс]<br /> <br /> == Требования ==<br /> * Физтех-почта (домен phystech.edu)<br /> * Аккаунт на [https://contest.yandex.ru Я.Контесте] (можно на физтех-почту)<br /> * Аккаунт на [https://gitlab.com гитлабе]<br /> <br /> Обязательно заполнить [https://forms.gle/7qxBb6BdmAFd3mXE6 форму регистрации на курс] до 1 ноября! В противном случае считается, что курс вы сдавать не планируете или вы согласны на добровольную пересдачу по обоим предметам.<br /> <br /> == План курса ==<br /> <br /> 1. Базовые алгоритмы<br /> - Бинарный поиск: классический, вещественный, по ответу<br /> - Префиксные суммы. Обобщение на произвольную ассоциативную и обратимую операцию<br /> - Основы теории чисел:<br /> * Модульная арифметика<br /> * Решето Эратосфена<br /> * Поиск обратного по модулю: с использованием функции Эйлера, с использованием расширенного алгоритма Евклида<br /> - Амортизационный анализ: метод монеток, метод потенциалов<br /> - Линейные контейнеры<br /> * Динамически расширяющийся буффер<br /> * Списки: односвязный, двусвязный<br /> * Адаптеры: стек, очередь, дек<br /> * Очередь с минимумом<br /> 2. Сортировки<br /> - Сортировка слиянием (MergeSort). Подсчет числа инверсий<br /> - Бинарная пирамида (Binary heap). Пирамидальная сортировка (HeapSort)<br /> - Быстрая сортировка (QuickSort)<br /> - Поиск k-й порядковой статистики<br /> 3. Деревья поиска<br /> - Наивное дерево поиска. Поддержка lower_bound, k-й порядковой статистики<br /> - AVL-дерево<br /> - Декартово дерево<br /> - Splay дерево<br /> 4. Хеш-таблицы<br /> - Метод цепочек<br /> - Универсальное семейство хеш-функций<br /> 5. Динамическое программирование (ДП)<br /> - Постановка задачи ДП<br /> - Задачи НВП (наибольшая возрастающая подпоследовательность), НОП (наибольшая общая подпоследовательность)<br /> - ДП по подотрезкам: подсчет числа подпоследовательностей палиндромов, задача о перемножении матриц<br /> 6. Структуры для работы с непрерывными данными<br /> - Постановка задач static/dynamic offline/online RMQ/RSQ<br /> - Дерево отрезков с групповыми операциями<br /> - Дерево Фенвика. Обобщение на многомерный случай<br /> 7. Вычислительная геометрия на плоскости<br /> - Взаимное расположение геометрических примитивов: точек, прямых, отрезков, окружностей<br /> - Работа с многоугольниками: подсчет площади, принадлежность точки<br /> - Выпуклая оболочка. Алгоритмы Джарвис, Грехема<br /> - Построение огибающих<br /> - Динамическая выпуклая оболочка, случай только с добавлением<br /> - Сумма Минковского. Построение для двух выпуклых многоугольников<br /> - Две ближайшие точки на плоскости<br /> - Две самые удаленные точки на плоскости<br /> <br /> == Оценивание ==<br /> За курс ставятся сразу две оценки: дифференцированный зачет за &quot;Практикум по алгоритмам и структурам данных&quot;, экзамен по дисциплине &quot;Алгоритмы и структуры данных&quot;.<br /> <br /> '''Оценивание дифференцированного зачета'''<br /> <br /> Оценка состоит из следующих компонент:<br /> <br /> 1. Баллы за контесты (далее ''A''): до 7 баллов<br /> <br /> Пусть X - число набранных баллов студентом, S - число набранных ''идеальным студентом'' баллов. Тогда баллы за контесты определяются как ''A = round(X / S, 2) * 7''<br /> <br /> 2. Баллы за теоретические задания (далее ''B''): до 3 баллов<br /> <br /> Пусть X - число набранных баллов студентом, S - число набранных ''идеальным студентом'' баллов. Тогда баллы за теоретические задания определяются как ''B = round(X / S, 2) * 3''<br /> <br /> 3. Бонус от преподавательского состава (далее ''B''): до 1 балла. Ставится семинаристом или лектором с шагом 0.1<br /> <br /> Последняя компонента. Пусть F - число задач, в решениях которых студент был уличен в плагиате. <br /> <br /> Итоговая оценка: ''clamp(round(A + B + C - F), 2, 10)'', однако если F &gt; 2, то итоговая оценка неуд(2).<br /> <br /> <br /> <br /> '''Оценивание экзамена'''<br /> <br /> [https://drive.google.com/file/d/1fswi8A-7BijuL8aaPfFRHMJvaxsEJPF6/view?usp=sharing Программа и правила проведения экзамена]<br /> <br /> == Команда курса ==<br /> <br /> Лектор курса [http://t.me/KulArt Кулапин Артур]<br /> <br /> Семинаристы:<br /> <br /> Филатенков Артур - семинарист Б05-251<br /> <br /> Смолин Александр - семинарист Б05-252<br /> <br /> Долта Артем - семинарист Б05-253<br /> <br /> Козловский Владислав - семинарист Б05-(153-155)<br /> <br /> == Дополнительные материалы ==<br /> <br /> [https://www.youtube.com/playlist?list=PL4_hYwCyhAvZtI5h-e2FBGLiygrGDWji0 Записи лекций 2022-2023 года]</div>

Кулапин Артур