Список заданий по ДМ 2к 2017 весна

2017-05-17T14:21:06Z

94.25.229.76:

<wikitex>
# Формальный степенной ряд $\exp(s) = e^s$ определен как $e^s=1+\frac{1}{1!}s+\frac{1}{2!}s^2+\frac{1}{3!}s^3+\ldots+\frac{1}{n!}s^n+\ldots$. Логично, что $e^{-s}=1-\frac{1}{1!}s+\frac{1}{2!}s^2-\frac{1}{3!}s^3+\ldots+(-1)^n\frac{1}{n!}s^n+\ldots$. Докажите, используя определение умножения для степенных рядов, что $e^se^{-s}=1$.
# Формальный степенной ряд $(1+s)^\alpha$ определен как $(1+s)^\alpha=1+\frac{\alpha}{1}s+\frac{\alpha(\alpha-1)}{1 \cdot 2}s^2+\ldots+\frac{\alpha(\alpha-1)\ldots(\alpha-n+1)}{1 \cdot 2 \cdot\ldots\cdot n}s^n+\ldots$. Докажите, что $(1+s)^\alpha(1+s)^\beta=(1+s)^{\alpha+\beta}$.
# Формальный степенной ряд $\ln\left(\frac{1}{1-s}\right)$ определен как $\ln\left(\frac{1}{1-s}\right)=s+\frac{1}{2}s^2+\frac{1}{3}s^3+\ldots+\frac{1}{n}s^n+\ldots$. Докажите, что $\exp\left(\ln\left(\frac{1}{1-s}\right)\right)=(1-s)^{-1}$.
# Пусть $B(s) = b_1s+b_2s^2+b_3s^3+\ldots+b_ns^n+\ldots$, причем $b_1\ne 0$. Пусть формальные степенные ряды $A(s)$ и $C(s)$ таковы, что $A(B(s)) = s$, $B(C(s))=s$. Докажите, что $A(s)=C(s)$ Этот ряд называется обратным к $B(s)$, обозначается как $B^{-1}(s)$.
# Докажите, что не существует формального степенного ряда $A(s)$, такого что $sA(s)=1$.
# Будем называть нулем степенной ряд $0(s) = 0 + 0s + 0s^2 + \ldots$. Докажите, что $A(s) \ne 0(s)$, $B(s) \ne 0(s)$, то $A(s)B(s) \ne 0(s)$.
# Пусть формальный степенной ряд $A(s)$ имеет целые коэффициенты. При каких условиях ряд $\frac{1}{A(s)}$ имеет целые коэффициенты?
# Пусть формальный степенной ряд $A(s)$ имеет целые коэффициенты. При каких условиях ряд $A^{-1}(s)$ имеет целые коэффициенты?
# Докажите, что $(A(s) + B(s))' = A'(s) + B'(s)$.
# Докажите, что $(A(s)B(s))' = A'(s)B(s) + A(s)B'(s)$.
# Докажите, что $\int(A'(s)B(s) + A(s)B'(s)) = A(s)B(s) - A(0)B(0)$.
# Найдите производящую функцию для последовательности $1, 2, 3, \ldots, n, \ldots$.
# Найдите производящую функцию для последовательности $0 \cdot 1, 1 \cdot 2, 2 \cdot 3, 3 \cdot 4, \ldots, (n - 1) \cdot n, \ldots$.
# Найдите производящую функцию для последовательности $1^2, 2^2, 3^2, \ldots, n^2, \ldots$.
# Производящая функция называется рациональной, если она представима в виде отношения двух многочленов. Для производящих функций каждой из следующих последовательностей выясните, является ли она рациональной, если да, приведите ее представление в таком виде. Последовательность $1, -2, 3, -4, 5, \ldots$.
# Последовательность $2, -6, 12, \ldots, (-1)^k(k+1)(k+2),\ldots$
# Последовательность $1, -4, 9, -16, \ldots, (-1)^k(k+1)^2,\ldots$
# Последовательность $1, 1, 4, 9, 25, \ldots, F_k^2,\ldots$
# Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0 + a_1, a_1 + a_2, \ldots, a_k+a_{k+1}$
# Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots, \sum\limits_{i=0}^ka_i,\ldots$
# Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_1b, a_2b^2, \ldots, a_kb^k, \ldots$
# Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, 0, a_1, 0, a_2, 0, a_3 \ldots$
# Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_2, a_4, a_6 \ldots$
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_1+\ldots+f_n=f_{n+2}-1$.
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_2+\ldots+f_{2n}=f_{2n+1}$.
# Найдите производящую функцию для замощений прямоугольника $2\times n$ доминошками и единичными клетками.
# Найдите производящую функцию для замощений прямоугольника $2\times n$ уголками (квадратами $2\times 2$ с вырезанной одной клеткой) и единичными клетками.
# Найдите производящую функцию для чисел Каталана.
# Произведением Адамара производящих функций $A(t) = a_0 + a_1t + a_2t^2 + \ldots$ и $B(t) = n_0 + n_1t + n_2t^2 + \ldots$ называется функция $C(t) = a_0b_0 + a_1b_1t + a_2b_2t^2 + \ldots$. Докажите, что если функции $A(t)$ и $B(t)$ рациональны, то такова и функция $C(t)$.
# Ландо, 2.16
# Является ли произведение Адамара для производящих функций допустимым конструировнием?
# Ландо, 2.9
# Ландо, 2.11 (а)
# Ландо, 2.11 (б)
# Ландо, 2.11 (в)
# Ландо, 2.11 (г)
# Ландо, 2.12
# Как оценить асимптотическое поведение чисел Каталана, используя производящую функцию?
# Докажите, что объединение перечислимых языков перичислимо.
# Докажите, что пересечение перечислимых языков перичислимо.
# Докажите, что конкатенация перечислимых языков перичислима.
# Докажите, что замыкание Клини перечислимого языка перичислимо.
# Докажите, что декартово произведение перечислимых языков перичислимо.
# Докажите, что проекция перечислимого языка пар на каждую из осей перечислима.
# Докажите, что функция вычислима тогда и только тогда, когда ее график перечислим.
# Докажите, что образ перечислимого множества под действием вычислимой функции перечислим.
# Докажите, что прообраз перечислимого множества под действием вычислимой функции перечислим.
# Шень, задание 7
# Шень, задание 8
# Шень, задание 9
# Шень, задание 10
# Шень, задание 11
# Шень, задание 12
# Шень, задание 13
# Шень, задание 14(а)
# Шень, задание 14(б)
# Шень, задание 14(в)
# Шень, задание 14(г)
# Шень, задание 14(д)
# Шень, задание 14(е)
# Шень, задание 14(ж)
# Шень, задание 15
# Шень, задание 16
# Шень, задание 23
# Шень, задание 24, разрешимым?
# Шень, задание 24, перечислимым?
# Шень, задание 25
# Шень, задание 26
# Используя теорему о рекурсии, докажите, что язык программ, которые останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым? Как по-другому можно доказать неразрешимость этого языка?
# Используя теорему о рекурсии, докажите, что язык программ, которые не останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым? Как по-другому можно доказать неразрешимость этого языка?
# Используя теорему о рекурсии, докажите, что язык программ, которые допускают бесконечное число слов, является неразрешимым. Как по-другому можно доказать неразрешимость этого языка?
# Покажите, что существует счётное число непересекающихся перечислимых множеств, никакие два из которых нельзя отделить разрешимым множеством. (Шень, задание 28)
# Шень, задание 29
# Шень, задание 30
# Шень, задание 31
# Докажите, что существуют две различные программы $p$ и $q$, такие что программа $p$ печатает текст программы $q$, а программа $q$ печатает текст программы $p$.
# Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_i$ печатает текст программы $p_{i+1}$.
# Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_1$ печатает пустую строку, а $p_i$ печатает текст программы $p_{i-1}$.
# Докажите, что для любого конечного $n$ существует последовательность программ $p_1, p_2, \ldots, p_n$, что $p_i$ печатает текст $p_{i+1}$, а $p_n$ печатает текст $p_1$.
# Рассмотрим два множества $A$ и $B$. Назовём их вычислимо изоморфными, если существует всюду определенная вычислимая биекция $\varphi$, такая что $x \in A$ тогда и только тогда, когда $\varphi(x) \in B$. Приведите пример бесконечных вычислимо изоморфных множеств.
# Докажите или опровергните, что любые два бесконечных разрешимых множества являются вычислимо изоморфными.
# Докажите или опровергните, что любые два бесконечных перечислимых множества являются вычислимо изоморфными.
# Множество $A$ называется m-сводимым к $B$, если существует вычислимая всюду определенная функция $f$, для которой $x \in A$ тогда и только тогда, когда $f(x) \in B$. Пишут $A \le_m B$. Докажите, что если $A$ неразрешимо и $A \le_m B$, то $B$ неразрешимо.
# Докажите, что если $A$ неперечислимо и $A \le_m B$, то $B$ неперечислимо.
# Верно ли, что для любого $A$ выполнено $A \le_m N \setminus A$? ($N$ - множество всех натуральных чисел/слов)
# Пусть $A$ перечислимо и $N \setminus A \le_m A$. Что можно сказать про $A$?
# Пусть $A$ перечислимо и $A \le_m N \setminus A$. Что можно сказать про $A$?
# Существует ли множество натуральных чисел $A$, к которому m-сводится любой множество натуральных чисел?
# Множество называется $m$-полным, если к нему m-сводится любое перечислимое множество. Докажите, что универсальное множество является $m$-полным.
# Докажите, что диагональ универсального множества (множество $\{u | (u, u) \in U\}$ является m-полным.
# Шень 52
# Шень 53
# ХМУ 9.22 (а)
# ХМУ 9.22 (б)
# ХМУ 9.22 (в)
# ХМУ 9.22 (г)
# ХМУ 9.22 (д)
# ХМУ 9.22 (е)
# ХМУ 9.5.1
</wikitex>

Викиконспекты - Вклад участника [ru]

Список заданий по ДМ 2к 2017 весна