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

1. Формальный степенной ряд $\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$.
2. Формальный степенной ряд $(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}$.
3. Формальный степенной ряд $\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}$.
4. Пусть $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)$.
5. Докажите, что не существует формального степенного ряда $A(s)$, такого что $sA(s)=1$.
6. Будем называть нулем степенной ряд $0(s) = 0 + 0s + 0s^2 + \ldots$. Докажите, что $A(s) \ne 0(s)$, $B(s) \ne 0(s)$, то $A(s)B(s) \ne 0(s)$.
7. Пусть формальный степенной ряд $A(s)$ имеет целые коэффициенты. При каких условиях ряд $\frac{1}{A(s)}$ имеет целые коэффициенты?
8. Пусть формальный степенной ряд $A(s)$ имеет целые коэффициенты. При каких условиях ряд $A^{-1}(s)$ имеет целые коэффициенты?
9. Докажите, что $(A(s) + B(s))' = A'(s) + B'(s)$.
10. Докажите, что $(A(s)B(s))' = A'(s)B(s) + A(s)B'(s)$.
11. Докажите, что $\int(A'(s)B(s) + A(s)B'(s)) = A(s)B(s) - A(0)B(0)$.
12. Найдите производящую функцию для последовательности $1, 2, 3, \ldots, n, \ldots$.
13. Найдите производящую функцию для последовательности $0 \cdot 1, 1 \cdot 2, 2 \cdot 3, 3 \cdot 4, \ldots, (n - 1) \cdot n, \ldots$.
14. Найдите производящую функцию для последовательности $1^2, 2^2, 3^2, \ldots, n^2, \ldots$.
15. Производящая функция называется рациональной, если она представима в виде отношения двух многочленов. Для производящих функций каждой из следующих последовательностей выясните, является ли она рациональной, если да, приведите ее представление в таком виде. Последовательность $1, -2, 3, -4, 5, \ldots$.
16. Последовательность $2, -6, 12, \ldots, (-1)^k(k+1)(k+2),\ldots$
17. Последовательность $1, -4, 9, -16, \ldots, (-1)^k(k+1)^2,\ldots$
18. Последовательность $1, 1, 4, 9, 25, \ldots, F_k^2,\ldots$
19. Последовательность $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}$
20. Последовательность $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$
21. Последовательность $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$
22. Последовательность $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$
23. Последовательность $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$
24. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_1+\ldots+f_n=f_{n+2}-1$.
25. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_2+\ldots+f_{2n}=f_{2n+1}$.
26. Найдите производящую функцию для замощений прямоугольника $2\times n$ доминошками и единичными клетками.
27. Найдите производящую функцию для замощений прямоугольника $2\times n$ уголками (квадратами $2\times 2$ с вырезанной одной клеткой) и единичными клетками.
28. Найдите производящую функцию для чисел Каталана.
29. Произведением Адамара производящих функций $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)$.
30. Ландо, 2.16
31. Является ли произведение Адамара для производящих функций допустимым конструировнием?
32. Ландо, 2.9
33. Ландо, 2.11 (а)
34. Ландо, 2.11 (б)
35. Ландо, 2.11 (в)
36. Ландо, 2.11 (г)
37. Ландо, 2.12
38. Как оценить асимптотическое поведение чисел Каталана, используя производящую функцию?
39. Докажите, что объединение перечислимых языков перичислимо.
40. Докажите, что пересечение перечислимых языков перичислимо.
41. Докажите, что конкатенация перечислимых языков перичислима.
42. Докажите, что замыкание Клини перечислимого языка перичислимо.
43. Докажите, что декартово произведение перечислимых языков перичислимо.
44. Докажите, что проекция перечислимого языка пар на каждую из осей перечислима.
45. Докажите, что функция вычислима тогда и только тогда, когда ее график перечислим.
46. Докажите, что образ перечислимого множества под действием вычислимой функции перечислим.
47. Докажите, что прообраз перечислимого множества под действием вычислимой функции перечислим.
48. Шень, задание 7
49. Шень, задание 8
50. Шень, задание 9
51. Шень, задание 10
52. Шень, задание 11
53. Шень, задание 12
54. Шень, задание 13
55. Шень, задание 14(а)
56. Шень, задание 14(б)
57. Шень, задание 14(в)
58. Шень, задание 14(г)
59. Шень, задание 14(д)
60. Шень, задание 14(е)
61. Шень, задание 14(ж)
62. Шень, задание 15
63. Шень, задание 16
64. Шень, задание 23
65. Шень, задание 24, разрешимым?
66. Шень, задание 24, перечислимым?
67. Шень, задание 25
68. Шень, задание 26
69. Используя теорему о рекурсии, докажите, что язык программ, которые останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым? Как по-другому можно доказать неразрешимость этого языка?
70. Используя теорему о рекурсии, докажите, что язык программ, которые не останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым? Как по-другому можно доказать неразрешимость этого языка?
71. Используя теорему о рекурсии, докажите, что язык программ, которые допускают бесконечное число слов, является неразрешимым. Как по-другому можно доказать неразрешимость этого языка?
72. Покажите, что существует счётное число непересекающихся перечислимых множеств, никакие два из которых нельзя отделить разрешимым множеством. (Шень, задание 28)
73. Шень, задание 29
74. Шень, задание 30
75. Шень, задание 31
76. Докажите, что существуют две различные программы $p$ и $q$, такие что программа $p$ печатает текст программы $q$, а программа $q$ печатает текст программы $p$.
77. Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_i$ печатает текст программы $p_{i+1}$.
78. Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_1$ печатает пустую строку, а $p_i$ печатает текст программы $p_{i-1}$.
79. Докажите, что для любого конечного $n$ существует последовательность программ $p_1, p_2, \ldots, p_n$, что $p_i$ печатает текст $p_{i+1}$, а $p_n$ печатает текст $p_1$.
80. Рассмотрим два множества $A$ и $B$. Назовём их вычислимо изоморфными, если существует всюду определенная вычислимая биекция $\varphi$, такая что $x \in A$ тогда и только тогда, когда $\varphi(x) \in B$. Приведите пример бесконечных вычислимо изоморфных множеств.
81. Докажите или опровергните, что любые два бесконечных разрешимых множества являются вычислимо изоморфными.
82. Докажите или опровергните, что любые два бесконечных перечислимых множества являются вычислимо изоморфными.
83. Множество $A$ называется m-сводимым к $B$, если существует вычислимая всюду определенная функция $f$, для которой $x \in A$ тогда и только тогда, когда $f(x) \in B$. Пишут $A \le_m B$. Докажите, что если $A$ неразрешимо и $A \le_m B$, то $B$ неразрешимо.
84. Докажите, что если $A$ неперечислимо и $A \le_m B$, то $B$ неперечислимо.
85. Верно ли, что для любого $A$ выполнено $A \le_m N \setminus A$? ($N$ - множество всех натуральных чисел/слов)
86. Пусть $A$ перечислимо и $N \setminus A \le_m A$. Что можно сказать про $A$?
87. Пусть $A$ перечислимо и $A \le_m N \setminus A$. Что можно сказать про $A$?
88. Существует ли множество натуральных чисел $A$, к которому m-сводится любой множество натуральных чисел?
89. Множество называется $m$-полным, если к нему m-сводится любое перечислимое множество. Докажите, что универсальное множество является $m$-полным.
90. Докажите, что диагональ универсального множества (множество $\{u | (u, u) \in U\}$ является m-полным.
91. Шень 52
92. Шень 53
93. ХМУ 9.22 (а)
94. ХМУ 9.22 (б)
95. ХМУ 9.22 (в)
96. ХМУ 9.22 (г)
97. ХМУ 9.22 (д)
98. ХМУ 9.22 (е)
99. ХМУ 9.5.1

</wikitex>