Blog:Advanced Algorithms

Ссылки сюда (7) →

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

2008-12-10 Темы к экзамену

Stas Fomin: Темы к экзамену совпадают с текущим списком опубликованных слайдов:

1. «Несложно о сложности. Примеры алгоритмов».
2. «Формально об алгоритмах. Вычислительные модели».
3. «Временная и пространственная сложность алгоритмов».
4. «Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC».
5. «Вероятностные вычисления. Классы RP, coRP, ZPP, BPP».
6. «Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема».
7. «PCP и аппроксимируемость».
8. «Жадный алгоритм в задачах о покрытии».
9. «Жадный алгоритм покрытия для почти всех исходных данных».
10. «Приближенный алгоритм для метрической задачи коммивояжера».
11. «Жадный алгоритм в задаче о рюкзаке».
12. «Динамическое программирование для задачи о рюкзаке».
13. «Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке».
14. «Полиномиальный в среднем алгоритм для задачи упаковки».
15. «Полиномиальный в среднем алгоритм для задачи о рюкзаке».
16. «Полиномиальный в среднем алгоритм для SAT».
17. «Вероятностный подсчет числа выполняемых наборов для ДНФ».
18. «MAX-SAT: вероятностное округление».
19. «MAX-SAT: дерандомизация».
20. «Дерандомизация Люби».
21. «MAX-CUT: вероятностное округление».
22. «Параллельный алгоритм Люби для максимального по включению независимого множества».Т.е. другие темы («византийское соглашение» и т.п. ) — читать и учить необязательно. Выбор счастливчиков, получивших отлично автоматом будет проведен 17 декабря. Но в любом случае, все ваши комментарии полученные до экзамена будут учтены и будут положительно влиять на оценку.

Разместил WikiSysop 10 декабря 2008 13:59 (GMT), нет комментариев.

2008-11-19 Эффективные алгоритмы: анонс экзамена

Stas Fomin: Сам экзамен деканат запланировал (ориентировочной) на 19 декабря в 110 КПМ МФТИ.

Начнем наверно в 10:40.

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

Возможны последующие сдачи, для улучшения оценки.

Они, скорее всего, будут проходить в ИСП РАН (Москва, м. Таганская, Большая Коммунистическая, д. 25). Комната 301.

Разместил WikiSysop 19 ноября 2008 15:21 (GMT), нет комментариев.

2008-11-18 Эффективные алгоритмы: стартует досрочная экзаменационная сессия

Stas Fomin: Итак, по курсу «Эффективные алгоритмы» стартует досрочная экзаменационная сессия, с возможностью получить отличную оценку автоматом, без единой встречи с экзаменаторами. Получить экзамен автоматом могут те, кто посетил не меньше 50% лекций, в спискемы пометили их вот таким цветом (оранжевым) фона. От избранных ожидается:

1. регулярная (в идеале — ежедневная) загрузка свежей версии книги «Эффективные алгоритмы и сложность вычислений». На этой же страничке указано, чем ее лучше читать.
2. Чтение ее. Можно пропускать темы не рассмотренные на лекциях.
3. Нахождение ошибок, опечаток. Фиксация вопросов и предложений.
4. Отсылка редактору.
5. Если чтение не закончено — повторяем, с шага 1.В результате, через три недели, к 19 декабря будут отобраны 10лучших, которые получат «отлично» автоматом.

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

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

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

Разместил WikiSysop 18 ноября 2008 15:31 (GMT), нет комментариев.

2008-11-17 Закрыта регистрация на курс «Эффективные алгоритмы»

Stas Fomin: Итак, регистрация студентов на курс «Эффективные алгоритмы» закрыта, лекции практически завершены. Было дано целых три с половиной месяца, чтобы зарегистрироваться, причем это можно было сделать даже не посещая лекций, просто по почте. Это достаточный срок, чтобы полностью определится с курсом по выбору, так что список зарегистрированных студентов окончательный, исключений не будет.

 __, __,  _, _  _, ___ __,  _, ___ _  _, _, _
 |_) |_  / _ | (_   |  |_) /_\  |  | / \ |\ |
 | \ |   \ / | , )  |  | \ | |  |  | \ / | \|
 ~ ~ ~~~  ~  ~  ~   ~  ~ ~ ~ ~  ~  ~  ~  ~  ~

            _, _,   _,  _, __, __,
           / ` |   / \ (_  |_  | \
           \ , | , \ / , ) |   |_/
            ~  ~~~  ~   ~  ~~~ ~

Разместил WikiSysop 17 ноября 2008 14:37 (GMT), нет комментариев.

2008-09-21 Начато чтение семестрового курс «Эффективные алгоритмы»

Stas Fomin: Начато чтение семестрового курса «Эффективные алгоритмы» для 6 курса ФУПМ МФТИ. Вся организационная информация указана по ссылке, сами лекции высокотехнологичны — читаются с проектором, есть электронная версия слайдов и книга «Эффективные алгоритмы и сложность вычислений», в библиотеке есть печатная версия книги. Активность студентов: посещение (см. список зарегистрированных студентов), вменяемое поведение на лекции - (не спать, задавать разумные вопросы, давать правильные ответы), конструктивные замечания и вопросы по электронной версии курса — учитывается. Экзамен будет приниматься только у зарегистрированных студентов, т.е. тех, кто хоть раз за три месяца посетит лекцию, или (в случае невозможности, например, тяжелой работы, болезни или семейного положения) договорится по email, об удаленном обучении, заключающемся в чтении книги и поиске в ней ошибок и предложении конструктивных замечаний. Короче, «проснувшиеся перед НГ» надоели, и обслуживаться не будут.

   ____ ___  _  _ ____ _  _ ____ ____ ___
   |__| |  \ |  | |__| |\ | |    |___ |  \
   |  | |__/  \/  |  | | \| |___ |___ |__/

____ _    ____ ____ ____ _ ___ _  _ _  _ ____
|__| |    | __ |  | |__/ |  |  |__| |\/| [__
|  | |___ |__] |__| |  \ |  |  |  | |  | ___]

Разместил WikiSysop 21 сентября 2008 13:56 (GMT), нет комментариев.

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