Курс лекций «Эффективные алгоритмы» — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(не показано 17 промежуточных версий этого же участника)
Строка 4: Строка 4:
 
* [[Special:MediawikiQuizzer/GRE-CS-v01|Еженедельная проверка — сегодня экспериментальная]]
 
* [[Special:MediawikiQuizzer/GRE-CS-v01|Еженедельная проверка — сегодня экспериментальная]]
 
-->
 
-->
 +
* [[Special:MediawikiQuizzer/Python|Еженедельная проверка]]
  
 
{{SideBar|
 
{{SideBar|
Строка 13: Строка 14:
 
* [[Special:MediawikiQuizzer/Эффективные алгоритмы-Экзамен|Тест для экзамена]]
 
* [[Special:MediawikiQuizzer/Эффективные алгоритмы-Экзамен|Тест для экзамена]]
 
-->
 
-->
 
 
<!--
 
<!--
 
[[Special:MediawikiQuizzer/Algs-6-course-ispras-weekly|Еженедельная тренировка]]
 
[[Special:MediawikiQuizzer/Algs-6-course-ispras-weekly|Еженедельная тренировка]]
 
-->
 
-->
 +
  
 
Курс лекций «Эффективные алгоритмы» для 6 курса МФТИ.
 
Курс лекций «Эффективные алгоритмы» для 6 курса МФТИ.
Строка 24: Строка 25:
 
----
 
----
  
 +
<!--
 
В целом голосование за время созвона прошло, результаты на странице [[Голосование за выбор времени созвона]],
 
В целом голосование за время созвона прошло, результаты на странице [[Голосование за выбор времени созвона]],
 
но если сильно изменится ситуация — заходите и переголосуйте там.
 
но если сильно изменится ситуация — заходите и переголосуйте там.
 +
-->
  
 
<!--
 
<!--
Строка 34: Строка 37:
 
;Преподаватель: [mailto:stas-fomin@yandex.ru С.А. Фомин]
 
;Преподаватель: [mailto:stas-fomin@yandex.ru С.А. Фомин]
  
Запись на курс 2021 года завершена, всем спасибо, исключений нет.
+
<!-- Запись на курс 2021 года завершена, всем спасибо, исключений нет. -->
  
<!--
 
 
Для ФУПМов 6 курса, желающих записаться на курс по выбору «Эффективные алгоритмы», нужно:
 
Для ФУПМов 6 курса, желающих записаться на курс по выбору «Эффективные алгоритмы», нужно:
 
{{:Как зарегистрироваться на курс}}
 
{{:Как зарегистрироваться на курс}}
  
 
<poll>
 
<poll>
UNSAFE_ID=aa-20210901
+
UNSAFE_ID=aa-20220901
 
ALTERNATIVE
 
ALTERNATIVE
 
OPEN_RESULTS
 
OPEN_RESULTS
Строка 47: Строка 49:
 
AUTHORIZED
 
AUTHORIZED
 
ALLOW_REVOTE
 
ALLOW_REVOTE
END_POLL 2021-10-15
+
END_POLL 2022-10-15
Записываемся на курс «Advanced Algorithms-2021»?
+
Записываемся на курс «Advanced Algorithms-2022»?
 
Да
 
Да
 
Нет
 
Нет
 
</poll>
 
</poll>
-->
+
* Установочный созвон будет наверно 9 сентября, раньше обычно бессмысленно.
  
 
<!--
 
<!--
Строка 90: Строка 92:
  
  
Вопросы пишите на [mailto:stas-fomin@yandex.ru почту], или задавайте в [https://vk.com/discopal группе].
+
Вопросы пишите на [mailto:stas-fomin@yandex.ru почту], или задавайте в [{{active-telegram-group-link}} группе].
  
 
<!--
 
<!--
Строка 99: Строка 101:
  
 
----
 
----
<!--
 
Зафиксирована запись следующих участников:
 
 
 
Печально, что несложные несколько пунктов инструкции оказались невывыполнимы для многих (не осилили даже пункт «На своей личной странице, написать хотя бы ФИО и группу»).
 
-->
 
 
 
<!--
 
 
SELECT user_name, user_real_name, user_email FROM `user` WHERE user_name IN (select poll_user from poll_vote WHERE poll_id='Xc12c3daeb861942efc77a234744170c') and user_id IN (select wl_user from watchlist where wl_title = "Advanced_Algorithms")
 
 
Итак, записались:
 
 
Списки переданы и зафиксированы в учебной части.
 
-->
 
 
 
 
 
  
 
* Проблемы → [mailto:stas-fomin@yandex.ru Стасу Фомину]
 
* Проблемы → [mailto:stas-fomin@yandex.ru Стасу Фомину]
 
<!-- * [[Календарь_лекций]] -->
 
  
 
<html><center>
 
<html><center>
Строка 134: Строка 114:
 
Если вы в зеленой группе — вы кандидат на «отлично автоматом».
 
Если вы в зеленой группе — вы кандидат на «отлично автоматом».
  
 +
<!--
 
«Отличники-автоматом» будут выбраны с помощью жадного алгоритма, и вероятностого округления, с использованием настоящих случайных чисел с http://random.org
 
«Отличники-автоматом» будут выбраны с помощью жадного алгоритма, и вероятностого округления, с использованием настоящих случайных чисел с http://random.org
 +
-->
  
<!--  
+
== Блок 1 ==
 +
----
 +
{{:Практикуемся В Алгоритмах}}
 +
----
  
Особый подход к Пятой ИСПРАН-группе.
+
Разберитесь, как зарегистрироваться на «лабе»
* [[Blog:Advanced Algorithms/Спецподход для студентов из ИСПРАН-группы]]
+
* [[Lab]]
  
У них особый список и отдельный учет:
+
== Блок 2 ==
<html><center>
+
Моделирование труднорешаемых задач и решение из промышленными солверами.
</p><div class="sites-embed-align-left-wrapping-off"><div class="sites-embed-border-on sites-embed sites-embed-full-width" style="width: 100%;"><h4 class="sites-embed-title">Успеваемость зарегистрированных студентов</h4><div class="sites-embed-object-title" style="display: none;">Эффективные алгоритмы(студенты).2007</div><div class="sites-embed-content sites-embed-type-spreadsheet"><iframe src="https://docs.google.com/spreadsheets/u/0/d/1UTgYTrhlvG6E8Paa7AdoZRQr-2iwZvlVPMkHfbt5FEk/htmlembed#gid=207856272" id="207856272" frameborder="0" height="400" width="100%"></iframe></div></div>
+
</div>
+
</center></html>
+
  
-->
+
{{:Моделирование бизнес-задач}}
  
 +
 +
== Блок 3 ==
 +
 +
Выберем несколько тем и теоретических задач.
 +
 +
Те, кто по результатам предущих блоков вышел на  «хор» до 12 декабря, смогут улучшить оценку
 +
* [[Blog:Advanced_Algorithms/2021-11-15_Research_Block]]
 +
 +
 +
 +
<!--
 
== Блок 1 ==
 
== Блок 1 ==
 
{{vimeoembed|324745701|800|450}}
 
{{vimeoembed|324745701|800|450}}
Строка 175: Строка 168:
 
* [[MAX-SAT: дерандомизация]]
 
* [[MAX-SAT: дерандомизация]]
 
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
 
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
 +
-->
  
 
+
<!--
 +
<!--
 
== Блок 2 ==
 
== Блок 2 ==
 
;Квест «4 задачи»: До 3 декабря  
 
;Квест «4 задачи»: До 3 декабря  
Строка 185: Строка 180:
 
;Квест «2 задачи из Spojcoding/Codechefing»
 
;Квест «2 задачи из Spojcoding/Codechefing»
 
* До 15 декабря.
 
* До 15 декабря.
* Прохождение квеста гарантирует «хор»
+
* Прохождение квеста гарантирует «хор» (7)
 
* Повторим условия:
 
* Повторим условия:
 
** Не Leetcoding
 
** Не Leetcoding
Строка 191: Строка 186:
 
** Да, должна проходить TL
 
** Да, должна проходить TL
  
 +
;Квест «4 задачи из Spojcoding/Codechefing»
 +
* До 15 декабря.
 +
* Прохождение квеста гарантирует «отл» (8)
 +
* Повторим условия:
 +
** Не Leetcoding
 +
** Только Python
 +
** Да, должна проходить TL
 +
-->
  
 +
 +
<!--
 
== Блок 3 ==
 
== Блок 3 ==
<!-- Выберем несколько тем и теоретических задач. -->
+
Выберем несколько тем и теоретических задач.
  
 
Те, кто по результатам предущих блоков вышел на  «хор» до 12 декабря, смогут улучшить оценку
 
Те, кто по результатам предущих блоков вышел на  «хор» до 12 декабря, смогут улучшить оценку
 
* [[Blog:Advanced_Algorithms/2021-11-15_Research_Block]]
 
* [[Blog:Advanced_Algorithms/2021-11-15_Research_Block]]
 +
-->
  
 
+
<!--
 
= Темы =
 
= Темы =
 
Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соответствующего PDF-файла.
 
Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соответствующего PDF-файла.
Строка 210: Строка 216:
 
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
 
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
  
<!-- Темы к ближайшему занятию. -->
 
 
* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
 
* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
 
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
 
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
Строка 220: Строка 225:
 
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
 
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
  
<!-- * [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]] -->
+
* [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]]  
  
  
  
=== Не будем их рассматривать ===
 
 
* [[Формально об алгоритмах. Вычислительные модели]]
 
* [[Формально об алгоритмах. Вычислительные модели]]
 
* [[Временная и пространственная сложность алгоритмов]]
 
* [[Временная и пространственная сложность алгоритмов]]
Строка 231: Строка 235:
 
* [[PCP и аппроксимируемость]]
 
* [[PCP и аппроксимируемость]]
  
<!-- {:Дерандомизация Люби} -->
 
 
* [[Параллельный алгоритм Люби для максимального по включению независимого множества]]
 
* [[Параллельный алгоритм Люби для максимального по включению независимого множества]]
  
Строка 240: Строка 243:
 
== Задачи ==
 
== Задачи ==
 
* [[LeetCoding]]
 
* [[LeetCoding]]
 
+
-->
 
<!--
 
<!--
 
Все статьи в этой категории — задачи, которые можно пытаться решать.
 
Все статьи в этой категории — задачи, которые можно пытаться решать.
Строка 283: Строка 286:
 
-->
 
-->
  
= Видеолекции =
+
= Материалы =
 +
Наверно не пригодятся для курса 2022 года.
 +
 
 +
== Видеолекции ==
 
* [[/Лекции осеннего семестра 2011]]
 
* [[/Лекции осеннего семестра 2011]]
 
** [http://narod.ru/disk/63720373001.d936acd53e1a20473d5073cbd232bc49/discopal.torrent.html торрент] с прошлогодними видео.
 
** [http://narod.ru/disk/63720373001.d936acd53e1a20473d5073cbd232bc49/discopal.torrent.html торрент] с прошлогодними видео.

Версия 15:59, 21 октября 2022


Курс лекций «Эффективные алгоритмы» для 6 курса МФТИ.


Кратко, что будет, чего не будет и что ждать.

  • Лекций — не будет. Это бред и бессмыслица, особенно при дистанционке. Созвоны будут при небходимости, в формате семинара, может индивидуальные.
  • Будет путешествие-квест, с разными активностями.
  • Берем только практические вещи — алгоритмы для разных задач, особенно NP-полных.
  • Условно будет три блока
    • Теоретический — прочитать темы, посмотреть записи лекций, пройти тестирование, возможно решить некоторые теорзадачи.
    • Тут будет первый отсев — если не проходите тесты (отсеим, скажем, 25% нижних), то «досвидания».
      • Не рекламируйте этот курс — чем меньше народу, тем будет лучше. Я заинтересован сократить численность всеми способами. Особенно нафиг я посылаю всех, кто пытается запрыгнуть в курс в середине семестра и позже. Без шансов. Когда-то прогибался в виде исключения, сейчас не буду.
    • Легкий практический — решение нескольки задач, даваемых на собеседованиях в IT-компаниях, типа LeetCoding, SpojCoding, CodeChefing и т.п.
    • Тут будет второй отсев — но можно будет тут свалить, получив «уд» — кому нужно время, и не очень все это интересно.
    • Теор-практический — взять некоторую тему из заданных (свежая статья, я отберу), и сделать ее разбор-презентацию-реализацию в каком-нибудь jupyter или cocalc-ноутбуке (там будет видно). Тут возможно будет и индивидуальная работа и может тренировка презентейшн скиллс, что полезно для ваших дипломов (сколько я смотрел защит, все ужасно).

Ну остальные новости будут в группе, если что. Вопросы тоже там или напрямую.

Как зарегистрироваться — написано на основной странице курса, где все и будет https://discopal.ispras.ru/Advanced-algorithms

Регистраций открыта до 15 октября.

Подумайте еще раз — надо ли вам это. «Халявы», «Лекций», «Оценок за удаленную посещаемость» тут не будет. Даже «уд. нахаляву». Посмотрите, вокруг полно интересных курсов по выбору.



Преподаватель
С.А. Фомин


Для ФУПМов 6 курса, желающих записаться на курс по выбору «Эффективные алгоритмы», нужно:

  • Зарегистрироваться здесь. Залогинится.
  • Зайти на страницу настроек, указать свой email и подтвердить его.
  • На своей личной странице (это не страница настроек, это то, что сверху слева, с иконкой человечка), написать хотя бы ФИО и группу.
    • Боже, как много народу с рассеянным вниманием уже до сюда не дочитывает.
  • Присоединится к телеграмм-группе.
  • Отметится в этом голосовании:

Записываемся на курс «Advanced Algorithms-2022»?

Да18
100%
Bolyarich, Cherniavskii, Ed.inozemtsev, GeraskinDA, Kiranov dmitry, Larin.dv, Molotkov.md, PankratovViktor, Philipakhiarov, Reroyu, Robohant, ScherbakIA, Shurtugal, SochnevaMA, Trmigor, Vshokorov, Тенемурл, Чеканов Кирилл
Нет0
0%

Вы должны войти в систему, чтобы участвовать в этом голосовании.

  • Установочный созвон будет наверно 9 сентября, раньше обычно бессмысленно.


Формат flipped classroom — т.е. по существующим материалам не будем повторять лекции, встречаться будем только для семинаров, и активной работы (решение задач, разбор сложных моментов, что-нибудь интересное придумаю) по заранее изученным материалам.


Вопросы пишите на почту, или задавайте в группе.




Успеваемость зарегистрированных студентов

В списке вы можете видеть разные цифры, отражающие вашу активность по темам курса. В конце — некоторые суммарные метрики, рассчитанные по волшебным формулам.

Если вы в зеленой группе — вы кандидат на «отлично автоматом».


Блок 1


2021-10-15 Practical Block 2021-11-03 14-27-56 image0.png

Концептуально:

2021-10-15 Practical Block 2021-11-03 15-02-30 image0.png

2021-10-15 Practical Block 2021-11-03 14-24-09 image0.png

(Их там 66)

    • Не нужно брать десятки задач на себя сразу, и освобождайте то, что не получается.
  • Решенное
    • Ну смотрите, как оформлено в прошлые годы
    • Решение на подстранице вашей личной страницы
      • Вики-ссылка на задачу
      • Python-код в «<source lang="python"></source>»
      • Метка «{{checkme}}», когда решите.
2021-10-15 Practical Block 2021-11-03 14-22-47 image0.png

(Их там 10)


  • Как легче решать Python
    • Загрузка данных
    • Выбирайте более свежий CPython или PyPy.

Разберитесь, как зарегистрироваться на «лабе»

Блок 2

Моделирование труднорешаемых задач и решение из промышленными солверами.

Концептуально:

  • Win-Win!
  • Бизнес-аналитикам, алгоритмистам, прожект и продукт-менеджерам.
  • Воркфлоу «взятия задачи» аналогичен блоку «Практикуемся_В_Алгоритмах»
    • Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в Lab17.
  • Надо решить одну! задачу, но очень желательно сделать это красиво!
    • Если все совсем шикарно — бонусные очки (если задача окажется сложной — тоже).
  • Идем на Lab17
  • «adv2022-course-pyomo-business-optimization» — курсы.
    • Если совсем новые в юпитер-ноутбуках — см. jupyter-intro
    • Параллельно можно смотреть воркшоп по Pyomo
    • Можно править, комментировать, но без вандализма, полезные улучшения (визуализации, исправления ошибок → бонус).
    • Там будет видео в каждом питон-ноутбуке.
  • Оформляем свои ноутбуки в папке «homeworks-2023», заведите там подпапку по вашему логину, желательно без пробелов.
  • Учимся на готовых решениях коллег - Решенные бизнес задачи, ну и в папке «optprob»



Блок 3

Выберем несколько тем и теоретических задач.

Те, кто по результатам предущих блоков вышел на «хор» до 12 декабря, смогут улучшить оценку





Материалы

Наверно не пригодятся для курса 2022 года.

Видеолекции

Книга

Специальная верстка для чтения с ноутбуков и КПК:

  • альбомная ориентация
  • крупные беззасечные шрифты

Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).

Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.

File:Book-advanced-algorithms.pdf

Book-advanced-algorithms.pdf

Примечания и ссылки

  • Рекомендуется прочитать хотя бы первые лекции по введению в Python и научные вычисления.

Полезная сопутствующая литература по курсу.