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

Централизованный алгоритм для WCP

2022-09-01T04:54:56Z

91.212.153.123:

Персистентная приоритетная очередь

2022-09-01T04:54:48Z

91.212.153.123:

Deepfake

2022-09-01T04:54:40Z

91.212.153.123:

Минимальная охватывающая окружность множества точек

2022-09-01T04:54:31Z

91.212.153.123:

Абсолютная погрешность

2022-09-01T04:54:24Z

91.212.153.123:

1ripmtnsumwc

2022-09-01T04:54:16Z

91.212.153.123:

Процесс Каратеодори

2022-09-01T04:54:07Z

91.212.153.123:

Основная информация о языкe

2022-09-01T04:53:59Z

91.212.153.123:

Динамическое программирование по профилю

2022-09-01T04:53:50Z

91.212.153.123:

Список заданий по ДМ 2к 2016 осень

2022-09-01T04:53:43Z

91.212.153.123:

Комбинаторные объекты

2022-09-01T04:53:35Z

91.212.153.123:

Тестовая страница2

2022-09-01T04:53:28Z

91.212.153.123:

{| 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 Майкл Наки].
|}

№1. Суммирование расходящихся рядов методом средних арифметических
Ряд <tex dpi='100'>\sum\limits_{n = 0}^\infty a_n</tex> имеет сумму <tex dpi='100'>S</tex> по '''методу средних арифметических''' (обозначают аббревиатурой с.а.), если <tex dpi='100'>S = \lim\limits_{n \rightarrow \infty} \frac 1{n + 1} \sum\limits_{k = 0}^n S_k</tex>.

№2. Суммирование расходящихся рядов методом Абеля
Пусть дан ряд <tex dpi='100'>\sum\limits_{n = 0}^{\infty}a_n</tex> и <tex dpi='100'> \forall t \in (0; 1) : \sum\limits_{n = 0}^{\infty}a_nt^n = f(t)</tex> (в классическом смысле). Тогда этот ряд имеет сумму <tex dpi='100'> S </tex> по '''методу Абеля''', если <tex dpi='100'> S = \lim\limits_{t \to 1 - 0} f(t)</tex>.

№3. Теорема Фробениуса
Условие
<tex dpi='100'> \sum\limits_{n = 0}^\infty a_n = S </tex> (с.а) <tex dpi='100'> \Rightarrow </tex> <tex dpi='100'> \sum\limits_{n = 0}^\infty a_n = S </tex> (А).

№4. Тауберова теорема Харди
Условие
<tex dpi='100'>\sum\limits_{k = 0}^\infty a_k = S</tex>(с.а.)
Тогда, если существует такое <tex dpi='100'> M > 0 </tex>, что <tex dpi='100'> \forall n \in \mathbb N: \sum\limits_{k = n + 1}^\infty a_k^2 \leq \frac{M}n </tex>, то <tex dpi='100'> \sum\limits_{k=0}^\infty a_k = S</tex>.

№5. Равномерная сходимость функционального ряда. Критерий Коши
<tex dpi='100'>f_1, f_2, \ldots</tex> равномерно сходится к <tex dpi='100'>f(x)</tex>, если
<tex dpi='100'>\forall \varepsilon\ > 0\ \exists N\ \forall n > N\ \forall x \in E : |f_n(x) - f(x)| < \varepsilon</tex>
Пишут, что <tex dpi='100'>f_n \rightrightarrows f</tex>.

Пусть на <tex dpi='100'>E</tex> задан функциональный ряд <tex dpi='100'>\sum\limits_{n = 1}^\infty f_n</tex>. Тогда он равномерно сходится к
<tex dpi='100'>f = \sum f_n</tex>, если
<tex dpi='100'>\forall\varepsilon\ > 0\ \exists N\ \forall n > N\ \forall x \in E : |S_n(x) - f(x)| < \varepsilon</tex>

Критерий Коши равномерной сходимости
УсловиеРяд равномерно сходится на <tex dpi='100'>E</tex> <tex dpi='100'>\iff</tex> <tex dpi='100'>\forall\varepsilon\ > 0\ \exists N\ \forall m, n : m \geq n > N\ \forall x \in E : \left|\sum\limits_{k = n}^m f_k(x)\right| < \varepsilon</tex>

№6. Признак Вейерштрасса
Условие
<tex dpi='100'>\sum\limits_{n = 1}^\infty f_n</tex>, <tex dpi='100'>\forall n \in \mathbb{N} </tex> , <tex dpi='100'> \forall x \in E : |f_n(x)| \leq a_n</tex>, <tex dpi='100'>\sum\limits_{n = 1}^\infty a_n</tex> - сходится.
Тогда <tex dpi='100'>\sum\limits_{n = 1}^\infty f_n</tex> равномерно сходится на <tex dpi='100'>E</tex>.

№7. Признак типа Абеля-Дирихле
Условие
Пусть: * <tex dpi='100'>\exists M: \forall x \in E \quad \forall N \in \mathbb N \quad \left |\sum\limits_{n = 1}^N b_n(x) \right| \le M</tex>
* <tex dpi='100'>\forall \varepsilon > 0 \quad \exists N \in \mathbb N \quad \forall n > N \quad \forall x \in E \quad |a_n(x)| < \varepsilon;\quad\exists N:\forall n>N\quad a_n \ge a_{n+1}</tex>
Тогда ряд <tex dpi='100'>\sum\limits_{n = 1}^\infty a_n(x)b_n(x)</tex> равномерно сходится.

№8. Предельный переход под знаком функционального ряда
Условие
Пусть на множестве <tex dpi='100'>E</tex> заданы функции <tex dpi='100'>f_n</tex>, <tex dpi='100'>a</tex> - предельная точка этого множества и
<tex dpi='100'>\forall n \in \mathbb{N}\ \exists\ \lim \limits_{x \to a} f_n(x)</tex>. Тогда если <tex dpi='100'>\sum \limits_{n = 0}^{\infty} f_n</tex> - равномерно
сходится на <tex dpi='100'>E</tex>, то выполняется равенство :
<tex dpi='100'>\lim \limits_{x \to a} \sum \limits_{n = 0}^{\infty} f_n(x) = \sum \limits_{n = 0}^{\infty} \lim\limits_{x \to a} f_n(x)</tex>

№9. Условия почленного интегрирования функционального ряда
Условие
Пусть <tex dpi='100'> f_{n} </tex> интегрируема и равномерно сходится к <tex dpi='100'> f </tex> на <tex dpi='100'> [a; b] </tex>. Тогда <tex dpi='100'> f </tex> тоже интегрируема, и
<tex dpi='100'> \lim \limits_{n \to \infty} \int\limits_{a}^{b} f_{n} = \int\limits_{a}^{b}f </tex>.
Условие
Пусть функциональный ряд состоит из <tex dpi='100'>f_n \in \mathcal{R}\left[ a, b \right ]</tex> и равномерно сходится на этом отрезке.
Тогда сумма ряда будет интегрируемой функцией, и будет выполняться:
<tex dpi='100'>\int\limits_{a}^{b} \sum\limits_{n = 1}^{\infty} f_{n}(x)dx =
\sum\limits_{n = 1}^{\infty} \int\limits_{a}^{b} f_{n}(x)dx</tex>

№10. Условия почленного дифференцирования функционального ряда
Условие
Пусть на <tex dpi='100'> (a, b) </tex> задан функциональный ряд <tex dpi='100'>\sum\limits_{n = 1}^{\infty} f_n</tex>, <tex dpi='100'>\exists c \in \langle a, b \rangle, \sum\limits_{n = 1}^{\infty}f_n(c)</tex> - сходится.
Пусть также <tex dpi='100'>\exists f_n'</tex> - непрерывна на <tex dpi='100'>\langle a, b \rangle</tex> и
<tex dpi='100'>\sum\limits_{n = 1}^{\infty} f_n'</tex> - равномерно сходится на <tex dpi='100'>\langle a, b\rangle</tex>, тогда на <tex dpi='100'>\langle a, b \rangle</tex> выполняется :
<tex dpi='100'>(\sum\limits_{n = 1}^{\infty} f_n(x))' = \sum\limits_{n = 1}^{\infty}f_n'(x)</tex>.

№11. Лемма Абеля
Условие
Пусть для некоторого <tex dpi='100'>x_0</tex> <tex dpi='100'>\sum\limits_{n = 0}^{\infty} a_n x_0^n</tex> - сходится.
Тогда <tex dpi='100'>\forall x_1 : |x_1| < |x_0|</tex> ряд <tex dpi='100'>\sum\limits_{n = 0}^\infty |a_n x_1^n|</tex> сходится.

№12. Теорема о радиусе сходимости
<tex dpi='100'>R = \sup \{|x| : \sum\limits_{n = 0}^\infty a_n x^n</tex> - сходится <tex dpi='100'>\}</tex>. Заметим, что возможны случаи <tex dpi='100'>R = 0</tex> и <tex dpi='100'>R = \infty</tex>.
Условие
Пусть есть ряд <tex dpi='100'>\sum\limits_{n = 0}^\infty a_n x^n</tex> и <tex dpi='100'>R</tex> - его радиус сходимости. Тогда
1) <tex dpi='100'>|x| < R</tex> <tex dpi='100'>\Rightarrow</tex> ряд абсолютно сходится.
2) <tex dpi='100'>\forall [a; b] \in (-R; R)</tex> ряд сходится абсолютно и равномерно.
3) <tex dpi='100'>|x| > R</tex> <tex dpi='100'>\Rightarrow</tex> ряд расходится.
4) <tex dpi='100'>|x| = R</tex> - неопределённость.

№13. Вычисление радиуса сходимости
Условие
Пусть есть <tex dpi='100'>\sum\limits_{n = 0}^\infty a_n x^n</tex>, <tex dpi='100'>R</tex> - его радиус сходимости. Тогда:
1) Если <tex dpi='100'>\exists q = \lim\limits_{n \to \infty} \left|\frac{a_n}{a_{n + 1} }\right|</tex>, то <tex dpi='100'>R = q</tex>.
2) Если <tex dpi='100'>\exists q = \lim\limits_{n \to \infty} \sqrt[n]{a_n}</tex>, то <tex dpi='100'>R = \frac1q</tex>
Замечание: на самом деле, есть формула Коши-Адамара, применимая в любом случае: <tex dpi='100'>R = \frac1{\overline{\lim} \sqrt[n]{|a_n|} }</tex>. <s> Но она сложная и никому не нужна. </s> Формула теоретическая, верхний предел вычислить часто невозможно.

№14. Дифференцирование и интегрирование степенных рядов
Вопрос: "Каковы будут радиусы сходимости почленно проинтегрированных или продифференцированных рядов?"
Ответ: "Почленное интегрирование или дифференцирование не меняет радиуса сходимости ряда".
утв:
УсловиеПромежуток сходимости степенного ряда совпадает с промежутком сходимости продифференцированного степенного ряда

№15. Степенной ряд, как ряд Тейлора своей суммы
<wikitex>
Пусть $ f(x) = \sum\limits_{n = 0}^{\infty} a_n (x - x_0)^n, \qquad R > 0 \qquad (x_0 - R; x_0 + R) $.
$ \sum\limits_{n = 0}^{\infty} \frac{f^{(n)}(x_0)}{n!} (x - x_0)^n $ - ряд Тейлора функции по степеням $ (x - x_0) $.
Сопоставим ряд с формулой Тейлора функции, которую можно писать для любого $ n $.
$ f(x) = \sum\limits_{k = 0}^{n} \frac{f^{(k)}(x_0)}{k!} (x - x_0)^k + r_n(x) \Rightarrow $ ряд получается из формулы при $ n \to \infty $. Если $ r_n(x) \rightarrow 0 $ при $ n \rightarrow \infty $, то можно перейти к пределу.
$ f(x) = \sum\limits_{k = 0}^{\infty} \frac{f^{(k)}(x_0)}{k!} (x - x_0)^k $, что является разложением функции в степенной ряд в точке $ x $.
Если при всех x из некоторой окрестности точки $ x_0 $ функция разлагается в степенной ряд, то это будет обязательно ряд Тейлора.
Если разложение возможно, то единственно. Изучается с помощью поведения остатка $ r_n(x) $.
</wikitex>

№16. Достаточное условие разложимости функции в ряд Тейлора
Для того, чтобы функция была разложима в ряд Тейлора, достаточно чтобы <tex dpi='100'> r_n \xrightarrow[n \to \infty]{} 0 </tex>

№17. Разложение в степенной ряд показательной и логарифмической функций
<wikitex>
$e^x \stackrel{def}{=} \sum\limits_{k = 0}^{\infty} \frac{x^k}{k!} $
$ \ln(1 + x) = \sum\limits_{k = 1}^n (-1)^{k - 1} \frac{x^k}k + r_n(x) $, причем $ r_n(x) = \frac{\ln^{(n + 1)} (1 + \theta_n x)}{(n + 1)!} x^{n + 1}, \theta_n \in (0; 1) $
</wikitex>

№18. Разложение в степенной ряд тригонометрических функций
<wikitex>
$\sin(x) = \sum\limits_{n = 0}^{\infty} {(-1)}^n \frac{x^{2n + 1}}{(2n + 1)!}$
$\cos(x) = \sum\limits_{n = 0}^{\infty} {(-1)}^n \frac{x^{2n}}{(2n)!}$
</wikitex>

№19. Биномиальный ряд Ньютона
<wikitex>
$ (1 + x)^{\alpha} = \sum\limits_{k = 1}^{\infty} \left[ \frac{\alpha (\alpha - 1) \dots (\alpha - k + 1)}{k!} x^k \right] + 1, \alpha \in \mathbb{R} $
$ r_n(x) = \frac{a (a - 1) \dots (a - n + 1) (a - n) (1 + \theta x)^{a - n - 1}}{n!} (1 - \theta)^n x^{n + 1} $ (в форме Коши)
</wikitex>

№20. Формула Стирлинга
<wikitex>
$ n! = \sqrt{2 \pi n} {\left ( \frac ne \right )}^n e^{\frac{\theta_n}{12n}} $
</wikitex>

№21. Нормированное пространство: арифметика предела
Условие
Пусть <tex dpi='100'>x_n</tex>, <tex dpi='100'>y_n</tex> — последовательности точек нормированного пространства <tex dpi='100'>(X, \|\cdot\|)</tex>, а <tex dpi='100'>\alpha_n</tex> — вещественная последовательность. Известно, что <tex dpi='100'>x_n \rightarrow x</tex>, <tex dpi='100'>y_n \rightarrow y</tex>, <tex dpi='100'>\alpha_n \rightarrow \alpha</tex>.
Тогда:
# <tex dpi='100'>x_n + y_n \rightarrow x + y</tex>
# <tex dpi='100'>\alpha_n x_n \rightarrow \alpha x</tex>
# <tex dpi='100'>\|x_n\| \rightarrow \|x\|</tex>

№22. Ряды в банаховых пространствах
Нормированное пространство <tex dpi='100'>(X, \|\cdot\|)</tex> называется '''B-пространством''', если для любой последовательности элементов <tex dpi='100'>X</tex>, для которых из <tex dpi='100'>\|x_n - x_m\| \to 0</tex> при <tex dpi='100'>n, m \to \infty</tex> вытекает существование предела последовательности.
<tex dpi='100'>\left \| \sum\limits_{k = 1}^\infty x_k \right \| \le \sum\limits_{k = 1}^\infty \| x_k \|</tex>

№23. Унитарные пространства, неравенство Шварца
Линейное множество со скалярным произведением называется унитарным пространством.
утв
<tex dpi='100'>|(x, y)| \le \sqrt{(x, x)}\sqrt{(y, y)}</tex>

№24. Гильбертовы пространства, экстремальное свойство ортонормированных систем
Среди нормированных пространств выделяется подкласс так называемых гильбертовых пространств.
Пусть <tex dpi='100'>H</tex> — линейное пространство. Величина <tex dpi='100'>(x, y) \in \mathbb R</tex> называется скалярным произведением точек множества <tex dpi='100'>H</tex>, если она удовлетворяет следующим трём аксиомам:
# <tex dpi='100'>(x, x) \ge 0</tex>, <tex dpi='100'>(x, x) = 0 \iff x = 0</tex>
# <tex dpi='100'>(x, y) = (y, x)</tex>
# <tex dpi='100'>(\alpha x + \beta y, z) = \alpha(x, z) + \beta(y, z)</tex>
Базируясь на этом неравенстве, определим норму <tex dpi='100'>\|x\| = \sqrt{(x, x)}</tex>.
Доказанное неравенство треугольника превращает <tex dpi='100'>H</tex> в нормированное пространство. Если оно является B-пространством, то его называют '''гильбертовым пространством'''.

Теорема Бесселя
Условие
Пусть <tex dpi='100'> l_1 \dots \l_n \dots </tex> - ОНС в <tex dpi='100'> H </tex> и <tex dpi='100'> x \in H </tex>, тогда
<tex dpi='100'> \sum \limits_{k=1}^{\infty} (x, l_k)^2 \le \|x\|^2</tex>
Экстремальное свойства ряда Фурье заключается в следующем: <tex dpi='100'>\sum \limits_{k=1}^{\infty} (x, l_k)^2</tex> располагается ближе всего к <tex dpi='100'>\|x\|^2</tex>, если <tex dpi='100'>l_k</tex> — ряд Фурье <tex dpi='100'>x</tex>.

№25. Ортогональные ряды в гильбертовых пространствах.
Ряд <tex dpi='100'> \sum\limits_{k = 1}^{\infty} x_k </tex> является '''ортогональным''', если <tex dpi='100'> \forall n \ne m \Rightarrow (x_n, x_m) = 0 </tex>.
В частности, так как <tex dpi='100'> l_1, \dots, l_n, \dots </tex> - ОНС в <tex dpi='100'> H </tex>(гильбертово), то <tex dpi='100'> \sum\limits_{k = 1}^{\infty} \alpha_k l_k </tex> - ортогональный ряд.

Условие
<tex dpi='100'>\sum\limits_{k = 1}^{\infty} x_k </tex> - сходящийся ортогональный ряд <tex dpi='100'> \Leftrightarrow \sum\limits_{k = 1}^{\infty} \| x_k \|^2 < + \infty </tex>.
При этом, если x - сумма ряда, то выполняется теорема Пифагора: <tex dpi='100'> \| x \|^2 = \sum\limits_{k = 1}^{\infty} \| x_k \|^2 </tex>

№26. Принцип сжатия Банаха
Пусть <tex dpi='100'>X</tex> - B-пространство. Пусть <tex dpi='100'>\overline V</tex> - замкнутый шар в <tex dpi='100'>X</tex>.<br>
<tex dpi='100'> \mathcal{T} : \overline V \to \overline V</tex> - '''сжатие''' на шаре <tex dpi='100'>\overline V</tex>, если <tex dpi='100'>\exists q \in (0;1) \ \forall x',x'' \in \overline V</tex> <tex dpi='100'> : \| \mathcal{T}x''-\mathcal{T}x' \| \le q \|x''-x'\|</tex>.
Теорема Банаха
У любого сжимающего отображения существует ровно одна неподвижная точка <tex dpi='100'>x^*=\mathcal{T}x^*</tex>.

№27. Линейные операторы в НП: непрерывность и ограниченность
Пусть <tex dpi='100'>X</tex>, <tex dpi='100'>Y</tex> — нормированные пространства, <tex dpi='100'>~\mathcal{A}\colon X \to Y</tex>. <tex dpi='100'>\mathcal{A}</tex> называется линейным оператором, если <tex dpi='100'>\mathcal{A} (\alpha x + \beta y ) = \alpha \mathcal{A} \left( x \right) + \beta \mathcal{A} \left( y \right), \forall \alpha, \beta \in \mathbb {R}, \forall x, y \in X</tex>
Л.о. называется ограниченным, если <tex dpi='100'>\exists m \in \mathbb {R} \ge 0: \forall x \in X \left \| \mathcal{A} \left( x \right) \right \| \le m \left \| x \right \|</tex>
Л.о. непрерывен в X, если <tex dpi='100'>\lim \limits_{\mathcal {4} x \to 0} \mathcal{A} \left( x + \mathcal{4}x \right) = \mathcal{A} \left( x \right) </tex>
Условие
Линейный оператор непрерывен тогда и только тогда, когда он ограничен.

№28. Норма линейного оператора
Нормой ограниченного оператора <tex dpi='100'>\left \| \mathcal{A} \right \|</tex> является <tex dpi='100'>\sup \limits_{\left \| x \right \| \le 1} \left \| \mathcal{A}x \right \|</tex>.

№29. Линейные функционалы в унитарном пространстве, разделение точек
'''Линейный функционал''' - линейный оператор вида <tex dpi='100'> \mathcal{A}: H \rightarrow \mathbb{R} </tex>, где <tex dpi='100'> H </tex> - гильбертово пространство.
Условие
Для любого <tex dpi='100'> x_0 \in H </tex> существует ограниченный линейный функционал <tex dpi='100'>f \colon H \to \mathbb{R}</tex>, обладающий такими свойствами:
# <tex dpi='100'>f \left ( x_0 \right ) = \left \| x_0 \right \|</tex>
# <tex dpi='100'>\left \| f \right \| = 1</tex>
Условие
<tex dpi='100'>\forall x \ne y\ \exists</tex> линейный функционал <tex dpi='100'>\mathcal{A} : \mathcal{A}x \ne \mathcal{A}y</tex>
Рассмотрим <tex dpi='100'>x-y</tex>. <tex dpi='100'>\exists \mathcal{A} : \mathcal{A}(x - y) = \| x- y\|</tex>.
По линейности, <tex dpi='100'>\mathcal{A}(x - y) = \mathcal{A}x - \mathcal{A}y</tex>. Значит, <tex dpi='100'>\mathcal{A}x \ne \mathcal{A}y</tex>.

№30. Пространство R^n : покоординатная сходимость
утв покоординатная сходимость в <tex dpi='100'>\mathbb R^n</tex>
Условие
Пусть дана последовательность <tex dpi='100'>\overline x^{(m)} \in \mathbb R^n</tex>. Тогда <tex dpi='100'>\overline x^{(m)} \rightarrow \overline x</tex> в <tex dpi='100'>\mathbb R^n</tex> тогда и только тогда, когда для любого <tex dpi='100'>j \in 1,\dots,n</tex> последовательность <tex dpi='100'>\overline x_j^{(m)} \rightarrow \overline x_j</tex>

№31. Полнота R^n
Условие
Пространство <tex dpi='100'>\mathbb R^n</tex> с евклидовой нормой является B-пространством.
док-во
Надо установить, что из сходимости в себе следует существование предела по норме <tex dpi='100'>\mathbb R^n</tex>.
Если <tex dpi='100'>\|\overline x^{(m)} - \overline x^{(p)}\| \rightarrow 0</tex>, то для любого <tex dpi='100'>j</tex> выполняется <tex dpi='100'>|x_j^{(m)} - x_j^{(p)}| \rightarrow 0</tex>. По критерию Коши для числовых последовательностей из этого следует, что каждая из последовательностей <tex dpi='100'>x_j^{(m)}</tex> имеет предел, то есть, последовательность точек сходится покоординатно.
Но по доказанному ранее утверждению из покоординатной сходимости следует сходимость по норме, что и требовалось доказать.

№32. Критерий компактности в R^n
Условие
Множество <tex dpi='100'> X </tex> в <tex dpi='100'> R^n </tex> компактно тогда и только тогда, когда оно замкнуто и ограничено.

Ворпос №33. Непрерывные отображения в R^n: координатные функции, непрерывность линейных операторов
Л.о. непрерывен в X, если <tex dpi='100'>\lim \limits_{\mathcal {4} x \to 0} \mathcal{A} \left( x + \mathcal{4}x \right) = \mathcal{A} \left( x \right) </tex>
Также, непрерывность л.о. совпадает с его непрерывностью в нуле.
В <tex dpi='100'>\mathbb{R}^n</tex> сходимость покоординатная. <tex dpi='100'>\left | \sum \limits_{k=1}^m a_{jk} x_k \right | \le \sum \limits_{k=1}^m \left | a_{jk} \right | \left | x_k \right | \le \sqrt {\sum \limits_{k=1}^m \left | a_{jk} \right | ^ 2} \left \| \overline x \right \|</tex> (по неравенству Коши для сумм), таким образом, из <tex dpi='100'>\overline x \to 0</tex> неизбежно следует <tex dpi='100'>\sum \limits_{k=1}^m a_{jk} x_k \to 0</tex>
Утв Условие
<tex dpi='100'>\left \| \mathcal{A} \right \| \le \sqrt{\sum \limits_{k=1}^n \sum \limits_{j=1}^m a_{jk}^2}</tex>
док-во
<tex dpi='100'>\overline y = \mathcal{A} \overline x, y_j = \sum \limits_{k=1}^n a_{jk} x_k</tex> — здесь отчётливо видно правило умножения матриц. Отсюда понятно, почему часто устанавливают связь между линейными операторами и матрицами: <tex dpi='100'>\mathcal{A} \colon \mathbb{R}^n \to \mathbb{R}^m \longleftrightarrow \mathcal{A} = \left ( a_{jk} \right )</tex>, где <tex dpi='100'>j</tex> и <tex dpi='100'>k</tex> пробегают от <tex dpi='100'>1</tex> до <tex dpi='100'>n</tex> и <tex dpi='100'>m</tex> соответственно, а <tex dpi='100'>\mathcal{A} \overline x </tex> — результат действия л.о. <tex dpi='100'>\mathcal{A}</tex> на точку <tex dpi='100'>\overline x</tex> можно представить в виде произведения матрицы <tex dpi='100'>\mathcal{A}</tex> и столбца <tex dpi='100'>x</tex>.
В <tex dpi='100'>\mathbb{R}^n</tex> сходимость покоординатная. <tex dpi='100'>\left | \sum \limits_{k=1}^m a_{jk} x_k \right | \le \sum \limits_{k=1}^m \left | a_{jk} \right | \left | x_k \right | \le \sqrt {\sum \limits_{k=1}^m \left | a_{jk} \right | ^ 2} \left \| \overline x \right \|</tex> (по неравенству Коши для сумм), таким образом, из <tex dpi='100'>\overline x \to 0</tex> неизбежно следует <tex dpi='100'>\sum \limits_{k=1}^m a_{jk} x_k \to 0</tex>
Итак, линейный оператор, действующий из одного конечномерного пространства в другое, всегда непрерывен.

№34. Дифференциал отображения и частные производные, дифференцируемость суперпозиции
Пусть <tex dpi='100'>V_{r}(x)</tex> -шар в <tex dpi='100'>X, \quad \mathcal{F} : V_r(x) \to Y </tex>. <tex dpi='100'>\mathcal{F}</tex> - '''дифференцируема''' в точке <tex dpi='100'>x</tex>, если существует зависящий от <tex dpi='100'> x </tex> ограниченный линейный оператор <tex dpi='100'>\mathcal{A} : X \to Y</tex>, такой, что если <tex dpi='100'>\left \| \Delta x \right \| < r \quad (x + \Delta x \in V_r(x))</tex>, то:
<tex dpi='100'> \mathcal{F}(x + \Delta x) - \mathcal{F}(x) = \mathcal{A}(\Delta x) + \alpha(\Delta x) \left \| \Delta x \right \| </tex>,
причем <tex dpi='100'> \alpha(\Delta x) \rightarrow 0</tex> при <tex dpi='100'>\Delta x \rightarrow 0</tex>
Тогда <tex dpi='100'>\mathcal{A}(x) = \mathcal{F}'(x)</tex> - '''производная Фреше''' отображения <tex dpi='100'>\mathcal{F}</tex> в точке <tex dpi='100'>x</tex>.
Условие
Композиция дифференцируемых отображений дифференцируема. Производная Фреше равна композиции производных Фреше отображений.
Пусть <tex dpi='100'>\mathcal{F} : V_r(x) \to Y, y = \mathcal{F}(x), \mathcal{G} : V_{r_1}(y) \to Z \quad \exists \mathcal{F}'(x), \mathcal{G}'(y), \mathcal{T} = \mathcal{G} \circ \mathcal{F}</tex>, тогда <tex dpi='100'>\exists \mathcal{T}'(x) = \mathcal{G}'(y)\mathcal{F}'(x)</tex>
Данный предел называется '''частной производной''' первого порядка функции <tex dpi='100'>\mathcal{F}_i</tex> по переменной <tex dpi='100'>x_j</tex>.
<tex dpi = "140">A_{ij} = \lim\limits_{h \to 0} \frac{\mathcal{F}_i(\overline{x} + h\overline{e_j}) - \mathcal{F}_i(x)}{h} = \frac{\partial \mathcal{F}_i}{\partial x_j}</tex>

№35. Формула конечных приращений для функции многих переменных
<tex dpi='100'>\mathcal{F}_i(\overline{a}) - \mathcal{F}_i(\overline{b}) = \mathcal{F}'_i(\theta_i\overline{a}+(1-\theta_i)\overline{b})(\overline{a}-\overline{b})</tex>

№36. Неравенство Лагранжа
Условие
Пусть <tex dpi='100'>V</tex> - шар в <tex dpi='100'>\mathbb{R}^n, \quad \mathcal{F} : V \to \mathbb{R}^m, \quad \mathcal{F}</tex> -дифференцируема в каждой точке шара, тогда:<br>
<tex dpi='100'>\forall \overline{a},\overline{b} \in V : \left|\left| \mathcal{F}(\overline{b}) - \mathcal{F}(\overline{a})\right|\right| \le M\left|\left|\overline{b}-\overline{a}\right|\right|</tex>, где <tex dpi='100'>M = \sup\limits_{x \in [\overline{a},\overline{b}]} \left|\left|\mathcal{F}'(\overline{x})\right|\right| </tex>

№37. Достаточное условие дифференцируемости функции многих переменных
Условие
Пусть <tex dpi='100'>V(a) \subset \mathbb{R}^n</tex> <tex dpi='100'>y = f(x_1,...,x_n)</tex>, <tex dpi='100'>y : V \to \mathbb{R}</tex>
<tex dpi='100'>\forall x \in V: \ \exists \frac{\partial f}{\partial x_j}</tex>, каждая из которых, как функция <tex dpi='100'>n</tex> переменных, непрерывна в <tex dpi='100'>\overline{a} :\lim\limits_{\overline{x} \to \overline{a}}\frac{\partial f}{\partial x_j}(\overline{x})
= \frac{\partial f}{\partial x_j}(\overline{a})</tex>.
Тогда существует дифференциал этой функции в точке <tex dpi='100'>a</tex>.

№38. Дифференциалы высших порядков, теорема о смешанных производных
Определим частные производные и дифференциалы высших порядков.
<tex dpi='100'>\frac \partial{\partial x_j}</tex> — оператор, дифференцирующий функцию по <tex dpi='100'>x_j</tex>. Последовательное применение такого рода оператора даёт нам частные производные высших порядков.
Пусть <tex dpi='100'>z = f(x,y)</tex>. Тогда <tex dpi='100'>\frac \partial{\partial y} \left ( \frac {\partial f}{\partial x} \right )\stackrel{\mathrm{def}}{=}\frac {\partial^2 f}{\partial x \partial y}</tex> — частная производная второго порядка функции <tex dpi='100'>f</tex>. Дифференцирование осуществляется по переменной в знаменателе, слева направо.
Пусть в двумерном шаре у функции <tex dpi='100'>z = f(x,y)</tex> существуют смешанные производные второго порядка и каждая из них непрерывна в некоторой точке <tex dpi='100'>\overline a</tex> этого шара. Тогда в <tex dpi='100'>\overline a</tex>: <tex dpi='100'>\frac {\partial^2 f}{\partial x \partial y} (\overline a)=\frac {\partial^2 f}{\partial y \partial x}(\overline a)</tex>

№39. Формула Тейлора для функции многих переменных
<tex dpi='100'>f(\overline a+t\Delta \overline a)-f(\overline a)=\sum \limits_{k=1}^n \frac {d^{k}f(\overline a)}{k!}+\frac {d^{n+1}f(\overline a+\theta\Delta \overline a)}{(n+1)!}</tex>

№40. Безусловный экстремум: необходимое и достаточное условия
Опр: Пусть задан линейный функционал <tex dpi='100'>y = f(x_1, x_2, \dots, x_n) </tex> на <tex dpi='100'> V(\overline{a}) \subset R^n </tex>.
Если при <tex dpi='100'>\| \Delta \overline{a} \| \le \delta</tex>, <tex dpi='100'>\delta \approx 0 \Rightarrow f(\overline{a} + \Delta \overline{a}) \le f(\overline{a})</tex>, то <tex dpi='100'>a</tex> {{---}} '''точка локального максимума'''. Аналогично определяется точка локального минимума.
Аналог теоремы Ферма
Пусть <tex dpi='100'>f</tex> дифференцируема в точке локального экстремума <tex dpi='100'>a</tex>. Тогда <tex dpi='100'>\forall j = 1..n : \frac{\partial{f}}{\partial{x_j}} \overline{a} = 0</tex>

№41. Локальная теорема о неявном отображении
О неявном отображении
Условие
Пусть для <tex dpi='100'>f</tex> поставлена задача о неявном отображении, с начальными данными <tex dpi='100'>(x_0,y_0)</tex>. Известно, что в окрестности начальных данных<tex dpi='100'>f_{\overline y}'</tex> непрерывно зависит от <tex dpi='100'>\overline x,\overline y</tex> и непрерывно обратима в <tex dpi='100'>(x_0,y_0)</tex>. Тогда в некоторой окрестности начальных данных неявное отображение существует.
{{TODO | t = здесь надо еще написать что-нибудь типа определения неявного отображения

№42. Исследование функции многих переменных на условный экстремум
<tex dpi='100'>z=f(\overline x, \overline y),~\overline x=(x_1,\dots x_n),~\overline y=(y_1,\dots y_m)</tex>. Пусть заданы «уравнения связи» в количестве m:
<tex dpi='100'>\begin{cases} g_1(\overline x,\overline y)=0\\
g_2(\overline x,\overline y)=0\\
\dots\\
g_m(\overline x,\overline y)=0 \end{cases};</tex>
<tex dpi='100'>(\overline{x_0},\overline{y_0})</tex> — '''условный максимум''' функции <tex dpi='100'>f</tex>, если для всех <tex dpi='100'>\overline x \approx \overline{x_0},~\overline y \approx \overline{y_0}</tex> и <tex dpi='100'>(\overline x,\overline y)</tex>, удовлетворяющих уравнениям связи, выполняется неравенство <tex dpi='100'>f(\overline x,\overline y)\le f(\overline {x_0},\overline {y_0})</tex>. Если же <tex dpi='100'>f(\overline x,\overline y)\ge f(\overline {x_0},\overline {y_0}),~(\overline{x_0},\overline{y_0})</tex> — '''условный минимум'''.

№43. Определенный интеграл, зависящий от параметра: непрерывность, интегрирование и дифференцирование
<wikitex>
Рассматриваем $ z = f(x, y) $, заданную на прямоугольнике $ a \le x \le b; \quad c \le y \le d $.
$ f $ непрерывна.
$ F(y) = \int\limits_a^b f(x, y) dx $ - интеграл, зависящий от параметра.
# $ F(y) $ - непрерывна на $ [c; d] $.
# Если существует непрерывная $ \frac{\partial f}{\partial y} $, то cуществует $ F'(y) = \int\limits_a^b \frac{\partial f}{\partial y} (x, y) dx $ - формула Лейбница.
# $ \int\limits_c^d F(y) dy = \int\limits_a^b dx \int\limits_c^d f(x, y) dy $ - формула читается справа налево, является повторным интегралом и по сути означает смену местами интегралов по двум переменным.
</wikitex>

№44. Равномерная сходимость несобственного интеграла, зависящего от параметра, признак Вейерштрасса
<wikitex>
Если выполняется следующее условие: $ f $ непрерывна, $ \forall \varepsilon > 0 : \exists A_0 : \forall A > A_0 , \forall y_0 \in [c; d] \Rightarrow | \int\limits_A^{\infty} f(x, y_0) dx | < \varepsilon $, то $ F(y) = \int\limits_a^{\infty} f(x, y) dx $ равномерно сходится на $ [c; d] $.
Вейерштрасс Признак равномерной сходимости несобственных интегралов
Условие
Пусть $ |f(x, y) | \le g(x)\ \forall x \ge a, \forall y \in [c; d] $.
Пусть $ \int\limits_a^{\infty} g(x) dx $ - сходится. Тогда соответствующий интеграл равномерно сходится на $ [c; d] $.
</wikitex>

№45. Несобственный интеграл, зависящий от параметра: непрерывность
<wikitex>
$ F(y) = \int\limits_a^{\infty} f(x, y) dx \stackrel{?}{\Rightarrow} \Delta F(y) \xrightarrow[\Delta y \to 0]{} 0 $
</wikitex>

№46. Несобственный интеграл, зависящий от параметра: интегрирование
<wikitex>
$ \int\limits_c^d dy \int\limits_a^{\infty} f(x, y) dx = \int\limits_a^{\infty} dx \int\limits_c^d f(x,y) dy $
</wikitex>

№47. Несобственный интеграл, зависящий от параметра: дифференцирование
<wikitex>
$ \int\limits_a^{\infty} \frac{\partial f}{\partial y} (x, y) dx = \left( \int\limits_c^{y} g(t) dt \right)' = \left( \int\limits_a^{\infty} f(x, y) dx \right)' $
</wikitex>

№48. Понятие о Гамма и Бета функциях Эйлера
<wikitex>
$ B (a, b) = \int\limits_0^1 x^{a - 1} (1 - x)^{b - 1} dx $
$ \Gamma (a) = \int\limits_0^{\infty} x^{a - 1} e^{-x} dx $
В обоих случаях: интегралы, зависящие от параметра.
Легко понять, что $ B (a, b) $ Сходится при $ a, b > 0 $; $ \Gamma(a) $ сходится при $ a > 0 $.
</wikitex>

№49. Интеграл Римана по прямоугольнику: критерий существования
<tex dpi='100'>(\bar{x_i}, \bar{y_i}) \in \Pi_{ij}</tex>
<tex dpi='100'>\sigma(f, \tau) = \sum\limits_{i= 0}^{n - 1} \sum\limits_{j = 0}^{m - 1} f(\bar{x_i}, \bar{y_j}) \delta x_i \delta y_j</tex>
<tex dpi='100'>|\Pi_{ij}| = \delta x_i \delta y_j</tex>
Двойной интеграл <tex dpi='100'>\iint\limits_\Pi f = \iint\limits_\Pi f(x, y) dx dy = \lim\limits_{\operatorname{rang} \tau \to 0} \sigma(f, \tau)</tex>
<tex dpi='100'>\underline{s}(f, \tau) = \sum\limits_{i, j} m_{ij} \delta x_i \delta y_j</tex>,
<tex dpi='100'>\overline{s}(f, \tau) = \sum\limits_{i, j} M_{ij} \delta x_i \delta y_j</tex>
если <tex dpi='100'>f</tex> - непрерывна на <tex dpi='100'> \Pi </tex>, то существует <tex dpi='100'>\iint\limits_\Pi f</tex>(достаточное условие интегрируемости).

№50. Аддитивность интеграла по прямоугольнику
* <tex dpi='100'>\exists \iint\limits_\Pi f \iff \forall m \ \exists \int\limits_{\Pi_m} f</tex>
* <tex dpi='100'>\iint\limits_\Pi f = \sum\limits_{m = 1}^p \, \iint\limits_{\Pi_m} f</tex>

№52. Критерий квадрируемости фигуры по Жордану
<tex dpi='100'>E \subset \mathbb{R}^2</tex> '''квадрируема по Жордану''', если существует <tex dpi='100'>\iint\limits_E 1</tex>. Значение этого интеграла называется 'площадью фигуры'.

№53. Условие существования интеграла по квадрируемому компакту
Условие
Пусть <tex dpi='100'>E</tex> - квадрируемый компакт на плоскости, <tex dpi='100'>f</tex> непрерывна на <tex dpi='100'>E</tex>. Тогда существует <tex dpi='100'>\iint\limits_E f</tex>.

№55. Вычисление площади фигуры в криволинейных координатах
<tex dpi='100'>\int \int dx dy = \int \int | J(u, v) | du dv </tex>

№56. Замена переменных интегрирования в двойном интеграле
<tex dpi='100'>\mathcal{J}(u_1, \ldots, u_n) = \left|\begin{array}{ccc}\frac{\partial x_1}{\partial u_1} & \cdots & \frac{\partial x_1}{\partial u_n} \\\vdots & \ddots & \vdots \\\frac{\partial x_n}{\partial u_1} & \cdots & \frac{\partial x_n}{\partial u_n} \\\end{array}\right| \ne 0</tex>
<tex dpi='100'>\int\limits_E f(\bar x) d \bar x = \int\limits_{E'} f(\bar x(\bar u)) |\mathcal{J}(\bar u)| d \bar u</tex>

№57. Обзор формул для многократных интегралов

Контексты и синтаксические моноиды

2022-09-01T04:53:19Z

91.212.153.123:

Умножение по Монтгомери

2022-09-01T04:53:12Z

91.212.153.123:

Представление производящей функций в виде непрерывных дробей

2022-09-01T04:53:04Z

91.212.153.123:

Задачи интерполирования функции

2022-09-01T04:52:56Z

91.212.153.123:

Теорема Банаха об обратном операторе

2022-09-01T04:52:48Z

91.212.153.123:

Тест Миллера-Рабина

2022-09-01T04:52:40Z

91.212.153.123:

Производные некоторых элементарных функций

2022-09-01T04:52:31Z

91.212.153.123:

Об интеграле Фурье

2022-09-01T04:52:23Z

91.212.153.123:

F2Cmax

2022-09-01T04:52:15Z

91.212.153.123:

Каскадный сумматор

2022-09-01T04:52:08Z

91.212.153.123:

Собственные векторы и собственные значения

2022-09-01T04:51:59Z

91.212.153.123:

Математическая логика

2022-09-01T04:51:52Z

91.212.153.123:

1ripmtnsumwu

2022-09-01T04:51:43Z

91.212.153.123:

Матфизика 6 семестр задания с лекций

2022-09-01T04:51:36Z

91.212.153.123:

Многопоточная сортировка слиянием

2022-09-01T04:51:28Z

91.212.153.123:

Метод главных компонент (PCA)

2022-09-01T04:51:20Z

91.212.153.123:

Неполные данные и null

2022-09-01T04:51:12Z

91.212.153.123:

Алгоритмы маршритизации

2022-09-01T04:51:05Z

91.212.153.123:

Вершинная, рёберная связность, связь между ними и минимальной степенью вершины

2022-09-01T04:50:55Z

91.212.153.123:

P2 pi1 prec ri Sum Ci

2022-09-01T04:50:48Z

91.212.153.123:

Цепные коды

2022-09-01T04:50:41Z

91.212.153.123:

Матричный умножитель

2022-09-01T04:50:33Z

91.212.153.123:

Приведение грамматики к ослабленной нормальной форме Грейбах

2022-09-01T04:50:25Z

91.212.153.123:

Пересечение всех максимальных по включению барьеров

2022-09-01T04:50:17Z

91.212.153.123:

Граф компонент рёберной двусвязности

2022-09-01T04:50:10Z

91.212.153.123:

Формальные грамматики

2022-09-01T04:50:01Z

91.212.153.123:

Теорема Карпа — Липтона

2022-09-01T04:49:54Z

91.212.153.123:

Метод генерации случайной перестановки, алгоритм Фишера-Йетса

2022-09-01T04:49:46Z

91.212.153.123:

Алгоритм Джонсона

2022-09-01T04:49:38Z

91.212.153.123:

Функция потерь и эмпирический риск

2022-09-01T04:49:31Z

91.212.153.123:

Теорема о компактности сопряжённого оператора

2022-09-01T04:49:23Z

91.212.153.123:

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

2022-09-01T04:49:16Z

91.212.153.123:

{| 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 Майкл Наки].
|}

# Формальный степенной ряд $\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)$.
# Будем называть нулем степенной ряд $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)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)$.
# Найдите производящую функцию для последовательности $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$.
# Последовательность $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$ с вырезанной одной клеткой) и единичными клетками.
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_1+f_3+\ldots+f_{2n-1}=f_{2n}-1$.
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0^2+f_1^2+f_2^2+\ldots+f_n^2=f_nf_{n+1}$.
# Найдите производящую функцию для чисел "трибоначчи" $f_0=f_1=f_2=1$, $f_n = f_{n-1}+f_{n-2}+f_{n-3}$.
# Найдите производящую функцию для последовательности, заданной рекуррентностью $f_0=f_1=f_2=1$, $f_n = f_{n-1}-2f_{n-3}$.
# Производящая функция называется рациональной, если она представима в виде отношения двух многочленов. Для производящих функций каждой из следующих последовательностей выясните, является ли она рациональной, если да, приведите ее представление в таком виде. Последовательность $1, -2, 3, -4, 5, \ldots$.
# Последовательность $2, -6, 12, \ldots, (-1)^k(k+1)(k+2),\ldots$
# Последовательность $0, 1, 4, 9, 16, 25, \ldots, k^2,\ldots$
# Последовательность $0, 1, 8, 27, 64, 125, \ldots, k^3,\ldots$
# Последовательность $0, 1, 2^s, 3^s, 4^s, 5^s, \ldots, k^s,\ldots$ для константного целого $s>0$
# Последовательность $1, -4, 9, -16, \ldots, (-1)^k(k+1)^2,\ldots$
# Последовательность $1, 1, 4, 9, 25, \ldots, F_k^2,\ldots$
# Найдите производящую функцию для чисел Каталана.
# Путь Моцкина - путь, начинающийся в точке $(0, 0)$, составленный из векторов $(1, 1)$, $(1, 0)$, $(1, -1)$, не опускающийся ниже оси $OX$ и заканчивающийся в точке $(n, 0)$. Напишите рекуррентное соотношение для числа путей Моцкина, найдите производящую функцию для числа таких путей.
# Рассмотрим множество путей на прямой, начинающихся в 0, состоящих из шагов длины 1 вправо или влево. Будем называть такой путь блужданием. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в 0.
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в 0 и не заходящих в отрицательную полупрямую.
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$.
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$ и не заходящих в отрицательную полупрямую.
# <s> Найдите производящую функцию для последовательности, заданной рекуррентным соотношением $a_0 = 2$, $a_n = a_{n-1}^2$. </s>
# <s> Найдите производящую функцию для последовательности, заданной рекуррентным соотношением $a_0 = 2$, $a_n = a_{n-1}^3$. </s>
# <s> Найдите производящую функцию для последовательности, заданной рекуррентным соотношением $a_0=a_1= 2$, $a_n = a_{n-1}\cdot a_{n - 2}$. </s>
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 5a_{n-1}-6a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-2}-a_{n-1}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 4a_{n-1}-4a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
# Петя заинтересовался, что будет, если последовательность, заданная линейным рекуррентным соотношением, имеет производящую фукнцию, в знаменателе которой стоит $Q(t)=(1-ct)(1+ct)$, ведь тогда асимптотическое поведение членов на четных и нечетных позициях разное. Разберитесь.
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 2a_{n-1}-2a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
# Докажите, что если последовательность $a_n$ допускает представление в виде $a_n = \sum_i p_i(n)q_i^n$, где $p_i(n)$ - полиномы, и все $q_i$ различны, то такое представление единственно с точностью до порядка слагаемых.
# Используя результат из предыдушего задания, докажите, что формальный степенной ряд $\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$ не представим в виде отношения двух полиномов.
# Произведением Адамара двух производящих функций $A(t)$ и $B(t)$ называется призводящая функция для ряда $C(t) = a_0b_0+a_1b_1t+a_2b_2t^2+\ldots+a_nb_nt^n+\ldots$. Докажите, что если $A(t)$ и $B(t)$ являются отношениями двух полиномов, то таким же свойством обладает и $C(t)$.
# Найдите произведение Адамара $\frac{1}{1-x}$ и $\frac{1}{1-2x}$.
# Найдите произведение Адамара $\frac{1}{1-2x}$ и $\frac{1}{1-3x}$.
# Найдите произведение Адамара $\frac{1}{1+3x-x^2}$ и $\frac{1}{1-2x}$.
# Найдите произведение Адамара $\frac{1}{1-2x-x^2}$ и $\frac{1}{1-2x}$.
# Пусть $A$ - семейство комбинаторных объектов. Пусть $M = MSet(A)$, а $P = Set(A)$. Докажите, что $M(t) = P(t)M(t^2)$.
# Пусть $A$ - семейство комбинаторных объектов с производящей функцией $A(t)$. Обозначим как $Seq^k(A)$ множество последовательностей длины $k$, каждый элемент которого является последовательностью из $k$ объектов. Найдите производящую функцию для $Seq^k(A)$.
# Пусть $A$ - семейство комбинаторных объектов с производящей функцией $A(t)$. Обозначим как $Seq^{\le k}(A)$ множество последовательностей длины не большей $k$, каждый элемент которого является последовательностью из не более чем $k$ объектов. Найдите производящую функцию для $Seq^{\le k}(A)$.
# Пусть $A$ - семейство комбинаторных объектов с производящей функцией $A(t)$. Обозначим как $Seq^{\ge k}(A)$ множество последовательностей длины не меньшей $k$, каждый элемент которого является последовательностью из не менее чем $k$ объектов. Найдите производящую функцию для $Seq^{\ge k}(A)$.
# Пусть $A$ - семейство комбинаторных объектов с производящей функцией $A(t)$. Пусть $\mathbb{N}$ - множество натуральных чисел, (вес числа $k$ равен $k$). Пусть $T \subset \mathbb{N}$, обозначим как $T(t)$ производящую функцию для множества $T$. Обозначим как $Seq_T(A)$ множество последовательностей элементов из $A$, где длина последовательности лежит в множестве $T$. Обозначим как $Z$ множество из одного элемента веса $1$. Обозначим как $C^T$ множество представлений в виде суммы, где порядок слагаемых важен и слагаемые выбраны из множества $T$. Осознайте, что $C^T = Seq(Seq_T(Z))$. Найдите производяющую функцию для $C^T$.
# Обозначим как $P^T$ множество разбиений на слагаемые, где порядок слагаемых не важен, а слагаемые выбраны из множества $T$. Осознайте, что $P^T = MSet(Seq_T(Z))$. Найдите производяющую функцию для $P^T$.
# Индекс Хирша. Докажите, что $\prod\limits_{n=1}^\infty\frac{1}{1-z^n}=\sum\limits_{n\ge 0}\frac{z^{n^2}}{((1-z)\cdots(1-z^n))^2}$.
# Докажите, что $\frac{1}{1-z}=\prod\limits_{j=0}^\infty(1+z^{2^j})$.
# Экспоненциальная производящая функция для целочисленной последовательности называется функцией Гурвица. Докажите, что сумма, произведение, интеграл и производная функции Гурвица является функцией Гурвица.
# Докажите, что результат подстановки функции Гурвица в функцию Гурвица является функцией Гурвица
# Опишите класс помеченных объектов $seq(cyc(Z))$. Найдите его экспоненциальную производящую функцию.
# Будем обозначать $seq_T$, $cyc_T$, $set_T$ соответственно последовательности, циклы и множества, размер которых принадлежит множеству $T$. Опишите класс помеченных объектов $set(cyc_{> 1}(Z))$. Найдите его экспоненциальную производящую функцию.
# Опишите класс помеченных объектов $set(cyc_{1, 2}(Z))$. Найдите его экспоненциальную производящую функцию.
# Сюрьекции на $r$-элементное множество. Осознайте, что $seq_{=r}(set_{\ge 1}(Z))$ задаёт сюрьекции на $r$-элементное множество. Найдите экспоненциальную производящую функцию.
# Разбиения на $r$ множеств. Осознайте, что $set_{=r}(set_{\ge 1}(Z))$ задаёт разбиения на $r$-элементное множество. Найдите экспоненциальную производящую функцию. Что стоит при $z^n$?
# Гиперболический синус $\mathrm{sh}\,z$ равен $\frac{1}{2}(e^{z}-e^{-z})$. Гиперболический косинус $\mathrm{ch}\,z$ равен $\frac{1}{2}(e^{z}+e^{-z})$. Рассмотрим разбиения $n$-элементного множества на непустые подмножества. Для произвольных подмножеств экспоненциальная производящая функция равна $e^{e^z-1}$. Докажите, что для разбиений на нечетное число подмножеств экспоненциальная производящая функция равна $\mathrm{sh}(e^z-1)$.
# Докажите, что для разбиений на четное число подмножеств экспоненциальная производящая функция равна $\mathrm{ch}(e^z-1)$.
# Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит нечетное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{sh}\,z}$.
# Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит четное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{ch}\,z-1}$. Почему здесь в показателе степени есть $-1$, а в предыдущем задании нет?
# Обобщите четыре предыдущих задания. Как выглядят экспоненциальные производящие функции для разбиений на (не)четное число подмножеств, каждое из которых содержит (не)четное число элементов? (Необходимо дать четыре ответа для всех комбинаций)
# Найдите производящую функцию для слов над $m$-буквенным алфавитом (вес каждой буквы равен 1, слова равен его длине).
# Обозначим как $W$ множество слов над алфавитом $\{a, b\}$. Осознайте, что $W=Seq\{a\}\times Seq(\{b\}\times Seq\{a\})$. Проверьте равенство для производящих функций.
# Обозначим как $W^{(k)}$ множество слов над алфавитом $\{a, b\}$, не содержащих $k$ букв $a$ подряд. Запишите $W^{(k)}$ через $Seq_T$ и $\times$. Найдите производящую функцию для $W^{(k)}$.
# Обобщите задание 72 на произвольный алфавит.
# Обобщите задание 73 на произвольный алфавит.
# Неявное задание КО. Пусть $A$, $B$ и $X$ - семейства комбинаторных объектов, причем $B \cap X = \varnothing$, $A = B \cup X$. Пусть производящие функции для $A$ и $B$ - $A(t)$ и $B(t)$, соответственно. Найдите производящую функцию $X(t)$.
# Неявное задание КО 2. Пусть $A$, $B$ и $X$ - семейства комбинаторных объектов, причем $A = B \times X$. Пусть производящие функции для $A$ и $B$ - $A(t)$ и $B(t)$, соответственно. Найдите производящую функцию $X(t)$.
# Неявное задание КО 3. Пусть $A$ и $X$ - семейства комбинаторных объектов, причем $A = Seq(X)$. Пусть производящая функция для $A$ - $A(t)$. Найдите производящую функцию $X(t)$.
# Неявное задание КО 4. Пусть $A$ и $X$ - семейства комбинаторных объектов, причем $A = MSet(X)$. Пусть производящая функция для $A$ - $A(t)$. Найдите производящую функцию $X(t)$.
# Докажите, что объединение перечислимых языков перeчислимо.
# Докажите, что пересечение перечислимых языков перeчислимо.
# Докажите, что конкатенация перечислимых языков перeчислима.
# Докажите, что замыкание Клини перечислимого языка перeчислимо.
# Докажите, что декартово произведение перечислимых языков перeчислимо.
# Докажите, что проекция перечислимого языка пар на каждую из осей перечислима.
# Пусть $A \subset \Sigma^*$. Функция $f:A \to \Sigma^*$ называется вычислимой, если существует программа, которая по входу $x \in A$ выдает $f(x)$, а на входах не из $A$ зависает. Приведите пример невычислимой функции.
# Докажите, что функция вычислима тогда и только тогда, когда ее график перечислим.
# Докажите, что образ перечислимого множества под действием вычислимой функции перечислим.
# Докажите, что прообраз перечислимого множества под действием вычислимой функции перечислим.
# В этой и последующих задачах вместо разрешимых и перечислимых языков рассматриваются разрешимые и перечислимые множества натуральных чисел. Это на самом деле одно и то же, достаточно установить естественную биекцию между натуральными числами и словами в градуированном лексикографическом порядке. Теорема об униформизации. Пусть $F$ — перечислимое множество пар натуральных чисел. Докажите. что существует вычислимая функция $f$, определённая на тех и только тех $x$, для которых найдётся $y$, при котором $\langle x,y\rangle \in F$, причём значение $f(x)$ является одним из таких $y$
# Даны два перечислимых множества $X$ и $Y$. Докажите, что найдутся два непересекающихся перечислимых множества $X'$ и $Y'$, таких что $X' \subset X$, $Y' \subset Y$, $X' \cup Y' = X \cup Y$.
# Докажите, что если перечислимое множество перечислимо в возрастающем порядке, то оно является разрешимым.
# Докажите, что любое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество.
# Покажите, что для всякой вычислимой функции $f$ существует вычислимая функция, являющаяся «псевдообратной» к $f$ в следующем смысле: область определения $g$ совпадает с областью значений $f$, и при этом $f(g(f(x))) = f(x)$ для всех $x$, при которых $f(x)$ определено.
# Вещественное число $\alpha$ называется вычислимым, если существует вычислимая функция $a$, которая по любому рациональному $\varepsilon > 0$ даёт рациональное приближение к $\alpha$ с ошибкой не более $\varepsilon$, то есть $|\alpha − a(\varepsilon)| \le \varepsilon$ для любого рационального $\varepsilon > 0$. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда множество рациональных чисел, меньших $\alpha$, разрешимо.
# Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда последовательность знаков представляющей его десятичной (или двоичной) дроби вычислима.
# Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к $\alpha$ (последнее означает, что можно алгоритмически указать $N$ по $\varepsilon$ в стандартном $\varepsilon$-$N$-определении сходимости.)
# Покажите, что сумма, произведение, разность и частное вычислимых вещественных чисел вычислимы. Покажите, что корень многочлена с вычислимыми коэффициентами вычислим.
# Сформулируйте и докажите утверждение о том, что предел вычислимо сходящейся последовательности вычислимых вещественных чисел вычислим.
# Вещественное число $\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) трёх перечислимых множеств.
# Докажите, что множество $\langle p \rangle$ программ, останавливающихся на своём собсвтенном исходном коде, перечислимо, но не разрешимо.
# Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ перечислимо?
# Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ разрешимо?
# Множество $U \subset \mathbb{N} \times \mathbb{N}$ разрешимо. Можно ли утверждать, что множество «нижних точек» множества $U$, то есть множество $V = \{\langle x,y\rangle | (\langle x,y\rangle \in U)$ и $(\langle x,z\rangle \not\in U$ для всех $z < y)\}$ является разрешимым?
# В предыдущем задании можно ли утверждать, что $V$ перечислимо, если $U$ перечислимо?
# Покажите, что существуют перечислимые снизу, но не вычислимые числа. Указание: рассмотрим сумму ряда $\sum 2^{-k}$ по $k$ из какого-либо перечислимого множества $P$. Она всегда перечислима снизу, но будет вычислимой только при разрешимом $P$.)
# Покажите, что существует множество, которое можно представить в виде симметрической разности трёх перечислимых множеств, но нельзя представить в виде симметрической разности двух перечислимых множеств
# Используя теорему о рекурсии, докажите, что язык программ, которые останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
# Используя теорему о рекурсии, докажите, что язык программ, которые не останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
# Используя теорему о рекурсии, докажите, что язык программ, которые допускают бесконечное число слов, является неразрешимым.
# Докажите, что существуют две различные программы $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 : \mathbb{N} \to \mathbb{N}$, такая что $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 \mathbb{N} \setminus A$?
# Пусть $A$ перечислимо и $\mathbb{N} \setminus A \le_m A$. Что можно сказать про $A$?
# Пусть $A$ перечислимо и $A \le_m \mathbb{N} \setminus A$. Что можно сказать про $A$?
# Существует ли множество натуральных чисел $A$, к которому m-сводится любой множество натуральных чисел?
# Множество называется m-полным, если к нему m-сводится любое перечислимое множество. Докажите, что универсальное множество является $m$-полным.
# Докажите, что диагональ универсального множества (множество $\{u | (u, u) \in U\}$ является m-полным.
# Рассмотрим список слов $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'^*$. Следовательно проблема проверки того, что КС-грамматика порождает регулярный язык, неразрешима.
# Докажите, что проблема проверки того, что дополнение языка заданной КС-грамматики является КС-языком, неразрешима.
# Рассмотрим абстрактный вычислитель "автомат с очередью" - по аналогии с автоматом с магазинной памятью, но вместо стека очередь. На переходе автомат извлекает первый символ из головы очереди, смотрит очередной символ на ленте и текущее состояние, переходит в новое состояние и добавляет в конец очереди произвольную строку. Докажите, что автомат с очередью может распознать любой перечислимый язык (указание: просимулируйте на автомате с очередью автомат с двумя стеками).
# Докажите, что машина Тьюринга без возможности записи на ленту, эквивалентна по вычислительной мощности конечному автомату.
# Отберем у машины Тьюринга возможность перемещаться налево, но разрешим новую команду RESET, которая перемещает головку на первый символ входного слова. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
# Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только два раза: если значение в этой ячейке менялось уже дважды, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
# Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только один раз: если значение в этой ячейке уже менялось, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
# Множество $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$ называется иммунным, если оно бесконечно, но не является эффективно бесконечным. Множество называется простым, если оно перечислимо, а его дополнение иммунно. Докажите, что существует простое множество. Указание: рассмотрите множество $T = \left\{\langle p, x\rangle | p(x) = 1, x > 2p\right\}$.
# Докажите, что множество является иммунным тогда и только тогда, когда оно не содержит бесконечных разрешимых подмножеств.
# Два перечислимых множества $A$ и $B$, где $A \cap B = \varnothing$ называются неотделимыми, если не сущестует разрешимых множеств $X$ и $Y$, таких что $A \subset X$, $B \subset Y$, $X \cup Y = \varnothing$. Покажите, что существуют неотделимые множества. Указание: рассмотрите множества пар $\langle p, x\rangle$, где $p$ - программа, возвращающая целое число, для некоторого условия.
# Обобщите определение неотделимых множеств на счетное семейство множеств. Докажите, что существует счетное семейство неотделимых множеств.
# Докажите, что существует вычислимая функция $f$, у которой не существует всюду определенного вычислимого продолжения.

OSI Model

2022-09-01T04:49:08Z

91.212.153.123:

Heavy-light декомпозиция

2022-09-01T04:49:00Z

91.212.153.123:

Теорема Банаха-Штейнгауза

2022-09-01T04:48:51Z

91.212.153.123:

Рёберная раскраска двудольного графа

2022-09-01T04:48:44Z

91.212.153.123:

Ранжирование

2022-09-01T04:48:36Z

91.212.153.123:

Дифф3сем-оглавление

2022-09-01T04:48:28Z

91.212.153.123: