Blog:Advanced Algorithms
Материал из DISCOPAL
Новости курса «Эффективные алгоритмы» для 6 курса ФУПМ МФТИ.
2023-05-17 Feedback
- Времени осталось мало!
- Все еще полно легких задач → 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 Кто решил бизнес-задачи, запишите по ним видеоролики
2023-04-22 Feedback
- Активней с задачами
- Поправки:
- Без 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 балл → т.е. минимум «хор», кто никак не проявлялся, либо «отл» если достаточно очков за тесты и классную активность.
- чем быстрее начнете → тем быстрее освободитесь для сессии (и возможно более удобные задачи).
2023-03-04 Feedback
- «Фактор A»
WTF, не надо так
Не делайте так. Посмотрите как оформлять.
https://vimeo.com/91590613 https://vimeo.com/803931121
Через некоторое время просто удалю здесь все. Вернее верну исходную версию, ибо вы просто стерли решением постановку.
Кто-то неверно делает ссылку на задачу →
- Кто-то вырвался вперед…
- Участник:DmitryTeterin/rungs — ну просто же (первые расхватают все легкое!).
- Но очень хотелось бы увидеть хотя бы 2/3 успешно начавших
- «Официальные видеоразборы» подшиваю к решенным задачам.
- Ну можно смотреть из альбома (начинайте с самых коротких? увы, не получилось отсортировать).
- «Как зайти на Spoj»
- Browsec (есть для FF)
- Кончилась «легкая сортировка с литкода» — насыпал много новых и легких.
2023-03-01 Feedback
- Логинимся, и разогревочный тест проверки заданий который были в фокусе 3 недели → Cозвонный тест
- Ну ведь не сложно же, решения в пару строчек → Участник:Loochek/Assignments/Maximum_Number_of_Consecutive_Values_You_Can_Make
- Я проверяю, так что только рабочие решения, и желательно, чтобы легче копировать → [1]
- Ждем ваших решений → Категория:На_проверку
- Что странно → совсем нет Категория:Reserved, Зарезервированные практические задачи
- Совсем еще не начали даже смотреть решения
- Ответы на ваши вопросы.
- Как оформлять задачи и особенно, как заводить личные подстраницы → https://vimeo.com/803931121
Жадные алгоритмы, Python, Leetcode, система визуализации алгоритмов — начинаем «в алгоритмы»
- Разные группы, разный уровень — это нормально, выровняем.
- Бывают хакеры, год назад ваша группа → Blog:Advanced_Algorithms/Путь_хакера_—_решение_задачи_с_codechef_на_питон._С_машинным_кодом
- Есть кто вообще не.
- В любом случае → Python оптимален для объяснения и набросков алгоритмов.
- Если уж совсем дремучие люди → им может помочь Udaff.
- Если нет, ничего страшного → идем на http://pythontutor.ru/, https://exercism.org/tracks/python
- После основ, попробуем жадные алгоритмы на Python и Leetcode.
- Если не получается сходу, давайте посмотрим десятки моих разборов решений,
и поиграйте с ними и их визуализацией живьем, для полного понимания.
- Lab17 — как регистрироваться и присоединится к вашему проекту.
- Запускаем VS Code Server в вашем проекте папке «algo-visual».
Немного теории по жадным алгоритмам, наши темы:
И начинаем процесс, см. ↓↓↓↓
Концептуально:
- Win-Win!
- Абсолютно практические задачи с собеседований.
- LeetCode
- CodeChef
- SpojCode
- Сотни решенных и нерешенных
- Условно поделены на «Dynamic Programming», «Greedy», «Random», «Sorting», «Numbers»
- Нужно быть залогиненным
- Скрыто из интернета
- Изучайте Решенные практические задачи (Их там 1301)
- Надо решить N задач из 4 разных разделов. На Python.
- 8 если до 2024-11-01
- А если нет, просто блокируется доступ к другим квестам (отчисляем).
- Кроме может ОЧЕНЬ особых случаев.
- Старайтесь сделать максимально читаемое решение, и тут хороший повод потренировать стиль PEP-8, см. Blog:Advanced_Algorithms/Python-решения_—_давайте_потренируемся_их_сделать_питонистей
- За задачи из CodeChef и SpojCoding будут дополнительные бонусные очки (1 балл из настоящей 10 бальной оценки!), их решать сложнее, там не подсказывают тест вызвавший ошибку, там могут быть жесткие TL, надо больше стараться, и да, их надо решать именно на Python (любом, который есть на сервисе, хоть PyPy) оптимизировать вам могут помочь статьи:
- Бонусные задачи вполне решаются, если их не боятся → вот из последних решений → Участник:Mishaglik/Solutions/Spoj/FRQPRIME
- Выбирайте задачи из Открытые практические задачи, переходите к редактированию по «Беру…» →
- помечайте их как {{reserve-task|~~~~~}}
- Зарезервированные задачи убираются в Зарезервированные практические задачи
(Их там 175)
- Не нужно брать десятки задач на себя сразу, и освобождайте то, что не получается.
- Решенное
- Ну смотрите, как оформлено в прошлые годы
- Решение на подстранице вашей личной страницы
- Вики-ссылка на задачу
- Python-код в «<source lang="python"></source>»
- Метка «{{checkme}}», когда решите.
- Внизу вставка всего этого по клику →
- Они попадут в Категория:На проверку
(Их там 81)
- Как легче решать Python
- Загрузка данных
- Выбирайте более свежий CPython или PyPy.
Давайте каждый попробует за неделю сделать хотя бы одну задачу на жадные алгоритмы!
- ↑ На lab17 новая версия, незапатченная, работаю над.
2023-02-09 Вводное знакомство
- Да
- Нет
Вы должны войти в систему, чтобы участвовать в этом голосовании.
- Если нет, ничего страшного → идем на http://pythontutor.ru/, https://exercism.org/tracks/python
Знаете ли вы Jupyter-ноутбуки?
- Да
- Нет
Вы должны войти в систему, чтобы участвовать в этом голосовании.
- Если нет (и даже если да), идем на Lab17, там курс по ним.
Знаете ли вы теорию сложности с вероятностными классами (RP-BPP…)?
- Да
- Нет
Вы должны войти в систему, чтобы участвовать в этом голосовании.
- Если нет, ничего страшного разберемся в этом курсе.
Решали ли вы задачи на Leetcode/Codechef/Spoj… ?
- Да
- Нет
Вы должны войти в систему, чтобы участвовать в этом голосовании.
- Если нет, ничего страшного разберемся в этом курсе.
Хорошие практики компактных Pyomo-формулировок на примере решения «Производство подразделяемых задач»
В продолжении темы Blog:Advanced Algorithms/Хорошие практики компактных Pyomo-формулировок на примере решения «Задачи о станках» рассмотрим рефакторинг решения Участник:PankratovViktor/Производство подразделяемых задач.
2022-12-09 Feedback
- Blog:Advanced Algorithms/2022-12-06 «Воспроизведение статей» — на отл. — важно для отличников.
- Blog:Advanced Algorithms/Разбор оптимизационной задачи «Группировка людей»
- Blog:Advanced Algorithms/Хорошие практики компактных Pyomo-формулировок на примере решения «Задачи о станках»
- Blog:Advanced Algorithms/Задача о двух кучах камней и примеры использования различных ЦЛП-солверов
- Категория:На_проверку — через нее общение.
- Не забывайте чинить и переводить туда из Категория:Проблемы_в_решении
- План перехват → 5 бонусных баллов, кто найдет ошибку в чужом решении!
- Те, кто прошел отборочный блок с задачами — вас нет, ищите другой курс, фан в другом месте (чего только нет)
- Те, кто решает задачи ради бонусов — решайте Spoj/Chef только они приносят бонусы.
- Не забывайте вопросы о постановке в страницу-решения → Участник:Philipakhiarov/Производство_штучных_изделий
2022-12-06 «Воспроизведение статей» — на отл.
Для тех, кому не хватило баллов, обязательная программа (алгоритмические задачи и бизнес-задачи) выполнена, и готовы идти на «отлично».
Концептуально:
- Это на «отл»
- Win-Win!
- Подготовка к защите дипломов-курсовых-кандидатских — моделирование диплома-научной работы и ее защиты.
- Анализ научной статьи про алгоритмы, с переложением ключевой части в Jupyter-ноутбук.
- Полностью «переписывать статью не надо» — не надо переводить-копировать все содержание.
- Доказательства не нужны.
- Разобраться в введении
- Моделировать постановку задачи (обычно это ЦЛП)
- Возможно придумать тестовые данные, если их там нет или не прилагались к статье.
- Воспроизвести максимально декомпозировав, основной алгоритм — попробовать смоделировать и воспроизвести алгоритм для решения.
- Некоторые примеры работ в папке articles2jupyter-examples
- глобальная проблема воспроизводимости + https://paperswithcode.com/ → мы помогаем решать.
- Если что не получается — пингуйте.
- Запишите к ним видеоролик, как в Blog:Advanced Algorithms/2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики
- Научитесь пользоваться OBS — (см. также [1]), попробуйте использовать экранное рисование ([2]) и сделать это живым и доступным.
- Запишите видео-презентацию и забросьте мне (unlisted youtube, файлохранилища…)
- Полностью «переписывать статью не надо» — не надо переводить-копировать все содержание.
- Если предлагаемые статьи не понравились, а есть что-то про алгоритмы по теме вашей работы-диплома → можете работать над этим.
- Может прямо это и будет драфтом дипломной работы
- Презентацию можно сделать прямо из Jupyter-ноутбука, см RISE.
- Воркфлоу «взятия задачи» аналогичен блоку «Практикуемся_В_Алгоритмах» и «Моделирование бизнес-задач»
- Также, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в Lab.
- Выбирайте задачи из Открытые статьи для разбора, переходите к редактированию по «Беру…», резервируйте, как обычно …
- Идем на Lab
- Оформляем свои ноутбуки в папке «advalg-2022-homeworks»
- Учимся на готовых решениях коллег в соседних папках и решениях прошлых лет → articles2jupyter-examples
Разбор оптимизационной задачи «Группировка людей»
Хорошие практики компактных Pyomo-формулировок на примере решения «Задачи о станках»
- Старайтесь делать компактные и читаемые Pyomo-формулировки
- тогда даже не понадобится куча плохочитаемых латех-пояснений.
- Посмотрите — как индексировать переменные и ограничения, как использовать слайсы в суммах, поменьше лишнего кода (особенно всяких скобок).
- Задача Optprob/Покупка станков
- Решение Участник:Cherniavskii/BusinessProblems/Покупка станков (там ссылка на ноутбук).
Задача о двух кучах камней и примеры использования различных ЦЛП-солверов
«Задача о двух кучах камней и примеры использования различных ЦЛП-солверов»
- компактная задача и постановка, однако на которой зафейлился CBC — наш солвер «по умолчанию», и возник повод попробовать другие ЦЛП-солверы, и повод пошевелить постановку.
2022-12-02 Feeback
- Оценки по умолчанию уже есть
- Расхватывают простые задачи!
- Пока еще есть из чего выбирать → Открытые бизнес-задачи
- Blog:Advanced Algorithms/2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики
- Если что-то не понятно, смело смотрите Решенные бизнес задачи решения коллег.
- Если у кого-то в чем-то затык — пишите мне, не затягивайте.
- Схема «балл за блок» плюс бонусы на еще балл.
- У кого нет бонусных баллов, но хотите «отл» — скоро будут задания на «отл».
- Многие вышли на «хор» и близки к «отл» оценку
- Осталось по сути пара недель, не задерживаем.
- Созвон 2 декабря не факт что получится, конференция.
2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики
Кто решил бизнес-задачи, и чье решение уже проверено и признано правильным, — запишите разьясняющие видеоролики по вашим решениям с помощью OBS (это универсальное решение для создания видеодокументации — можно использовать камеру (и даже с хромакеем), можно использовать стилус для рисования, но на худой конец, просто скринкаст с нормальным звуком, ну и курсор можно сделать побольше... — так тоже пойдет.
Ох, понял, что никто не пошел смотреть ссылки, поэтому полезное тут повторю рядом
- Не экономьте битрейт при записи OBS — ставьте при записи 3 Mbit, потом видеохостинги сами ужмут. Или перепакуете. Главное, не потратить время, получив замыленный и нечитаемый текст юпитер-ноутбуков, очень обидно. Почти как не записать звук.
- Сначала запишите минутку видео со звуком и послушайте — например, выяснится, что звука вообще нет, или он ужасный (что-то с уровнем например — можно поиграть настройками OBS), а то и вовсе надо сменить микрофон. Для общажных условий, любой микрофон прищепка (стоит копейки, пригодится вам обязательно — сейчас все айти удаленное, непрерывные созвоны — и возможно вас еле терпят и ненавидят за бубнящий микрофон, но почему-то не говорят) может оказаться лучше обычного встроенного в ноутбук микрофона, который может поймать электрошумы из собственной схемы, эхо плохомеблированной комнаты общежития, и т.п.
- Сделайте полноэкранный режим броузера — больше места для полезной информации.
- Лучше в discopal-lab понажимать на кнопочку с плюсиком → это лучше, чем просто увеличивать шрифты во всем броузере, хотя и можно и так.
- Особенно это важно, когда у вас слабое разрешение — 720 например.
- Полезно сделать курсор большим — в виндах, KDE и GNOME это настраивается по разному, но настраивается.
Потом можно либо мне файл прислать, либо сами на любой видеохостинг (ну хоть на ютуб в unlisted mode) можете загрузить — подошью ваше обьяснение, и это будет работать как обучающий материал для ваших коллег! Ну или поместите «На проверку» решение, написав, что дописали ролик. Просто если вы это сделаете «тихо», где-то добавив ссылку в ноутбук, я это просто не замечу....
2022-11-27 Разбор задачи «Капитальные инвестиции» и решения студента
Задача Optprob/Капитальные инвестиции
Ключевой вывод:
- Пусть будет больше говорящих переменных (про каждый факт)
- Их связывают простые ограничения
- И целевая функция простая
- Это будет легче верифицировать и модифицировать.
- Решатели сами выкинут лишние переменные и превратят модель в плоскую.
2022-11-03 Feedback
- Загадка по TL → Участник:Larin.dv/Tree_of_comprimes, почему важно приводить ссылки на решения. Знает кто почему так?
- Квест на отл?
- Категория:Проблемы_в_решении
- В целом, все справились, кто не справился — отчислен.
Переходим к «Курс лекций «Эффективные алгоритмы»#Блок 2» (уже несколько недель его делают те, кто приходил на созвоны, несколько задержался придумывая задачи).
2022-10-14 Feedback
- Не забывайте добавлять ссылки на задачи → [1], [2] … теряю время.
- «Насыпано» несколько сотен задач из литкода (чтобы полегче), по темам, где стало маловато задач
- возможно с «ошибками» классификации,
- возможно слабенькие («сложение двух целых»)
- но это неважно.
- Многие пришли к финишу →
- Категория:Проблемы в решении — непроход по TL, прилагайте ссылки на сабмишн.
- Если не прорубаетесь с кодчиф-спож → оставьте тестовые данные → с вашим алгоритмом → Участник:Vshokorov/Codechef/QRYLAND
- Начинайте, кто боится — ну несложно же → User:Vshokorov/leetcode/find-center-of-star-graph
- Пробуйте Lab
2022-10-07 Feedback
- Решаем именно на Python!
- Нужны решения именно на Python! (иногда встречающиеся решения не на Python это тестовый запуск в 2019)
- → Категория:Проблемы в решении
- [1], [2], [3], …
- Оформляем именно как подстраницу → [4], [5]
- Участник:Vshokorov/Codechef/QRYLAND — если никак не решается, делайте генератор тестовых данных (но отдельно, в файл!).
- A_index
- Надо насыпать новых. Обещаю много легких, из литкода.
- Поздравляем первых закрывших блок.
- Втягивайтесь! Ибо второй блок придется идти без вас!
- 100500 решений ([6], Решенные практические задачи, [7]…)
2022-09-30 Feeback
- Начните решать! Все же очень просто!
- Не забудьте залогинится — решения скрываются от индексации (не бойтесь, поиском никто не найдет),
- Решайте задачи из разных тем! (См. «Bolyarich и динамическое программирование») — т.е. можно, но необязательно.
- 6 задач из 4 тем. (если задача на 2 темы — удобно — «я размазываю») — пока еще никто не набрал, хотя многие близко (снизить до 5 из 4?).
- Возможно нужны специальные занятия с отстающими.
- Дедлайна нет, но так вы не успеете на остальные квесты (плюс вас будем ждать некоторое время).
- По оформлению
- Используйте вики-ссылки.
- Лишнее писать не обязательно. Ваше авторство зафиксировано.
- Ну если вы не Участник:Ed.inozemtsev, Участник:Чеканов Кирилл
- Если еще и ссылка на проверочное решение — совсем замечательно.
- «Добрый день! Решаю задачу на codechef. Запустил свое решение, обернул весь в код try/except, но все равно на каких-то тестах возвращает RE, что это может значить? » [1]
- Скорее всего таймлимит или падение. Если не получается, и жалко сил, — опубликуйте свой генератор тестовых данных, зачтем как задачу и бонусный балл — может следующие поколения добьют, или на сервере поправят таймлимит.
- Насчет ресерч части — если у вас есть что-то, что хотите потренировать срочно, можно начать с этого.
