Blog:Advanced Algorithms
Новости курса «Эффективные алгоритмы» для 6 курса ФУПМ МФТИ.
2024-10-14 Feedback
- Плиз вики-ссылки на страницу задания → ну вот так 1, 2, 3
- Старайтесь скопировать на страницу задание аккуратно, с «class Solution», с правильными отступами → 1, 2, 3
- Не забывает проверять Категория:Проблемы_в_решении
- 8 задач в 4 темах (распределяйте по темам!):
- Ну и давайте активней! Кстати, бонусные задачи вовсю берутся!
- Напоминаю — вы выбираете удобное время → Blog:Advanced_Algorithms/2024-09-21_Выбираем_удобное_время_созвонов
2024-10-08 Feedback
- Литкодовых задач насыпано (если вдруг кончились — пингуйте!).
- Стиль — важно (особенно для тех, кто с других языков) (типа 1, 2, 3). Важно для других квестов, типа Моделирование бизнес-задач, Моделирование труднорешаемых задач
- Codechef-сложные для Python, примеры как надо стараться — насыпано, так что увы, не могу засчитать.
- Не надо дергать меня на решения которые не проходят тесткейсы (1, 2…)
- Плюс в кодешефе какая-то фигня с миграцией judjing систем с июля — если видите, что не сабмитится решение → не берите (1) — пока вы не можете проверить, не могу и я засчитать (буду ждать, может к декабрю что-то сделают).
- с другой стороны, может в новой системе будет легче с TL.
- Указывайте какой питон (PyPy/CPython…), а лучше — сразу ссылку на прошедший сабмишн. Это особенно поможет, когда решение по TL проходит на грани (то проходит, то нет). Многие сразу догадались так делать (1)
- Не перегружайте одну тему — вам надо накрыть 4!
- Плиз, аккуратней с описаниями задач, не ломайте разметку.
- Если кто из 5 группы, и уже играл в Практикуемся В Алгоритмах — пинганите, этот квест зачту и так. Но можете поборотся за бонусные задачи.
- Есть прошедшие квест — вас уже ждут:
- Попробуем созвон в пятницу. Blog:Advanced_Algorithms/2024-09-21_Выбираем_удобное_время_созвонов
- Работал кто с Ghidra?
- Есть у кого-то желание изучать Sympy Physics и моделирование механики?
2024-09-21 Выбираем удобное время созвонов
Непрерывное голосование или антиголосование за время созвонов.
Какое время удобно для онлайн-созвона на неделе?
|
Вы должны войти в систему, чтобы участвовать в этом голосовании.
Ну и наоборот, антиголосование (чтобы не выбрать и максимально неудобное для многих время) — тут можно хоть все сделать «неудобным», если у вас хватит на это терпения.
В какое время вы точно не можете?
|
Вы должны войти в систему, чтобы участвовать в этом голосовании.
2024-09-08 Презентация курса «на осень 2024»
- Заголовок
- Advanced Algorithms/2024-09-08 Презентация курса «на осень 2024»
- Автор
- Стас Фомин
- Нижний колонтитул
- Advanced Algorithms/2024-09-08 Презентация курса «на осень 2024»
- Дополнительный нижний колонтитул
- Стас Фомин, 00:48, 21 сентября 2024
Не портите страницы задач, оформляйте правильно
- Изучите как оформлять — Практикуемся В Алгоритмах
- Решения только на своих подстраницах, правильно оформленные, с ссылкой на страницу-задачи!
- Ну вот свежий пример для ленящихся смотреть обьяснение → Участник: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 Выбираем удобное время для созвонов
Обсуждается удобное время созвона. Не каждую неделю, но несколько проведем.
- У вас по пять «голосов», можно их потратить на один или несколько слотов, можете их отзывать, и перенаправлять на другое время.
По идее, со временем должна выйти сходимость к какой-то удобной всем точке. Ну или по крайней мере, я смогу выбрать из какого-то не совсем уж неудобного всем «локального максимума».
Какое время удобно для онлайн-созвона на неделе?
|
Вы должны войти в систему, чтобы участвовать в этом голосовании.
Ну и наоборот, антиголосование (чтобы не выбрать и максимально неудобное для многих время).
В какое время вы точно не можете?
|
Вы должны войти в систему, чтобы участвовать в этом голосовании.