Короткая ссылка: Advanced-algorithms

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

Кратко, что будет, чего не будет и что ждать.

Лекций — не будет. Это бред и бессмыслица, особенно при дистанционке. Созвоны будут при небходимости, в формате семинара, может индивидуальные.
Будет путешествие-квест, с разными активностями.
Берем только практические вещи — алгоритмы для разных задач, особенно NP-полных.
Условно будет три блока
- Теоретический — прочитать темы, посмотреть записи лекций, пройти тестирование, возможно решить некоторые теорзадачи.
- Тут будет первый отсев — если не проходите тесты (отсеим, скажем, 25% нижних), то «досвидания».
  - Не рекламируйте этот курс — чем меньше народу, тем будет лучше. Я заинтересован сократить численность всеми способами. Особенно нафиг я посылаю всех, кто пытается запрыгнуть в курс в середине семестра и позже. Без шансов. Когда-то прогибался в виде исключения, сейчас не буду.
- Легкий практический — решение нескольки задач, даваемых на собеседованиях в IT-компаниях, типа LeetCoding, SpojCoding, CodeChefing и т.п.
- Тут будет второй отсев — но можно будет тут свалить, получив «уд» — кому нужно время, и не очень все это интересно.
- Теор-практический — взять некоторую тему из заданных (свежая статья, я отберу), и сделать ее разбор-презентацию-реализацию в каком-нибудь jupyter или cocalc-ноутбуке (там будет видно). Тут возможно будет и индивидуальная работа и может тренировка презентейшн скиллс, что полезно для ваших дипломов (сколько я смотрел защит, все ужасно).

Ну остальные новости будут в группе, если что. Вопросы тоже там или напрямую.

Как зарегистрироваться — написано на основной странице курса, где все и будет https://discopal.ispras.ru/Advanced-algorithms

Регистраций открыта до 15 октября.

Подумайте еще раз — надо ли вам это. «Халявы», «Лекций», «Оценок за удаленную посещаемость» тут не будет. Даже «уд. нахаляву». Посмотрите, вокруг полно интересных курсов по выбору.

Преподаватель: С.А. Фомин

Для ФУПМов 6 курса, желающих записаться на курс по выбору «Эффективные алгоритмы», нужно:

Зарегистрироваться здесь. Залогинится.
Зайти на страницу настроек, указать свой email и подтвердить его.
На своей личной странице (это не страница настроек, это то, что сверху слева, с иконкой человечка), написать хотя бы ФИО и группу.
- Боже, как много народу с рассеянным вниманием уже до сюда не дочитывает.
Присоединится к телеграмм-группе.
Отметится в этом голосовании:

Записываемся на курс «Advanced Algorithms-2022»?

Да

18

100%

Bolyarich, Cherniavskii, Ed.inozemtsev, GeraskinDA, Kiranov dmitry, Larin.dv, Molotkov.md, PankratovViktor, Philipakhiarov, Reroyu, Robohant, ScherbakIA, Shurtugal, SochnevaMA, Trmigor, Vshokorov, Тенемурл, Чеканов Кирилл

Нет

0

0%

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

Установочный созвон будет наверно 9 сентября, раньше обычно бессмысленно.

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

Вопросы пишите на почту, или задавайте в группе.

Проблемы → Стасу Фомину

Успеваемость зарегистрированных студентов

В списке вы можете видеть разные цифры, отражающие вашу активность по темам курса. В конце — некоторые суммарные метрики, рассчитанные по волшебным формулам.

Если вы в зеленой группе — вы кандидат на «отлично автоматом».

Блок 1

Концептуально:

Win-Win!
Абсолютно практические задачи с собеседований.
- LeetCode
- CodeChef
- SpojCode
- Сотни решенных и нерешенных
Условно поделены на «Dynamic Programming», «Greedy», «Random», «Sorting», «Numbers»
Нужно быть залогиненным
- Скрыто из интернета
Изучайте Решенные практические задачи (Их там 825)
Надо решить 8 задач из 4 разных разделов. На Python.
За задачи из CodeChef и SpojCoding будут дополнительные бонусные очки (+3 очка)
10 очков — улучшение оценки на балл.

Выбирайте задачи из Открытые практические задачи, переходите к редактированию по «Беру…» →

- помечайте их как {{reserve-task|~~~~~}}
Зарезервированные задачи убираются в Зарезервированные практические задачи

(Их там 29)

- Не нужно брать десятки задач на себя сразу, и освобождайте то, что не получается.
Решенное
- Ну смотрите, как оформлено в прошлые годы
- Решение на подстранице вашей личной страницы
  - Вики-ссылка на задачу
  - Python-код в «<source lang="python"></source>»
  - Метка «{{checkme}}», когда решите.

- - Внизу вставка всего этого по клику →
Они попадут в Категория:На проверку

(Их там 9)

Как легче решать Python
- Загрузка данных
- Выбирайте более свежий CPython или PyPy.

Разберитесь, как зарегистрироваться на «лабе»

Lab

Блок 2

Моделирование труднорешаемых задач и решение из промышленными солверами.

Концептуально:

Win-Win!
Бизнес-аналитикам, алгоритмистам, прожект и продукт-менеджерам.
Воркфлоу «взятия задачи» аналогичен блоку «Практикуемся_В_Алгоритмах»
- Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в Lab.
Надо решить 2 задачи
- Если красиво и понятно оформлено — бонусные очки (если задача окажется сложной — тоже).

Выбирайте задачи из Открытые бизнес-задачи, переходите к редактированию по «Беру…» →
Зарезервированные задачи убираются в Зарезервированные практические задачи

Идем на Lab
«adv2022-course-pyomo-business-optimization» — курсы.
- Если совсем новые в юпитер-ноутбуках — см. jupyter-intro
- Параллельно можно смотреть воркшоп по Pyomo
- Можно править, комментировать, но без вандализма.
- Там будет видео в каждом питон-ноутбуке.
Оформляем свои ноутбуки в папке «advalg-2022-homeworks»
Учимся на готовых решениях коллег - Решенные бизнес задачи

Блок 3

Выберем несколько тем и теоретических задач.

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

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

Концептуально:

Это на «отл»
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

Материалы

Наверно не пригодятся для курса 2022 года.

Видеолекции

Книга

Специальная верстка для чтения с ноутбуков и КПК:

альбомная ориентация
крупные беззасечные шрифты

Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).

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

File:Book-advanced-algorithms.pdf

Примечания и ссылки

Рекомендуется прочитать хотя бы первые лекции по введению в Python и научные вычисления.

Полезная сопутствующая литература по курсу.

Очень хорошие лекции по классической теории сложности, написанные одним из корифеев оной: Introduction to Complexity Theory by Oded Goldreich
Более краткий курс по классической теории сложности, университет Technion.
Еще один классический курс лекций по теории сложности от László Lovász.
А. Китаев, А. Шень, М. Вялый, Классические и квантовые вычисления — замечательная книга. Содержит отличное введение в теорию сложности.
С. Дасгупта, Х. Пападимитриу, У. Вазирани, Алгоритмы [3]

[ Хронологический вид ]Комментарии

Можно ввести какое-то ограничение на количество забронированных задач? Люди бронируют по 10 задач и за неделю не делают ни одной из них.

— Глеб Фоков • 7 ноября 2020 в 14:48

страница

Да, я учел, ваш коммент, стал «срубать блокировки» старше 5 дней. Ограничение по количеству увы, в таком простом ворфлоу сделать сложно, остается рассчитывать на разумность и совесть (что не залочит все задачи) участников.

— Стас Фомин • 17 декабря 2020 в 14:53

страница

Войдите, чтобы комментировать.