Редактирование: Список заданий по ДМ 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. В рамках одной группы пара (язык программирования - номер задания) должна быть уникальной. Выберите язык программирования, отличный от предыдущего задания. | ||
Строка 135: | Строка 135: | ||
# Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только два раза: если значение в этой ячейке менялось уже дважды, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга. | # Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только два раза: если значение в этой ячейке менялось уже дважды, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга. | ||
# Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только один раз: если значение в этой ячейке уже менялось, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга. | # Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только один раз: если значение в этой ячейке уже менялось, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга. | ||
− | # Клеточный автомат представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии, множество состояний $Q$, обозначим состояние ячейки $i$ как $s[i]$. Исходно все ячейки находятся в состоянии $B \in Q$, кроме ячеек с номерами от 1 до $n$. Ячейка с номером $i$, где $1 \le i \le n$ находится в состоянии $x_i$, где $x$ - входное слово (будем считать, что $\Sigma \subset Q$, $B \notin \Sigma$). Правила работы клеточного автомата такие: задано число $d$ и функция $f : Q^{2d+1} \to Q$. За один шаг все клетки меняют состояние по следующему правилу: новое состояние клетки $i$ равно $f(s[i - d], s[i - d + 1], \ldots, s[i + d - 1], s[i + d])$. Если клетка с номером $0$ переходит в состояние $Y$, то автомат допускает слово $x$. Докажите, что для | + | # Клеточный автомат представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии, множество состояний $Q$, обозначим состояние ячейки $i$ как $s[i]$. Исходно все ячейки находятся в состоянии $B \in Q$, кроме ячеек с номерами от 1 до $n$. Ячейка с номером $i$, где $1 \le i \le n$ находится в состоянии $x_i$, где $x$ - входное слово (будем считать, что $\Sigma \subset Q$, $B \notin \Sigma$). Правила работы клеточного автомата такие: задано число $d$ и функция $f : Q^{2d+1} \to Q$. За один шаг все клетки меняют состояние по следующему правилу: новое состояние клетки $i$ равно $f(s[i - d], s[i - d + 1], \ldots, s[i + d - 1], s[i + d])$. Если клетка с номером $0$ переходит в состояние $Y$, то автомат допускает слово $x$. Докажите, что для $d > 1$ клеточный автомат эквивалентен по вычислительной мощности машине Тьюринга. |
# Докажите, что счётчиковые машины с одним счётчиком распознают больше языков, чем конечные автоматы. | # Докажите, что счётчиковые машины с одним счётчиком распознают больше языков, чем конечные автоматы. | ||
# Докажите, что счётчиковые машины с одним счётчиком распознают меньше языков, чем автоматы с одним стеком, даже детерминированные. | # Докажите, что счётчиковые машины с одним счётчиком распознают меньше языков, чем автоматы с одним стеком, даже детерминированные. | ||
Строка 141: | Строка 141: | ||
# Модифицируем счётчиковую машину: разрешим на переходе сравнивать значение в счётчике не только с 0, но и с любым другим целым числом (общее число переходов должно быть конечно). Докажите, что получившаяся модель эквивалентна по вычислительной мощности обычной счётчиковой машине с тем же числом счётчиков. | # Модифицируем счётчиковую машину: разрешим на переходе сравнивать значение в счётчике не только с 0, но и с любым другим целым числом (общее число переходов должно быть конечно). Докажите, что получившаяся модель эквивалентна по вычислительной мощности обычной счётчиковой машине с тем же числом счётчиков. | ||
# Модифицируем счётчиковую машину: пусть зафиксировано число $b$ и разрешим счётчикам хранить только числа от $0$ до $b$. Какие языки распознают такие машины для различного числа счётчиков? | # Модифицируем счётчиковую машину: пусть зафиксировано число $b$ и разрешим счётчикам хранить только числа от $0$ до $b$. Какие языки распознают такие машины для различного числа счётчиков? | ||
− | # Стековая машина с бесконечным числом стеков. Пусть у стековой машины бесконечное число стеков и специальный счётчик, который показывает, какой стек сейчас анализируется. Функция переходов: $ | + | # Стековая машина с бесконечным числом стеков. Пусть у стековой машины бесконечное число стеков и специальный счётчик, который показывает, какой стек сейчас анализируется. Функция переходов: $delta: Q \times (\Sigma \cup \varepsilon) \times \Pi \to {\cal P}_{<+\infty}\left( Q \times \Pi^* \times \{-1, 0, +1\}\right)$, где последний компонент результата функции указывает, что происходит с номером текущего стека. Докажите, что такая машина эквивалентна машине с двумя стеками. |
− | # Специальное задание. Автоматы Вольфрама. Рассмотрим клеточный автомат с двумя состояниями и $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 соседей черные, она остаётся черной, иначе она становится белой. Найдите в интернете симулятор игры жизнь и примеры интересных конфигураций. Поэкспериментируйте с ними. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |