Школа179

Как многие вероятно догадываются, задача «планарен ли заданный граф» имеет алгоритмическое решение. Мы разберёмся, как именно её решать, и как ускорить алгоритм до полиномиального с использованием интересной техники, приходящей из алгебраической топологии. Она позволяет таким же образом решать некоторые многомерные обобщения задачи про графы, а другие, открытые до сих пор, не позволяет, и об этом мы тоже поговорим, если позволит время.
Участникам предлагается исследовать следующую задачу: стороны 2n-угольника случайным образом разбиты на пары и склеены без перекрутки. С какой вероятностью какая поверхность может быть получена? То же, если перекрутки разрешены.
Как мы узнаем в курсе, ординалы можно складывать и умножать, и даже возводить в степень. Правда, сложение и умножение ординалов не коммутативны — тем интереснее разобраться, как они работают! Например, сколько корней может иметь квадратное уравнение? А линейное (и при каких условиях)? Участникам предлагается самостоятельно поставить вапросы такого сорта, и затем хорошенько поломать над ними голову.