Курс лекций «Эффективные алгоритмы» — различия между версиями
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
(не показаны 42 промежуточные версии этого же участника) | |||
Строка 1: | Строка 1: | ||
<!-- https://prod.liveshare.vsengsaas.visualstudio.com/join?356FB217B4C56E51B049FD76EAFACED6B274 | <!-- https://prod.liveshare.vsengsaas.visualstudio.com/join?356FB217B4C56E51B049FD76EAFACED6B274 | ||
+ | --> | ||
+ | <!-- | ||
+ | * [[Special:MediawikiQuizzer/GRE-CS-v01|Еженедельная проверка — сегодня экспериментальная]] | ||
--> | --> | ||
Строка 7: | Строка 10: | ||
}} | }} | ||
− | <!-- | + | <!-- |
* [[Special:MediawikiQuizzer/Эффективные алгоритмы-Экзамен|Тест для экзамена]] | * [[Special:MediawikiQuizzer/Эффективные алгоритмы-Экзамен|Тест для экзамена]] | ||
--> | --> | ||
− | |||
[[Special:MediawikiQuizzer/Algs-6-course-ispras-weekly|Еженедельная тренировка]] | [[Special:MediawikiQuizzer/Algs-6-course-ispras-weekly|Еженедельная тренировка]] | ||
Курс лекций «Эффективные алгоритмы» для 6 курса МФТИ. | Курс лекций «Эффективные алгоритмы» для 6 курса МФТИ. | ||
+ | |||
+ | ---- | ||
+ | {{:Blog:Advanced Algorithms/2021-09-03 Анонс «Эффективных алгоритмов-2021»}} | ||
+ | ---- | ||
+ | |||
+ | В целом голосование за время созвона прошло, результаты на странице [[Голосование за выбор времени созвона]], | ||
+ | но если сильно изменится ситуация — заходите и переголосуйте там. | ||
<!-- | <!-- | ||
Строка 21: | Строка 30: | ||
--> | --> | ||
− | ; | + | ;Преподаватель: [mailto:stas-fomin@yandex.ru С.А. Фомин] |
+ | Запись на курс 2021 года завершена, всем спасибо, исключений нет. | ||
+ | |||
+ | <!-- | ||
Для ФУПМов 6 курса, желающих записаться на курс по выбору «Эффективные алгоритмы», нужно: | Для ФУПМов 6 курса, желающих записаться на курс по выбору «Эффективные алгоритмы», нужно: | ||
{{:Как зарегистрироваться на курс}} | {{:Как зарегистрироваться на курс}} | ||
<poll> | <poll> | ||
− | UNSAFE_ID=aa- | + | UNSAFE_ID=aa-20210901 |
ALTERNATIVE | ALTERNATIVE | ||
OPEN_RESULTS | OPEN_RESULTS | ||
Строка 33: | Строка 45: | ||
AUTHORIZED | AUTHORIZED | ||
ALLOW_REVOTE | ALLOW_REVOTE | ||
− | END_POLL | + | END_POLL 2021-10-15 |
− | Записываемся на курс «Advanced Algorithms- | + | Записываемся на курс «Advanced Algorithms-2021»? |
Да | Да | ||
Нет | Нет | ||
</poll> | </poll> | ||
+ | --> | ||
<!-- | <!-- | ||
Строка 62: | Строка 75: | ||
--> | --> | ||
+ | <!-- | ||
Вводное занятие проведено — всем изучать материалы на | Вводное занятие проведено — всем изучать материалы на | ||
[[Курс лекций «Эффективные алгоритмы»]] — книгу, видео и все-такое. | [[Курс лекций «Эффективные алгоритмы»]] — книгу, видео и все-такое. | ||
Строка 67: | Строка 81: | ||
{{!|Встречаемся в 903 КПМ, 4 октября, 18:30}} | {{!|Встречаемся в 903 КПМ, 4 октября, 18:30}} | ||
− | + | --> | |
Формат flipped classroom — т.е. по существующим материалам не будем повторять лекции, встречаться будем только для семинаров, и активной работы (решение задач, разбор сложных моментов, что-нибудь интересное придумаю) по заранее изученным материалам. | Формат flipped classroom — т.е. по существующим материалам не будем повторять лекции, встречаться будем только для семинаров, и активной работы (решение задач, разбор сложных моментов, что-нибудь интересное придумаю) по заранее изученным материалам. | ||
Строка 133: | Строка 147: | ||
--> | --> | ||
− | = | + | == Блок 1 == |
+ | {{vimeoembed|324745701|800|450}} | ||
− | + | Простые классические алгоритмы. Динамическое программирование. | |
+ | Навыки мемоизации, работы с структурами данных. | ||
− | === | + | |
+ | === Теория === | ||
* [[Несложно о сложности. Примеры алгоритмов]] | * [[Несложно о сложности. Примеры алгоритмов]] | ||
* [[Жадный алгоритм в задачах о покрытии]] | * [[Жадный алгоритм в задачах о покрытии]] | ||
* [[Жадный алгоритм покрытия для почти всех исходных данных]] | * [[Жадный алгоритм покрытия для почти всех исходных данных]] | ||
* [[Жадный алгоритм в задаче о рюкзаке]] | * [[Жадный алгоритм в задаче о рюкзаке]] | ||
+ | * [[Динамическое программирование для задачи о рюкзаке]] | ||
+ | * [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]] | ||
+ | * [[Вероятностная проверка тождеств]] | ||
− | === | + | * [[Полиномиальный в среднем алгоритм для задачи упаковки]] |
− | + | * [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]] | |
− | * [[ | + | * [[Полиномиальный в среднем алгоритм для SAT]] |
− | * [[ | + | |
+ | * [[Вероятностный подсчет числа выполняемых наборов для ДНФ]] | ||
+ | * [[MAX-SAT: вероятностное округление]] | ||
+ | * [[MAX-CUT: вероятностное округление]] | ||
+ | |||
+ | * [[MAX-SAT: дерандомизация]] | ||
+ | * [[Приближенный алгоритм для метрической задачи коммивояжера]] | ||
+ | |||
+ | |||
+ | == Блок 2 == | ||
+ | ;Квест «4 задачи»: До 3 декабря | ||
+ | * [[Blog:Advanced_Algorithms/2021-10-15_Practical_Block]] | ||
+ | * Прохождение квеста гарантирует «уд» | ||
+ | * Непрохождение → «неуд» | ||
+ | |||
+ | ;Квест «2 задачи из Spojcoding/Codechefing» | ||
+ | * До 15 декабря. | ||
+ | * Прохождение квеста гарантирует «хор» (7) | ||
+ | * Повторим условия: | ||
+ | ** Не Leetcoding | ||
+ | ** Только Python | ||
+ | ** Да, должна проходить TL | ||
+ | |||
+ | ;Квест «4 задачи из Spojcoding/Codechefing» | ||
+ | * До 15 декабря. | ||
+ | * Прохождение квеста гарантирует «отл» (8) | ||
+ | * Повторим условия: | ||
+ | ** Не Leetcoding | ||
+ | ** Только Python | ||
+ | ** Да, должна проходить TL | ||
+ | |||
+ | == Блок 3 == | ||
+ | <!-- Выберем несколько тем и теоретических задач. --> | ||
+ | |||
+ | Те, кто по результатам предущих блоков вышел на «хор» до 12 декабря, смогут улучшить оценку | ||
+ | * [[Blog:Advanced_Algorithms/2021-11-15_Research_Block]] | ||
+ | |||
+ | |||
+ | = Темы = | ||
+ | Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соответствующего PDF-файла. | ||
+ | |||
+ | * [[Несложно о сложности. Примеры алгоритмов]] | ||
+ | * [[Жадный алгоритм в задачах о покрытии]] | ||
+ | * [[Жадный алгоритм покрытия для почти всех исходных данных]] | ||
+ | * [[Жадный алгоритм в задаче о рюкзаке]] | ||
− | |||
* [[Динамическое программирование для задачи о рюкзаке]] | * [[Динамическое программирование для задачи о рюкзаке]] | ||
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]] | * [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]] | ||
+ | |||
+ | <!-- Темы к ближайшему занятию. --> | ||
* [[Полиномиальный в среднем алгоритм для задачи упаковки]] | * [[Полиномиальный в среднем алгоритм для задачи упаковки]] | ||
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]] | * [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]] | ||
* [[Полиномиальный в среднем алгоритм для SAT]] | * [[Полиномиальный в среднем алгоритм для SAT]] | ||
− | |||
* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]] | * [[Вероятностный подсчет числа выполняемых наборов для ДНФ]] | ||
* [[MAX-SAT: вероятностное округление]] | * [[MAX-SAT: вероятностное округление]] | ||
* [[MAX-CUT: вероятностное округление]] | * [[MAX-CUT: вероятностное округление]] | ||
* [[MAX-SAT: дерандомизация]] | * [[MAX-SAT: дерандомизация]] | ||
+ | * [[Приближенный алгоритм для метрической задачи коммивояжера]] | ||
<!-- * [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]] --> | <!-- * [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]] --> | ||
− | |||
− | |||
Строка 181: | Строка 244: | ||
== Задачи == | == Задачи == | ||
+ | * [[LeetCoding]] | ||
+ | |||
+ | <!-- | ||
Все статьи в этой категории — задачи, которые можно пытаться решать. | Все статьи в этой категории — задачи, которые можно пытаться решать. | ||
* [[:Category:Нерешенные задачи]]. Осталось {{!|{{PAGESINCATEGORY: Нерешенные задачи}}}} нерешенных задач. | * [[:Category:Нерешенные задачи]]. Осталось {{!|{{PAGESINCATEGORY: Нерешенные задачи}}}} нерешенных задач. | ||
Строка 206: | Строка 272: | ||
Эти задачи заводим в | Эти задачи заводим в | ||
[[:Category:Предложенные студентами задачи]] | [[:Category:Предложенные студентами задачи]] | ||
− | |||
− | |||
− | |||
Все статьи в этой категории — задачи, которые можно пытаться решать. | Все статьи в этой категории — задачи, которые можно пытаться решать. | ||
Строка 223: | Строка 286: | ||
Проверенное решение перейдет в [[:Category:Решения]] или, | Проверенное решение перейдет в [[:Category:Решения]] или, | ||
если возникнут вопросы-возражения в [[:Category:Проблемы в решении]]. | если возникнут вопросы-возражения в [[:Category:Проблемы в решении]]. | ||
+ | --> | ||
= Видеолекции = | = Видеолекции = | ||
Строка 253: | Строка 317: | ||
* Еще один классический [http://www.cs.yale.edu/HTML/YALE/CS/HyPlans/lovasz/complex.ps курс лекций по теории сложности от László Lovász.] | * Еще один классический [http://www.cs.yale.edu/HTML/YALE/CS/HyPlans/lovasz/complex.ps курс лекций по теории сложности от László Lovász.] | ||
* ''А. Китаев, А. Шень, М. Вялый'', [http://discopal.ispras.ru/img_auth.php/9/96/Qbook_.pdf Классические и квантовые вычисления] — замечательная книга. Содержит отличное введение в теорию сложности. | * ''А. Китаев, А. Шень, М. Вялый'', [http://discopal.ispras.ru/img_auth.php/9/96/Qbook_.pdf Классические и квантовые вычисления] — замечательная книга. Содержит отличное введение в теорию сложности. | ||
+ | * ''С. Дасгупта, Х. Пападимитриу, У. Вазирани'', Алгоритмы [http://www.math.nsc.ru/LBRT/k5/OR-MMF/dasgupta_2014.pdf] | ||
− | |||
− | |||
---- | ---- | ||
{{:Библиотека}} | {{:Библиотека}} |
Версия 15:30, 8 декабря 2021
- 2024-03-28: Эксперимент — улучшаем старые решения ← Advanced Algorithms
- 2024-03-28: Python-решения — давайте потренируемся их сделать питонистей ← Advanced Algorithms
- 2024-02-26: Feedback ← Advanced Algorithms
Курс лекций «Эффективные алгоритмы» для 6 курса МФТИ.
Кратко, что будет, чего не будет и что ждать.
- Лекций — не будет. Это бред и бессмыслица, особенно при дистанционке. Созвоны будут при небходимости, в формате семинара, может индивидуальные.
- Будет путешествие-квест, с разными активностями.
- Берем только практические вещи — алгоритмы для разных задач, особенно NP-полных.
- Условно будет три блока
- Теоретический — прочитать темы, посмотреть записи лекций, пройти тестирование, возможно решить некоторые теорзадачи.
- Тут будет первый отсев — если не проходите тесты (отсеим, скажем, 25% нижних), то «досвидания».
- Не рекламируйте этот курс — чем меньше народу, тем будет лучше. Я заинтересован сократить численность всеми способами. Особенно нафиг я посылаю всех, кто пытается запрыгнуть в курс в середине семестра и позже. Без шансов. Когда-то прогибался в виде исключения, сейчас не буду.
- Легкий практический — решение нескольки задач, даваемых на собеседованиях в IT-компаниях, типа LeetCoding, SpojCoding, CodeChefing и т.п.
- Тут будет второй отсев — но можно будет тут свалить, получив «уд» — кому нужно время, и не очень все это интересно.
- Теор-практический — взять некоторую тему из заданных (свежая статья, я отберу), и сделать ее разбор-презентацию-реализацию в каком-нибудь jupyter или cocalc-ноутбуке (там будет видно). Тут возможно будет и индивидуальная работа и может тренировка презентейшн скиллс, что полезно для ваших дипломов (сколько я смотрел защит, все ужасно).
Ну остальные новости будут в группе, если что. Вопросы тоже там или напрямую.
Как зарегистрироваться — написано на основной странице курса, где все и будет https://discopal.ispras.ru/Advanced-algorithms
Регистраций открыта до 15 октября.
Подумайте еще раз — надо ли вам это. «Халявы», «Лекций», «Оценок за удаленную посещаемость» тут не будет. Даже «уд. нахаляву». Посмотрите, вокруг полно интересных курсов по выбору.
В целом голосование за время созвона прошло, результаты на странице Голосование за выбор времени созвона, но если сильно изменится ситуация — заходите и переголосуйте там.
- Преподаватель
- С.А. Фомин
Запись на курс 2021 года завершена, всем спасибо, исключений нет.
Формат flipped classroom — т.е. по существующим материалам не будем повторять лекции, встречаться будем только для семинаров, и активной работы (решение задач, разбор сложных моментов, что-нибудь интересное придумаю) по заранее изученным материалам.
Вопросы пишите на почту, или задавайте в группе.
- Проблемы → Стасу Фомину
В списке вы можете видеть разные цифры, отражающие вашу активность по темам курса. В конце — некоторые суммарные метрики, рассчитанные по волшебным формулам.
Если вы в зеленой группе — вы кандидат на «отлично автоматом».
«Отличники-автоматом» будут выбраны с помощью жадного алгоритма, и вероятностого округления, с использованием настоящих случайных чисел с http://random.org
Содержание
Блок 1
Простые классические алгоритмы. Динамическое программирование. Навыки мемоизации, работы с структурами данных.
Теория
- Несложно о сложности. Примеры алгоритмов
- Жадный алгоритм в задачах о покрытии
- Жадный алгоритм покрытия для почти всех исходных данных
- Жадный алгоритм в задаче о рюкзаке
- Динамическое программирование для задачи о рюкзаке
- Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке
- Вероятностная проверка тождеств
- Полиномиальный в среднем алгоритм для задачи упаковки
- Полиномиальный в среднем алгоритм для задачи о рюкзаке
- Полиномиальный в среднем алгоритм для SAT
- Вероятностный подсчет числа выполняемых наборов для ДНФ
- MAX-SAT: вероятностное округление
- MAX-CUT: вероятностное округление
Блок 2
- Квест «4 задачи»
- До 3 декабря
- Blog:Advanced_Algorithms/2021-10-15_Practical_Block
- Прохождение квеста гарантирует «уд»
- Непрохождение → «неуд»
- Квест «2 задачи из Spojcoding/Codechefing»
- До 15 декабря.
- Прохождение квеста гарантирует «хор» (7)
- Повторим условия:
- Не Leetcoding
- Только Python
- Да, должна проходить TL
- Квест «4 задачи из Spojcoding/Codechefing»
- До 15 декабря.
- Прохождение квеста гарантирует «отл» (8)
- Повторим условия:
- Не Leetcoding
- Только Python
- Да, должна проходить TL
Блок 3
Те, кто по результатам предущих блоков вышел на «хор» до 12 декабря, смогут улучшить оценку
Темы
Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соответствующего PDF-файла.
- Несложно о сложности. Примеры алгоритмов
- Жадный алгоритм в задачах о покрытии
- Жадный алгоритм покрытия для почти всех исходных данных
- Жадный алгоритм в задаче о рюкзаке
- Динамическое программирование для задачи о рюкзаке
- Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке
- Полиномиальный в среднем алгоритм для задачи упаковки
- Полиномиальный в среднем алгоритм для задачи о рюкзаке
- Полиномиальный в среднем алгоритм для SAT
- Вероятностный подсчет числа выполняемых наборов для ДНФ
- MAX-SAT: вероятностное округление
- MAX-CUT: вероятностное округление
- MAX-SAT: дерандомизация
- Приближенный алгоритм для метрической задачи коммивояжера
Не будем их рассматривать
- Формально об алгоритмах. Вычислительные модели
- Временная и пространственная сложность алгоритмов
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC
- Вероятностные вычисления. Классы RP, coRP, ZPP, BPP
- PCP и аппроксимируемость
Тренировка
Проверь себя, помнишь ли элементарные понятия и факты из курса. Тест будет на экзамене, чтобы отсеять совсем невменяемых.
Задачи
Видеолекции
- /Лекции осеннего семестра 2011
- торрент с прошлогодними видео.
- /Лекции осеннего семестра 2012
- Курс_лекций_«Сложность_алгоритмов»_(ИСПРАН,_3_курс_МФТИ)/Лекции_весеннего_семестра_2013
Книга
Специальная верстка для чтения с ноутбуков и КПК:
- альбомная ориентация
- крупные беззасечные шрифты
Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).
Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.
File:Book-advanced-algorithms.pdf
Примечания и ссылки
- Рекомендуется прочитать хотя бы первые лекции по введению в Python и научные вычисления.
Полезная сопутствующая литература по курсу.
- Очень хорошие лекции по классической теории сложности, написанные одним из корифеев оной: Introduction to Complexity Theory by Oded Goldreich
- Более краткий курс по классической теории сложности, университет Technion.
- Еще один классический курс лекций по теории сложности от László Lovász.
- А. Китаев, А. Шень, М. Вялый, Классические и квантовые вычисления — замечательная книга. Содержит отличное введение в теорию сложности.
- С. Дасгупта, Х. Пападимитриу, У. Вазирани, Алгоритмы [1]