Спецкурс и спецсеминар в новом семестре

[Maxim Babenko]

Всем привет,

В наступающем семестре я хочу попробовать прочитать совсем новый спецкурс.

Представьте себе, что у вас есть доска наподобие шахматной, которая разбита на квадратные клетки. Некоторые клетки в ней отсутствуют. Вам предлагается покрыть ее доминошками размера 1x2 без пересечений. Сколько есть способов это сделать?

Неискушенный наблюдатель  сразу заметит, что ответ равен нулю, если число клеток нечётно, но вряд ли сможет предложить алгоритм для общего случая, более эффективный, чем полный перебор. Отдельные специалисты по олимпиадному программированию вспомнят словосочетание "ДП про профилю" и, возможно, смогут решить задачу при небольших размерах доски. Наконец, математик заметит, что здесь речь идёт о подсчёте числа совершенных паросочетаний в графе, а это известная #P-полная задача.

Удивительно, но полиномиальный алгоритм для  этой задачи все же есть, и своим существованием он обязан планарности графа. Планарные графы (то есть графы, допускающие  укладку на плоскости без самопересечений рёбер) образуют интересный и обширный класс, для которого многие алгоритмические задачи решаются более эффективно, чем в общем случае. О таких методах и пойдёт речь на спецкурсе.

Для интересующихся также приведу чуть более подробный список тем:

1. Планарные графы, запрещенные миноры, критерий Куратовского, двойственность

2. Построение укладок графов на плоскости.

3. Укладки на решетках небольшого размера, метод регулярных разметок.

3. Перманенты, детерминанты и пфаффианы. Паросочетания в планарных графах.

4. Сепараторы в планарных графах.

5. Кратчайшие пути в планарных графах.

6. Потоки и разрезы в планарных графах.

7. Метод Бейкера, приближенные алгоритмы для NP-трудных задач в планарных графах.

Теперь несколько организационных замечаний:

1) С местом проведения занятия все более менее ясно -- это 2 ГУМ, там есть много свободных аудиторий.

2) По времени проведения -- как обычно, 5 пара. Относительно времени предлагаю устроить голосование.

https://docs.google.com/spreadsheet/ccc?key=0AummvUp64CSgdHpxRU45VW56c1otUk9Td3UzTTNUT3c&hl=en_US&authkey=CIjsmdkI

Заходите и заполняйте!

3) Мне нужен доброволец, готовый повесить завтра-послезавтра бумажки с анонсами на мехмате.

4) Сразу после спецкурса у нас традиционно будет проходить спецсеминар. Нужны желающие сделать доклад. Леша Черепанов, ау!

[Nastya Melnikova]

Подскажите более точно место проведения, пожалуйста :)

[Maxim Babenko]

Всем привет,

Собираемся сегодня на 5-й паре во 2 ГУМ (там, где ВМК) около ауд. 413.

Может ли кто-нибудь дописать эту информацию на тех объявлениях, что
были вывешены? (На кафедре и на 15 этаже.)

[Ilya Razenshteyn]

А конспекты планируются?

2011/9/20 Maxim Babenko <maxim....@gmail.com>:

[Maxim Babenko]

Планируется съёмка. Соответственно вопрос: кто-нибудь поедет из Яндекса сегодня?

2011/9/21 Ilya Razenshteyn <ily...@gmail.com>

[Ignat Kolesnichenko]

Ведется съемка спецсеминара и спецкурса, анонсы и видео можно найти
тут http://cotass.wordpress.com/

p.s. Лучше позже, чем никогда. :)

On Sep 21, 10:06 am, Maxim Babenko <maxim.babe...@gmail.com> wrote:
> Планируется съёмка. Соответственно вопрос: кто-нибудь поедет из Яндекса
> сегодня?
>

> 2011/9/21 Ilya Razenshteyn <ilya...@gmail.com>
>
>
>
>
>
>
>
> > А конспекты планируются?
>
> > 2011/9/20 Maxim Babenko <maxim.babe...@gmail.com>:

[Alexey Zolotov]

А можно ссылку на видеофайлы? Или могу прийти на спецкурс с жестким диском и скачать. Мой планшет не любит flv видео.

[Ilya Razenshteyn]

Смотри на ноуте.

2011/12/1 Alexey Zolotov <fre...@freopen.org>:

[Ignat Kolesnichenko]

Если video.yandex.ru не устраивает -- можно придти на семинар и
переписать. У меня они в формате mov хранятся.