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_2024_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0 Алгоритмы и структуры данных (Русскоязычные иностранцы) 2024 весна - История изменений 2026-04-10T21:50:15Z История изменений этой страницы в вики 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)_2024_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0&diff=2960&oldid=prev Кулапин Артур: /* Дополнительные материалы */ 2024-04-18T19:40:08Z <p>‎<span dir="auto"><span class="autocomment">Дополнительные материалы</span></span></p> <table class="diff diff-contentalign-left" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr style="vertical-align: top;" lang="ru"> <td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 19:40, 18 апреля 2024</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l146" >Строка 146:</td> <td colspan="2" class="diff-lineno">Строка 146:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>== Дополнительные материалы ==</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>== Дополнительные материалы ==</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[https://www.youtube.com/playlist?list=PL4_hYwCyhAvZZ_DqJ7mS_xyG_AsyerfdB Записи лекций <del class="diffchange diffchange-inline">2022</del>-<del class="diffchange diffchange-inline">2023 </del>года]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[https://www.youtube.com/playlist?list=PL4_hYwCyhAvZZ_DqJ7mS_xyG_AsyerfdB Записи лекций <ins class="diffchange diffchange-inline">2023</ins>-<ins class="diffchange diffchange-inline">2024 </ins>года]</div></td></tr> <!-- diff cache key pi_wiki-wiki:diff:version:1.11a:oldid:2959:newid:2960 --> </table> Кулапин Артур 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)_2024_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0&diff=2959&oldid=prev Кулапин Артур: /* Дополнительные материалы */ 2024-04-18T19:39:56Z <p>‎<span dir="auto"><span class="autocomment">Дополнительные материалы</span></span></p> <table class="diff diff-contentalign-left" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr style="vertical-align: top;" lang="ru"> <td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 19:39, 18 апреля 2024</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l146" >Строка 146:</td> <td colspan="2" class="diff-lineno">Строка 146:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>== Дополнительные материалы ==</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>== Дополнительные материалы ==</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[https://www.youtube.com/playlist?list=<del class="diffchange diffchange-inline">PL4_hYwCyhAvZtI5h-e2FBGLiygrGDWji0 </del>Записи лекций 2022-2023 года]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[https://www.youtube.com/playlist?list=<ins class="diffchange diffchange-inline">PL4_hYwCyhAvZZ_DqJ7mS_xyG_AsyerfdB </ins>Записи лекций 2022-2023 года]</div></td></tr> <!-- diff cache key pi_wiki-wiki:diff:version:1.11a:oldid:2958:newid:2959 --> </table> Кулапин Артур 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)_2024_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0&diff=2958&oldid=prev Кулапин Артур: Оформление АиСД иностранцы 2023-24 2024-04-18T19:39:18Z <p>Оформление АиСД иностранцы 2023-24</p> <p><b>Новая страница</b></p><div>= Общие сведения =<br /> * Семестр: 4/6 (второй/третий курсы)<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/1iKxP1mSW6g1uFv1tQZJ0k66yh9uW1iLG?usp=sharing Папка с теоретическими заданиями]<br /> <br /> [https://docs.google.com/spreadsheets/d/1gOHDoOq6Da6o5w2XG5IX5uM4drify0tdeZ1-mux33n8/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. Обходы графов. DFS<br /> - Хранение графа: матрица и список смежности<br /> - Обход в ширину (DFS)<br /> * Атрибуты вершин: цвета, времена входа и выхода<br /> * Лемма о белых путях<br /> * Топологическая сортировка<br /> * Компоненты сильной связности. Алгоритм Косарайю<br /> * Реберная двусвязность. Поиск мостов<br /> * Поиск точек сочленения<br /> 2. Кратчайшие пути<br /> - BFS: классический, 0-1, 1-k, 0-k<br /> - Алгоритм Дейкстры<br /> - Эвристический поиск. Алгоритм A-star<br /> - Алгоритм Форда-Беллмана<br /> - Алгоритм Флойда-Уоршелла<br /> - Поиск циклов отрицательного веса<br /> 3. Система непересекающихся множеств<br /> 4. Минимальные остовые деревья<br /> - Лемма о безопасном ребре<br /> - Алгоритм Прима. Аналогии с алгоритмом Дейкстры<br /> - Алгоритм Крускала.<br /> 5. Наименьший общий предок<br /> - Наивное решение<br /> - Двоичные подъемы<br /> - Сведение LCA &lt;-&gt; RMQ<br /> - Алгоритм Фараха-Колтона-Бендера<br /> - static online RMQ с линейным предподсчетом и константным ответом на запрос<br /> 6. Паросочетания<br /> - Двудольные графы<br /> - Теорема Бержа<br /> - Алгоритм Куна<br /> 7. Потоки<br /> - Понятие сети, потока, разреза. Модификации сети<br /> - Остаточная сеть<br /> - Соотношение между величинами потоков и разрезов<br /> - Теорема Форда-Фалкерсона<br /> - Схема Форда-Фалкерсона<br /> * Алгоритм Форда-Фалкерсона<br /> * Алгоритм Эдмондса-Карпа<br /> - Схема Диница<br /> * Блокирующий поток<br /> * Удаляющий обход<br /> - Потенциал сети. Первая теорема Карзанова<br /> - Алгоритм Хопкрофта-Карпа<br /> 8. Строки<br /> - Поиск паттерна в тексте<br /> * Префикс-функция. Алгоритм Кнута-Морриса-Прата<br /> * Z-функция. Алгоритм Кнута-Морриса-Прата<br /> * Полиномиальное хеширование. Алгоритм Рабина-Карпа<br /> - Поиск множества паттернов в тексте<br /> * Бор<br /> * Автомат Ахо-Корасик<br /> - Алгоритмы на подстроках. Суффиксный автомат<br /> * Теорема Майхилла-Нероуда<br /> * Наивное построение<br /> * Линейный алгоритм<br /> - Поиск паттернов с ошибками<br /> * Метрика Левенштейна. Алгоритм Ландау-Вишкина<br /> * Метрика Хэмминга. Быстрое преобразование Фурье<br /> <br /> == Оценивание ==<br /> За курс ставятся сразу две оценки: дифференцированный зачет за &quot;Практикум по алгоритмам и структурам данных&quot;, экзамен по дисциплине &quot;Алгоритмы и структуры данных&quot;.<br /> <br /> '''Оценивание дифференцированного зачета'''<br /> <br /> Оценка состоит из следующих компонент:<br /> <br /> 1. Баллы за контесты (далее ''A''): до 7.5 баллов<br /> <br /> Пусть X - число набранных баллов студентом, S - число набранных ''идеальным студентом'' баллов. Тогда баллы за контесты определяются как ''A = round(X / S, 2) * 7.5''<br /> <br /> 2. Баллы за теоретические задания (далее ''B''): до 2.5 баллов<br /> <br /> Пусть X - число набранных баллов студентом, S - число набранных ''идеальным студентом'' баллов. Тогда баллы за теоретические задания определяются как ''B = round(X / S, 2) * 2.5''<br /> <br /> 3. Бонус от преподавательского состава (далее ''B''): до 1 балла. Ставится семинаристом или лектором с шагом 0.1<br /> <br /> 4. Пусть F - число задач, в решениях которых студент был уличен в плагиате. <br /> <br /> Итоговая оценка: ''clamp(round(A + B + C - F), 2, 10)'', однако если F &gt; 2, то итоговая оценка неуд(2).<br /> <br /> Последнее требование. В каждом контесте есть две задачи с ревью, проходящем на [https://gitlab.com гитлабе] в созданном для вас после заполнения формы репозитории. Для каждого контеста выкладываются требования для сдачи ревью. Для получения чего-либо выше неуд(2) необходимо сдать хотя бы треть задач с ревью.<br /> <br /> <br /> <br /> '''Оценивание экзамена'''<br /> <br /> Программа и правила проведения экзамена - TBA<br /> <br /> == Команда курса ==<br /> <br /> Лектор курса [http://t.me/KulArt Кулапин Артур]<br /> <br /> Семинаристы:<br /> <br /> Семинарист Б05-251 - [http://t.me/illusion_cat Филатенков Артур]<br /> <br /> Семинарист Б05-252 - [http://t.me/alresing Смолин Александр]<br /> <br /> Семинарист Б05-253 - [http://t.me/artyomdolta Долта Артем]<br /> <br /> Cеминарист Б05-(153-155) - [http://t.me/k_kozlik_k Козловский Владислав]<br /> <br /> Ассистенты<br /> <br /> [http://t.me/shedulerka Вашкевич Егор]<br /> <br /> [http://t.me/mikipaw Павлов Михаил]<br /> <br /> [http://t.me/Drago_160 Мешков Владислав]<br /> <br /> [http://t.me/kronte32 Драчёв Данила]<br /> <br /> [http://t.me/astessh Стешенко Александр]<br /> <br /> [http://t.me/Aminov_Sh Аминов Шахром]<br /> <br /> [http://t.me/kot0ffskiy Сушков Богдан]<br /> <br /> == Дополнительные материалы ==<br /> <br /> [https://www.youtube.com/playlist?list=PL4_hYwCyhAvZtI5h-e2FBGLiygrGDWji0 Записи лекций 2022-2023 года]</div> Кулапин Артур