Редактирование: Список заданий по ДМ 2к 2016 осень

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 121: Строка 121:
 
# Для заданных $a$ и нечетного простого $p$, проверьте, что существует $x$: $x^2 \equiv a \mod p$ за $O(\log p)$
 
# Для заданных $a$ и нечетного простого $p$, проверьте, что существует $x$: $x^2 \equiv a \mod p$ за $O(\log p)$
 
# Решите задачу дискретного логарифма для простого модуля $p$ вида  $2^k + 1$ за $O(\mathop{poly}(k))$.
 
# Решите задачу дискретного логарифма для простого модуля $p$ вида  $2^k + 1$ за $O(\mathop{poly}(k))$.
# Докажите лемму о паросочетании в графе замен (формулировка тут: [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D0%BF%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B8_%D0%B2_%D0%B3%D1%80%D0%B0%D1%84%D0%B5_%D0%B7%D0%B0%D0%BC%D0%B5%D0%BD], доказательство неправильное - неверный индукционный переход)
 
# Рассмотрим два матроида $M_1$ и $M_2$. Как связаны максимальное независимое множество пересечения $M_1 \cap M_2$ и база $M_1 \cup M_2^*$? ($M_2^*$ - матроид, двойственный $M_2$)
 
# Докажите теорему Радо: пусть $M$ - матроид с ранговой функцией $r$, $X = X_1 \cup X_2 \cup ...\cup X_k$, причем все $X_i$ попарно не пересекаются. Будем называть независимой системой представителей независимое множество $A$, такое что $|A \cap X_i| \le 1$. Пусть $A_{max}$ - максимальная по мощности независимая система представителей. Тогда $|A_{max}|=\min_{Z\subset \{1,..,k\}}(r(\cup_{i\in Z} X_i)+k-|Z|)$.
 
# Предложите алгоритм построения максимальной независимой системы представителей.
 
# Докажите, что длина кратчайшего пути из $S$ в $T$ в алгоритме построения базы пересечения матроидов не убывает.
 
# Докажите, что число различных длин кратчайшего пути из $S$ в $T$, которые встречаются в алгоритме построения базы пересечения матроидов, есть $O(\sqrt n)$.
 
# Докажите, что сумма длин кратчайших пути из $S$ в $T$, которые встречаются в алгоритме построения базы пересечения матроидов, есть $O(n \log n)$.
 
# Игра Шеннона. Рассмотрим игру на связном графе с множеством ребер $E$. Играют два игрока, cut и link, первым ходит cut. Игроки по очереди добавляют себе ребра, не использованные на предыдущих ходах. В конце игры link выигрывает, если по его ребрам можно дойти от любой вершины до любой. Докажите, что link выигрывает при оптимальной игре, если и только если в графе существует два непересекающихся остовных дерева.
 
# Игра Шеннона на произвольном матроиде. Рассмотрим игру на матроиде $M$. Играют два игрока, cut и link, первым ходит cut. Игроки по очереди выбирают себе элементы носителя, не использованные на предыдущих ходах. В конце игры link выигрывает, если его множество содержит базу матроида. Докажите, что link выигрывает при оптимальной игре, если и только если в графе существует две непересекающихся базы.
 
# Пусть $M$ - невырожденная квадратная матрица над вещественными числами. Докажите, что для любого множества строк $R$ найдется множество столбцов той же мощности $C$, что миноры $R\times C$ и $\overline{R}\times \overline{C}$ - ненулевые (как $\overline T$ обозначено множество строк/столбцов, не входящих в $T$).
 
# Задан двудольный граф, каждая вершина имеет вес. Требуется выбрать паросочетание, чтобы суммарный вес покрытых вершин был максимален. Решите эту задачу, не используя сведение к обычной задаче о назначениях.
 
 
</wikitex>
 
</wikitex>

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)