Викилоги

Моделирование труднорешаемых задач работает на нашей лабе и не требует ничего кроме броузера. Но если есть желание работать локально (плохой интернет), или привычка к 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»
• Нужно быть залогиненным
  • Скрыто из интернета
• Изучайте Решенные практические задачи (Их там 1395)
• Надо решить 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|~~~~~}}
• Зарезервированные задачи убираются в Зарезервированные практические задачи

(Их там 152)

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

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

(Их там 18)

• Как легче решать 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/Производство подразделяемых задач.

• Optprob/Хранение артефактов на складе
• ноутбук

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

• • Те, кто решает задачи ради бонусов — решайте Spoj/Chef только они приносят бонусы.
• Не забывайте вопросы о постановке в страницу-решения → Участник:Philipakhiarov/Производство_штучных_изделий

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

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

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

• Воркфлоу «взятия задачи» аналогичен блоку «Практикуемся_В_Алгоритмах» и «Моделирование бизнес-задач»
  • Также, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в Lab.

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

• Идем на Lab
• Оформляем свои ноутбуки в папке «advalg-2022-homeworks»
• Учимся на готовых решениях коллег в соседних папках и решениях прошлых лет → articles2jupyter-examples

• Optprob/Группировка людей
• ноутбук

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

Студенту — не забыть доделать визуализацию результатата покрасивей (граф, кластеры, связи там). Например, как-то так → [1], [2]

• Старайтесь делать компактные и читаемые Pyomo-формулировки
  • тогда даже не понадобится куча плохочитаемых латех-пояснений.
• Посмотрите — как индексировать переменные и ограничения, как использовать слайсы в суммах, поменьше лишнего кода (особенно всяких скобок).
• Задача Optprob/Покупка станков
  • Решение Участник:Cherniavskii/BusinessProblems/Покупка станков (там ссылка на ноутбук).

«Задача о двух кучах камней и примеры использования различных ЦЛП-солверов»

• компактная задача и постановка, однако на которой зафейлился CBC — наш солвер «по умолчанию», и возник повод попробовать другие ЦЛП-солверы, и повод пошевелить постановку.

• Optprob/Поделить_поровну
• ноутбук

• Оценки по умолчанию уже есть
• Расхватывают простые задачи!
  • Пока еще есть из чего выбирать → Открытые бизнес-задачи
  • Blog:Advanced Algorithms/2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики
• Если что-то не понятно, смело смотрите Решенные бизнес задачи решения коллег.
  • Если у кого-то в чем-то затык — пишите мне, не затягивайте.
• Схема «балл за блок» плюс бонусы на еще балл.
  • У кого нет бонусных баллов, но хотите «отл» — скоро будут задания на «отл».
• Многие вышли на «хор» и близки к «отл» оценку
• Осталось по сути пара недель, не задерживаем.
• Созвон 2 декабря не факт что получится, конференция.

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

Ох, понял, что никто не пошел смотреть ссылки, поэтому полезное тут повторю рядом

• Не экономьте битрейт при записи OBS — ставьте при записи 3 Mbit, потом видеохостинги сами ужмут. Или перепакуете. Главное, не потратить время, получив замыленный и нечитаемый текст юпитер-ноутбуков, очень обидно. Почти как не записать звук.
• Сначала запишите минутку видео со звуком и послушайте — например, выяснится, что звука вообще нет, или он ужасный (что-то с уровнем например — можно поиграть настройками OBS), а то и вовсе надо сменить микрофон. Для общажных условий, любой микрофон прищепка (стоит копейки, пригодится вам обязательно — сейчас все айти удаленное, непрерывные созвоны — и возможно вас еле терпят и ненавидят за бубнящий микрофон, но почему-то не говорят) может оказаться лучше обычного встроенного в ноутбук микрофона, который может поймать электрошумы из собственной схемы, эхо плохомеблированной комнаты общежития, и т.п.

• Сделайте полноэкранный режим броузера — больше места для полезной информации.
• Лучше в discopal-lab понажимать на кнопочку с плюсиком → это лучше, чем просто увеличивать шрифты во всем броузере, хотя и можно и так.
  • Особенно это важно, когда у вас слабое разрешение — 720 например.
• Полезно сделать курсор большим — в виндах, KDE и GNOME это настраивается по разному, но настраивается.

Потом можно либо мне файл прислать, либо сами на любой видеохостинг (ну хоть на ютуб в unlisted mode) можете загрузить — подошью ваше обьяснение, и это будет работать как обучающий материал для ваших коллег! Ну или поместите «На проверку» решение, написав, что дописали ролик. Просто если вы это сделаете «тихо», где-то добавив ссылку в ноутбук, я это просто не замечу....

Задача Optprob/Капитальные инвестиции

• Решение студента, и фидбек по нему

• Решение преподавателя с разбором

Ключевой вывод:

• Пусть будет больше говорящих переменных (про каждый факт)
• Их связывают простые ограничения
• И целевая функция простая
• Это будет легче верифицировать и модифицировать.
• Решатели сами выкинут лишние переменные и превратят модель в плоскую.

• Загадка по TL → Участник:Larin.dv/Tree_of_comprimes, почему важно приводить ссылки на решения. Знает кто почему так?
  • Квест на отл?
• Категория:Проблемы_в_решении
• В целом, все справились, кто не справился — отчислен.

Переходим к «Курс лекций «Эффективные алгоритмы»#Блок 2» (уже несколько недель его делают те, кто приходил на созвоны, несколько задержался придумывая задачи).

• Не забывайте добавлять ссылки на задачи → [1], [2] … теряю время.
• «Насыпано» несколько сотен задач из литкода (чтобы полегче), по темам, где стало маловато задач
• возможно с «ошибками» классификации,
• возможно слабенькие («сложение двух целых»)
• но это неважно.
• Многие пришли к финишу →

• Категория:Проблемы в решении — непроход по TL, прилагайте ссылки на сабмишн.
• Если не прорубаетесь с кодчиф-спож → оставьте тестовые данные → с вашим алгоритмом → Участник:Vshokorov/Codechef/QRYLAND
• Начинайте, кто боится — ну несложно же → User:Vshokorov/leetcode/find-center-of-star-graph
• Пробуйте Lab