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

Материал из DISCOPAL
Перейти к: навигация, поиск






Проходим квест:

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

Записываемся на курс «Эффективные алгоритмы (Иннополис)-2024»?

Да33
100%
ADanilenko, Akazikov, AlferovIS, Eavladimirov, EjenY, Evgeny Poturilo, Evvnes, Gallyamov.im, Glbmkrv, Isypovi, Izwin is, Kdzelenova, Korchagin sergey, KoshelevEA, LunevLA, Maratkhusainov, MariaZharova, Markvernikov, Miroshnichenko, MordashovAP, NikitaAkshaev, Nikitashapovalov, RomanFilonov, Seryj09, Solovev, Ssergomol, Ssyrovatkin, Tiniakov.ad, Vladyur, VoyakinaES, Yaroslav Klimov М05-304Б, Ydanyok, Зайченкова Екатерина
Нет0
0%

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






Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ.

Лекторы
Стас Фомин,



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

Ведется список посещений.

В карантинное время — занимаемся самостоятельно по темам из раздела «Фокус», читаем книгу, смотрим видео и слайды, решаем задачи, см. ниже.


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


Книга

На растерзание отдается свежая сборка — можно искать в ней ошибки (они 100% есть — даже орфографические).

Специально искать опечатки смысла мало, проще действовать по принципу WIN-WIN, читать с помощью PDFXChange или другого ридера, позволяющего делать комментарии, делать пометки по ходу чтения и отсылать (каждый день) помеченный вариант на mailto:stas-fomin@yandex.ru. И каждый день скачивать заново — ибо книга будет пересобираться и меняться постоянно.

?

Темы

Усвоим весь объем — вовсе нет.png

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

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


Тренировка

Проверь себя, помнишь ли элементарные понятия и факты из курса.

Практика

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

(Их там 118)

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

(Их там 25)


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

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

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

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

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


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

Моделирование труднорешаемых задач 2023-04-24 14-45-02 image0.png

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

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

Результат .

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


Что делать?.

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

Тогда можно .

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

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

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

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

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

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

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

Ваш квест .

  • Pyomo-сведение к ЦЛП → PyomoLogo.png — есть Pyomo-формулировка для ЦЛП., Data-vis-logo.png — есть тестовые данные и визуализация.
  • 3SAT-сведение к задаче → Npc-reduction-python-logo.png — есть сведение на Python NP-полной задачи к данной.
  • Вероятностное тестирование → Yes-you-can-icon.png Можно доработать — сделать Вероятностное тестирование NPC-сведения!
  • Можно
    • все для одной задачи,
    • можно для разных (исправление ошибки или улучшение — ОК)
Желательно напрямую с 3SAT .

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

Моделирование труднорешаемых задач 2023-04-27 00-05-30 image0.png

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

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

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

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

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

Кому надо 10-баллов — запишите видеоролики по вашим питон-ноутбукам, см. Blog:Advanced Algorithms/2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики

Теоретические упражнения

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

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




Книга

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

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

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

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

File:book-advanced-algorithms.pdf

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

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

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



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

(нет элементов)

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

Источник — «https://discopal.ispras.ru/index.php?title=Курс_«Эффективные_алгоритмы_для_труднорешаемых_задач»&oldid=28774»