Blog:Advanced Algorithms
Новости курса «Эффективные алгоритмы» для 6 курса ФУПМ МФТИ.
2009-09-21 Стартует курс «Эффективные алгоритмы»
Stas Fomin: Начиная с 4 сентября 2009 года стартует полусеместровый курс «Эффективные алгоритмы» для 6 курса ФУПМ МФТИ.
Курс по выбору, но выбор этот надо сделать осознано и вовремя. Т.е. подразумевается, что надо записаться на курс, посетив хотя бы одну лекцию в течении двух месяцев (deadline 30 октября 2009 года), либо, в крайнем случае (учеба зарубежом и т.п.) — напишите нам (Стас Фомин), что-нибудь придумаем. А поток внезапно осознавших желание сдать предмет только при приближении экзаменационной сессии будет совершенно легитимно игнорироваться.
Занятия еженедельно, по пятницам, в 10:45, 115 аудитория КПМ МФТИ. Возможны исключения — пропуск лекции по причине занятости лекторов, но об этом будет обязательно предупреждение в этом блоге — так что подписывайтесь, и предупреждайте менее продвинутых сокурсников. Лекции высокотехнологичные — проектор, ноутбук, слайды, демонстрации — тупо записывать ничего не придется, но спать тоже нежелательно.
Есть домашняя страничка курса, там указаны все нужные ссылки — на материалы, книгу в электронной форме (в бумажной — есть в библиотеке), слайды, и даже несколько видеолекций.
В курсе будет приветствоваться любая конструктивная активность студентов — нахождение опечаток и ошибок в материалах, посещение лекций, решение упражнений, и т.п. — все это будет учтено и не забыто. Возможно в этом семестре будет попытка самостоятельной реализации студентами алгоритмов на языке Python — это даст возможность «почувствовать» алгоритмы с минимальными накладными расходами на «программизмы».
_ _
/\ | | | |
/ \ __| |__ __ __ _ _ __ ___ ___ __| |
/ /\ \ / _` |\ \ / // _` || '_ \ / __|/ _ \ / _` |
/ ____ \| (_| | \ V /| (_| || | | || (__| __/| (_| |
/_/ _\_\\__,_| \_/ \__,_||_|_|_| \___|\___| \__,_|
/\ | | (_)| | | |
/ \ | | __ _ ___ _ __ _ | |_ | |__ _ __ ___ ___
/ /\ \ | | / _` | / _ \ | '__|| || __|| '_ \ | '_ ` _ \ / __|
/ ____ \ | || (_| || (_) || | | || |_ | | | || | | | | |\__ \
/_/ \_\|_| \__, | \___/ |_| |_| \__||_| |_||_| |_| |_||___/
__/ |
|___/
2009-06-16 Сложность алгоритмов: экзамен прошел
Stas Fomin: Прошел экзамен по «сложность алгоритмов». Тем, кто успешно сдал — веселых каникул, те, кто хочет пересдать — договаривайтесь о времени с Николаем Николаевичем. Любые другие вопросы по курсу — Стасу Фомину.
2009-06-08 Экзамен по курсу «Сложность алгоритмов»
Stas Fomin: Экзамен по курсу «Сложность алгоритмов» будет в ИСПРАН, в 11:30, 10 июня. Встреча около комнаты 301, а там видно будет.
2009-02-25 «сложность алгоритмов» — 2009
Stas Fomin: Стартовал курс «Сложность алгоритмов» весеннего семестра 2009. Вся информация по курсу будет здесь.
___ _
/ (_) | | o
| __ _ _ _ _ | | _ _|_
| / \_/ |/ |/ | |/ \_|/ |/ /\/ | | | |
\___/\__/ | | |_/|__/ |__/|__/ /\_/|_/|_/ \_/|/
/| /|
\| \|
_
| |
__ | |
/ \_|/
\__/ |__/
|\
|/
___, _ _
/ | | | o | |
| | | | __, __ ,_ _|_ | | _ _ _ ,
| | |/ / | / \_/ | | | |/ \ / |/ |/ | / \_
\__/\_/|__/\_/|/\__/ |_/|_/|_/| |_/ | | |_/ \/
/|
\|
2008-12-25 Экзамен завершен
Stas Fomin: Экзамен(ы) завершен(ы)! Поздравляю всех с полученными результатами. Если кому-то страшно нужно будет спасти красный диплом, то потенциально возможность пересдать на «отлично» в зимнюю экзаменационную сессию (после 10 января) сохраняется. В таком случае, свяжитесь с нами.
2008-12-22 Эффективные алгоритмы: экзамен-1
Stas Fomin: Итак, как и обещано, Top-10, отобранных из числа посещавших лекции и участвующих в вычитывании и конструктивном комментировании книги, получили «отлично» автоматом. Таким образом, посещения лекций дают возможность проявить себя в удобном сотрудничестве (что особенно актуально для студентов с жестким графиком), ну а сотрудничество вознаграждается неиллюзорной экономией времени и нервов, потребляемых стандартным экзаменом. В целом, «зачистка» текста была вполне конструктивной, за исключением того момента, что вместо ожидаемого месяца совместной работы и неторопливых и вдумчивых консультаций по email, получился аврал за несколько дней до экзамена, когда все «проснулись», и помчались зарабатывать баллы. В следующий раз, правила будут изменены, чтобы добавить преимущества тем, кто начал готовиться заблаговременно.
Послание следующим поколениям: это не тот экзамен, к которому можно подготовится за пару ночей на «отлично». К тому же, мы будем повышать планку, и, например, зубрение ответов на тесты будет недостаточно для «удовлетворитено».
Прошел и основной экзамен. В целом, более 2/3 зарегистрированных получили оценки.
Следующий этап будет ориентировочно в 12:00, 24 декабря в ИСПРАН. Сбор у комнаты 301.
2008-12-10 Темы к экзамену
Stas Fomin: Темы к экзамену совпадают с текущим списком опубликованных слайдов:
- «Несложно о сложности. Примеры алгоритмов».
- «Формально об алгоритмах. Вычислительные модели».
- «Временная и пространственная сложность алгоритмов».
- «Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC».
- «Вероятностные вычисления. Классы RP, coRP, ZPP, BPP».
- «Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема».
- «PCP и аппроксимируемость».
- «Жадный алгоритм в задачах о покрытии».
- «Жадный алгоритм покрытия для почти всех исходных данных».
- «Приближенный алгоритм для метрической задачи коммивояжера».
- «Жадный алгоритм в задаче о рюкзаке».
- «Динамическое программирование для задачи о рюкзаке».
- «Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке».
- «Полиномиальный в среднем алгоритм для задачи упаковки».
- «Полиномиальный в среднем алгоритм для задачи о рюкзаке».
- «Полиномиальный в среднем алгоритм для SAT».
- «Вероятностный подсчет числа выполняемых наборов для ДНФ».
- «MAX-SAT: вероятностное округление».
- «MAX-SAT: дерандомизация».
- «Дерандомизация Люби».
- «MAX-CUT: вероятностное округление».
- «Параллельный алгоритм Люби для максимального по включению независимого множества».Т.е. другие темы («византийское соглашение» и т.п. ) — читать и учить необязательно. Выбор счастливчиков, получивших отлично автоматом будет проведен 17 декабря. Но в любом случае, все ваши комментарии полученные до экзамена будут учтены и будут положительно влиять на оценку.
2008-11-19 Эффективные алгоритмы: анонс экзамена
Stas Fomin: Сам экзамен деканат запланировал (ориентировочной) на 19 декабря в 110 КПМ МФТИ.
Начнем наверно в 10:40.
Формат экзамена: тесты на знание основных определений и результатов (пользоваться материалами нельзя), по результатам тестов определяются «слабые» области, по ним задаются вопросы и задачи (при подготовке пользоваться материалами можно).
Возможны последующие сдачи, для улучшения оценки.
Они, скорее всего, будут проходить в ИСП РАН (Москва, м. Таганская, Большая Коммунистическая, д. 25). Комната 301.
2008-11-18 Эффективные алгоритмы: стартует досрочная экзаменационная сессия
Stas Fomin: Итак, по курсу «Эффективные алгоритмы» стартует досрочная экзаменационная сессия, с возможностью получить отличную оценку автоматом, без единой встречи с экзаменаторами. Получить экзамен автоматом могут те, кто посетил не меньше 50% лекций, в спискемы пометили их вот таким цветом (оранжевым) фона. От избранных ожидается:
- регулярная (в идеале — ежедневная) загрузка свежей версии книги «Эффективные алгоритмы и сложность вычислений». На этой же страничке указано, чем ее лучше читать.
- Чтение ее. Можно пропускать темы не рассмотренные на лекциях.
- Нахождение ошибок, опечаток. Фиксация вопросов и предложений.
- Отсылка редактору.
- Если чтение не закончено — повторяем, с шага 1.В результате, через три недели, к 19 декабря будут отобраны 10лучших, которые получат «отлично» автоматом.
Но и остальные будут не в проигрыше — вся активность по вычитыванию (свидетельствующая, что студент по крайней мере пытался читать и понимать курс) будет обязательно учитываться на экзамене — так что вычитыванием могут заниматься все — все это зачтется.
Единственное, повторимся — «отлично автоматом» получат только лучшие из «оранжевой группы», остальным — только бонусы.
Заметим, что на экзамене (который не «автоматом») следует к бескомпромиссной и глубокой проверке знаний («халявы» или «удовл. автоматом» - нет). Т.е. есть, если не готовиться, то все шансы просто не сдать экзамен.
2008-11-17 Закрыта регистрация на курс «Эффективные алгоритмы»
Stas Fomin: Итак, регистрация студентов на курс «Эффективные алгоритмы» закрыта, лекции практически завершены. Было дано целых три с половиной месяца, чтобы зарегистрироваться, причем это можно было сделать даже не посещая лекций, просто по почте. Это достаточный срок, чтобы полностью определится с курсом по выбору, так что список зарегистрированных студентов окончательный, исключений не будет.
__, __, _, _ _, ___ __, _, ___ _ _, _, _
|_) |_ / _ | (_ | |_) /_\ | | / \ |\ |
| \ | \ / | , ) | | \ | | | | \ / | \|
~ ~ ~~~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
_, _, _, _, __, __,
/ ` | / \ (_ |_ | \
\ , | , \ / , ) | |_/
~ ~~~ ~ ~ ~~~ ~
2008-09-21 Начато чтение семестрового курс «Эффективные алгоритмы»
Stas Fomin: Начато чтение семестрового курса «Эффективные алгоритмы» для 6 курса ФУПМ МФТИ. Вся организационная информация указана по ссылке, сами лекции высокотехнологичны — читаются с проектором, есть электронная версия слайдов и книга «Эффективные алгоритмы и сложность вычислений», в библиотеке есть печатная версия книги. Активность студентов: посещение (см. список зарегистрированных студентов), вменяемое поведение на лекции - (не спать, задавать разумные вопросы, давать правильные ответы), конструктивные замечания и вопросы по электронной версии курса — учитывается. Экзамен будет приниматься только у зарегистрированных студентов, т.е. тех, кто хоть раз за три месяца посетит лекцию, или (в случае невозможности, например, тяжелой работы, болезни или семейного положения) договорится по email, об удаленном обучении, заключающемся в чтении книги и поиске в ней ошибок и предложении конструктивных замечаний. Короче, «проснувшиеся перед НГ» надоели, и обслуживаться не будут.
____ ___ _ _ ____ _ _ ____ ____ ___ |__| | \ | | |__| |\ | | |___ | \ | | |__/ \/ | | | \| |___ |___ |__/ ____ _ ____ ____ ____ _ ___ _ _ _ _ ____ |__| | | __ | | |__/ | | |__| |\/| [__ | | |___ |__] |__| | \ | | | | | | ___]