Blog:Advanced Algorithms

Материал из DISCOPAL
Перейти к: навигация, поиск

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

Уважаемые все пропустившие…

«Wish you were here»© «Опоздавшая Молодежь™»

Этот курс отличается стандартных курсов «зачитывания книжки» и «решения/списывания избитых упражнений + долбления заезженных тестов», основные его квесты расчитаны на активную работу в коллаборативных средах над уникальными (и поэтому «одноразовыми») заданиями, и требует большого внимания преподавателя. Он не масштабируется как «Calculus 101» и прочее такое[1]. В процессе «прогрева», в простом входном квесте типа Практикуемся В Алгоритмах учащиеся с одной стороны «вкатываются» в принципы взаимодействия, с другой — выясняется их количество и уровень — и в зависимости от этого строится основная карта заданий (например Blog:Advanced Algorithms/2024-09-08 Презентация курса «на осень 2024»).

Т.е. если было видно, что к курсу присоединяется сотня активно взаимодействующих, он был бы просто другой, с другими правилами, баллами, принципами. И наоборот, при считанных единицах, тоже было бы по-другому — и может более интересней, у нас были и индивидуальные работы над дипломами и исследовательским проектами.

Поэтому многократно озвучены справедливые и обоснованные правила, что если кто-то не присоединился к работе за время большее половины времени на курс[2], не говоря уже о прохождении[3] простого входного квеста — то это ваш выбор в отношении этого курса по выбору[4]. Он не один, курсов по выбору много, вы свой выбор сделали. Это невозможно запрыгивать на поезд, когда поезд уже давно ушел (нет, это индивидуальный коучинг, и не масштабируемый MOOC с тестами). И нет, чекание где-то за пределами нашего пространства работы, галочки, что вы выбрали курс, чтобы потом придти, по физтеховской привычке на «экзамен», и продавливать «я тут сам что-то изучал», «вы обязаны принять экзамен» , «ваще поставьте уд, раз я нашел кто ведет курс» — не работает (достаточно халявные пути прохождения на «уд» допускались и были, если бы учащийся хотя бы стартовал вовремя).

В этом году даже выяснилось, что лучше было бы сделать правила отсечки жесче — десятки набежавших за сутки до дедлайна, не извлекли никакой пользы от кривой публикации списанных заданий, но принесли и видимо, принесут много проблем процессу. Да, вы можете жаловаться декану-ректору-президенту-спортлото-… Уверен, вы даже можете добится закрытия курса прямо до окончания, или как-то иначе навредить процессу — пострадают при этом только ваши коллеги-студенты, серьезно.

Т.е. правила озучены, правила зафиксированы, делать индивидуальные исключения по бытовым детским причинам попросту неэтично (этой ссылкой и текстом я одинаково отвечаю на десятки таких запросов в ТГ и почте).

Запрыгнуть на стандартный поезд уже не получится. Единственные возможные исключения по опыту, это для персонажей декларирующих «Я уже бог в Алгоритмах/Computer Science/Hacking» (олимпиады, западные универы, огромный промышленный опыт), поэтому мне этот курс виделся детским, и я рассчитывал что все будет автоматом за счет Божественного Сияния… Тогда, индивидуально я еще могу предложить (не гарантированно, надо посмотреть резюме, пообщатся), пройти индивидуальные исследовательские работы, как-то связанные с этим курсом и алгоритмами (тут я очень надеюсь на пользу). Сейчас их список примерно такой (попробую вспомнить все, и да, мне надо будет поднимать стенды, активно взаимодействовать и т.п.).

  • Для тех, кто хорош и интересуется…
  • Для тех, кто ОЧЕНЬ хорош в ML в области какого-нибудь scoring/prediction можно поднять ценные околопромышленные датасеты.
  • Для тех, кто очень хорош в Python-backend — есть идея про NEOS-like сервер для Pyomo (для курсов Моделирование бизнес-задач и Моделирование труднорешаемых задач).
  • Для тех кто очень крут в комбинаторных алгоритмах — есть что покрутить.



  1. Хотя работа над этим ведется, ну и некоторые, принципиально новые методологические принципы освещены в докладах [1], [2]
  2. Два месяца это выше любой крыши
  3. Даже при регистрации — непрохождение входного теста — graceful отчисление, т.е. никаких отрицательных оценок, просто «мирный развод», ничего не пойдет в ведомости
  4. Да, есть многолетняя договоренность с МОУ об этом

2024-11-01 Feedback

2024-11-01 Feedback 2024-11-01 08-34-33 image0.png
2024-11-01 Feedback 2024-11-01 11-53-40 image0.png
  • Я понимаю, что многие, особенно все десятки тех, кто присоединились к активности в последние дни, и фигачащих решения ежеминутно, просто находят и копируют… (доставляют еще чередование стиля кода решений разных задач одним участником, опубликованные с разницой в минуту…)
    • Это очень печально, ибо профанирует идею win-win (я впустую «трачу одноразовые задачи», вы изображаете что решаете, театр™). Да, я всегда говорил, что так можно — просто вы «обманули кондуктора, купили билет, но не поехали», правила квеста обьявлены и соблюдаются.
    • Я «поддерживаю и такую игру», надеюсь, что хоть в процессе копирования вы чему-нибудь научитесь (как выглядит питон код, как редактировать статьи в MediaWiki), и может хотя бы потом, вы разберетесь, как работает скопированное (кстати, получите «отлично» за курс, если пройдете квест Визуализация алгоритмов — кстати, этот квест сейчас самое оптимальное, для честно решавших, для «отл» оценки), или просто заинтересуетесь и начнете тренироваться и решать задачи для себя.
    • Хотя, если философствовать, «гордая физтеховская фича» тянуть все до последнего, потом «не приходя в сознание» сделать «что-то наот…сь» — одна из причин наблюдаемого вокруг («театр безопасности-политики-технологий…»).
  • Я игнорирую «решения» тех, кто не осилил прочитать самые первые абзацы «домашней страницы курса» и выполнить квест «Как_зарегистрироваться_на_курс». Я действительно боюсь неуправляемых и «функционально безграмотных» — не в силах буду взаимодействовать. А блин, прямым текстом — например «заполненная личная страница, где есть ФИО и номер группы».
  • Безмозглое [1] тоже игнорирую. Вернее запоминаю как оскобление.
  • Если вы закрыли входной квест, не надо больше решать литкодовских задач, это не увеличит ваш балл, просто лишит задач (особенно легких [2]), тем, кому их не хватает.

2024-10-30 Feedback

2024-10-30 Feedback 2024-10-31 08-52-17 image0.png
  • Пожалуйста, прекратите
    • создавать хрень → [1]
    • ломать описания задач [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16]
    • это портит работу остальных студентов и ворует мое время. Если вы не в состоянии посмотреть вводные обучающие видео, или понять, как оформляют остальные по примеру — найдите кого-то из сокурсников, кто вас проведет за ручку.
    • что-то ни в одном предыдущем курсе так плохо с пониманием, здравым смыслом, и вменяемостью не было.
    • теперь я просто буду банить, если увижу такое.
  • Сотни зарегистрированных задач в Категория:Reserved — если уж зарезервировали — решайте, не тяните.
    • Можно было бы разрешить «отбирать», если нет решения за пару недель, но попробуем обойтись без этого.
2024-10-30 Feedback 2024-10-31 06-39-38 image0.png
  • Для невменяемых невнимательных, не разобравшихся, даже не прочитавших описание квеста
    • решения только на Python → [17], [18], решения на других языка не нужны.
  • Пишите также имя, а не только сокращения ФИО. [19]
2024-10-30 Feedback 2024-10-31 07-21-23 image0.png
  • Насыпаны литкодовые задачи… пришлось скрести по сусекам, «расширять категории», возиться с API, зато именно «Graph» теперь-полным-полно.
  • По входному квесту сдвинут дедлайн до 5 ноября, ибо внезапно набежало под конец куча народа и наконец зашевелились.
    • Но как и обещалось всегда — новые регистрации закрыты и все такое. Кто за 2 месяца прошел квест по регистрации — с теми и работаем.
    • Всех ресурсов — моего времени, подготовленных одноразовых квестов — не хватит на сотни внезапно возжелавших халявы.
  • Добавляйте ссылку на сабмишн, особенно для SPOJ/Codechef, ибо там несколько версий питонов, непонятно с каким пройдет. Даже для SPOJ это можно сделать — вот пример Участник:KoshelevEA/Solutions/Spoj/CUBEFR

2024-10-25 Feedback

2024-10-25 Feedback 2024-10-25 17-53-17 image0.png
  • Задержавшимся — оформляйте решения на своих личных подстраницах, найдите их, не портите постановки задач. [1], [2], [3], я не буду смотреть, только мучительно буду откатывать этот вандализм.
  • Еще раз — ну проверяйте свои решения сабмитом! Глупо тратить мое и свое время на [4], [5], [6]
  • В комменты тоже не надо срписать [7], [8], [9]
  • Пароль к алгоритмы.испран.рф очередной раз напомнен во всех наших чатах.
  • Починил разметку в Открытые практические задачи
    • Если не хватает легких литкодовских в какой-то секции — пингуйте (в какой секции кончились), насыплю.
      • Они ну ооочень легкие a, b, c, d, e, f, g
      • А уж с какой скоростью их решают! От резервирования до решения меньше чем за минуту! [10]
      • Сколько можно повторять, как оформлять → [11], [12]
  • Идет работа над «бизнес-задачами» (Отдельный разбор будет).
  • Идет работа над тестами, скоро опробуем на созвонах!

2024-10-14 Feedback

  • Плиз вики-ссылки на страницу задания → ну вот так 1, 2, 3
  • Старайтесь скопировать на страницу задание аккуратно, с «class Solution», с правильными отступами → 1, 2, 3
  • Не забывает проверять Категория:Проблемы_в_решении
  • 8 задач в 4 темах (распределяйте по темам!):
2024-10-14 Feedback 2024-10-14 07-53-28 image0.png
  • Ну и давайте активней! Кстати, бонусные задачи вовсю берутся!
2024-10-14 Feedback 2024-10-14 08-01-45 image0.png

2024-10-08 Feedback

2024-10-08 Feedback 2024-10-08 08-15-11 image0.png
2024-10-08 Feedback 2024-10-08 08-15-47 image0.png
  • Литкодовых задач насыпано (если вдруг кончились — пингуйте!).
  • Стиль — важно (особенно для тех, кто с других языков) (типа 1, 2, 3). Важно для других квестов, типа Моделирование бизнес-задач, Моделирование труднорешаемых задач
  • Codechef-сложные для Python, примеры как надо стараться — насыпано, так что увы, не могу засчитать.
    • Не надо дергать меня на решения которые не проходят тесткейсы (1, 2…)
    • Плюс в кодешефе какая-то фигня с миграцией judjing систем с июля — если видите, что не сабмитится решение → не берите (1) — пока вы не можете проверить, не могу и я засчитать (буду ждать, может к декабрю что-то сделают).
      • с другой стороны, может в новой системе будет легче с TL.
  • Указывайте какой питон (PyPy/CPython…), а лучше — сразу ссылку на прошедший сабмишн. Это особенно поможет, когда решение по TL проходит на грани (то проходит, то нет). Многие сразу догадались так делать (1)
  • Не перегружайте одну тему — вам надо накрыть 4!
2024-10-08 Feedback 2024-10-08 13-31-59 image0.png

2024-09-21 Выбираем удобное время созвонов

Непрерывное голосование или антиголосование за время созвонов.

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

Понедельник 10:007
33%
Понедельник 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: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:000
0%
Среда 11:000
0%
Среда 12:000
0%
Среда 13:000
0%
Среда 14:000
0%
Среда 15:000
0%
Среда 16:000
0%
Среда 18:000
0%
Среда 19:000
0%
Среда 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:001
5%
Четверг 19:001
5%
Четверг 20:001
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:0010
48%
Пятница 19:001
5%
Пятница 20:000
0%

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

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

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

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

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

2024-09-08 Презентация курса «на осень 2024»

Заголовок

Advanced Algorithms/2024-09-08 Презентация курса «на осень 2024»
Автор
Стас Фомин
Нижний колонтитул
Advanced Algorithms/2024-09-08 Презентация курса «на осень 2024»
Дополнительный нижний колонтитул

Стас Фомин, 00:48, 21 сентября 2024

→ продолжить чтение…

Не портите страницы задач, оформляйте правильно

Обзор квестов курса

Эксперимент — улучшаем старые решения

Несколько беспокоит, что многие из вас так и не приступали к практическим задачам. Возможно это почему-то сложно, или непонятно, а близок уже второй дедлайн (и главное, из-за него блокируется доступ к остальным квестам).

Экспериментально до второго дедлайна (2024-04-08) попробуем такую схему:

  • Можно взять любую из решенных задач, у которой не было решений в этом году — посмотреть-попробовать имеющееся Python-решение — и если получится его ускорить в 2 раза, то это решение тоже засчитаем. Как обычно, надеюсь, это будет честная работа.
Эксперимент — улучшаем старые решения 2024-03-28 16-04-56 image0.png
  • Ну разумеется, при оформлении все также — «резервируем» страницу-задачу и т.п., включая проверку стиля, и все остальные правила сохраняются.
  • И конечно, не стоит держать решения у себя до самого последнего момента дедлайна — мне очень не хотелось бы получить разом сотню решений на проверку под самый конец, отгружайте по готовности — что не успею проверить, то …


Python-решения — давайте потренируемся их сделать питонистей

При решении квеста «Практикуемся В Алгоритмах» жалко, что часто вижу технически питон код, но совсем не в питон стиле — переписанный нейросетями с других языков, плохо отформатированный, грязный... а ведь именно четкость и читаемость, это то, что я хочу чтобы получилось, до того, как перейдем к чему-то типа «Моделирование труднорешаемых задач», ибо там уже это править будет тяжело.

Чтобы прочувствовать дзен-питона, давайте хотя бы сначала придерживаться PEP-8, ну, или формально, проверяйте онлайн-чекером — чтобы это не прошло впустую, я тоже буду им проверять, и «заворачивать» решение, пока не пройдет. Это совсем несложное ограничение, грызу локти, что не делал такого раньше. Заодно это будет мотивировать добавить комментариев и сделать код более читаемым.

Ну 100% прохождение чистым сделать не получится — в LeetCode например, уже, как правило навязывают «непитоновое» название функции класса в каком-нибудь CamelCase, но в остальном, это будет неплохая тренировка питон-стиля — нормальные названия переменных, избавится от привычки ставить лишнюю пунктуацию, правильная расстановка пробелов и т.п.


2024-02-26 Feedback

Обращаю внимание — решать задачи по алгоритмической практике именно на Python. Первый квест по регистрации должен был научить вас внимательности.

2024-02-26 Feedback 2024-02-26 13-59-13 image0.png

Цель — именно взбодрить 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, но не осилили и упростили).
  • Не откладывайте, ибо все задачи с простыми решениями на пару строк (A, B) разберут! Или выбьют все задачи из какой-нибудь категории!
  • C другой стороны, те кто набрал нужное количество — остановитесь, оставьте задачи остальным (задачи это ценный ресурс, и цель не замучить вас, а чисто подтянуть-проверить-выровнять)! Кто закрыл квест, у тех будет подкрашено как-то так:
2024-02-26 Feedback 2024-02-26 14-33-39 image0.png

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


Регистрируемся, начинаем работать, выбираем удобное время созвонов

Итак, надеюсь трехчасовая презентация курса неделю наза была понятна, ожидаю, что начнется регистрация и работа. Пока как-то явно не все (желающие) осилили квест регистрации:

Регистрируемся, начинаем работать, выбираем удобное время созвонов 2024-02-14 16-21-38 image0.png

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

Вот мотивация — зарегистрированные могут голосовать и что-то выбирать.

Обсудим удобное время созвона. Аудиторию уже отобрали (кому-то она была нужна, а нам она особо не нужна, и даже неудобна в нашем формате), так что давайте подумаем, когда вам удобно, я попробую подстроится.

Кстати — завтра занятий не будет, рано еще что-то проверять, мне так кажется, давайте втягиваться пока — ну и передайте тем, кто не был, и даже не добрался до телеграмм-группы.

Итак:

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

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

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

Понедельник 10:000
0%
Понедельник 11:000
0%
Понедельник 12:000
0%
Понедельник 13:000
0%
Понедельник 14:000
0%
Понедельник 15:000
0%
Понедельник 16:000
0%
Понедельник 17:005
16%
Понедельник 18:001
3%
Понедельник 19:001
3%
Понедельник 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:003
10%
Вторник 18:001
3%
Вторник 19:000
0%
Вторник 20:000
0%
Среда 10:000
0%
Среда 11:000
0%
Среда 12:000
0%
Среда 16:000
0%
Среда 18:002
6%
Среда 19:000
0%
Среда 20:000
0%
Четверг 10:000
0%
Четверг 11:000
0%
Четверг 12:002
6%
Четверг 13:002
6%
Четверг 14:000
0%
Четверг 15:000
0%
Четверг 16:000
0%
Четверг 17:000
0%
Четверг 18:008
26%
Четверг 19:001
3%
Четверг 20:000
0%
Пятница 10:000
0%
Пятница 11:000
0%
Пятница 12:000
0%
Пятница 13:000
0%
Пятница 14:000
0%
Пятница 15:000
0%
Пятница 16:002
6%
Пятница 17:000
0%
Пятница 18:000
0%
Пятница 19:001
3%
Пятница 20:002
6%

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

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

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

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

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


Пользуясь случаем, напомню очевидное


Если что-то не работает, не получается — не стесняйте, пишите лично в телеграм — возможно прямо лично созвонимся и разберемся, что не так.

Разбор задачи «Независимое множество ребер»

TLDR
  • Не забывайте хотя бы перед сдачей прогонять ноутбук сверху донизу (можно запутаться в порядке выполнения ячеек и инициализации переменных)
  • Повторяемые вещи да, стоит засунуть в функцию (включая генерацию модели), но тогда не забывайте чтобы функция работала от параметров, а не от непонятно где заданных глобальных переменных
  • Используйте мои хелперы, чтобы парсить данные, входные данные держите прямо в ноутбуке, в плоских строках — нам тут не нужна возня с CSV-файлами
  • Преобразования данных как раз удобно показывать в ячейках ноутбука — новая структура — и сразу что в ней. Пандасовые датафреймы красивы, не надо их печатать превращая в строки.
  • При визуализации графа, запоминайте сгенеренную планаризацию прямо в нем же.
  • Индексы модели полезны, стоит итерировать по ним, если надо что-то делать с переменными.

Разбор задачи «Управление загрязняющими продуктами»

Управление загрязняющими продуктами 2023-12-23 13-25-41 image0.png



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

Разбор задачи «Управление Дисциплинами»

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

Разбор задачи «Домостроительство»

Разбор задачи «Домостроительство» 2023-11-28 04-14-15 image0.png


Pyomo-is-nice-after-lingo.svg
  • Решение студента
    • Обратите внимание, несмотря на правильный ответ, оно не ОК (и не только по оформлению). Это не ЦЛП.
  • Важно: Добивайтесь, чтобы и у вас в конце-концов решал CBC солвер, точно должно получится!

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


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

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

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

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

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

« новейшие ‹ 20 более новых старейшие »