Викилоги

• Задача: Optprob/Управление_загрязняющими_продуктами
• ноутбук

• Читаемость важна:
  • Лучше понятные индексы, а не мутные генераторы
  • С «врапперами-декораторами» ограничения красивей и компактней.
• Ставьте линейные задачи (проверяйте, что солвер «cbc» тоже решает)

• Ноутбук
• Используйте хелпер-функции, чтобы грузить таблицы исходных данных в numpy-массивы и словари — это необходимо для работы с изменениями данных.
• Используйте SCIP по умолчанию (будет быстрее), но в конце проверьте, что и CBC нормально отработает — он «проверит», что у вас будет ЦЛП, а не квадратичное программирование, или что-то хитрое, что умеет SCIP.
• Еще одна полезная хелпер-функция «pretty_solution» — «красиво распечатает решение».

• Разбираем Optprob/Домостроительство
  • ноутбук
  • посмотрим и решение студента

• Решение студента
  • Обратите внимание, несмотря на правильный ответ, оно не ОК (и не только по оформлению). Это не ЦЛП.

• Важно: Добивайтесь, чтобы и у вас в конце-концов решал CBC солвер, точно должно получится!

• Ноутбук

• Оригинальное решение → Участник:3xMike/Optprob/Размещение административных учреждений

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

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

TLDR

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

В рамках ревью ваших заданий (конкретно Участник: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 не обязательно должно быть большой константой.
• Смело смотрите решения друг-друга, подглядывая интересное и полезное.

• В целом, опять почти разделались с входным блоком.

• Благо снова насыпано кучу легких, +1, хотя не все еще готовы (из тех, кто не смотрит, [1], Участник:Sfirstov/Eff_algos/Dynamic_Programming/Maximum_Sum_With_Exactly_K_Elements/ мои фидбеки очевидно).

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

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

• • ну не шлите мне непроходящие решения!, это же оскобляет.
• Активней с бизнес-оптимизацией, вот фидбек-замечания-советы вашим коллегам Blog:Advanced Algorithms/Разбор задачи «Назначение студентов в группы», Участник:3xMike/Optprob/Размещение административных учреждений
• Если что непонятно, спрашивайте на странице-решения, типа так и отправляйте «на проверку» (можете стирать категорию «проблемы в решении»)
• Скоро будут дополнительные блоки.

• У кого «зеленое» можно приступать к Курс лекций «Эффективные алгоритмы»#Блок 3 — «Бизнес-моделирование»

• В принципе, там на Lab17 достаточно посмотреть примеры в папке «adv2022-course-pyomo-business-optimization», рекомендуемый порядок — по номерам, но необязательно.

• почти к каждому ноуту подлинковано короткое объясняющее видео — не пропускайте.
• в папке «optprob» примеры прошлогодних решенных задач, с видеопрезентациями ваших старших коллег (ну и местами моими, буду еще добавлять разборы).

• полезное дополнительное:
  • Blog:Advanced Algorithms/Хорошие практики компактных Pyomo-формулировок на примере решения «Производство подразделяемых задач»
  • Blog:Advanced Algorithms/2022-12-19 Разбор задачи «Хранилище артефактов»
  • Blog:Advanced Algorithms/Разбор оптимизационной задачи «Группировка людей»
  • Blog:Advanced Algorithms/Хорошие практики компактных Pyomo-формулировок на примере решения «Задачи о станках»
  • Blog:Advanced Algorithms/Задача о двух кучах камней и примеры использования различных ЦЛП-солверов — правда на Lab17 (пока) нет других солверов, кроме «cbc». Но теоретически для решения задач другие не понадобятся.
  • Blog:Advanced Algorithms/2022-11-27 Разбор задачи «Капитальные инвестиции» и решения студента

• Заводите подпапку (по имени вашего логина желательно) в папке «homeworks-2023» — там и делайте ваши задания.
• И когда задание будет проверено (цифры сойдутся, претензий грубых не будет) → запишите ролик-презентацию, см. Blog:Advanced Algorithms/2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики

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

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

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

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

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

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

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

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

• Есть завершившие квест, но есть и даже не начавшие. →
  
  • Скоро начнутся новые квесты, на Lab17, последний раз обновил пригласительный токен. Не тяните с регистрацией (ну если вам не «уд» надо).

• Ссылка на страницу задачи + [1] + [2] + [3], не сразу на литкод, важно.
• Вики-разметка, это полезно и красиво + [4], [5] + [6]
  • Есть еще такое:

• Пожалуйста, делайте так, чтобы ваш код можно было быстро проверить, просто скопировав (не отрезайте «class Solution» и т.п.).
• Тем более, когда надо править код, когда чтобы он заработал.
• Еще лучше, когда будет готовая ссылка на сабмишн.
• Претензии стирать не надо, исправленный код (если что не так), добавьте просто ниже.

• Не боимся, очень многие решаются в пару строк → 1, 2 … не тяните.

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

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

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

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

• См. Решенные практические задачи
• Если не совсем понятно, идем сюда, живая лаборатория «Иллюстрированных Алгоритмов», видео ссылками в коде, ну или просто смотреть альбом.
• Совсем не знаете Python → http://pythontutor.ru (там только классов нет, но это почти не нужно), или https://exercism.org/tracks/python
• Если что-то непонятно — пишите, вполне можно сделать даже индивидуальный созвон, если что-то вот совсем не получается.

• Если скучно и некруто → выбирайте задачи со Spoj/Codechef → за них бонусные баллы, там возможно надо будет серьезно пооптимизировать
  • Blog:Advanced_Algorithms/Python-оптимизация_жадного_алгоритма_из_codechef
  • Blog:Advanced_Algorithms/Python-оптимизация_алгоритма_динамического_программирования_из_codechef
• или даже стать хакером:
  • Blog:Advanced_Algorithms/Путь_хакера_—_решение_задачи_с_codechef_на_питон._С_машинным_кодом

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

Моделирование труднорешаемых задач работает на нашей лабе и не требует ничего кроме броузера. Но если есть желание работать локально (плохой интернет), или привычка к 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.

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

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

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

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

• Все еще полно легких задач → 1, 2, 3, 4, 5, 6 …
• По-прежнему, кто-то ленится даже проверять → !1!, !2! → не надо так!
  • Если ваше решение в Категория:Проблемы_в_решении — оно не зачтено, его надо чинить.
• Не надо решать зарезервированные другими участниками задачи, см. Участник:DamirShodiev/minimum-time-to-visit-a-cell-in-a-grid — это неправильно.
• Схема оценок → уже появились предварительные.
• Квест для «занятых» → как выйти на «хор» (и в перспективе на «отл»)
  • через решение теорзадач (местами легких). Решите (ВСЕГО!) 3 задачи в двух темах, или одну бонусную в Решаем теоретические упражнения.
  • Может будут отдельные созвоны с тестами (набрать хоть какие-то баллы). Скорее всего во вторник 20.
• Моделирование труднорешаемых задач → не забудьте подключить проект, иначе ничего не увидите по ссылкам.
• Кому надо 10-баллов — запишите видеоролики по вашим питон-ноутбукам, см. Blog:Advanced Algorithms/2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики

• Активней с задачами
• Поправки:
  • [1] — резервируем с «~~~~» — чтобы было понятно кто.
  • [2] — и когда решили — тоже.
• Без TL не пройдет → Участник:Iamkrendel/Assignments/Escape_the_spreading_fire. Может поможет:
  • Blog:Advanced Algorithms/Python-оптимизация алгоритма динамического программирования из codechef
  • Blog:Advanced_Algorithms/Python-оптимизация жадного алгоритма из codechef
  • Blog:Advanced Algorithms/Python-оптимизация алгоритма динамического программирования из codechef
    • И только от отчаяния стоит идти путем хакера → Blog:Advanced Algorithms/Путь хакера — решение задачи с codechef на питон. С машинным кодом
• По-прежнему полно простых задач, Участник:Bruks/Solutions/partition-array-such-that-maximum-difference-is-k, Участник:Ilya/Solutions/sort-the-people, Участник:Krym4s/leetcode/maximum-consecutive-floors-without-special-floors, Участник:JulesIMF/node-with-highest-edge-score … — накрывающих даже несколько тем!

• Голосовалка → Vote-week-2023-04-07
  • Очень неактивно
  • 2.5 человека на вторник-вечер и четверг-утро.
  • Ну попробуем сегодня и вторник вечер.

• Но PULL/vs PUSH

• Поздравляем User:DmitryTeterin и нескольких других → можно переходить к следующему блоку
  • Моделирование труднорешаемых задач
  • Смотреть можно и остальным, но сначала решите задачи, перед тем, что-то делать («фейсконтроль»).

• В этом году достаточно «одной полной задачи» — Pyomo+NPC+Вероятностные тесты

• +1 балл → т.е. минимум «хор», кто никак не проявлялся, либо «отл» если достаточно очков за тесты и классную активность.
• чем быстрее начнете → тем быстрее освободитесь для сессии (и возможно более удобные задачи).

• «Фактор A»

WTF, не надо так

• Leetcode/array-with-elements-not-equal-to-average-of-neighbors

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

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

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

• [1]

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

• Участник:JulesIMF/max-difference-you-can-get-from-changing-an-integer

• Кто-то вырвался вперед… 
  • Участник:DmitryTeterin/rungs — ну просто же (первые расхватают все легкое!).
  • Но очень хотелось бы увидеть хотя бы 2/3 успешно начавших

• «Официальные видеоразборы» подшиваю к решенным задачам.
  • Ну можно смотреть из альбома (начинайте с самых коротких? увы, не получилось отсортировать).

• «Как зайти на Spoj»
  • Browsec (есть для FF)

• Кончилась «легкая сортировка с литкода» — насыпал много новых и легких.

• Логинимся, и разогревочный тест проверки заданий который были в фокусе 3 недели → Cозвонный тест
• Ну ведь не сложно же, решения в пару строчек → Участник:Loochek/Assignments/Maximum_Number_of_Consecutive_Values_You_Can_Make
• Я проверяю, так что только рабочие решения, и желательно, чтобы легче копировать → [1]
• Ждем ваших решений → Категория:На_проверку
• Что странно → совсем нет Категория:Reserved, Зарезервированные практические задачи
• Совсем еще не начали даже смотреть решения

• Ответы на ваши вопросы.
  • Как оформлять задачи и особенно, как заводить личные подстраницы → https://vimeo.com/803931121

• Разные группы, разный уровень — это нормально, выровняем.
  • Бывают хакеры, год назад ваша группа → Blog:Advanced_Algorithms/Путь_хакера_—_решение_задачи_с_codechef_на_питон._С_машинным_кодом
  • Есть кто вообще не.
  • В любом случае → Python оптимален для объяснения и набросков алгоритмов.

Всяко лучше чем Rust/C++

• • • Если уж совсем дремучие люди → им может помочь Udaff.
• Если нет, ничего страшного → идем на http://pythontutor.ru/, https://exercism.org/tracks/python
• После основ, попробуем жадные алгоритмы на Python и Leetcode.

• Если не получается сходу, давайте посмотрим десятки моих разборов решений,

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

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

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

• Жадный алгоритм в задачах о покрытии
• Жадный алгоритм в задаче о рюкзаке

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

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

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

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

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

(Их там 151)

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

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

(Их там 22)

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

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

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

• Как зарегистрироваться на курс
• Lab17
• Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ)

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

1. Да
2. Нет

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

Проверим?

• Если нет, ничего страшного → идем на http://pythontutor.ru/, https://exercism.org/tracks/python

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

1. Да
2. Нет

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

• Если нет (и даже если да), идем на Lab17, там курс по ним.

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

1. Да
2. Нет

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

Проверим?

• Если нет, ничего страшного разберемся в этом курсе.
  • Смотрим Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ)#Темы
  • Смотрим Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ)#Книга

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

1. Да
2. Нет

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

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

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