Короткая ссылка: Advanced-algorithms

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

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

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

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

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

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

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

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

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

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

+ Зарегистрируйтесь на «лабе»

Lab17

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

Да

14

100%

3xMike, Abatur, Alyona Urmashova, Bagurgl, Igorvozhga, Ivanstepanov, Lachin Sergey, LightVillet, OMShitikov, Sanya, Serj964, Sfirstov, Анна Дмитриенко, М05-204, Сергей Артерчук

Нет

0

0%

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

Первое установочное занятие будет 8 сентября, в 18-30 в 903 КПМ

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

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

Проблемы → Стасу Фомину

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

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

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

Содержание

1 Блок 1 — Практика
2 Блок 2 — Моделирование труднорешаемых задач
3 Блок 3 — «Бизнес-моделирование»
4 Блок 4 — Теоретические упражнения
5 Темы
6 Материалы

Блок 1 — Практика

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

Win-Win!
Абсолютно практические задачи с собеседований.
- LeetCode
- CodeChef
- SpojCode
- Сотни решенных и нерешенных
Условно поделены на «Dynamic Programming», «Greedy», «Random», «Sorting», «Numbers»
Нужно быть залогиненным
- Скрыто из интернета
Изучайте Решенные практические задачи (Их там 1370)
Надо решить N задач из 4 разных разделов. На Python.
- 8 если до 2024-11-01
- А если нет, просто блокируется доступ к другим квестам (отчисляем).
  - Кроме может ОЧЕНЬ особых случаев.
Старайтесь сделать максимально читаемое решение, и тут хороший повод потренировать стиль PEP-8, см. Blog:Advanced_Algorithms/Python-решения_—_давайте_потренируемся_их_сделать_питонистей
За задачи из CodeChef и SpojCoding будут дополнительные бонусные очки (1 балл из настоящей 10 бальной оценки!), их решать сложнее, там не подсказывают тест вызвавший ошибку, там могут быть жесткие TL, надо больше стараться, и да, их надо решать именно на Python (любом, который есть на сервисе, хоть PyPy) оптимизировать вам могут помочь статьи:
Бонусные задачи вполне решаются, если их не боятся → вот из последних решений → Участник:Mishaglik/Solutions/Spoj/FRQPRIME

Выбирайте задачи из Открытые практические задачи, переходите к редактированию по «Беру…» →

- помечайте их как {{reserve-task|~~~~~}}
Зарезервированные задачи убираются в Зарезервированные практические задачи

(Их там 116)

- Не нужно брать десятки задач на себя сразу, и освобождайте то, что не получается.
Решенное
- Ну смотрите, как оформлено в прошлые годы
- Решение на подстранице вашей личной страницы
  - Вики-ссылка на задачу
  - Python-код в «<source lang="python"></source>»
  - Метка «{{checkme}}», когда решите.

- - Внизу вставка всего этого по клику →
Они попадут в Категория:На проверку

(Их там 20)

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

Блок 2 — Моделирование труднорешаемых задач

Обязательно посмотрите

Цели: для осеннего курса 2023, где собрались скорее заинтересованные практикой, чем сложностью задач, можно

Сделать одну задачу целиком (визуализация, постановка в ЦЛП и сведение от 3SAT)
Или пару задач «поверхностно» — постановка + визуализация (это легкая часть), без части про сведение от 3SAT и тестирования (это может быть очень головоломно).
Можно сделать и больше, такой же блок, может заменить решение задачи из Моделирование бизнес-задач, если те почему-то не понравились.
Может можно будет даже сделать и меньше, если будет сделано качественно (красивая визуализация, или сложная задача и т.п) — т.е. не надо гнать количество, лучше сделать хорошо и красиво.
Разумеется, можно использовать все, что найдете в интернете (код, статьи, книги), или подскажут нейросети (но они обычно подсказывают неверно).

Проблема текущих подходов.

Проблема текущих подходов к преподаванию вычислительной сложности и труднорешаемых задач:

«ненужная заумь для ботанов»
«всякой фигни как матло у нас нет, у нас проектный подход»© (день открытых дверей МФТИ).
множество книг, слайдов, видео и т.п. — но все как правило перепев «ГД», на досках или одноразовых веселых видео.
- но не «живые модели»!

Результат .

Нет навыков проверяемых доказательств
Не получаются навыки работы с труднорешаемыми задачами.
- Мучать «эвристики» и «нейросети» не приходя в сознание.
  - «Какая у вас задача» — ну мы тут «GAN» сети пробовали, вот теперь трансформеры… — Задача то какая?

Что делать?.

… — Это же проблема Бен Бецалеля. Калиостро же доказал, что она не имеет решения.… — Мы сами знаем, что она не имеет решения, … Мы хотим знать, как её решать. ©

Научится формализованно формулировать
- ЦЛП
- 3SAT
Использовать решатели
- ЦЛП (cbc, coin, SCIP, CPLEX, GUROBI, COPT, MIPT…)
- SAT (см. SAT-Races [1]).

Тогда можно .

Часто решить задачу для реальных данных сходу
- Или покрутить постановку чтобы задача решалась (релаксация бизнес-ограничений).
Начать тестировать
- Алгоритмы полиномиальные в среднем
- Приближенные алгоритмы с гарантией точности
- Вероятностные алгоритмы
- Эвристики
Доказать труднорешаемость
- Конструктивное сведение кодом, тестирование
- Потом статья с объяснением.

Конструктивные алгоритмические доказательства .

Что вы получите .

Навыки моделирования
- в PYOMO, сразу см. воркшоп, Зеркало
- в PYSAT
- Jupyter Notebooks

→ Бизнес-аналитик-алгоритмист! (нарасхват!)
→ Курсовые-дипломы-статьи в JN
- В любой ситуации

С чем работаем .

Настоящие классические задачи в одном месте (ГД+ВК+…)
- Open Classic Hard Problems
  - Не пугайтесь, вам достаточно изучить одну задачу… но можно и все.
    - Не «книга, толщиной защищающая от прочтения»
Там (см. беджики-ссылки)
- Постановки
- Наброски ноутбуков для всех задач в Lab17
- Частично готовая модель
  - - тестовые данные (генератор)
    - визуализация
    - сведение к ЦЛП через Pyomo
    - сведение с 3SAT к задаче
    - вероятностное тестирование
    - видео с разьяснениями

Начать с простого .

Ваш квест .

Pyomo-сведение к ЦЛП → — есть Pyomo-формулировка для ЦЛП., — есть тестовые данные и визуализация.
3SAT-сведение к задаче → — есть сведение на Python NP-полной задачи к данной.
Вероятностное тестирование → Можно доработать — сделать Вероятностное тестирование NPC-сведения!
Можно
- все для одной задачи,
- можно для разных (исправление ошибки или улучшение — ОК)

Желательно напрямую с 3SAT .

Без классического дерева сведения (но можно копировать функции сведения тех задач).

Как с этим работаем .

Выбирайте задачи из Open Classic Hard Problems, переходите к редактированию по «Беру…» →
- Зарезервированные задачи просто помечаются в том же списке, для простоты.
  - Если видите, что зарезервировано кем-то в прошлом году — можно снять чужое резервирование, и поставить свое.
- Воркфлоу «взятия задачи» аналогичен блоку «Практикуемся_В_Алгоритмах»
- Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в «лаборатории»..
Текущая лаборатория
- Lab22
- Lab17 заболела (и может сдохла).
Как поотлаживаться локально через VSCode — потом.

Еще раз обо всем этом на одном слайде .

Файл:Idea-hard-problems-course.svg

Картинка в полный размер

Блок 3 — «Бизнес-моделирование»

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

Win-Win!
Бизнес-аналитикам, алгоритмистам, прожект и продукт-менеджерам.
Идем на https://алгоритмы.испран.рф

В папке «adv2022-course-pyomo-business-optimization» — курсы.
- Если совсем новые в юпитер-ноутбуках — см. jupyter-intro
- Параллельно можно смотреть воркшоп по Pyomo, ну или книги.
- Можно править, комментировать, но без вандализма, полезные улучшения (визуализации, исправления ошибок → бонус).
- Там будет видео в каждом питон-ноутбуке.
Учимся на готовых решениях^[1] коллег или разборах автора курса - Решенные бизнес задачи, ну и в папке «optprob» «adv2022-course-pyomo-business-optimization курса»
- Наверное одни из самых простых и вводных:
- Некоторые решения правда озвучены студентами и их решения могут так сказать, не следовать лучшим практикам — посмотрите обязательно какие-нибудь разборы от автора курса.
- Внутри видео могут быть возможно еще неоткрытые бонус-квесты (типа что-то сделать-визулизировать и т.п.)

Уровень 1: «потренироваться на кошках» — решите пару уже решенных задач, постарайтесь оформлять максимально компактно и понятно:

используйте хелперы
выделите построение модели в функцию от параметров
максимально понятные русскоязычные атрибуты модели.
оформляем свои ноутбуки в подпапке «homeworks/2024-autumn», заведите там подпапку по вашему логину, желательно без пробелов. Там же можно сохранять какие-то версии обучающих ноутбуков, если хотите с ними жестко поиграть.
сравните с решением, если вроде решение совпадает (или вы уверены, нашли ошибку и решили более правильно) — пинганите меня на ревью.

Цена — 1 балла за две задачи, но это обязательно, чтобы перейти к остальным квестам этого блока. Если найдете более эффективную постановку — например, раньше не решалось быстро через CBC, а теперь решается, ну или раза в два быстрее стало с SCIP, и т.п. — 1-2 балла.

Бонусный квест: который можно совместить с обучением — сделать визуализацию (matplotlib-networkx-seaborn-d3js… что хотите, на худой конец просто таблицей), для какой-нибудь решенной задачи, как в

… если ее нет. Это креативная задача, при этом потребует понимания решенной задачи — балл за хорошую визуализацию. Цена: 1-2 балла (ну насколько хорошая будет визуализация)

Уровень 2: решение нерешенной задачи:

Надо решить одну! нерешенную задачу, но очень желательно сделать это красиво!
Воркфлоу «взятия задачи» аналогичен блоку «Практикуемся_В_Алгоритмах»
Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук подпапке «homework/2024/autumn» на алгоритмах.
- Если все совсем шикарно — бонусные очки (если задача окажется сложной — тоже).
Выбирайте задачи из Открытые бизнес-задачи, переходите к редактированию по «Беру…» →
Зарезервированные задачи убираются в Зарезервированные практические задачи

Цена: 1-2 балла (насколько хорошо оформленно, насколько хорошая будет визуализация)

Можно решать дополнительные задачи (к первой задаче), но наверно всего больше двух пока не надо (нерешенные задачи — ценный ресурс, я его экономлю). Старайтесь сделать качественно, тогда можно будет решать больше.

Уровень 3: записать видеоролик по хорошо решенной задаче (если она сдана, отработаны претензии к оформлению и все такое). Используйте OBS

Научитесь пользоваться OBS — (см. также [2]), попробуйте использовать экранное рисование ([3]) и сделайте видео живым и понятным.
См. также → Blog:Advanced Algorithms/2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики

Цена: 1 балл, но постарайтесь.

Для истории, презентация от 2022 года: 📺 видео 📺

Блок 4 — Теоретические упражнения

Достаточно 4 задач из двух тем.

Нужно быть залогиненным
- Скрыто из интернета
Надо решить N задач из M разных разделов.
Либо одну бонусную задачу — считаем, что ее решение закрывает квест.

Выбирайте задачи из Open Exercises, переходите к редактированию по «Беру…»
- помечайте их как {{reserve-task|~~~~~}}
- Решение на подстранице вашей личной страницы
  - Вики-ссылка на задачу
  - Решение — можно использовать текст, латех целиком внутри тега «latex», или просто вставки математики внутри тега «m»
  - На худой конец — очень аккуратно оформить на листочке, сфотографировать, загрузить файлы (разберетесь).
  - Метка «{{checkme}}», когда решите.
  - Внизу вставка всего этого по клику →
Они попадут в Категория:На проверку
Все как обычно в наших квестах.

Изучайте чужие решения
- Категория:Решенные задачи
- Смотрите «Ссылки сюда» → решения студентов.

Темы

Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соответствующего PDF-файла.

Несложно о сложности. Примеры алгоритмов

Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема

Параллельный алгоритм Люби для максимального по включению независимого множества

Материалы

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

Видеолекции

Книга

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

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

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

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

File:Book-advanced-algorithms.pdf

Смешное — реакция «обычных программистов»

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

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

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

Очень хорошие лекции по классической теории сложности, написанные одним из корифеев оной: Introduction to Complexity Theory by Oded Goldreich
Более краткий курс по классической теории сложности, университет Technion.
Еще один классический курс лекций по теории сложности от László Lovász.
А. Китаев, А. Шень, М. Вялый, Классические и квантовые вычисления — замечательная книга. Содержит отличное введение в теорию сложности.
С. Дасгупта, Х. Пападимитриу, У. Вазирани, Алгоритмы [4]

↑ Особенно для физтехов, которые скипают теорию и не приходя в сознание смотрят «как решать»

[ Хронологический вид ]Комментарии

Можно ввести какое-то ограничение на количество забронированных задач? Люди бронируют по 10 задач и за неделю не делают ни одной из них.

— Глеб Фоков • 7 ноября 2020 в 14:48

страница

Да, я учел, ваш коммент, стал «срубать блокировки» старше 5 дней. Ограничение по количеству увы, в таком простом ворфлоу сделать сложно, остается рассчитывать на разумность и совесть (что не залочит все задачи) участников.

— Стас Фомин • 17 декабря 2020 в 14:53

страница

Войдите, чтобы комментировать.

[1] Особенно для физтехов, которые скипают теорию и не приходя в сознание смотрят «как решать»

[1]

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