Blog:Advanced Algorithms

Материал из DISCOPAL
Версия от 20:45, 28 декабря 2010; StasFomin (обсуждение | вклад) (Новая страница: «Новости курса «Эффективные алгоритмы» для 6 курса ФУПМ МФТИ.»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Разбор задачи «Размещение административных учреждений»


Размещение административных учреждений 2023-11-27 20-59-05 image0.png

Общие советы и соображения

  • Используйте хелперы (см. первую ячейку), чтобы максимально ненапряжно распарсить данные задачи
    • представьте что там вам присылают каждый день уродливые ворды или эксели, и вам каждый раз приходится все это набирать.
  • Лучше по-русски и по компактней, ну ужасно и тавтологично же «Indeces», не придется писать много русского и латех-текста
  • Модель лучше возвращать функцией — легче модифицировать, гибче, все лучше.
  • Поменьше грубых принтов — большинство объектов умеют сами себя хорошо показывать в ноутбуках.
  • Когда разряженные матрицы в решении — лучше показывать суть по ненулевым переменным решения, типа «что изменилось» — тут можно и printы.

Разместил Стас Фомин 28 ноября 2023 14:09 (GMT), нет комментариев.

Что делать, если солвер непонятно ругается

TLDR
  • Скорее всего, что-то не так с формулировкой — у вас не ЦЛП (Pyomo позволяет формулировать и не ЦЛП)
  • Чтобы понять, идите итерационно от простой формулировки к сложной, проверяя, что ни формулировка не падает, и солвер решает.
  • Или бисектите, комментируйте ограничения, используйте Timeline для отката.

Разместил Стас Фомин 24 ноября 2023 08:24 (GMT), нет комментариев.

Разбор задачи «Назначение студентов в группы»

В рамках ревью ваших заданий (конкретно Участник:Bagurgl/Назначение студентов в группы), как-то возникло желание сделать разбор-решение задачи Optprob/Назначение_студентов_в_группы, прямо в ноутбуке Участник:Bagurgl.

Можете смотреть решение там, но если Участник:Bagurgl вдруг решит удалить сильно переписать, то на всякий случай, сохраню эту свое видение правильной компактной и верифицируемой бизнес-модели и тут. 

def get_model(распределение_по_уровням, рейтинг_уровня, число_групп, макс_размер_группы):
    m = pe.ConcreteModel()
 
    число_уровней = len(распределение_по_уровням)
    блестящий = число_уровней - 1
    отличник = блестящий - 1
    m.I = range(число_уровней)
    m.J = range(число_групп)
 
    m.x = pe.Var(m.J, m.I, within=pe.NonNegativeIntegers)
 
    def рейтинг_группы(j):
        return sum([рейтинг_уровня[i] * m.x[j, i] for i in m.I])
 
    m.макс_рейтинг = pe.Var()
    @m.Constraint(m.J)            
    def макс_рейтинг_больше_всех(m, j):
        return m.макс_рейтинг >= рейтинг_группы(j)
 
    m.мин_рейтинг  = pe.Var()
    @m.Constraint(m.J)            
    def мин_рейтинг_меньше_всех(m, j):
        return m.мин_рейтинг <= рейтинг_группы(j)
 
    @m.Objective(sense=pe.minimize)                
    def дисбаланс(m):
        return m.макс_рейтинг - m.мин_рейтинг
 
    @m.Constraint(m.I)            
    def распределение_по_уровням_совпадает(m, i):
        return sum(m.x[..., i]) == распределение_по_уровням[i]
 
    @m.Constraint(m.I)            
    def размер_группы_не_превосходит_заданный(m, j):
        return sum(m.x[j, ...]) <= макс_размер_группы
 
    m.есть_блестящий = pe.Var(m.J, within=pe.Binary)
    @m.Constraint(m.J, [0, 1])            
    def установим_блестящего(m, j, t):
        if t:
            return распределение_по_уровням[блестящий] * m.есть_блестящий[j] >=  m.x[j, блестящий]
        return m.есть_блестящий[j] <=  m.x[j, блестящий]
 
    @m.Constraint(m.J, m.J)            
    def если_у_вас_есть_блестящий_а_у_нас_нет_докажите_что_у_вас_нет_лишнего(m, j, k):
        if j == k:
            return pe.Constraint.Skip
        return m.x[k, блестящий] <= 1 + распределение_по_уровням[блестящий] * (m.есть_блестящий[j] + 1 - m.есть_блестящий[k])
    return m
 
    @m.Constraint(m.J, m.J)            
    def если_у_вас_есть_блестящий_а_у_нас_нет_мы_требуем_не_меньше_отличников(m, j, k):
        if j == k:
            return pe.Constraint.Skip
        return m.x[j, отличник] - m.x[k, отличник] >= -распределение_по_уровням[отличник] * (m.есть_блестящий[j] + 1 - m.есть_блестящий[k])
    return m

Краткие выводы (что вспомнил):

  • Старайтесь сделать компактно и понятно (вам еще потом видео записывать, а кому-то его придется смотреть и все это читать).
    • Если можно обойтись без формул-латеха — то и не надо. Это как раз бич бизнес-оптимизационных статей, куча невнятных переменных, запутанные формулы — это только затрудняет верификацию.
    • Можно заводить промежуточные переменные-функции, для большей понятности
  • Удобно модель возвращать функцией от входных данных (легче играть с параметрами).
  • Делайте модель итерационно, смотрите что получается — и добавляйте и меняйте ограничения, поэкспериментируйте и с входными данными.
  • Давайте использовать по умолчанию солвер «SCIP», меньше вероятности, что затупит даже на этих детских задачах (в этом году пока мы без Gurobi и других более эффективных солверов, хотя я пытаюсь их вернуть).
  • Посмотрите в решении функции мои хелперы как быстро смотреть решение — ну можете доработать и свои, полезно сделать какую-нибудь интересную визуализацию (ну если там графы какие или еще что вдруг).
  • BigM не обязательно должно быть большой константой.
  • Смело смотрите решения друг-друга, подглядывая интересное и полезное.

Разместил Стас Фомин 13 ноября 2023 10:52 (GMT), нет комментариев.

2023-11-13 Feedback

  • В целом, опять почти разделались с входным блоком.
2023-11-13 Feedback 2023-11-13 13-31-10 image0.png

Дедлайны просрочены, с другой стороны, насыпано кучу легких → хороший повод потренироваться. Теперь надо решить 12 задач по 5 темам (всего там 6 тем).

  • После декабря → 16 задач по 6 темам.


Разместил Стас Фомин 13 ноября 2023 10:51 (GMT), нет комментариев.

Запускаем блок «Моделирование бизнес-задач»

Запускаем блок «Моделирование бизнес-задач» 2023-10-23 01-01-13 image0.png
  • В принципе, там на Lab17 достаточно посмотреть примеры в папке «adv2022-course-pyomo-business-optimization», рекомендуемый порядок — по номерам, но необязательно.
Запускаем блок «Моделирование бизнес-задач» 2023-10-23 01-06-53 image0.png
  • почти к каждому ноуту подлинковано короткое объясняющее видео — не пропускайте.
  • в папке «optprob» примеры прошлогодних решенных задач, с видеопрезентациями ваших старших коллег (ну и местами моими, буду еще добавлять разборы).
Запускаем блок «Моделирование бизнес-задач» 2023-10-23 02-34-58 image0.png

Разместил Стас Фомин 22 октября 2023 23:46 (GMT), нет комментариев.

2023-10-19 Выбираем удобное время для созвонов

Обсуждается удобное время созвона. Не каждую неделю, но несколько проведем.

  • У вас по пять «голосов», можно их потратить на один или несколько слотов, можете их отзывать, и перенаправлять на другое время.

По идее, со временем должна выйти сходимость к какой-то удобной всем точке. Ну или по крайней мере, я смогу выбрать из какого-то не совсем уж неудобного всем «локального максимума».

Какое время удобно для онлайн-созвона на неделе?

Понедельник 10:0025
42%
Понедельник 11:000
0%
Понедельник 12:000
0%
Понедельник 13:000
0%
Понедельник 14:000
0%
Понедельник 15:001
2%
Понедельник 16:000
0%
Понедельник 17:000
0%
Понедельник 18:000
0%
Понедельник 19:001
2%
Понедельник 20:000
0%
Вторник 10:000
0%
Вторник 11:000
0%
Вторник 12:000
0%
Вторник 13:000
0%
Вторник 14:000
0%
Вторник 15:000
0%
Вторник 16:000
0%
Вторник 17:000
0%
Вторник 18:000
0%
Вторник 19:001
2%
Вторник 20:000
0%
Среда 10:000
0%
Среда 11:000
0%
Среда 12:000
0%
Среда 16:000
0%
Среда 17:000
0%
Среда 18:000
0%
Среда 19:002
3%
Среда 20:003
5%
Четверг 10:000
0%
Четверг 11:000
0%
Четверг 12:000
0%
Четверг 13:000
0%
Четверг 14:000
0%
Четверг 15:000
0%
Четверг 16:000
0%
Четверг 17:000
0%
Четверг 18:000
0%
Четверг 19:0024
41%
Четверг 20:002
3%
Пятница 10:000
0%
Пятница 11:000
0%
Пятница 12:000
0%
Пятница 13:000
0%
Пятница 14:000
0%
Пятница 15:000
0%
Пятница 16:000
0%
Пятница 17:000
0%
Пятница 18:000
0%
Пятница 19:000
0%
Пятница 20:000
0%

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

Ну и наоборот, антиголосование (чтобы не выбрать и максимально неудобное для многих время).

В какое время вы точно не можете?

Понедельник 10:004
2%
Понедельник 11:004
2%
Понедельник 12:006
3%
Понедельник 13:004
2%
Понедельник 14:003
2%
Понедельник 15:003
2%
Понедельник 16:003
2%
Понедельник 17:003
2%
Понедельник 18:003
2%
Понедельник 19:003
2%
Понедельник 20:003
2%
Вторник 10:004
2%
Вторник 11:005
3%
Вторник 12:006
3%
Вторник 13:003
2%
Вторник 14:003
2%
Вторник 15:003
2%
Вторник 16:003
2%
Вторник 17:003
2%
Вторник 18:003
2%
Вторник 19:002
1%
Вторник 20:002
1%
Среда 10:003
2%
Среда 11:004
2%
Среда 12:006
3%
Среда 16:003
2%
Среда 17:003
2%
Среда 18:003
2%
Среда 19:002
1%
Среда 20:002
1%
Четверг 10:003
2%
Четверг 11:004
2%
Четверг 12:006
3%
Четверг 13:004
2%
Четверг 14:004
2%
Четверг 15:004
2%
Четверг 16:003
2%
Четверг 17:003
2%
Четверг 18:003
2%
Четверг 19:002
1%
Четверг 20:002
1%
Пятница 10:004
2%
Пятница 11:005
3%
Пятница 12:006
3%
Пятница 13:005
3%
Пятница 14:005
3%
Пятница 15:003
2%
Пятница 16:003
2%
Пятница 17:003
2%
Пятница 18:003
2%
Пятница 19:002
1%
Пятница 20:002
1%
Ничего из перечисленного1
1%

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


Разместил Стас Фомин 19 октября 2023 21:15 (GMT), нет комментариев.

2023-10-17 Feedback

  • Есть завершившие квест, но есть и даже не начавшие. →
    2023-10-17 Feedback 2023-10-19 23-28-58 image0.png
    • Скоро начнутся новые квесты, на Lab17, последний раз обновил пригласительный токен. Не тяните с регистрацией (ну если вам не «уд» надо).
2023-10-17 Feedback 2023-10-17 20-26-19 image0.png
  • Не боимся, очень многие решаются в пару строк → 1, 2 … не тяните.

Разместил Стас Фомин 19 октября 2023 21:09 (GMT), нет комментариев.

2023-09-22 Feedback

  • Только двое прошли тест по регистрации до конца («все всё заполнили и оказались на Lab17»). Нагоняйте! Еще раз выписал пригласительный токен, не ждите, когда протухнет и он.
  • Кто не очень уверенно работает с Jupyter ноутбуками → пролистайте по порядку номеров краткий крешкурс по Jupyter-ноутбукам, и нашей системе коллаборативных юпитер-ноутбуков (можно смело редактировать, править, что-то исправлять). Рекомендуется на самом деле всем.

Сейчас идет первый квест → Blog:Advanced_Algorithms/Жадные_алгоритмы,_Python,_Leetcode,_система_визуализации_алгоритмов_—_начинаем_«в_алгоритмы» (там только ссылка на проект другая будет, у вас → идем сюда.

  • Некоторые уже начали решать, видите — решения элементарны → 1, 2, 3… но не затягивайте, легкие задачи обычно выбивают первыми.
    • Группа «ИСПРАН» кто уже решал такие задачи на третьем курсе — зачтутся и прошлые, просто пинганите, когда у вас наберется.
  • Deadlinы где-то до конца октября, но чем раньше, тем лучше — можно перейти к следующим задачам.

Если вы не уверенно программируете простые задачи на Python, ничего страшного!


  • Насчет тестов и остальных блоков — это дальше.

Разместил Стас Фомин 22 сентября 2023 15:42 (GMT), нет комментариев.

Развертывание «Моделирования труднорешаемых задач» локально под линуксом

Моделирование труднорешаемых задач работает на нашей лабе и не требует ничего кроме броузера. Но если есть желание работать локально (плохой интернет), или привычка к vscode, то можно и все развернуть локально.

Под Linux все должно быть просто: 

git clone https://gitlab.ispras.ru/discopal/hard-problems-formulations.git
cd hard-problems-formulations


Если у вас федора-центось или что-то производное с пакетным менеджером DNF — вызовите 

./install-packages-fedora-rhel.sh

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

Потом должны встать без ошибок в локальный каталог-виртуаленв питоновские пакеты (ваш набор библиотек в системном питоне совсем не пострадает): 

./install-env.sh 
code .
  • Полезный опыт овладения VSCode — универсальный швейцарский нож ITшника.
  • Возможность отладки, построчно и REPL.

Новую версию ноутбука желательно заливать через лабу, копированием или аплоадом...


Разместил Стас Фомин 21 мая 2023 13:18 (GMT), нет комментариев.

2023-05-20 Разбор ошибок в вероятностном тестировании сведения 3SAT к Minimum Exact Cover

Разбор ошибок в вероятностном тестировании сведения 3SAT к Minimum Exact Cover.

2023-05-20 Разбор ошибок в вероятностном тестировании сведения 3SAT к Minimum Exact Cover 2023-05-20 11-22-57 image0.png

TLDR: На самом деле, надо не забывать конвертировать решение ЦЛП для решенной задачи к True/False решениям о выполнимости 3SAT формулы.

Разместил Стас Фомин 20 мая 2023 08:25 (GMT), нет комментариев.

2023-05-17 Feedback

  • Времени осталось мало!

2023-05-17 Feedback 2023-05-19 15-28-29 image0.png 2023-05-17 Feedback 2023-05-19 15-29-48 image0.png


Разместил Стас Фомин 18 мая 2023 08:39 (GMT), нет комментариев.

2023-04-22 Feedback

2023-03-22 Feedback 2023-04-25 01-18-11 image0.png

2023-03-22 Feedback 2023-04-25 12-08-01 image0.png
  • Голосовалка → Vote-week-2023-04-07
    • Очень неактивно
    • 2.5 человека на вторник-вечер и четверг-утро.
    • Ну попробуем сегодня и вторник вечер.
2023-04-22 Feedback 2023-04-25 13-42-20 image0.png
  • Но PULL/vs PUSH
2023-04-22 Feedback 2023-04-25 12-25-38 image0.png


2023-03-22 Feedback 2023-04-25 12-10-10 image0.png
  • В этом году достаточно «одной полной задачи» — Pyomo+NPC+Вероятностные тесты
2023-03-22 Feedback 2023-04-25 12-14-44 image0.png
  • +1 балл → т.е. минимум «хор», кто никак не проявлялся, либо «отл» если достаточно очков за тесты и классную активность.
  • чем быстрее начнете → тем быстрее освободитесь для сессии (и возможно более удобные задачи).


Разместил Стас Фомин 25 апреля 2023 11:20 (GMT), нет комментариев.

2023-03-04 Feedback


  • «Фактор A»

WTF, не надо так

Не делайте так. Посмотрите как оформлять.

https://vimeo.com/91590613 https://vimeo.com/803931121

Через некоторое время просто удалю здесь все. Вернее верну исходную версию, ибо вы просто стерли решением постановку.

Кто-то неверно делает ссылку на задачу →


  • Кто-то вырвался вперед… 
    • Участник:DmitryTeterin/rungs — ну просто же (первые расхватают все легкое!).
    • Но очень хотелось бы увидеть хотя бы 2/3 успешно начавших
  • «Официальные видеоразборы» подшиваю к решенным задачам.
    • Ну можно смотреть из альбома (начинайте с самых коротких? увы, не получилось отсортировать).
  • «Как зайти на Spoj»
  • Кончилась «легкая сортировка с литкода» — насыпал много новых и легких.

Разместил Стас Фомин 6 марта 2023 20:49 (GMT), нет комментариев.

2023-03-01 Feedback

→
2023-03-01 Feedback 2023-03-01 21-50-17 image0.png
→
2023-03-01 Feedback 2023-03-01 21-53-52 image0.png
  • Ответы на ваши вопросы.
    • Как оформлять задачи и особенно, как заводить личные подстраницы → https://vimeo.com/803931121

Разместил Стас Фомин 2 марта 2023 08:54 (GMT), нет комментариев.

Жадные алгоритмы, Python, Leetcode, система визуализации алгоритмов — начинаем «в алгоритмы»

Всяко лучше чем Rust/C++
      • Если уж совсем дремучие люди → им может помочь Udaff.
  • Если нет, ничего страшного → идем на http://pythontutor.ru/, https://exercism.org/tracks/python
  • После основ, попробуем жадные алгоритмы на Python и Leetcode.
Жадные алгоритмы, Python, Leetcode, система визуализации алгоритмов — начинаем «в алгоритмы» 2023-02-20 01-24-46 image0.png

и поиграйте с ними и их визуализацией живьем, для полного понимания.

  • Lab17 — как регистрироваться и присоединится к вашему проекту.
  • Запускаем VS Code Server в вашем проекте папке «algo-visual».
    • Теоретически, может сработать ссылка, но может нет[1], тогда смотрите видео как.
    • Открываем Python-файл и PNG-картинку визуализации в соседних вкладках VS Code, смотрим видео с объяснениями, играем, понимаем.
    • Не обязательно все смотреть, можно только непонятное, ролики минимальны 5-10 минут.

Немного теории по жадным алгоритмам, наши темы:

И начинаем процесс, см. ↓↓↓↓

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

(Их там 116)

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

(Их там 20)


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

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

  1. ↑ На lab17 новая версия, незапатченная, работаю над.

Разместил Стас Фомин 19 февраля 2023 23:59 (GMT), нет комментариев.

2023-02-09 Вводное знакомство

Знаете ли вы Python?

  1. Да
  2. Нет

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

Проверим?

Знаете ли вы Jupyter-ноутбуки?

  1. Да
  2. Нет

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

Знаете ли вы теорию сложности с вероятностными классами (RP-BPP…)?

  1. Да
  2. Нет

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

Проверим?

Решали ли вы задачи на Leetcode/Codechef/Spoj… ?

  1. Да
  2. Нет

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

  • Если нет, ничего страшного разберемся в этом курсе.

Разместил Стас Фомин 9 февраля 2023 07:11 (GMT), нет комментариев.

Хорошие практики компактных Pyomo-формулировок на примере решения «Производство подразделяемых задач»

В продолжении темы Blog:Advanced Algorithms/Хорошие практики компактных Pyomo-формулировок на примере решения «Задачи о станках» рассмотрим рефакторинг решения Участник:PankratovViktor/Производство подразделяемых задач.

Разместил Стас Фомин 22 декабря 2022 01:01 (GMT), нет комментариев.

2022-12-19 Разбор задачи «Хранилище артефактов»

Разместил Стас Фомин 19 декабря 2022 16:50 (GMT), нет комментариев.

2022-12-09 Feedback

Course-2022-balls.drawio.svg

2022-12-09 Feedback 2022-12-09 16-58-43 image0.png


Разместил Стас Фомин 11 декабря 2022 13:21 (GMT), нет комментариев.

2022-12-06 «Воспроизведение статей» — на отл.

Для тех, кому не хватило баллов, обязательная программа (алгоритмические задачи и бизнес-задачи) выполнена, и готовы идти на «отлично».

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

  • Это на «отл»
  • Win-Win!
  • Подготовка к защите дипломов-курсовых-кандидатских — моделирование диплома-научной работы и ее защиты.
  • Анализ научной статьи про алгоритмы, с переложением ключевой части в Jupyter-ноутбук.
    • Полностью «переписывать статью не надо» — не надо переводить-копировать все содержание.
      • Доказательства не нужны.
    • Разобраться в введении
    • Моделировать постановку задачи (обычно это ЦЛП)
      • Возможно придумать тестовые данные, если их там нет или не прилагались к статье.
    • Воспроизвести максимально декомпозировав, основной алгоритм — попробовать смоделировать и воспроизвести алгоритм для решения.
    • Некоторые примеры работ в папке articles2jupyter-examples
    • глобальная проблема воспроизводимости + https://paperswithcode.com/ → мы помогаем решать.
    • Если что не получается — пингуйте.
    • Запишите к ним видеоролик, как в Blog:Advanced Algorithms/2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики
    • Научитесь пользоваться OBS — (см. также [1]), попробуйте использовать экранное рисование ([2]) и сделать это живым и доступным.
    • Запишите видео-презентацию и забросьте мне (unlisted youtube, файлохранилища…)


  • Если предлагаемые статьи не понравились, а есть что-то про алгоритмы по теме вашей работы-диплома → можете работать над этим.
    • Может прямо это и будет драфтом дипломной работы
    • Презентацию можно сделать прямо из Jupyter-ноутбука, см RISE.
  • Идем на Lab
  • Оформляем свои ноутбуки в папке «advalg-2022-homeworks»
  • Учимся на готовых решениях коллег в соседних папках и решениях прошлых лет → articles2jupyter-examples

Разместил Стас Фомин 6 декабря 2022 12:06 (GMT), нет комментариев.

« новейшие … старейшие »
Источник — «https://discopal.ispras.ru/index.php?title=Blog:Advanced_Algorithms&oldid=142»