Экзамен завершен

Экзамен(ы) завершен(ы)! Поздравляю всех с полученными результатами. Если кому-то страшно нужно будет спасти красный диплом, то потенциально возможность пересдать на «отлично» в зимнюю экзаменационную сессию (после 10 января) сохраняется. В таком случае, свяжитесь с нами.

                                              ____
                                             {} _  \
                                                |__ \
                                               /_____\
                             /\                \o o)\)_______
                             /\                (<  ) /#######\
                            /  \             __{'~` }#########|
                            /~~\o           /  {   _}_/########|
                           /o   \          /   {  / _|#/ )####|
                          /~~*~~~\        /   \_~/ /_ \  |####|
                         o/    o \        \______\/  \ | |####|
                         /~~~~~~~~\~`      \__________\|/#####|
                        /__*_______\        |__[X]_____/ \###/
                             ||             /___________\
                           \====/            |    |/    |
                            \__/             |___/ |___/
                                            _|   /_|   /
                                           (___,_(___,_)
                _________________________________________________
                    _     _   __     ____     ____     _     _
                    /    /    / |    /    )   /    )   |    /
                ---/___ /----/__|---/____/---/____/----|---/-----
                  /    /    /   |  /        /          |  /
                _/____/____/____|_/________/___________|_/_______
                                                        /
                                                    (_ /
    _________________________________________________________________________
        _     _   _____  _      _      _     _   _____    __     ____      /
        /|   /    /    ' |  |  /       |    /    /    '   / |    /    )   /
    ---/-| -/----/__-----|-/|-/--------|---/----/__------/__|---/___ /---/---
      /  | /    /        |/ |/         |  /    /        /   |  /    |   /
    _/___|/____/____ ____/__|__________|_/____/____ ___/____|_/_____|__o_____
                                        /
                                    (_ /

Эффективные алгоритмы: экзамен-1

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

Послание следующим поколениям: это не тот экзамен, к которому можно подготовится за пару ночей на «отлично». К тому же, мы будем повышать планку, и, например, зубрение ответов на тесты будет недостаточно для «удовлетворитено».

Прошел и основной экзамен. В целом, более 2/3 зарегистрированных получили оценки.

Следующий этап будет ориентировочно в 12:00, 24 декабря в ИСПРАН. Сбор у комнаты 301.

    _        ________   ____  ____        _        ____    ____        _
 .-| |-.    |_   __  | |_  _||_  _|      / \      |_   \  /   _|    .-| |-.
 \     /      | |_ \_|   \ \  / /       / _ \       |   \/   |      \     /
|_     _|     |  _| _     > `' <       / ___ \      | |\  /| |     |_     _|
 /     \     _| |__/ |  _/ /'`\ \_   _/ /   \ \_   _| |_\/_| |_     /     \
 '-|_|-'    |________| |____||____| |____| |____| |_____||_____|    '-|_|-'

Темы к экзамену

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

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 декабря. Но в любом случае, все ваши комментарии полученные до экзамена будут учтены и будут положительно влиять на оценку.