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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 128: Строка 128:
 
# Докажите, что для любого конечного $n$ существует последовательность программ $p_1, p_2, \ldots, p_n$, что $p_i$ печатает текст $p_{i+1}$, а $p_n$ печатает текст $p_1$.
 
# Докажите, что для любого конечного $n$ существует последовательность программ $p_1, p_2, \ldots, p_n$, что $p_i$ печатает текст $p_{i+1}$, а $p_n$ печатает текст $p_1$.
 
# Докажите, что язык программ для которых не существует более короткой программы, которая на любом входе ведёт себя так же, является неразрешимым.
 
# Докажите, что язык программ для которых не существует более короткой программы, которая на любом входе ведёт себя так же, является неразрешимым.
# Докажите, что язык программ для которых не существует программы такой же длины, которая на любом входе ведёт себя так же, является либо конечным, либо неразрешимым.
+
# Докажите, что язык программ для которых не существует программы такой же длины, которая на любом входе ведёт себя так же, является неразрешимым.
 
# Специальное задание: выберите нетривиальный язык программирования и напишите на нём программу, которая выводит свой собственный код. Не используйте код из интернета, напишите сами. Языки программирования всех студентов в рамках одной группы должны быть различны.
 
# Специальное задание: выберите нетривиальный язык программирования и напишите на нём программу, которая выводит свой собственный код. Не используйте код из интернета, напишите сами. Языки программирования всех студентов в рамках одной группы должны быть различны.
 
# Специальное задание: выберите нетривиальный язык программирования и напишите на нём программы, которые демонстрируют решение одного из заданий 125-128. В рамках одной группы пара (язык программирования - номер задания) должна быть уникальной. Выберите язык программирования, отличный от предыдущего задания.
 
# Специальное задание: выберите нетривиальный язык программирования и напишите на нём программы, которые демонстрируют решение одного из заданий 125-128. В рамках одной группы пара (язык программирования - номер задания) должна быть уникальной. Выберите язык программирования, отличный от предыдущего задания.
Строка 144: Строка 144:
 
# Специальное задание. Автоматы Вольфрама. Рассмотрим клеточный автомат с двумя состояниями и $d = 1$. Пусть $n = 1$ и исходно нулевая клетка в состоянии $1$, а остальные клетки в состоянии $0$. Переходы автомата можно задать восемью битами: новым состоянием клетки для всех 8 возможных состояний клеткии её соседей. Можно нарисовать состояние всех клеток после каждого шага в виде двумерного изображения (см, например, https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D0%BE_110 для правила 110). Изучите разные правила. Выберите наиболее интересные по вашему мнению правила переходов.
 
# Специальное задание. Автоматы Вольфрама. Рассмотрим клеточный автомат с двумя состояниями и $d = 1$. Пусть $n = 1$ и исходно нулевая клетка в состоянии $1$, а остальные клетки в состоянии $0$. Переходы автомата можно задать восемью битами: новым состоянием клетки для всех 8 возможных состояний клеткии её соседей. Можно нарисовать состояние всех клеток после каждого шага в виде двумерного изображения (см, например, https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D0%BE_110 для правила 110). Изучите разные правила. Выберите наиболее интересные по вашему мнению правила переходов.
 
# Специальное задание. Игра "Жизнь" Конвея. Рассмотрим бесконечное клетчатое поле, каждая клетка может быть белой или черной. За один ход клетки перекрашиваются по следующему правилу: если у белой клетки ровно три из восьми черных соседа, она становится черной, иначе остаётся белой. Если у черной клетки 2 или 3 из 8 соседей черные, она остаётся черной, иначе она становится белой. Найдите в интернете симулятор игры жизнь и примеры интересных конфигураций. Поэкспериментируйте с ними.
 
# Специальное задание. Игра "Жизнь" Конвея. Рассмотрим бесконечное клетчатое поле, каждая клетка может быть белой или черной. За один ход клетки перекрашиваются по следующему правилу: если у белой клетки ровно три из восьми черных соседа, она становится черной, иначе остаётся белой. Если у черной клетки 2 или 3 из 8 соседей черные, она остаётся черной, иначе она становится белой. Найдите в интернете симулятор игры жизнь и примеры интересных конфигураций. Поэкспериментируйте с ними.
# Рассмотрим список слов $A = \{\alpha_1, \alpha_2, \ldots, \alpha_n\}$ над алфавитом $\Sigma$. Введем $n$ новых различных символов $d_1, d_2, \ldots, d_n$. Рассмотрим алфавит $\Sigma' = \Sigma \cup \{d_1, d_2, \ldots, d_n\}$. Рассмотрим КС-грамматику с одним нетерминалом $S$, алфавитом $\Sigma'$ и $n + 1$ правилом: $S \to \alpha_1 S d_1$,  $S \to \alpha_2 S d_2, \ldots, S \to \alpha_n S d_n$, $S \to \varepsilon$. Язык, порождаемый этой грамматикой, называется языком списка $A$ и обозначается как $L_A$. Опишите все слова языка $L_A$.
 
# Докажите, что для любого списка $A$ дополнение до его языка списка $\overline{L_A}$ является КС-языком. Указание: постройте МП-автомат для $\overline{L_A}$.
 
# Докажите, что проблема проверки пустоты пересечения двух КС-грамматик неразрешима.
 
# Докажите, что проблема проверки эквивалентности двух КС-грамматик неразрешима.
 
# Докажите, что проблема проверки, что язык заданной КС-грамматики совпадает с языком заданного регулярного выражения, неразрешима.
 
# Докажите, что проблема проверки того, что любое слово можно породить в заданной КС-грамматике, неразрешима.
 
# Докажите, что проблема проверки того, что язык одной заданной КС-грамматики входит в язык другой заданной КС-грамматики, неразрешима.
 
# Докажите, что проблема проверки того, что язык заданного регулярного выражения входит в язык заданной КС-грамматики, неразрешима.
 
# Докажите, что проблема проверки того, что язык заданной КС-грамматики содержит палиндром, неразрешима.
 
# Пусть задано два списка $A$ и $B$. Докажите, что $\overline{L_A} \cup \overline{L_B}$ является регулярным тогда и только тогда, когда он совпадает с $\Sigma'^*$. Следовательно проблема проверки того, что КС-грамматика порождает регулярный язык, неразрешима.
 
# Докажите, что проблема проверки того, что дополнение языка заданной КС-грамматики является КС-языком, неразрешима.
 
# Односторонние исчисления. Рассмотрим конечный набор правил $P$ вида $\alpha \rightarrow \beta$. Будем говорить, что из слова $x$ выводится $y$ с помощью $P$, если можно получить $x$ из $y$, выполнив ноль или более раз замену подстроки $x$, совпадающей с $\alpha$ для некоторого правила на $\beta$ для этого правила. Докажите, что множество троек $(P, x, y)$, где из $x$ выводится $y$ с помощью $P$ неразрешимо.
 
# Двусторонние исчисления. Рассмотрим конечный алфавит $\Sigma$ и набор правил вида $\alpha \leftrightarrow \beta$. Будем говорить, что слова $x$ и $y$ эквивалентны с точностью до $P$, если можно получить $x$ из $y$, выполнив ноль или более раз замену подстроки $x$, совпадающей с $\alpha$ для некоторого правила на $\beta$ для этого правила или $\beta$ для некоторого правила на $\alpha$ для этого правила. Докажите, что множество троек $(P, x, y)$, где $x$ эквивалентен $y$ с точность до $P$ неразрешимо.
 
# Докажите, существует конкретное множество правил одностороннего исчисления $P$, что для него множество пар $(x, y)$, где из $x$ выводится $y$ с помощью $P$ неразрешимо.
 
# Докажите, существует конкретное множество правил двустороннего исчисления $P$, что для него множество пар $(x, y)$, где $x$ эквивалентно $y$ с точностью до $P$ неразрешимо. (Это задание можно переформулировать в терминах полугрупп так: докажите, что существует полугруппа с конечным множеством образующих и конечным множеством соотношений, что проверка равенства слов в этой полугруппе неразрешима)
 
# Предыдущее задание можно обобщить на группы: докажите, что существует группа с конечным множеством образующих и конечным множеством соотношений, что проверка равенства слов в этой группе неразрешима. Отличие от предыдущего задания: вместе с каждым символом $c$ существует также символ $c^{-1}$ и соотношения $cc^{-1}\leftrightarrow\varepsilon$, $c^{-1}c\leftrightarrow\varepsilon$..
 
# Докажите, что следующее свойство перечислимых языков является перечислимым: язык содержит палиндром.
 
# Докажите, что следующее свойство перечислимых языков является перечислимым: язык содержит два слова одинаковой длины.
 
# Докажите, что следующее свойство перечислимых языков является перечислимым: язык содержит два слова разной длины.
 
# Докажите, что следующее свойство перечислимых языков не является перечислимым: все слова языка имеют различную длину.
 
# Докажите, что следующее свойство перечислимых языков не является перечислимым: язык не содержит заданное слово $x$.
 
# Является ли что следующее свойство перечислимых языков перечислимым: язык содержит пару $(p, x)$, для которой $p(x) = 1$?
 
# Является ли что следующее свойство перечислимых языков перечислимым: язык содержит пару $(p, x)$, для которой $p(x) \ne 1$?
 
# Множество $A$ назвается эффективно бесконечным, если существует всюду определенная вычислимая функция $f$, которая по числу $n$ выводит $n$ различных элементов множества $A$. Докажите, что если множество $A$ содержит бесконечное перечислимое подмножество, то оно эффективно бесконечно.
 
# Докажите, что если множество $A$ эффективно бесконечно, то оно содержит бесконечное перечислимое подмножество.
 
# Обозначим как $L(p)$ множество слов, которые допускается программой $p$. Множество $A$ назвается эффективно неперечислимым, если существует всюду определенная вычислимая функция $f$, которая по программе $p$ указывает слово $x$, такое что $x \in L(p) \oplus A$. Докажите, что дополнение к диагонали универсального множества $\overline D$, где $D = \left\{p | \langle p, p\rangle \in U\right\}$, является эффективно неперечислимым.
 
# Докажите, что дополнение к универсальному множеству $\overline U$ является эффективно неперечислимым.
 
# Докажите, что любое эффективно неперечислимое множество является эффективно бесконечным.
 
# Докажите, что множество является иммунным тогда и только тогда, когда оно не содержит бесконечных разрешимых подмножеств.
 
# Рассмотрим два множества $A$ и $B$. Назовём их вычислимо изоморфными, если существует всюду определенная вычислимая биекция $\varphi : \mathbb{N} \to \mathbb{N}$, такая что $x \in A$ тогда и только тогда, когда $\varphi(x) \in B$. Приведите пример различных бесконечных вычислимо изоморфных множеств.
 
# Докажите или опровергните, что любые два бесконечных разрешимых множества, дополнения к которым также бесконечны, являются вычислимо изоморфными.
 
# Докажите или опровергните, что любые два бесконечных перечислимых множества, дополнения к которым также бесконечны, являются вычислимо изоморфными.
 
# Существует ли множество натуральных чисел $A$, к которому m-сводится любой множество натуральных чисел?
 
# Множество называется m-полным, если к нему m-сводится любое перечислимое множество. Докажите, что универсальное множество является $m$-полным.
 
# Докажите, что диагональ универсального множества (множество $\{u | (u, u) \in U\}$ является m-полным.
 

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

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

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