Список заданий по ТВС весна 2016 — различия между версиями
| Строка 1: | Строка 1: | ||
| + | {| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;" | ||
| + | |+ | ||
| + | |-align="center" | ||
| + | |'''НЕТ ВОЙНЕ''' | ||
| + | |-style="font-size: 16px;" | ||
| + | | | ||
| + | 24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. | ||
| + | |||
| + | Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. | ||
| + | |||
| + | Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. | ||
| + | |||
| + | Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. | ||
| + | |||
| + | ''Антивоенный комитет России'' | ||
| + | |-style="font-size: 16px;" | ||
| + | |Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. | ||
| + | |-style="font-size: 16px;" | ||
| + | |[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки]. | ||
| + | |} | ||
| + | |||
<wikitex> | <wikitex> | ||
# (12) TPQBF - множество истиных булевых формул с кванторами в предваренной форме. Говорят, то формула находится в предваренной форме, если она имеет вид $Qx_1Qx_2...Qx_n\varphi(x_1, x_2, \ldots, x_n)$, где $Q$ - кванторы, а $\varphi$ - булева формула. Докажите, что TPQBF является PS-полным. | # (12) TPQBF - множество истиных булевых формул с кванторами в предваренной форме. Говорят, то формула находится в предваренной форме, если она имеет вид $Qx_1Qx_2...Qx_n\varphi(x_1, x_2, \ldots, x_n)$, где $Q$ - кванторы, а $\varphi$ - булева формула. Докажите, что TPQBF является PS-полным. | ||
Версия 08:23, 1 сентября 2022
| НЕТ ВОЙНЕ |
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
<wikitex>
- (12) TPQBF - множество истиных булевых формул с кванторами в предваренной форме. Говорят, то формула находится в предваренной форме, если она имеет вид $Qx_1Qx_2...Qx_n\varphi(x_1, x_2, \ldots, x_n)$, где $Q$ - кванторы, а $\varphi$ - булева формула. Докажите, что TPQBF является PS-полным.
- (13) TPQBCNF - множество истиных булевых формул с кванторами в предваренной форме и КНФ. Такие формулы имеют вид вид $Qx_1Qx_2...Qx_n\varphi(x_1, x_2, \ldots, x_n)$, где $Q$ - кванторы, а $\varphi$ - булева формула в КНФ. Докажите, что TPQBCNF является PS-полным.
- (22) Игра Generalized Geography происходит по следующим правилам. Задан ориентированный граф $G$% и стартовая вериша в нем, в которой исходно находится фишка. Два игрока делают ходы по очереди. Очередным ходом игрок выбирает исходящее из текущей вершины ребро и перемещает фишку по нему. При этом запрещается повторно посещать уже посещенные вершины. Игрок, который не может сделать ход, проигрывает. Язык GG - множество пар "граф-начальная вершина", где в соответствующей игре выигрывает первый игрок. Докажите, что язык GG является PS-полным. Указание: сведите к нему язык TPQBCNF
- (27) Вершинная игра Шеннона на графе происходит по следующим правилам. Задан неориентированный граф $G$% и вершины $s$ и $t$ в нем, два игрока: Link и Cut делают ходы по очереди. Очередным своим ходом игрок Link выбирает вершину и помечает ее как неуязвимую, а игрок Cut выбирает вершину, не помеченную ранее игроком Link, и удаляет ее. Удалять вершины $s$ и $t$ запрещается. Link выигрывает, если в графе существует путь по неуязвимым вершинам от $s$ до $t$. Язык VSG - множество троек "граф-$s$-$t$", где в соответствующей игре выигрывает Link. Докажите, что язык VSG является PS-полным. Указание: сведите к нему язык TPQBCNF
</wikitex>
