Алгоритмы и сложность. Алгебра и криптография.

Переезд

2010-12-29T12:13:00.001+03:00

Этот блог закрывается, новости курсов теперь будут здесь.

Всех с наступающим НГ!

Ближайший экзамен по «Сложности алгоритмов» — 22 июня.

2010-06-21T16:46:00.001+04:00

Ближайший экзамен по «Сложности алгоритмов» для 4 курса ФУПМ МФТИ, будет проведен во вторник, 22 июня, 2010 года.

Место и время сбора — 301 аудитория, ИСП РАН, 11:30.

Ближайший экзамен по «Сложности алгоритмов» — 17 июня

2010-06-16T00:13:00.001+04:00

Ближайший экзамен по «Сложности алгоритмов» для 4 курса ФУПМ МФТИ, будет проведен в четверг, 17 июня, 2010 года.

Место и время сбора — 301 аудитория, ИСП РАН, 11:00.

Ближайший экзамен по «Сложности алгоритмов» — 9 июня

2010-06-08T12:57:00.000+04:00

Ближайший экзамен по «Сложности алгоритмов» для 4 курса ФУПМ МФТИ, будет проведен в среду, 9 июня, 2010 года.

Место и время сбора — 301 аудитория, ИСП РАН, 11:30. Не стоит пытаться сдавать два экзамена в один день — будут и другие возможности сдать.

По поводу следующей сдачи, договоритесь между собой об удобном всем дне и выходите на контакт.

перенос экзамена

2010-05-25T23:08:00.000+04:00

По просьбам группы, чьим представителем выступает Андрей Прохоров, экзамен переносится.

Подробнее — http://sites.google.com/site/isprascourses/algorithms-complexity

Экзамен по «Сложности алгоритмов», весна 2010

2010-05-20T13:29:00.004+04:00

Предварительный (а возможно, и окончательный) экзамен по «Сложности алгоритмов» для 4 курса ФУПМ МФТИ, будет проведен в среду, 26 мая, 2010 года.

Место и время сбора — 301 аудитория, ИСП РАН, 11:00.

Активные студенты будут награждены оценкой «автоматом».

лекций по «Сложности алгоритмов» в этом семестре больше не будет!

2010-05-04T23:12:00.001+04:00

Кстати, лекций по «Сложности алгоритмов» в этом семестре больше не будет! Готовьтесь к экзамену!

Прошла вторая сдача.

2009-12-18T16:28:00.003+03:00

Прошла вторая сдача.

Третья сдача будет в ИСПРАН, 24 декабря, четверг, 11:30, но только при условии предварительной записи!. Записываться по email: stanislav.fomin@gmail.com.

Первый заход на экзамен.

2009-12-16T22:10:00.002+03:00

В пятницу, 11 декабря, прошел первый прием экзамена по курсу «Эффективные алгоритмы», более половины получили оценки.

Следующий заход для оставшихся будет 18 декабря, опять в пятницу, в 10:30, но, внимание!, в Институте Системного Программирования, http://www.ispras.ru, встреча в комнате 301, а там видно будет. Передайте всем оставшимся.

2009-12-07T14:11:00.002+03:00

Экзамен будет 11 и 18 декабря, в 115 КПМ. В к экзамену допускаются следующие зарегистрированные студенты. Исключений не будет — этот курс необязательный, по выбору, было более чем три месяца возможности выбрать этот курс и записаться. Можно получить оценку автоматом, как — те кто ходил на лекции, в курсе.

6 ноября — каникулы

2009-11-02T11:42:00.001+03:00

По многочисленным просьбам студентов, уезжающих на ноябрьские каникулы, лекция 6 ноября отменяется.

Передайте всем заинтересованным.

Стартует курс «Эффективные алгоритмы»

2009-09-21T21:09:00.004+04:00

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

Курс по выбору, но выбор этот надо сделать осознано и вовремя. Т.е. подразумевается, что надо записаться на курс, посетив хотя бы одну лекцию в течении двух месяцев (deadline 30 октября 2009 года), либо, в крайнем случае (учеба зарубежом и т.п.) — напишите нам (Стас Фомин), что-нибудь придумаем. А поток внезапно осознавших желание сдать предмет только при приближении экзаменационной сессии будет совершенно легитимно игнорироваться.

Занятия еженедельно, по пятницам, в 10:45, 115 аудитория КПМ МФТИ. Возможны исключения — пропуск лекции по причине занятости лекторов, но об этом будет обязательно предупреждение в этом блоге — так что подписывайтесь, и предупреждайте менее продвинутых сокурсников. Лекции высокотехнологичные — проектор, ноутбук, слайды, демонстрации — тупо записывать ничего не придется, но спать тоже нежелательно.

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

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

                    _                                     _
          /\       | |                                   | |
         /  \    __| |__   __ __ _  _ __    ___  ___   __| |
        / /\ \  / _` |\ \ / // _` || '_ \  / __|/ _ \ / _` |
       / ____ \| (_| | \ V /| (_| || | | || (__|  __/| (_| |
      /_/   _\_\\__,_|  \_/  \__,_||_|_|_| \___|\___| \__,_|
     /\    | |                    (_)| |  | |
    /  \   | |  __ _   ___   _ __  _ | |_ | |__   _ __ ___   ___
   / /\ \  | | / _` | / _ \ | '__|| || __|| '_ \ | '_ ` _ \ / __|
  / ____ \ | || (_| || (_) || |   | || |_ | | | || | | | | |\__ \
 /_/    \_\|_| \__, | \___/ |_|   |_| \__||_| |_||_| |_| |_||___/
                __/ |
               |___/

Сложность алгоритмов: экзамен прошел

2009-06-17T01:37:00.002+04:00

Прошел экзамен по «сложность алгоритмов». Тем, кто успешно сдал — веселых каникул, те, кто хочет пересдать — договаривайтесь о времени с Николаем Николаевичем. Любые другие вопросы по курсу — Стасу Фомину.

Экзамен по курсу «Сложность алгоритмов»

2009-06-09T00:09:00.001+04:00

Экзамен по курсу «Сложность алгоритмов» будет в ИСПРАН, в 11:30, 10 июня. Встреча около комнаты 301, а там видно будет.

«сложность алгоритмов» — 2009

2009-02-25T18:35:00.001+03:00

Стартовал курс «Сложность алгоритмов» весеннего семестра 2009. Вся информация по курсу будет здесь.

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

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

2008-12-26T02:29:00.000+03:00

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

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

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

2008-12-22T11:55:00.000+03:00

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

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

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

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

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

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

2008-12-10T16:59:00.000+03:00

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

«Несложно о сложности. Примеры алгоритмов».
«Формально об алгоритмах. Вычислительные модели».
«Временная и пространственная сложность алгоритмов».
«Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC».
«Вероятностные вычисления. Классы RP, coRP, ZPP, BPP».
«Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема».
«PCP и аппроксимируемость».
«Жадный алгоритм в задачах о покрытии».
«Жадный алгоритм покрытия для почти всех исходных данных».
«Приближенный алгоритм для метрической задачи коммивояжера».
«Жадный алгоритм в задаче о рюкзаке».
«Динамическое программирование для задачи о рюкзаке».
«Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке».
«Полиномиальный в среднем алгоритм для задачи упаковки».
«Полиномиальный в среднем алгоритм для задачи о рюкзаке».
«Полиномиальный в среднем алгоритм для SAT».
«Вероятностный подсчет числа выполняемых наборов для ДНФ».
«MAX-SAT: вероятностное округление».
«MAX-SAT: дерандомизация».
«Дерандомизация Люби».
«MAX-CUT: вероятностное округление».
«Параллельный алгоритм Люби для максимального по включению независимого множества».

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

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

2008-11-19T18:21:00.000+03:00

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

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

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

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

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

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

2008-11-18T18:31:00.000+03:00

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

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

В результате, через три недели, к 19 декабря будут отобраны 10 лучших, которые получат «отлично» автоматом.

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

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

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

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

2008-11-17T17:37:00.000+03:00

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

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

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

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

2008-09-21T17:56:00.000+04:00

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

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

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