Blog:Advanced Algorithms
Новости курса «Эффективные алгоритмы» для 6 курса ФУПМ МФТИ.
2024-11-10 Feedback по GRE-квестам
По поводу квеста Изучение тестов по Computer Science
- Синтаксис вообще такой, но там главное как оформлять правильные варианты, в частности
- Ну уж орфографию то можно проверять в броузере — [1]
- Вот полезная кнопка → → она улучшает [2] + [3] типографику-пунктуацию-верстку (хотя и не всю [4]).
- В сам вопрос не надо писать номер, а вот в комментарии ниже да, полезно записать откуда он взялся → «файл.pdf Qномер_вопроса Pномер_страницы»
- В название вопроса как раз лучше писать тему и его смысл (это не покажут при проигрывании теста, но проще с этим работать составителю).
- А вот терминология — это важно, и размышление над описанием вопроса как раз поможет не допускать косяков, над которыми будут мучаться отвечающие. Сверяйтесь с википедией при переводе и т.п.
- Общие блоки для нескольких вопросов можно смело выкидывать в шаблоны.
- Блок ответов, если ответы короткие — лучше оформить списком.
- Кстати, ну хотя бы уровень «списки в медиавики-википедия-разметке» культурный человек должен знать.
- Ну и LaTeX-разметку хотя бы на уровне формул — она переживет TeX/LaTeX-системы как таковые.
Англотермины, да и переменные всякие внутри русского текста полезно выделять курсивом.
- Также, особенно чтобы не косячить с маттегами, вполне можно курсивом заменять выделение сущностей, если там нет сложных формул или даже верхних-нижних индексов.
Если можно покрасить код (найти близкий язык) — то покрасьте.
Если нашли где-то еще книгу с тестами, которых тут нет, и хотите поработать по ней — свяжитесь с преподавателем (киньте ее), добавлю и можно будет работать по ней.
- 2 балла за нее!
Ну и на следующем созвоне попробуем какой-нибудь из этих тестов… так что за некорректные вопросы возможно на вас обидятся коллеги:
И кстати, Подарочный квест для тех кто смотрит.
Уважаемые все пропустившие…
«Wish you were here»© «Опоздавшая Молодежь™»
Этот курс отличается стандартных курсов «зачитывания книжки» и «решения/списывания избитых упражнений + долбления заезженных тестов», основные его квесты расчитаны на активную работу в коллаборативных средах над уникальными (и поэтому «одноразовыми») заданиями, и требует большого внимания преподавателя. Он не масштабируется как «Calculus 101» и прочее такое[1]. В процессе «прогрева», в простом входном квесте типа Практикуемся В Алгоритмах учащиеся с одной стороны «вкатываются» в принципы взаимодействия, с другой — выясняется их количество и уровень — и в зависимости от этого строится основная карта заданий (например Blog:Advanced Algorithms/2024-09-08 Презентация курса «на осень 2024»).
Т.е. если было видно, что к курсу присоединяется сотня активно взаимодействующих, он был бы просто другой, с другими правилами, баллами, принципами. И наоборот, при считанных единицах, тоже было бы по-другому — и может более интересней, у нас были и индивидуальные работы над дипломами и исследовательским проектами.
Поэтому многократно озвучены справедливые и обоснованные правила, что если кто-то не присоединился к работе за время большее половины времени на курс[2], не говоря уже о прохождении[3] простого входного квеста — то это ваш выбор в отношении этого курса по выбору[4]. Он не один, курсов по выбору много, вы свой выбор сделали. Это невозможно запрыгивать на поезд, когда поезд уже давно ушел (нет, это индивидуальный коучинг, и не масштабируемый MOOC с тестами). И нет, чекание где-то за пределами нашего пространства работы, галочки, что вы выбрали курс, чтобы потом придти, по физтеховской привычке на «экзамен», и продавливать «я тут сам что-то изучал», «вы обязаны принять экзамен» , «ваще поставьте уд, раз я нашел кто ведет курс» — не работает (достаточно халявные пути прохождения на «уд» допускались и были, если бы учащийся хотя бы стартовал вовремя).
В этом году даже выяснилось, что лучше было бы сделать правила отсечки жесче — десятки набежавших за сутки до дедлайна, не извлекли никакой пользы от кривой публикации списанных заданий, но принесли и видимо, принесут много проблем процессу. Да, вы можете жаловаться декану-ректору-президенту-спортлото-… Уверен, вы даже можете добится закрытия курса прямо до окончания, или как-то иначе навредить процессу — пострадают при этом только ваши коллеги-студенты, серьезно.
Т.е. правила озучены, правила зафиксированы, делать индивидуальные исключения по бытовым детским причинам попросту неэтично (этой ссылкой и текстом я одинаково отвечаю на десятки таких запросов в ТГ и почте).
Запрыгнуть на стандартный поезд уже не получится. Единственные возможные исключения по опыту, это для персонажей декларирующих «Я уже бог в Алгоритмах/Computer Science/Hacking» (олимпиады, западные универы, огромный промышленный опыт), поэтому мне этот курс виделся детским, и я рассчитывал что все будет автоматом за счет Божественного Сияния… Тогда, индивидуально я еще могу предложить (не гарантированно, надо посмотреть резюме, пообщатся), пройти индивидуальные исследовательские работы, как-то связанные с этим курсом и алгоритмами (тут я очень надеюсь на пользу). Сейчас их список примерно такой (попробую вспомнить все, и да, мне надо будет поднимать стенды, активно взаимодействовать и т.п.).
- Для тех, кто хорош и интересуется…
- в физике-механике, доработка обучающих материалов на базе Jupyter Notebook c Sympy Physics Mechanics.
- в функциональщине-верификации — доработка обучающих материалов на базе Jupyter Notebook про Haskell / Idris.
- в Ghidra — есть что исследовать (связанное да, с курсами Моделирование бизнес-задач и Моделирование труднорешаемых задач).
- в машинном обучении в «классификации текстов» (с LLM или просто BERTaми, но с пониманием edge), можно переподнять автокатегоризацию для MediaWiki, или что-то такое.
- просто очень хорош в prompt engineering — есть квесты по разговору-классификации с gemma2 сообществ VK.
- Для тех, кто ОЧЕНЬ хорош в ML в области какого-нибудь scoring/prediction можно поднять ценные околопромышленные датасеты.
- Для тех, кто очень хорош в Python-backend — есть идея про NEOS-like сервер для Pyomo (для курсов Моделирование бизнес-задач и Моделирование труднорешаемых задач).
- Для тех кто очень крут в комбинаторных алгоритмах — есть что покрутить.
- ↑ Хотя работа над этим ведется, ну и некоторые, принципиально новые методологические принципы освещены в докладах [1], [2]
- ↑ Два месяца это выше любой крыши
- ↑ Даже при регистрации — непрохождение входного теста — graceful отчисление, т.е. никаких отрицательных оценок, просто «мирный развод», ничего не пойдет в ведомости
- ↑ Да, есть многолетняя договоренность с МОУ об этом
2024-11-01 Feedback
- Разгребаю набежавшую волну примерно в порядке регистрации.
- Я понимаю, что многие, особенно все десятки тех, кто присоединились к активности в последние дни, и фигачащих решения ежеминутно, просто находят и копируют… (доставляют еще чередование стиля кода решений разных задач одним участником, опубликованные с разницой в минуту…)
- Это очень печально, ибо профанирует идею win-win (я впустую «трачу одноразовые задачи», вы изображаете что решаете, театр™). Да, я всегда говорил, что так можно — просто вы «обманули кондуктора, купили билет, но не поехали», правила квеста обьявлены и соблюдаются.
- Я «поддерживаю и такую игру», надеюсь, что хоть в процессе копирования вы чему-нибудь научитесь (как выглядит питон код, как редактировать статьи в MediaWiki), и может хотя бы потом, вы разберетесь, как работает скопированное (кстати, получите «отлично» за курс, если пройдете квест Визуализация алгоритмов — кстати, этот квест сейчас самое оптимальное, для честно решавших, для «отл» оценки), или просто заинтересуетесь и начнете тренироваться и решать задачи для себя.
- Хотя, если философствовать, «гордая физтеховская фича» тянуть все до последнего, потом «не приходя в сознание» сделать «что-то наот…сь» — одна из причин наблюдаемого вокруг («театр безопасности-политики-технологий…»).
- Я игнорирую «решения» тех, кто не осилил прочитать самые первые абзацы «домашней страницы курса» и выполнить квест «Как_зарегистрироваться_на_курс». Я действительно боюсь неуправляемых и «функционально безграмотных» — не в силах буду взаимодействовать. А блин, прямым текстом — например «заполненная личная страница, где есть ФИО и номер группы».
- Безмозглое [1] тоже игнорирую. Вернее запоминаю как оскобление.
- Если вы закрыли входной квест, не надо больше решать литкодовских задач, это не увеличит ваш балл, просто лишит задач (особенно легких [2]), тем, кому их не хватает.
2024-10-30 Feedback
- Пожалуйста, прекратите
- создавать хрень → [1]
- ломать описания задач [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16]…
- это портит работу остальных студентов и ворует мое время. Если вы не в состоянии посмотреть вводные обучающие видео, или понять, как оформляют остальные по примеру — найдите кого-то из сокурсников, кто вас проведет за ручку.
- что-то ни в одном предыдущем курсе так плохо с пониманием, здравым смыслом, и вменяемостью не было.
- теперь я просто буду банить, если увижу такое.
- Сотни зарегистрированных задач в Категория:Reserved — если уж зарезервировали — решайте, не тяните.
- Можно было бы разрешить «отбирать», если нет решения за пару недель, но попробуем обойтись без этого.
- Для
невменяемыхневнимательных, не разобравшихся, даже не прочитавших описание квеста - Пишите также имя, а не только сокращения ФИО. [19]
- Насыпаны литкодовые задачи… пришлось скрести по сусекам, «расширять категории», возиться с API, зато именно «Graph» теперь-полным-полно.
- По входному квесту сдвинут дедлайн до 5 ноября, ибо внезапно набежало под конец куча народа и наконец зашевелились.
- Но как и обещалось всегда — новые регистрации закрыты и все такое. Кто за 2 месяца прошел квест по регистрации — с теми и работаем.
- Всех ресурсов — моего времени, подготовленных одноразовых квестов — не хватит на сотни внезапно возжелавших халявы.
- Добавляйте ссылку на сабмишн, особенно для SPOJ/Codechef, ибо там несколько версий питонов, непонятно с каким пройдет. Даже для SPOJ это можно сделать — вот пример Участник:KoshelevEA/Solutions/Spoj/CUBEFR
2024-10-25 Feedback
- Задержавшимся — оформляйте решения на своих личных подстраницах, найдите их, не портите постановки задач. [1], [2], [3], я не буду смотреть, только мучительно буду откатывать этот вандализм.
- Еще раз — ну проверяйте свои решения сабмитом! Глупо тратить мое и свое время на [4], [5], [6]
- В комменты тоже не надо
срписать [7], [8], [9]
- Пароль к алгоритмы.испран.рф очередной раз напомнен во всех наших чатах.
- Починил разметку в Открытые практические задачи
- Идет работа над «бизнес-задачами» (Отдельный разбор будет).
- Старайтесь при «переработке решенных» использовать лучшие практики рекомендованных примеров из Моделирование бизнес-задач.
- Идет работа над тестами, скоро опробуем на созвонах!
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ы.