Список заданий по ТФЯ 2015 - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:33:59Z

rollbackEdits.php mass rollback

88.208.225.209 в 04:19, 1 сентября 2022

2022-09-01T04:19:36Z

212.100.156.67 в 19:17, 5 сентября 2016

2016-09-05T19:17:50Z

84.42.11.174 в 17:20, 22 ноября 2015

2015-11-22T17:20:54Z

84.42.11.174 в 06:54, 16 ноября 2015

2015-11-16T06:54:06Z

84.42.11.174 в 06:53, 16 ноября 2015

2015-11-16T06:53:18Z

37.58.59.162 в 10:52, 9 ноября 2015

2015-11-09T10:52:36Z

77.234.215.133 в 18:08, 29 октября 2015

2015-10-29T18:08:10Z

89.112.0.201: sta

2015-10-11T18:25:10Z

sta

194.85.160.133 в 14:22, 3 октября 2015

2015-10-03T14:22:33Z

← Предыдущая		Версия 16:33, 4 сентября 2022
Строка 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>
	= Теория формальных языков, 5 семестр =		= Теория формальных языков, 5 семестр =

← Предыдущая		Версия 04:19, 1 сентября 2022
Строка 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>
	= Теория формальных языков, 5 семестр =		= Теория формальных языков, 5 семестр =

@@ Строка 13: / Строка 13: @@
 # Постройте детерминированный автомат для предыдущего задания или докажите, что в нем слишком много состояний, чтобы его рисовать ;).
 # Постройте регулярное выражение для языка слов над бинарным алфавитом, в которых нет двух нулей подряд.
-# Построить конечный автомат для языка слов над бинарным алфавитом, в которых число 0 кратно 3.
+# Построить конечный автомат для языка слов над бинарным алфавитом, которые представляют собой двоичное число, кратное 3.
 # ХМУ 4.2.2, стр 163
 # ХМУ 4.2.3, стр 163

← Предыдущая		Версия 17:20, 22 ноября 2015
Строка 115:		Строка 115:
	# Пусть множество пар $A=\{(x, y)\}$ перечислимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)\| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо?		# Пусть множество пар $A=\{(x, y)\}$ перечислимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)\| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо?
	# Пусть множество пар $A=\{(x, y)\}$ разрешимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)\| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо? Разрешимо?		# Пусть множество пар $A=\{(x, y)\}$ разрешимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)\| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо? Разрешимо?
		+	# Пусть $A$ - произвольный список слов $(a_1, a_2, \ldots, a_n)$ над алфавитом $\Sigma$, содержащем хотя бы 2 символа. Рассмотрим алфавит $\Pi = \Sigma \cup \{1, 2, \ldots, n\}$. Обозначим как $L_A$ язык, содержащий множество слов, порождаемых грамматикой $S\to\varepsilon$, $S\to a_1S1$, ..., $S\to a_n S n$. Докажите, что для любого списка язык $\overline{L_A}$ дополнение до $L_A$ является контекстно-свободным.
		+	# В этой и последующих задачах для задания КС-языка используется некоторая произвольная его КС-грамматика, а для задания регулярного языка - на ваш выбор конечный автомат или регулярное выражение. Докажите, что задача проверки пустоты пересечения контекстно-свободных языков алгоритмически неразрешима.
		+	# Докажите, что задача равенства двух контекстно-свободных языков алгоритмически неразрешима.
		+	# Докажите, что задача проверка равенства заданных контекстно-свободного языка и регулярного языка алгоритмически неразрешима.
		+	# Докажите, что задача проверки равенства КС-языка языку $\Sigma^*$ алгоритмически неразрешима
		+	# Докажите, что задача проверки, что один контекстно-свободный язык является подмножеством другого алгоритмически неразрешима.
		+	# Докажите, что задача проверки, что заданный регулярный язык является подмножеством заданного контекстно-свободного алгоритмически неразрешима.
		+	# Докажите, что множество КС-грамматик, порождающих язык, содержащий хотя бы один палиндром, неразрешимо
		+	# Докажите, что язык $\overline{L_A}\cup\overline{L_B}$ является регулярным тогда и только тогда, когда он совпадает с $\Sigma^*$, то есть соответствующий экземпляр ПСП неразрешим. Сделайте вывод относительно возможности проверки КС-языка на регулярность.
		+	# Докажите, что задача проверки, что дополнение КС-языка является КС-языком, алгоритмически неразрешима

@@ Строка 113: / Строка 113: @@
 # Пусть $A(x,y)$ - функция от двух аргументов и для любого $x$ функция $A_x(y)=A(x, y)$ как функция одного аргумента - вычислима. Значит ли это. что функция $A$ вычислима как функция двух аргументов?
 # Функция $f$ называется продолжением функции $g$, если для любого $n$, такого что $g$ определена, $f$ также определена и $f(n) = g(n)$. Докажите, что существует вычислимая функция $d(n)$, такая что никакая всюду определенная вычислимая функция $f(n)$ не является ее продолжением.
-# Пусть множество пар $A=\{(x, y)\}$ перечислимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, z)\in A \Rightarrow z \ge y\}$ перечислимо?
+# Пусть множество пар $A=\{(x, y)\}$ перечислимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо?
-# Пусть множество пар $A=\{(x, y)\}$ разрешимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, z)\in A \Rightarrow z \ge y\}$ перечислимо? Разрешимо?
+# Пусть множество пар $A=\{(x, y)\}$ разрешимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо? Разрешимо?

← Предыдущая		Версия 06:53, 16 ноября 2015
Строка 110:		Строка 110:
	# Покажите, что следующие три свойства множества $X$ равносильны: (1) $X$ можно представить в виде $A \setminus B$, где $A$ — перечислимое множество, а $B$ — его перечислимое подмножество; (2) $X$ можно представить в виде $A \setminus B$, где $A$ и $B$ — перечислимые множества; (3) $X$ можно представить в виде симметрической разности двух перечислимых множеств.		# Покажите, что следующие три свойства множества $X$ равносильны: (1) $X$ можно представить в виде $A \setminus B$, где $A$ — перечислимое множество, а $B$ — его перечислимое подмножество; (2) $X$ можно представить в виде $A \setminus B$, где $A$ и $B$ — перечислимые множества; (3) $X$ можно представить в виде симметрической разности двух перечислимых множеств.
	# Покажите, что множество $X$ можно представить в виде $A\setminus (B\setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности (суммы по модулю 2) трёх перечислимых множеств.		# Покажите, что множество $X$ можно представить в виде $A\setminus (B\setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности (суммы по модулю 2) трёх перечислимых множеств.
		+	# Пусть $A(x,y)$ - вычислимая функция от двух аргументов. Докажите, что для любого $x$ функция $A_x(y)=A(x, y)$ как функция одного аргумента - вычислима.
		+	# Пусть $A(x,y)$ - функция от двух аргументов и для любого $x$ функция $A_x(y)=A(x, y)$ как функция одного аргумента - вычислима. Значит ли это. что функция $A$ вычислима как функция двух аргументов?
		+	# Функция $f$ называется продолжением функции $g$, если для любого $n$, такого что $g$ определена, $f$ также определена и $f(n) = g(n)$. Докажите, что существует вычислимая функция $d(n)$, такая что никакая всюду определенная вычислимая функция $f(n)$ не является ее продолжением.
		+	# Пусть множество пар $A=\{(x, y)\}$ перечислимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)\| (x, z)\in A \Rightarrow z \ge y\}$ перечислимо?
		+	# Пусть множество пар $A=\{(x, y)\}$ разрешимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)\| (x, z)\in A \Rightarrow z \ge y\}$ перечислимо? Разрешимо?

← Предыдущая		Версия 10:52, 9 ноября 2015
Строка 99:		Строка 99:
	# Докажите, что множество чисел $i$, таких, что в десятичной записи числа $\pi$ встречается последовательность из $i$ семерок подряд, перечислимо. Является ли оно разрешимым? Почему?		# Докажите, что множество чисел $i$, таких, что в десятичной записи числа $\pi$ встречается последовательность из $i$ семерок подряд, перечислимо. Является ли оно разрешимым? Почему?
	# Докажите, что множество чисел $i$, таких, что в десятичной записи числа $\pi$ как подстрока десятичная запись $i$, перечислимо. Можно ли привести тот же аргумент, что и в предыдущем задании, для доказательства его (не)разрешимости?		# Докажите, что множество чисел $i$, таких, что в десятичной записи числа $\pi$ как подстрока десятичная запись $i$, перечислимо. Можно ли привести тот же аргумент, что и в предыдущем задании, для доказательства его (не)разрешимости?
		+	# Докажите, что любое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество.
		+	# Пусть $f$ - вычислимая функция. Докажите, что существует вычислимая функция $g$ с областью определения, совпадающей с областью значений $f$, такая что $f(g(f(x))) = f(x)$ для любого $x$, на котором $f$ определена.
		+	# Вещественное число $\alpha$ называется вычислимым, если существует вычислимая функция $a$, которая по любому рациональному $\varepsilon > 0$ даёт рациональное приближение к $\alpha$ с ошибкой не более $\varepsilon$, то есть $\|\alpha-a(\varepsilon)\| \le \varepsilon$ для любого рационального $\varepsilon > 0$. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда множество рациональных чисел, меньших $\alpha$, разрешимо
		+	# Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда последовательность знаков представляющей его десятичной (или двоичной) дроби вычислима.
		+	# Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к $\alpha$ (то есть является вычислимой функция, которая по $\varepsilon$ возвращает $n_0$, такое что $\|a_n - \alpha\| \le \varepsilon$ для $n > n_0$)
		+	# Покажите, что сумма, произведение, разность и частное вычислимых действительных чисел вычислимы. Покажите, что корень многочлена с вычислимыми коэффициентами вычислим.
		+	# Сформулируйте и докажите утверждение о том, что предел вычислимо сходящейся последовательности вычислимых действительных чисел вычислим.
		+	# Вещественное число $\alpha$ называют перечислимым снизу, если множество всех рациональных чисел, меньших $\alpha$, перечислимо. Перечислимость сверху определяется аналогично. Докажите, что число $\alpha$ перечислимо снизу тогда и только тогда, когда оно является пределом некоторой вычислимой возрастающей последовательности рациональных чисел.
		+	# Докажите, что вещественное число вычислимо тогда и только тогда, когда оно перечислимо снизу и сверху.
		+	# Покажите, что следующие три свойства множества $X$ равносильны: (1) $X$ можно представить в виде $A \setminus B$, где $A$ — перечислимое множество, а $B$ — его перечислимое подмножество; (2) $X$ можно представить в виде $A \setminus B$, где $A$ и $B$ — перечислимые множества; (3) $X$ можно представить в виде симметрической разности двух перечислимых множеств.
		+	# Покажите, что множество $X$ можно представить в виде $A\setminus (B\setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности (суммы по модулю 2) трёх перечислимых множеств.

← Предыдущая		Версия 18:08, 29 октября 2015
Строка 88:		Строка 88:
	# Рассмотрим детерминированный автомат с магазинной памятью, для которого выполнены свойства из двух предыдущих заданий. Докажите, что для любого состояния $p$ автомата и строки $\gamma$ в стеке существует строка $s$, для которой выполняется следующее свойство. Начав в состоянии $p$ и со стеком $\gamma$, считав строку $s$ автомат переходит некоторое состояние $q$ и имеет в стеке $\beta$, причем какую бы строку далее автомат не получил на вход, на вершине стека никогда не окажется второй символ $\beta$.		# Рассмотрим детерминированный автомат с магазинной памятью, для которого выполнены свойства из двух предыдущих заданий. Докажите, что для любого состояния $p$ автомата и строки $\gamma$ в стеке существует строка $s$, для которой выполняется следующее свойство. Начав в состоянии $p$ и со стеком $\gamma$, считав строку $s$ автомат переходит некоторое состояние $q$ и имеет в стеке $\beta$, причем какую бы строку далее автомат не получил на вход, на вершине стека никогда не окажется второй символ $\beta$.
	# На основании трех предыдущих заданий докажите, что не существует детерминированного автомата с магазинной памятью для языка палиндромов.		# На основании трех предыдущих заданий докажите, что не существует детерминированного автомата с магазинной памятью для языка палиндромов.
		+	# Докажите, что объединение и пересечение разрешимых языков разрешимо.
		+	# Докажите, что объединение и пересечение перечислимых языков перечислимо.
		+	# Докажите, что конкатенация и замыкание Клини разрешимых языков разрешимы.
		+	# Докажите, что конкатенация и замыкание Клини перечислимых языков перечислимы.
		+	# Докажите, что если множества $A$ и $B$ разрешимы (перечислимы), то их декартово произведение перечислимо.
		+	# Докажите, что образ перечислимого множества под действием вычислимой (не обязательно всюду определенной) функции перечислим.
		+	# Докажите, что прообраз перечислимого множества под действием вычислимой (не обязательно всюду определенной) функции перечислим.
		+	# Теорема об униформизации. Пусть задано перечислимое множество пар $F$. Докажите, что найдется вычислимая функция $f$, такая что для любого $x$, для которого существует $y$, такой что $(x,y)\in F$ выполнено, что $(x, f(x)) \in F$.
		+	# Пусть даны два перечислимых множества $X$ и $Y$. Докажите, что существуют непересекающиеся перечислимые множества $X' \subset X$ и $Y' \subset Y$, такие что $X' \cup Y' = X \cup Y$.
		+	# Докажите, что множество чисел $i$, таких, что в десятичной записи числа $\pi$ встречается последовательность из $i$ семерок подряд, перечислимо. Является ли оно разрешимым? Почему?
		+	# Докажите, что множество чисел $i$, таких, что в десятичной записи числа $\pi$ как подстрока десятичная запись $i$, перечислимо. Можно ли привести тот же аргумент, что и в предыдущем задании, для доказательства его (не)разрешимости?

← Предыдущая		Версия 18:25, 11 октября 2015
Строка 73:		Строка 73:
	# Докажите, что язык $\{0^n1^m2^n\| n \ne m\}$ не является КС.		# Докажите, что язык $\{0^n1^m2^n\| n \ne m\}$ не является КС.
	# Приведите пример не КС-языка, для которого выполнена лемма о разрастании.		# Приведите пример не КС-языка, для которого выполнена лемма о разрастании.
		+	# Постройте МП-автомат для языка $0^n1^n$.
		+	# Постройте МП-автомат для языка слов, где число нулей равно числу единиц.
		+	# Постройте МП-автомат для языка $0^n1^{2n}$.
		+	# Постройте МП-автомат для языка $0^n1^m2^{n+m}$.
		+	# Постройте МП-автомат для языка $0^{2n}1^n$.
		+	# Постройте МП-автомат для языка $0^n1^n\cup0^n1^{2n}$.
		+	# Постройте МП-автомат для языка слов $0^n1^m$, где $n \le m \le 2n$.
		+	# Докажите, что для любых $p$ и $q$ существует МП-автомат для языка слов $0^n1^m$, где $n/m=p/q$
		+	# Постройте автомат с магазинной памятью для языка слов над алфавитом $\{0, 1, 2\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.
		+	# Существует ли для языка из предыдущего задания детерминированный автомат?
		+	# Постройте автомат с магазинной памятью для языка палиндромов.
		+	# Докажите, что для любого автомата с магазинной памятью существует эквивалентный, который на каждом переходе кладет в стек не более 2 символов. Ваша конструкция должна сохранять детерминированность автомата, если ранее он был детерминированным.
		+	# Докажите, что для любого детерминированного автомата с магазинной памятью существует эквивалентный, который при $\varepsilon$-переходе только снимает или заменяет верхний символ стека (то есть размер стека не увеличивается на $\varepsilon$-переходах).
		+	# Рассмотрим детерминированный автомат с магазинной памятью, для которого выполнены свойства из двух предыдущих заданий. Докажите, что для любого состояния $p$ автомата и строки $\gamma$ в стеке существует строка $s$, для которой выполняется следующее свойство. Начав в состоянии $p$ и со стеком $\gamma$, считав строку $s$ автомат переходит некоторое состояние $q$ и имеет в стеке $\beta$, причем какую бы строку далее автомат не получил на вход, на вершине стека никогда не окажется второй символ $\beta$.
		+	# На основании трех предыдущих заданий докажите, что не существует детерминированного автомата с магазинной памятью для языка палиндромов.

← Предыдущая		Версия 14:22, 3 октября 2015
Строка 62:		Строка 62:
	# Верно ли, что любую КС-грамматику можно привести к форме, когда любое правило имеет вид $A\to BCD$ или $A\to a$?		# Верно ли, что любую КС-грамматику можно привести к форме, когда любое правило имеет вид $A\to BCD$ или $A\to a$?
	# Верно ли, что любой КС-язык над односимвольным алфавитом является регулярным?		# Верно ли, что любой КС-язык над односимвольным алфавитом является регулярным?
		+	# ХМУ 7.2.1 (а)
		+	# ХМУ 7.2.1 (б)
		+	# ХМУ 7.2.1 (в)
		+	# ХМУ 7.2.1 (г)
		+	# ХМУ 7.2.1 (д)
		+	# ХМУ 7.2.1 (е)
		+	# ХМУ 7.2.5 (а)
		+	# ХМУ 7.2.5 (б)
		+	# Докажите, что язык $\{0^n1^m2^n3^m\}$ не является КС.
		+	# Докажите, что язык $\{0^n1^m2^n\| n \ne m\}$ не является КС.
		+	# Приведите пример не КС-языка, для которого выполнена лемма о разрастании.