Blog:Advanced Algorithms
Новости курса «Эффективные алгоритмы» для 6 курса ФУПМ МФТИ.
Не портите страницы задач, оформляйте правильно
- Изучите как оформлять — Практикуемся В Алгоритмах
- Решения только на своих подстраницах, правильно оформленные, с ссылкой на страницу-задачи!
- Ну вот свежий пример для ленящихся смотреть обьяснение → Участник:Taekwandodo/task3, Участник:Taekwandodo/task8
- не портите страницы задач — вы только тратите мое время на попытки восстановить — [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20]
- Решите хотя бы 14 задач.
Эксперимент — улучшаем старые решения
Несколько беспокоит, что многие из вас так и не приступали к практическим задачам. Возможно это почему-то сложно, или непонятно, а близок уже второй дедлайн (и главное, из-за него блокируется доступ к остальным квестам).
Экспериментально до второго дедлайна (2024-04-08) попробуем такую схему:
- Можно взять любую из решенных задач, у которой не было решений в этом году — посмотреть-попробовать имеющееся Python-решение — и если получится его ускорить в 2 раза, то это решение тоже засчитаем. Как обычно, надеюсь, это будет честная работа.
- Ну разумеется, при оформлении все также — «резервируем» страницу-задачу и т.п., включая проверку стиля, и все остальные правила сохраняются.
- И конечно, не стоит держать решения у себя до самого последнего момента дедлайна — мне очень не хотелось бы получить разом сотню решений на проверку под самый конец, отгружайте по готовности — что не успею проверить, то …
Python-решения — давайте потренируемся их сделать питонистей
При решении квеста «Практикуемся В Алгоритмах» жалко, что часто вижу технически питон код, но совсем не в питон стиле — переписанный нейросетями с других языков, плохо отформатированный, грязный... а ведь именно четкость и читаемость, это то, что я хочу чтобы получилось, до того, как перейдем к чему-то типа «Моделирование труднорешаемых задач», ибо там уже это править будет тяжело.
Чтобы прочувствовать дзен-питона, давайте хотя бы сначала придерживаться PEP-8, ну, или формально, проверяйте онлайн-чекером — чтобы это не прошло впустую, я тоже буду им проверять, и «заворачивать» решение, пока не пройдет. Это совсем несложное ограничение, грызу локти, что не делал такого раньше. Заодно это будет мотивировать добавить комментариев и сделать код более читаемым.
Ну 100% прохождение чистым сделать не получится — в LeetCode например, уже, как правило навязывают «непитоновое» название функции класса в каком-нибудь CamelCase, но в остальном, это будет неплохая тренировка питон-стиля — нормальные названия переменных, избавится от привычки ставить лишнюю пунктуацию, правильная расстановка пробелов и т.п.
2024-02-26 Feedback
Обращаю внимание — решать задачи по алгоритмической практике именно на Python. Первый квест по регистрации должен был научить вас внимательности.
Цель — именно взбодрить Python-знания, ибо на этом основаны и другие квесты, и в курсе труднорешаемых задач экономия байтов и свойства других языков ни к чему — стремитесь именно к простоте кода. [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13]
- Да, даже если вы решаете «бонусные задачи» на Spoj/Codechef ([14]) — тоже нужен питон, именно в этом цель. Да, иногда это сложно, иногда возможно не получится, поэтому за них (решенных именно на Python) большие бонусные баллы — «2 балла из 10 баллов оценки» (как за весь квест с остальными задачами, плюс можно хоть ими до «отл» набрать — но не факт, что у вас получится — хотя польза будет «не взлетим, так поплаваем»). Напомню, некоторые полезные ссылки по теме (но давайте теперь лучше без машинного кода, плиз, понятно, что так можно засунуть любое сишное решение, это забавно, и уже понятно как делать, но такое…):
- К вопросу об оформлении (для тех, кто так и не стал смотреть как оформлять правильно) — надо делать вики-ссылки на исходную страницу-задачу: [15], [16], [17], [18], [19]. Это важно! Вики-ссылки двухсторонние поддерживающие сохранение целостности при переименовании ресурсов (именно таким задумывался Интернет, в рамках проекта Xanadu, но не осилили и упростили).
- Посмотрите на дзен питона и PEP8 — лучше убрать все ненужное, старайтесь сделать максимально компактно и читаемо! (тут точно можно выкидывать типизацию в функциях, убирайте ненужную пунктуацию (кто привых к C/Java).
- Не откладывайте, ибо все задачи с простыми решениями на пару строк (A, B) разберут! Или выбьют все задачи из какой-нибудь категории!
- C другой стороны, те кто набрал нужное количество — остановитесь, оставьте задачи остальным (задачи это ценный ресурс, и цель не замучить вас, а чисто подтянуть-проверить-выровнять)! Кто закрыл квест, у тех будет подкрашено как-то так:
Пока мне именно важно, чтобы все втянулись, а не так, что «отличники» где-то в отрыве уже занимаются и труднорешаемыми задачами и пишут статью в Q1, а все остальные даже не приступили к квесту.
Регистрируемся, начинаем работать, выбираем удобное время созвонов
Итак, надеюсь трехчасовая презентация курса неделю наза была понятна, ожидаю, что начнется регистрация и работа. Пока как-то явно не все (желающие) осилили квест регистрации:
(явно меньше чем в телеграм-канале, явно не до конца осилен квест у «красных»). Я не хочу составлять списки по общему набору (у большинства же курс по выбору) — так что давайте, таки завершим квест.
Вот мотивация — зарегистрированные могут голосовать и что-то выбирать.
Обсудим удобное время созвона. Аудиторию уже отобрали (кому-то она была нужна, а нам она особо не нужна, и даже неудобна в нашем формате), так что давайте подумаем, когда вам удобно, я попробую подстроится.
Кстати — завтра занятий не будет, рано еще что-то проверять, мне так кажется, давайте втягиваться пока — ну и передайте тем, кто не был, и даже не добрался до телеграмм-группы.
Итак:
- У вас по пять «голосов», можно их потратить на один или несколько слотов, можете их отзывать, и перенаправлять на другое время.
По идее, со временем должна выйти сходимость к какой-то удобной всем точке. Ну или по крайней мере, я смогу выбрать из какого-то не совсем уж неудобного всем «локального максимума».
Какое время удобно для онлайн-созвона на неделе?
|
Вы должны войти в систему, чтобы участвовать в этом голосовании.
Ну и наоборот, антиголосование (чтобы не выбрать и максимально неудобное для многих время) — тут можно хоть все сделать «неудобным», если у вас хватит на это терпения.
В какое время вы точно не можете?
|
Вы должны войти в систему, чтобы участвовать в этом голосовании.
Пользуясь случаем, напомню очевидное
- Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ) — страница курса
- Изучаем, то, что в разделе «Фокус»
- Проходим квест «Практика»
Если что-то не работает, не получается — не стесняйте, пишите лично в телеграм — возможно прямо лично созвонимся и разберемся, что не так.
Разбор задачи «Независимое множество ребер»
- TLDR
- Не забывайте хотя бы перед сдачей прогонять ноутбук сверху донизу (можно запутаться в порядке выполнения ячеек и инициализации переменных)
- Повторяемые вещи да, стоит засунуть в функцию (включая генерацию модели), но тогда не забывайте чтобы функция работала от параметров, а не от непонятно где заданных глобальных переменных
- Используйте мои хелперы, чтобы парсить данные, входные данные держите прямо в ноутбуке, в плоских строках — нам тут не нужна возня с CSV-файлами
- Преобразования данных как раз удобно показывать в ячейках ноутбука — новая структура — и сразу что в ней. Пандасовые датафреймы красивы, не надо их печатать превращая в строки.
- При визуализации графа, запоминайте сгенеренную планаризацию прямо в нем же.
- Индексы модели полезны, стоит итерировать по ним, если надо что-то делать с переменными.
Разбор задачи «Управление загрязняющими продуктами»
- Читаемость важна:
- Лучше понятные индексы, а не мутные генераторы
- С «врапперами-декораторами» ограничения красивей и компактней.
- Ставьте линейные задачи (проверяйте, что солвер «cbc» тоже решает)
Разбор задачи «Управление Дисциплинами»
- Ноутбук
- Используйте хелпер-функции, чтобы грузить таблицы исходных данных в numpy-массивы и словари — это необходимо для работы с изменениями данных.
- Используйте SCIP по умолчанию (будет быстрее), но в конце проверьте, что и CBC нормально отработает — он «проверит», что у вас будет ЦЛП, а не квадратичное программирование, или что-то хитрое, что умеет SCIP.
- Еще одна полезная хелпер-функция «pretty_solution» — «красиво распечатает решение».
Разбор задачи «Домостроительство»
- Решение студента
- Обратите внимание, несмотря на правильный ответ, оно не ОК (и не только по оформлению). Это не ЦЛП.
- Важно: Добивайтесь, чтобы и у вас в конце-концов решал 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 не обязательно должно быть большой константой.
- Смело смотрите решения друг-друга, подглядывая интересное и полезное.
2023-11-13 Feedback
- В целом, опять почти разделались с входным блоком.
- Благо снова насыпано кучу легких, +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 Кто решил бизнес-задачи, запишите по ним видеоролики
2023-10-19 Выбираем удобное время для созвонов
Обсуждается удобное время созвона. Не каждую неделю, но несколько проведем.
- У вас по пять «голосов», можно их потратить на один или несколько слотов, можете их отзывать, и перенаправлять на другое время.
По идее, со временем должна выйти сходимость к какой-то удобной всем точке. Ну или по крайней мере, я смогу выбрать из какого-то не совсем уж неудобного всем «локального максимума».
Какое время удобно для онлайн-созвона на неделе?
|
Вы должны войти в систему, чтобы участвовать в этом голосовании.
Ну и наоборот, антиголосование (чтобы не выбрать и максимально неудобное для многих время).
В какое время вы точно не можете?
|
Вы должны войти в систему, чтобы участвовать в этом голосовании.
2023-10-17 Feedback
- Есть завершившие квест, но есть и даже не начавшие. →
- Скоро начнутся новые квесты, на Lab17, последний раз обновил пригласительный токен. Не тяните с регистрацией (ну если вам не «уд» надо).
- Ссылка на страницу задачи + [1] + [2] + [3], не сразу на литкод, важно.
- Вики-разметка, это полезно и красиво + [4], [5] + [6]
- Есть еще такое:
- Пожалуйста, делайте так, чтобы ваш код можно было быстро проверить, просто скопировав (не отрезайте «class Solution» и т.п.).
- Тем более, когда надо править код, когда чтобы он заработал.
- Еще лучше, когда будет готовая ссылка на сабмишн.
- Претензии стирать не надо, исправленный код (если что не так), добавьте просто ниже.
2023-09-22 Feedback
- Только двое прошли тест по регистрации до конца («все всё заполнили и оказались на Lab17»). Нагоняйте! Еще раз выписал пригласительный токен, не ждите, когда протухнет и он.
- Кто не очень уверенно работает с Jupyter ноутбуками → пролистайте по порядку номеров краткий крешкурс по Jupyter-ноутбукам, и нашей системе коллаборативных юпитер-ноутбуков (можно смело редактировать, править, что-то исправлять). Рекомендуется на самом деле всем.
Сейчас идет первый квест → Blog:Advanced_Algorithms/Жадные_алгоритмы,_Python,_Leetcode,_система_визуализации_алгоритмов_—_начинаем_«в_алгоритмы» (там только ссылка на проект другая будет, у вас → идем сюда.
- Некоторые уже начали решать, видите — решения элементарны → 1, 2, 3… но не затягивайте, легкие задачи обычно выбивают первыми.
- Группа «ИСПРАН» кто уже решал такие задачи на третьем курсе — зачтутся и прошлые, просто пинганите, когда у вас наберется.
- Deadlinы где-то до конца октября, но чем раньше, тем лучше — можно перейти к следующим задачам.
Если вы не уверенно программируете простые задачи на Python, ничего страшного!
- См. Решенные практические задачи
- Если не совсем понятно, идем сюда, живая лаборатория «Иллюстрированных Алгоритмов», видео ссылками в коде, ну или просто смотреть альбом.
- Совсем не знаете Python → http://pythontutor.ru (там только классов нет, но это почти не нужно), или https://exercism.org/tracks/python
- Если что-то непонятно — пишите, вполне можно сделать даже индивидуальный созвон, если что-то вот совсем не получается.
- Если скучно и некруто → выбирайте задачи со Spoj/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.
Новую версию ноутбука желательно заливать через лабу, копированием или аплоадом...
2023-05-20 Разбор ошибок в вероятностном тестировании сведения 3SAT к Minimum Exact Cover
Разбор ошибок в вероятностном тестировании сведения 3SAT к Minimum Exact Cover.
TLDR: На самом деле, надо не забывать конвертировать решение ЦЛП для решенной задачи к True/False решениям о выполнимости 3SAT формулы.