http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=37.58.59.162&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-29T05:40:31ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B9_%D0%BF%D0%BE_%D0%90%D0%A1%D0%94_2%D0%BA_2015_%D0%BE%D1%81%D0%B5%D0%BD%D1%8C&diff=49827Список заданий по АСД 2к 2015 осень2015-11-09T10:54:21Z<p>37.58.59.162: </p>
<hr />
<div><wikitex><br />
# Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.<br />
# Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл.<br />
# Будем называть ''согласованным циклом'' в графе класс эквивалентности циклических путей относительно циклического сдвига. При этом циклический путь не должен проходить два раза по одному ребру в разных направлениях. Докажите, что в графе есть согласованный цикл тогда и только тогда когда там есть цикл.<br />
# Петя придумал отношение средней связности: $u$ средне связана с $v$, если из $u$ достижима $v$ или из $v$ достижима $u$. Является ли это отношение отношением эквивалентности?<br />
# Пусть граф $G$ - объединение двух различных простых путей из $u$ в $v$. Докажите, что в $G$ есть цикл.<br />
# Харари 2.3<br />
# Харари 2.5<br />
# Харари 2.9<br />
# Харари 2.13<br />
# Харари 2.15<br />
# Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.<br />
# Харари 2.16<br />
# Харари 2.20<br />
# Харари 2.22<br />
# Харари 2.29<br />
# Харари 2.31<br />
# Харари 2.32<br />
# Харари 2.33<br />
# Харари 2.34 (а)<br />
# Харари 2.34 (б)<br />
# Харари 2.35<br />
# Харари 2.36<br />
# Харари 4.2<br />
# Харари 4.3<br />
# Харари 4.4<br />
# Харари 4.6<br />
# Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.<br />
# Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.<br />
# Какое максимальное число точек сочленения может быть в графе с $n$ вершинами?<br />
# При каких соотношениях $a$, $b$, $n$, $m$, $k$ существует граф с $a$ точками сочленения, $b$ мостами, $n$ вершинами, $m$ рёбрами, $k$ компонентами связности?<br />
# Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на цикле. Доказать, что вершинная двусвязность - это рефлексивно-транзитивное замыкание $R$.<br />
# Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.<br />
# Харари 3.2<br />
# Харари 3.3<br />
# Харари 3.4<br />
# Харари 3.5<br />
# Харари 3.6<br />
# Харари 3.7<br />
# Харари 3.9<br />
# Граф называется вершинно трёхсвязным, если он остаётся связным после удаления любых не более чем двух вершин. Доказать или опровергнуть, что в вершинно трёхсвязном графе любые три вершины лежат на простом цикле.<br />
# Граф называется вершинно k-связным, если он остаётся связным после удаления любых не более чем (k - 1) вершин. Доказать или опровергнуть, что в вершинно k-связном графе любые k вершин лежат на простом цикле.<br />
# Пусть $G$ - связный граф. Обозначим как $\kappa(G)$ - минимальное число вершин, которое необходимо удалить, чтобы граф потерял связность. (для полного графа это число равно n - 1), $\lambda(G)$ - минимальное число рёбер, которое необходимо удалить, чтобы граф потерял связность, $\delta(G)$ - минимальную степень в вершины в графе $G$. Докажите, что для любых $a$, $b$, $c$, таких что $1 \le a \le b \le c$, существует граф $G$, такой что $\kappa(G) = a$, $\lambda(G) = b$, $\delta(G) = c$.<br />
# Рассмотрим неориентированный граф $G$. Запустим dfs, затем ориентируем рёбра дерева dfs $T$ от корня, а остальные - к корню. Доказать, что компоненты сильной связности в получившемся графе равны компонентам рёберной двусвязности в исходном графе<br />
# Разработать алгоритм поиска компонент рёберной двусвязности, используя ровно один запуск dfs.<br />
# Разработать алгоритм поиска компонент вершинной двусвязности, используя ровно один запуск dfs.<br />
# Пусть $T$ - дерево dfs. Укажите способ за $O(E)$ посчитать число пар $(e_1, e_2)$, таких что 1) $e1 \in T$; 2) $e2\not\in T$; 3) граф $G$ после удаления рёбер $e_1$ и $e_2$ - не связен.<br />
# Пусть $T$ - дерево dfs. Укажите способ за $O(E)$ посчитать число пар $(e_1, e_2)$, таких что 1) $e1 \in T$; 2) $e2 \in T$; 3) граф $G$ после удаления рёбер $e_1$ и $e_2$ - не связен.<br />
# В первом издании Кормена была ошибка. Там было сказано, что вершина v есть точка сочленения тогда и только тогда, когда (v - корень И у v ≥ 2 сына) ИЛИ (v - не корень И up[v] ≥ enter[v]). Приведите контрпример.<br />
# Приведите пример графа с отрицательными рёбрами, на котором алгоритм Дейкстры работает неверно.<br />
# Пусть веса рёбер не обязательно неотрицательны, но отрицательных циклов нет. Добавим в алгоритм Дейкстры следующее: если производится успешная релаксация по ребру $vx$ и $x \in U$, то вешина $x$ удаляется из $U$. Докажите, что, если этот алгоритм находит кратчайшие пути в графе.<br />
# Приведите пример графа, в котором алгоритм из предыдущего задания рабоатает экспоненциальное время.<br />
# Предложите граф, в котором алгоритм Дейкстры делает $\Omega(E)$ успешных релаксаций<br />
# Доказать теорему об отсутствии кратчайшего пути на базе алгоритма Форда-Беллмана. (от $s$ до $v$ нет кратчайшего пути тогда и только тогда, когда она достижима из $u$, такой что после выполнения алгоритма Форда-Беллмана найдется ребро $xu$, для которого $d[x] + w(xu) < d[u]$)<br />
# Разработать алгоритм на базе Форда-Беллмана, который ищет в графе отрицательный цикл.<br />
# Укажите способ построить для некоторых $c_1, c_2 >0$ и любых V, E, где $c_1 V \le E \le c_2 V^2$ граф, на котором алгоритм Форда-Беллмана с очередью работает за $\Omega(VE)$.<br />
# Пусть в графе $G$ есть вершина $s$, из которой достижимы все вершины. Обозначим как $\mu^*$ минимальный средний вес цикла в графе. Докажите, что $\mu^* = \min_v\max_k\frac{d_n(v)-d_k(v)}{n-k}$, где $d_i(v)$ - длина кратчайшего пути из $s$ до $v$, содержащего ровно $i$ ребер.<br />
# Модифицируйте алгоритм Форда-Беллмана так, чтобы он находил в графе циклы минимального среднего веса за $O(VE)$ и $O(V^2)$ памяти.<br />
# Модифицируйте алгоритм Флойда, чтобы найти в графе отрицательный цикл.<br />
# Петя перепутал и написал в алгоритме Флойда "for i: for j: for k: relax(d[i][j], d[i][k]+d[k][j])". Постройте тест, на котором получившийся алгоритм работает неверно.<br />
# Петя перепутал и написал в алгоритме Флойда "for i: for j: for k: relax(d[i][j], d[i][k]+d[k][j])". Заметив, что это работает неверно, он запустил этот алгоритм два раза. Будет ли получившийся алгоритм "for t from 1 to 2: for i: for j: for k: relax(d[i][j], d[i][k]+d[k][j])" корректным?<br />
# В условиях теоремы Дирака предложить алгоритм нахождения в графе гамильтонова цикла.<br />
# Теорема Оре: если для любых вершин $u$ и $v$, не соединенных ребром, сумма степеней $deg(u) + deg(v) \ge n$, то в графе существует Гамильтонов цикл. В условиях теоремы Оре предложить алгоритм нахождения в графе гамильтонова цикла.<br />
# В условиях теоремы Хватала предложить алгоритм нахождения в графе гамильтонова цикла.<br />
# Харари 7.2<br />
# Харари 7.4<br />
# Харари 7.5<br />
# Харари 7.7<br />
# Харари 7.9<br />
# Харари 7.14<br />
# Харари 7.17<br />
# Харари 7.18<br />
# Посчитать хроматический многочлен цикла $C_n$<br />
# Посчитать хроматический многочлен колеса $C_n + K_1$.<br />
# Посчитать полного двудольного графа $K_{n,m}$.<br />
# Харари 12.2<br />
# Харари 12.3<br />
# Харари 12.4<br />
# Харари 12.5<br />
# Харари 12.6<br />
# Харари 12.12<br />
# Доказать формулу Зыкова для хроматического многочлена графа $G$: $P_G(x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}$, где $pt(G,i)$ — число способов разбить вершины $G$ на $i$ независимых множеств.<br />
# Доказать формулу Уитни: пусть $G$ - обыкновенный $(n, m)$ - граф. Тогда коэффициент при $x^i$, где $1\le i\le n$ в хроматическом многочлене $P_G(x)$ равен $\sum \limits_{j=0}^{m}{(-1)^jN(i, j)}$, где $N(i, j)$ - число остовных подграфов графа $G$, имеющих $i$ компонент связности и $j$ рёбер.<br />
# Харари 11.1<br />
# Харари 11.2<br />
# Харари 11.3<br />
# Харари 11.7<br />
# Харари 11.8<br />
# Харари 11.9<br />
# Харари 11.10<br />
# Харари 11.14<br />
# Харари 11.15<br />
# Харари 11.25</div>37.58.59.162http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B9_%D0%BF%D0%BE_%D0%A2%D0%A4%D0%AF_2015&diff=49826Список заданий по ТФЯ 20152015-11-09T10:52:36Z<p>37.58.59.162: </p>
<hr />
<div><wikitex><br />
= Теория формальных языков, 5 семестр =<br />
<br />
# Построить конечный автомат для языка слов над бинарным алфавитом, в которых четность числа 0 равна четности числа 1<br />
# Построить конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3<br />
# Построить конечный автомат для языка слов над бинарным алфавитом, в которых нет трех нулей подряд<br />
# Построить конечный автомат для языка слов над бинарным алфавитом, которые представляют собой двоичную запись чисел, кратных 5<br />
# Построить конечный автомат для языка слов над бинарным алфавитом, в которых число нулей не кратно 3<br />
# Построить конечный автомат для языка слов над бинарным алфавитом, в которых есть три нуля подряд. Сделайте вывод из последних двух заданий.<br />
# Построить конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 и которые представляют собой двоичную запись чисел кратных 5.<br />
# Построить конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 или которые представляют собой двоичную запись чисел кратных 5. Сделайте вывод из последних двух заданий.<br />
# Построить конечный автомат для языка слов над бинарным алфавитом, в пятый символ с конца - 0. Можно построить недетерминированный автомат.<br />
# Постройте детерминированный автомат для предыдущего задания или докажите, что в нем слишком много состояний, чтобы его рисовать ;).<br />
# Постройте регулярное выражение для языка слов над бинарным алфавитом, в которых нет двух нулей подряд.<br />
# Построить конечный автомат для языка слов над бинарным алфавитом, в которых число 0 кратно 3.<br />
# ХМУ 4.2.2, стр 163<br />
# ХМУ 4.2.3, стр 163<br />
# ХМУ 2.3.1, стр 83<br />
# Докажите, что минимальный ДКА для языка $(0|1)^*0(0|1)^k$ содержит минимум $2^k$ состояний<br />
# ХМУ 4.2.4, стр 163<br />
# ХМУ 4.2.5, стр 164<br />
# ХМУ 4.2.6, стр 164<br />
# ХМУ 4.2.7, стр 164<br />
# ХМУ 4.2.8, стр 164<br />
# ХМУ 4.2.10, стр 165<br />
# ХМУ 4.2.11, стр 165<br />
# Доказать нерегулярность языка слов $0^n1^n$<br />
# Доказать нерегулярность языка, каждое слово которого содержит поровну 0 и 1.<br />
# Доказать нерегулярность языка палиндромов.<br />
# Доказать нерегулярность языка тандемных повторов.<br />
# Доказать нерегулярность языка $0^n1^m$, $n \le m$<br />
# Доказать нерегулярность языка $0^n1^m$, $n \ne m$<br />
# Доказать нерегулярность языка $0^{n^2}$<br />
# Доказать нерегулярность языка $0^p$, $p$ {{---}} простое<br />
# Доказать нерегулярность языка двоичных записей простых чисел<br />
# Доказать нерегулярность языка $0^n1^m$, $gcd(n, m) = 1$<br />
# Доказать нерегулярность языка $0^a1^b2^c$, $a \ne b$ и $b \ne c$<br />
# Приведите пример нерегулярного языка, для которого выполнена лемма о разрастании<br />
# Доказать, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n)$.<br />
# Предложите алгоритм проверки того, что регулярный язык бесконечен<br />
# Предложите алгоритм проверки того, что регулярный язык является беспрефиксным<br />
# Предложите алгоритм проверки того, что один регулярный язык является подмножеством другого<br />
# Предложите алгоритм проверки того, что регулярные языки не пересекаются<br />
# ХМУ 4.3.1, стр 171.<br />
# ХМУ 4.3.2, стр 171.<br />
# Рассмотрим язык $\{x_0 y_0 z_0 x_1 y_1 z_1 \dots x_{n-1} y_{n-1} z_{n-1} \mid x_i, y_i, z_i \in \{0, 1\}\}$, где $ X = x_{n-1}x_{n-2}\dots x_0$ и аналогично представляется $Y$ и $Z$, причем $ X + Y = Z $. Докажите, что этот язык регулярный.<br />
# То же, что и предыдущее, только $\{x_{n-1} y_{n-1} z_{n-1} \dots x_1 y_1 z_1 x_0 y_0 z_0 \mid \dots \}$.<br />
# Рассмотрим язык $\{x_0 y_0 z_0 x_1 y_1 z_1 \dots x_{n-1} y_{n-1} z_{n-1} \mid x_i, y_i, z_i \in \{0, 1\}\}$, где $X = x_{n-1}x_{n-2}\dots x_0$ и аналогично представляется $Y$ и $Z$, причем $X \times Y = Z$. Докажите, что этот язык не является регулярным.<br />
# Рассмотрим отношение на словах $L$: $x \equiv y$, если для любых $u$, $v$ выполнено $uxv \in L \Leftrightarrow uyv \in L$. Классы эквивалентности этого отношения называются синтаксическим моноидом языка $L$. Докажите, что $L$ регулярный тогда и только тогда, когда синтаксический моноид $L$ конечен.<br />
# Придумайте семейство регулярных языков $L_i$, у которых ДКА для $L_i$ содержит $O(i)$ состояний, а синтаксический моноид $L_i$ имеет неполиномиальный размер.<br />
# Постройте КС-грамматику для правильных скобочных последовательностей с двумя типами скобок.<br />
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно числу единиц. Докажите, что ваша грамматика является правильной.<br />
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно удвоенному числу единиц. Докажите, что ваша грамматика является правильной.<br />
# Постройте КС-грамматику для языка $0^k1^n2^{k+n}$.<br />
# Постройте КС-грамматику для языка $0^k1^n2^{k+n}\cup 1^k0^n2^{k+n}$. Сделайте вывод о свойствах КС-языков.<br />
# Постройте КС-грамматику для языка $0^k1^n2^{k+n}1^i0^j2^{i+j}$. Сделайте вывод о свойствах КС-языков.<br />
# Постройте КС-грамматику для языка $0^i1^j2^k$, $i \ne j$ или $j \ne k$.<br />
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются палиндромами.<br />
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются правильными скобочными последовательностями.<br />
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей не равно числу единиц.<br />
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются тандемными повторами.<br />
# Верно ли, что любую КС-грамматику можно привести к форме, когда любое правило имеет вид $A\to BCD$ или $A\to a$?<br />
# Верно ли, что любой КС-язык над односимвольным алфавитом является регулярным?<br />
# ХМУ 7.2.1 (а)<br />
# ХМУ 7.2.1 (б)<br />
# ХМУ 7.2.1 (в)<br />
# ХМУ 7.2.1 (г)<br />
# ХМУ 7.2.1 (д)<br />
# ХМУ 7.2.1 (е)<br />
# ХМУ 7.2.5 (а)<br />
# ХМУ 7.2.5 (б)<br />
# Докажите, что язык $\{0^n1^m2^n3^m\}$ не является КС.<br />
# Докажите, что язык $\{0^n1^m2^n| n \ne m\}$ не является КС.<br />
# Приведите пример не КС-языка, для которого выполнена лемма о разрастании.<br />
# Постройте МП-автомат для языка $0^n1^n$.<br />
# Постройте МП-автомат для языка слов, где число нулей равно числу единиц.<br />
# Постройте МП-автомат для языка $0^n1^{2n}$.<br />
# Постройте МП-автомат для языка $0^n1^m2^{n+m}$.<br />
# Постройте МП-автомат для языка $0^{2n}1^n$.<br />
# Постройте МП-автомат для языка $0^n1^n\cup0^n1^{2n}$.<br />
# Постройте МП-автомат для языка слов $0^n1^m$, где $n \le m \le 2n$.<br />
# Докажите, что для любых $p$ и $q$ существует МП-автомат для языка слов $0^n1^m$, где $n/m=p/q$<br />
# Постройте автомат с магазинной памятью для языка слов над алфавитом $\{0, 1, 2\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.<br />
# Существует ли для языка из предыдущего задания детерминированный автомат?<br />
# Постройте автомат с магазинной памятью для языка палиндромов.<br />
# Докажите, что для любого автомата с магазинной памятью существует эквивалентный, который на каждом переходе кладет в стек не более 2 символов. Ваша конструкция должна сохранять детерминированность автомата, если ранее он был детерминированным.<br />
# Докажите, что для любого детерминированного автомата с магазинной памятью существует эквивалентный, который при $\varepsilon$-переходе только снимает или заменяет верхний символ стека (то есть размер стека не увеличивается на $\varepsilon$-переходах).<br />
# Рассмотрим детерминированный автомат с магазинной памятью, для которого выполнены свойства из двух предыдущих заданий. Докажите, что для любого состояния $p$ автомата и строки $\gamma$ в стеке существует строка $s$, для которой выполняется следующее свойство. Начав в состоянии $p$ и со стеком $\gamma$, считав строку $s$ автомат переходит некоторое состояние $q$ и имеет в стеке $\beta$, причем какую бы строку далее автомат не получил на вход, на вершине стека никогда не окажется второй символ $\beta$.<br />
# На основании трех предыдущих заданий докажите, что не существует детерминированного автомата с магазинной памятью для языка палиндромов.<br />
# Докажите, что объединение и пересечение разрешимых языков разрешимо.<br />
# Докажите, что объединение и пересечение перечислимых языков перечислимо.<br />
# Докажите, что конкатенация и замыкание Клини разрешимых языков разрешимы.<br />
# Докажите, что конкатенация и замыкание Клини перечислимых языков перечислимы.<br />
# Докажите, что если множества $A$ и $B$ разрешимы (перечислимы), то их декартово произведение перечислимо.<br />
# Докажите, что образ перечислимого множества под действием вычислимой (не обязательно всюду определенной) функции перечислим.<br />
# Докажите, что прообраз перечислимого множества под действием вычислимой (не обязательно всюду определенной) функции перечислим.<br />
# Теорема об униформизации. Пусть задано перечислимое множество пар $F$. Докажите, что найдется вычислимая функция $f$, такая что для любого $x$, для которого существует $y$, такой что $(x,y)\in F$ выполнено, что $(x, f(x)) \in F$.<br />
# Пусть даны два перечислимых множества $X$ и $Y$. Докажите, что существуют непересекающиеся перечислимые множества $X' \subset X$ и $Y' \subset Y$, такие что $X' \cup Y' = X \cup Y$.<br />
# Докажите, что множество чисел $i$, таких, что в десятичной записи числа $\pi$ встречается последовательность из $i$ семерок подряд, перечислимо. Является ли оно разрешимым? Почему?<br />
# Докажите, что множество чисел $i$, таких, что в десятичной записи числа $\pi$ как подстрока десятичная запись $i$, перечислимо. Можно ли привести тот же аргумент, что и в предыдущем задании, для доказательства его (не)разрешимости?<br />
# Докажите, что любое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество.<br />
# Пусть $f$ - вычислимая функция. Докажите, что существует вычислимая функция $g$ с областью определения, совпадающей с областью значений $f$, такая что $f(g(f(x))) = f(x)$ для любого $x$, на котором $f$ определена.<br />
# Вещественное число $\alpha$ называется вычислимым, если существует вычислимая функция $a$, которая по любому рациональному $\varepsilon > 0$ даёт рациональное приближение к $\alpha$ с ошибкой не более $\varepsilon$, то есть $|\alpha-a(\varepsilon)| \le \varepsilon$ для любого рационального $\varepsilon > 0$. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда множество рациональных чисел, меньших $\alpha$, разрешимо<br />
# Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда последовательность знаков представляющей его десятичной (или двоичной) дроби вычислима.<br />
# Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к $\alpha$ (то есть является вычислимой функция, которая по $\varepsilon$ возвращает $n_0$, такое что $|a_n - \alpha| \le \varepsilon$ для $n > n_0$)<br />
# Покажите, что сумма, произведение, разность и частное вычислимых действительных чисел вычислимы. Покажите, что корень многочлена с вычислимыми коэффициентами вычислим.<br />
# Сформулируйте и докажите утверждение о том, что предел вычислимо сходящейся последовательности вычислимых действительных чисел вычислим.<br />
# Вещественное число $\alpha$ называют перечислимым снизу, если множество всех рациональных чисел, меньших $\alpha$, перечислимо. Перечислимость сверху определяется аналогично. Докажите, что число $\alpha$ перечислимо снизу тогда и только тогда, когда оно является пределом некоторой вычислимой возрастающей последовательности рациональных чисел.<br />
# Докажите, что вещественное число вычислимо тогда и только тогда, когда оно перечислимо снизу и сверху.<br />
# Покажите, что следующие три свойства множества $X$ равносильны: (1) $X$ можно представить в виде $A \setminus B$, где $A$ — перечислимое множество, а $B$ — его перечислимое подмножество; (2) $X$ можно представить в виде $A \setminus B$, где $A$ и $B$ — перечислимые множества; (3) $X$ можно представить в виде симметрической разности двух перечислимых множеств.<br />
# Покажите, что множество $X$ можно представить в виде $A\setminus (B\setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности (суммы по модулю 2) трёх перечислимых множеств.</div>37.58.59.162