Список заданий по ДМ 2к 2024 весна - История изменений

Admin в 14:50, 8 мая 2024

2024-05-08T14:50:10Z

Admin в 12:17, 8 мая 2024

2024-05-08T12:17:13Z

Admin в 17:35, 4 мая 2024

2024-05-04T17:35:56Z

Admin в 14:50, 25 апреля 2024

2024-04-25T14:50:16Z

Admin в 13:21, 12 апреля 2024

2024-04-12T13:21:39Z

Admin в 07:18, 5 апреля 2024

2024-04-05T07:18:55Z

Admin в 13:44, 30 марта 2024

2024-03-30T13:44:48Z

Admin в 09:15, 21 марта 2024

2024-03-21T09:15:18Z

Admin в 09:14, 21 марта 2024

2024-03-21T09:14:57Z

Admin в 09:14, 21 марта 2024

2024-03-21T09:14:15Z

← Предыдущая		Версия 14:50, 8 мая 2024
Строка 239:		Строка 239:
	# Множество называется иммунным, если оно бесконечно, но не содержит бесконечных перечислимых подмножеств. Перечислимое множество называется простым, если дополнение к нему иммунно. Докажите, что существует простое множество.		# Множество называется иммунным, если оно бесконечно, но не содержит бесконечных перечислимых подмножеств. Перечислимое множество называется простым, если дополнение к нему иммунно. Докажите, что существует простое множество.
	# Докажите, что множество является иммунным тогда и только тогда, когда оно не содержит бесконечных разрешимых подмножеств.		# Докажите, что множество является иммунным тогда и только тогда, когда оно не содержит бесконечных разрешимых подмножеств.
		+	Это конец

← Предыдущая		Версия 12:17, 8 мая 2024
Строка 216:		Строка 216:
	# Приведите пример невычислимого предела сходящейся (но не вычислимо) последовательности вычислимых чисел		# Приведите пример невычислимого предела сходящейся (но не вычислимо) последовательности вычислимых чисел
	# Приведите пример невычислимого предела вычислимо сходящейся (но не вычислимой) последовательности вычислимых чисел		# Приведите пример невычислимого предела вычислимо сходящейся (но не вычислимой) последовательности вычислимых чисел
		+	# Рассмотрим список слов $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$.
		+	# Множество $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$ является эффективно неперечислимым.
		+	# Докажите, что любое эффективно неперечислимое множество является эффективно бесконечным.
		+	# Множество называется иммунным, если оно бесконечно, но не содержит бесконечных перечислимых подмножеств. Перечислимое множество называется простым, если дополнение к нему иммунно. Докажите, что существует простое множество.
		+	# Докажите, что множество является иммунным тогда и только тогда, когда оно не содержит бесконечных разрешимых подмножеств.

← Предыдущая		Версия 17:35, 4 мая 2024
Строка 194:		Строка 194:
	# Рассмотрим функцию $S(n)$, равную максимальной длине строки, выводимой программой длины $n$ на пустом входе. Докажите, что $S(n)$ невычислима.		# Рассмотрим функцию $S(n)$, равную максимальной длине строки, выводимой программой длины $n$ на пустом входе. Докажите, что $S(n)$ невычислима.
	# Рассмотрим произвольную всюду определенную вычислимую функцию $f : \Sigma^* \to \Sigma^*$. Докажите, что существует программа $p$, что $L(p) = L(f(p))$.		# Рассмотрим произвольную всюду определенную вычислимую функцию $f : \Sigma^* \to \Sigma^*$. Докажите, что существует программа $p$, что $L(p) = L(f(p))$.
		+	# Докажите, что счётчиковые машины с одним счётчиком распознают больше языков, чем конечные автоматы.
		+	# Модифицируем счётчиковую машину: разрешим счётчикам хранить как положительные, так и отрицательные значения (сравнивать можно по прежнему только с нулём). Докажите, что получившаяся модель эквивалентна по вычислительной мощности обычной счётчиковой машине с тем же числом счётчиков.
		+	# Стековая машина с бесконечным числом стеков. Пусть у стековой машины бесконечное число стеков и специальный счётчик, который показывает, какой стек сейчас анализируется. Функция переходов: $delta: Q \times (\Sigma \cup \varepsilon) \times \Pi \to {\cal P}_{<+\infty}\left( Q \times \Pi^* \times \{-1, 0, +1\}\right)$, где последний компонент результата функции указывает, что происходит с номером текущего стека. Докажите, что такая машина эквивалентна машине с двумя стеками.
		+	# Модифицируем счётчиковую машину: разрешим на переходе сравнивать значение в счётчике не только с 0, но и с любым другим целым числом (общее число переходов должно быть конечно). Докажите, что получившаяся модель эквивалентна по вычислительной мощности обычной счётчиковой машине с тем же числом счётчиков.
		+	# Отберем у машины Тьюринга возможность перемещаться налево, но разрешим новую команду RESET, которая перемещает головку на первый символ входного слова. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
		+	# Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только два раза: если значение в этой ячейке менялось уже дважды, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
		+	# Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только один раз: если значение в этой ячейке уже менялось, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
		+	# Докажите, что машина Тьюринга без возможности записи на ленту, эквивалентна по вычислительной мощности конечному автомату.
		+	# Докажите, что счётчиковые машины с одним счётчиком распознают меньше языков, чем автоматы с одним стеком, даже детерминированные.
		+	# Модифицируем счётчиковую машину: пусть зафиксировано число $b$ и разрешим счётчикам хранить только числа от $0$ до $b$. Какие языки распознают такие машины для различного числа счётчиков?
		+	# Вещественное число $\alpha$ называется вычислимым, если существует вычислимая функция $a$, которая по любому рациональному $\varepsilon > 0$ даёт рациональное приближение к $\alpha$ с ошибкой не более $\varepsilon$, то есть $\|\alpha − a(\varepsilon)\| \le \varepsilon$ для любого рационального $\varepsilon > 0$. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда множество рациональных чисел, меньших $\alpha$, разрешимо.
		+	# Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда последовательность знаков представляющей его десятичной (или двоичной) дроби вычислима. Последовательность называется вычислимой, если существует программа, которая по номеру $i$ выдает соответствующий элемент последовательности $a_i$.
		+	# Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к $\alpha$ (последнее означает, что можно алгоритмически указать $N$ по $\varepsilon$ в стандартном $\varepsilon$-$N$-определении сходимости.)
		+	# Покажите, что сумма, произведение, разность и частное вычислимых вещественных чисел вычислимы.
		+	# Покажите, что корень многочлена с вычислимыми коэффициентами вычислим.
		+	# Сформулируйте и докажите утверждение о том, что предел вычислимо сходящейся последовательности вычислимых вещественных чисел вычислим.
		+	# Вещественное число $\alpha$ называют перечислимым снизу, если множество всех рациональных чисел, меньших $\alpha$, перечислимо. (Перечислимость сверху определяется аналогично.) Докажите, что число $\alpha$ перечислимо снизу тогда и только тогда, когда оно является пределом некоторой вычислимой возрастающей последовательности рациональных чисел.
		+	# Докажите, что действительное число вычислимо тогда и только тогда, когда оно перечислимо снизу и сверху.
		+	# Докажите, что множество функций-приближений для рациональных вычислимых чисел $\alpha$ является неразрешимым. Указание: вспомните теорему о рекурсии.
		+	# Покажите, что существуют перечислимые снизу, но не вычислимые числа. Указание: рассмотрим сумму ряда $\sum 2^{-k}$ по $k$ из какого-либо множества $P$.
		+	# Приведите пример невычислимого предела сходящейся (но не вычислимо) последовательности вычислимых чисел
		+	# Приведите пример невычислимого предела вычислимо сходящейся (но не вычислимой) последовательности вычислимых чисел

← Предыдущая		Версия 14:50, 25 апреля 2024
Строка 179:		Строка 179:
	# Множество называется m-полным, если к нему m-сводится любое перечислимое множество. Докажите, что универсальное множество является $m$-полным.		# Множество называется m-полным, если к нему m-сводится любое перечислимое множество. Докажите, что универсальное множество является $m$-полным.
	# Докажите, что диагональ универсального множества (множество $\{u \| (u, u) \in U\}$ является m-полным.		# Докажите, что диагональ универсального множества (множество $\{u \| (u, u) \in U\}$ является m-полным.
		+	# Используя теорему о рекурсии, докажите, что язык программ, которые останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
		+	# Используя теорему о рекурсии, докажите, что язык программ, которые не останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
		+	# Используя теорему о рекурсии, докажите, что язык программ, которые допускают бесконечное число слов, является неразрешимым.
		+	# Используя теорему о рекурсии, докажите, что язык программ, которые допускают свой собственный исходный код, является неразрешимым.
		+	# Докажите, что существуют две различные программы $p$ и $q$, такие что программа $p$ печатает текст программы $q$, а программа $q$ печатает текст программы $p$.
		+	# Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_1$ печатает пустую строку, а $p_i$ печатает текст программы $p_{i-1}$.
		+	# Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_i$ печатает текст программы $p_{i+1}$.
		+	# Докажите, что для любого конечного $n$ существует последовательность программ $p_1, p_2, \ldots, p_n$, что $p_i$ печатает текст $p_{i+1}$, а $p_n$ печатает текст $p_1$.
		+	# Докажите, что язык программ, для которых не существует более короткой программы, которая на любом входе ведёт себя так же, является неразрешимым.
		+	# Докажите, что язык программ, для которых не существует программы такой же длины, которая на любом входе ведёт себя так же, является либо конечным, либо неразрешимым.
		+	# Докажите, что для любой всюду определенной вычислимой функции $f$ найдется значение $n$, для которого $BB(n) > f(n)$.
		+	# Докажите, что для любой всюду определенной вычислимой функции $f$ найдется бесконечно много значений $n$, для которых $BB(n) > f(n)$.
		+	# Пусть для любой строки $s$ выполнено $K(s) \ge f(s)$, где $f$ — всюду определенная вычислимая функция. Докажите, что найдется константа $C$, такая что $f(s) \le C$ для любой $s$.
		+	# Рассмотрим функцию $S(n)$, равную максимальной длине строки, выводимой программой длины $n$ на пустом входе. Докажите, что $S(n)$ невычислима.
		+	# Рассмотрим произвольную всюду определенную вычислимую функцию $f : \Sigma^* \to \Sigma^*$. Докажите, что существует программа $p$, что $L(p) = L(f(p))$.

← Предыдущая		Версия 13:21, 12 апреля 2024
Строка 159:		Строка 159:
	# Покажите, что множество $X$ можно представить в виде $A\setminus (B \setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности трёх перечислимых множеств.		# Покажите, что множество $X$ можно представить в виде $A\setminus (B \setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности трёх перечислимых множеств.
	# Покажите, что существует множество, которое можно представить в виде симметрической разности трёх перечислимых множеств, но нельзя представить в виде симметрической разности двух перечислимых множеств		# Покажите, что существует множество, которое можно представить в виде симметрической разности трёх перечислимых множеств, но нельзя представить в виде симметрической разности двух перечислимых множеств
		+	# Докажите, что если $A$ неперечислимо и $A \le_m B$, то $B$ неперечислимо.
		+	# Пусть $A$ перечислимо и $\mathbb{N} \setminus A \le_m A$. Что можно сказать про $A$?
		+	# Пусть $A$ перечислимо и $A \le_m \mathbb{N} \setminus A$. Что можно сказать про $A$?
		+	# Пусть дана функция $f : A \to \mathbb{N}$. Ее продолжением на множество $B \supset A$ называется функция $g:B \to \mathbb{N}$, что если $x\in A$, то $g(x) = f(x)$. Докажите, что существует вычислимая функция $f$, у которой не существует всюду определенного вычислимого продолжения.
		+	# Два перечислимых множества $A$ и $B$, где $A \cap B = \varnothing$ называются неотделимыми, если не сущестует разрешимых множеств $X$ и $Y$, таких что $A \subset X$, $B \subset Y$, $X \cap Y = \varnothing$. Покажите, что существуют неотделимые множества. Указание: рассмотрите множества пар $\langle p, x\rangle$, где $p$ - программа, возвращающая целое число, для некоторого условия.
		+	# Обобщите определение неотделимых множеств на счетное семейство множеств. Докажите, что существует счетное семейство неотделимых множеств.
		+	# Докажите, что множество программ, допускающих заданное конечное множество слов $x_1, \ldots, x_n$, перечислимо, но не разрешимо.
		+	# Докажите, что множество программ, допускающих бесконечное множество слов не разрешимо.
		+	# Докажите, что множество программ, зависающих на любом входе, не разрешимо.
		+	# Докажите, что множество программ, останавливающихся на своём собственном исходном коде, перечислимо, но не разрешимо.
		+	# Язык ограниченной задачи останова (bounded halting) $BH = \{ (p, t) \| p$ завершается на пустом входе за $t$ шагов $\}$. Докажите, что $BH$ разрешим.
		+	# Докажите, что существует разрешимое множество пар, проекция которого на одну из осей не является разрешимой.
		+	# Докажите, что существует разрешимое множество пар, проекция которого на каждую из осей не является разрешимой.
		+	# Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ перечислимо?
		+	# Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ разрешимо?
		+	# Множество $A \subset \mathbb{N} \times \mathbb{N}$ разрешимо. Можно ли утверждать, что множество «нижних точек» множества $A$, то есть множество $B = \{\langle x,y\rangle \| (\langle x,y\rangle \in A)$ и $(\langle x,z\rangle \not\in A$ для всех $z < y)\}$ является разрешимым?
		+	# В предыдущем задании можно ли утверждать, что $B$ перечислимо, если $A$ перечислимо?
		+	# Существует ли множество натуральных чисел $A$, к которому m-сводится любой множество натуральных чисел?
		+	# Множество называется m-полным, если к нему m-сводится любое перечислимое множество. Докажите, что универсальное множество является $m$-полным.
		+	# Докажите, что диагональ универсального множества (множество $\{u \| (u, u) \in U\}$ является m-полным.

← Предыдущая		Версия 07:18, 5 апреля 2024
Строка 141:		Строка 141:
	# Найдите ПФД для последовательности $a_n = 2^{\omega(n)}$, где $\omega(n)$ - количество различных простых делителей $n$.		# Найдите ПФД для последовательности $a_n = 2^{\omega(n)}$, где $\omega(n)$ - количество различных простых делителей $n$.
	# Найдите ПФД для последовательности $a_n = 3^{\omega(n)}$, где $\omega(n)$ - количество различных простых делителей $n$.		# Найдите ПФД для последовательности $a_n = 3^{\omega(n)}$, где $\omega(n)$ - количество различных простых делителей $n$.
		+	# Докажите, что объединение перечислимых языков перeчислимо, используя перечислители (не выполняйте сведение к полуразрешителю).
		+	# Докажите, что пересечение перечислимых языков перeчислимо, используя перечислители.
		+	# Докажите, что конкатенация перечислимых языков перeчислима.
		+	# Докажите, что замыкание Клини перечислимого языка перeчислимо.
		+	# Докажите, что декартово произведение перечислимых языков перeчислимо.
		+	# Докажите, что проекция перечислимого языка пар на каждую из осей перечислима.
		+	# Пусть $A \subset \Sigma^$. Функция $f:A \to \Sigma^$ называется вычислимой, если существует программа, которая по входу $x \in A$ выдает $f(x)$, а на входах не из $A$ зависает. Приведите пример невычислимой функции.
		+	# Графиком функции $f$ называется множество пар $(x, f(x))$ для тех $x$, на которых $f$ определена. Докажите, что функция вычислима тогда и только тогда, когда ее график перечислим.
		+	# Докажите, что образ перечислимого множества под действием вычислимой функции перечислим.
		+	# Докажите, что прообраз перечислимого множества под действием вычислимой функции перечислим.
		+	# В этой и последующих задачах вместо разрешимых и перечислимых языков рассматриваются разрешимые и перечислимые множества натуральных чисел. Это на самом деле одно и то же, достаточно установить естественную биекцию между натуральными числами и словами в градуированном лексикографическом порядке. Теорема об униформизации. Пусть $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)$ определено.
		+	# Покажите, что следующие три свойства множества $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$ — перечислимые множества, если и только если его можно представить в виде симметрической разности трёх перечислимых множеств.
		+	# Покажите, что существует множество, которое можно представить в виде симметрической разности трёх перечислимых множеств, но нельзя представить в виде симметрической разности двух перечислимых множеств

← Предыдущая		Версия 13:44, 30 марта 2024
Строка 123:		Строка 123:
	# Найдите ЭПФ для чисел Эйлера I рода		# Найдите ЭПФ для чисел Эйлера I рода
	# Найдите ЭПФ для чисел Эйлера II рода		# Найдите ЭПФ для чисел Эйлера II рода
		+	# В этом и следующих заданиях нужно выразить ПФД в замкнутом виде, возможно, используя $\zeta(s)$. Обозначим как $\sigma_k(n)$ сумму $d^k$, где $d$ пробегает все делители $n$ . Найдите ПФД для $\sigma_1(n)$
		+	# Найдите ПФД для $\sigma_k(n)$.
		+	# Найдите ПФД для последовательности $a_n$, где $a_n = 1$ если $n$ является квадратом целого числа, и $a_n = 0$ иначе.
		+	# Найдите ПФД для последовательности $a_n$, где $a_n = 1$ если $n$ свободно от квадратов, и $a_n = 0$ иначе.
		+	# Зная ПФД для последовательности $a_n$, найдите ПФД для последовательности $a_n \cdot \ln n$.
		+	# Функция Мангольдта $\Lambda_n$ равна $\ln p$, если $n = p^k$ для некоторого $k \ge 1$, и 0 иначе. Найдите ПФД для последовательности $\Lambda_n$.
		+	# Докажите, что если $f(n)$ - мультипликативная функция, то $g(n) = \sum\limits_{d \| n} f(d)$ тоже мультипликативна.
		+	# Докажите, что свертка Дирихле двух мультипликативных функций мультипликативна.
		+	# Докажите, что обратная по Дирихле функция к мультипликативной функции мультипликативна.
		+	# Используя ПФД, докажите, что $\sum\limits_{d \| n}\varphi(d) = n$
		+	# Используя ПФД, докажите, что $\sum\limits_{d \| n}\sigma_1(d)\varphi(n/d) = n \sigma_0(n)$.
		+	# Назовем функцию полностью мультипликативной, если $f(ab) = f(a)f(b)$ для любых $a$ и $b$. Какие значения $f(n)$ достаточно задать, чтобы определить $f$ на всех положительных натуральных числах?
		+	# Найдите ПФД для функции $\lambda(n) = (-1)^k$, где $k$ - количество простых делителей $n$ (с учетом кратности). Чему равна $\sum\limits_{d \| n} \lambda(d)$?
		+	# Рассмотрим строки из 0 и 1. Скажем, что строка $s$ периодичная, если ее можно представить как $k$ копий одной строки $p$: $s = p^k$ для некоторого $k > 1$. Выведите формулу для количества апериодичных строк для произвольного $n$. Указание: используйте формулу обращения Мебиуса.
		+	# Найдите ПФД для последовательности $a_n = $ количество упорядоченных разбиений числа $n$ на (не обязательно простые) $k$ множителей, множитель 1 разрешен.
		+	# Найдите ПФД для последовательности $a_n = $ количество упорядоченных разбиений числа $n$ на $\ge 0$ (не обязательно простых) множителей, множитель 1 запрещен.
		+	# Найдите ПФД для последовательности $a_n = 2^{\omega(n)}$, где $\omega(n)$ - количество различных простых делителей $n$.
		+	# Найдите ПФД для последовательности $a_n = 3^{\omega(n)}$, где $\omega(n)$ - количество различных простых делителей $n$.

@@ Строка 111: / Строка 111: @@
 # Рассмотрим комбинаторный объект ""строки из 0 и 1, без двух 1 подряд"". Представьте его как конструируемый комбинаторный объект, найдите его ПФ от двух переменных ($A_{n, m}$ равно количеству строк длины $n$ из $m$ единиц).
 # Найдите асимптотический главный член среднего количества единиц в таких строках длины $n$.
-# Рассмотрим производящую функцию для непомеченных деревьев с порядком на детях, заданную уравнением $T(z) = \frac {z} {1 - T(z)}$.
+# Рассмотрим производящую функцию для непомеченных деревьев с порядком на детях, заданную уравнением $T(z) = \frac {z} {1 - T(z)}$. Введем производящую функцию $G(z)$, равную сумме $d+1$ по всем таким деревьям (где $d$ - степень корня). Докажите, что $G(z) = \frac {T(z)}{z} - 1$.
 # Найдите точное выражение для средней степени корня в деревьях из прошлого задания. Найдите предел при $n \to \infty$.
 # Используя формулу обращения Лагранжа, найдите количество корневых лесов, состоящих из $k$ непомеченных деревьев с порядком на детях, порядок деревьев важен.

← Предыдущая		Версия 09:14, 21 марта 2024
Строка 107:		Строка 107:
	# Комбинаторный объект ""двоичная куча"". Рассмотрим помеченные двоичные деревья, где каждая вершина имеет двух детей, левого и правого (любое из этих поддеревьев может быть пустым), а также число в родителе вершины меньше числа в самой вершине (так, вершина с номером 1 --- всегда корень). Используя комбинаторную конструкцию ""произведение с коробочкой"", составьте и решите уравнение на экспоненциальную производящую функцию для двоичных куч.		# Комбинаторный объект ""двоичная куча"". Рассмотрим помеченные двоичные деревья, где каждая вершина имеет двух детей, левого и правого (любое из этих поддеревьев может быть пустым), а также число в родителе вершины меньше числа в самой вершине (так, вершина с номером 1 --- всегда корень). Используя комбинаторную конструкцию ""произведение с коробочкой"", составьте и решите уравнение на экспоненциальную производящую функцию для двоичных куч.
	# Обозначим за $G(t)$ экспоненциальную производящую функцию всех помеченных графов. Чему равно $g_n$? Выразите экспоненциальную производящую функцию связных помеченных графов, используя $G(t)$.		# Обозначим за $G(t)$ экспоненциальную производящую функцию всех помеченных графов. Чему равно $g_n$? Выразите экспоненциальную производящую функцию связных помеченных графов, используя $G(t)$.
		+	# Найдите среднее число слагаемых, равных 1, в случайном упорядоченном разбиении числа $n$ на положительные слагаемые.
		+	# Найдите среднее число слагаемых, равных $k$, в случайном упорядоченном разбиении числа $n$ на положительные слагаемые.
		+	# Рассмотрим комбинаторный объект ""строки из 0 и 1, без двух 1 подряд"". Представьте его как конструируемый комбинаторный объект, найдите его ПФ от двух переменных ($A_{n, m}$ равно количеству строк длины $n$ из $m$ единиц).
		+	# Найдите асимптотический главный член среднего количества единиц в таких строках длины $n$.
		+	# Рассмотрим производящую функцию для непомеченных деревьев с порядком на детях, заданную уравнением $T(z) = \frac {z} {1 - T(z)}$.
		+	Введем производящую функцию $G(z)$, равную сумме $d+1$ по всем таким деревьям (где $d$ - степень корня). Докажите, что $G(z) = \frac {T(z)}{z} - 1$.
		+	# Найдите точное выражение для средней степени корня в деревьях из прошлого задания. Найдите предел при $n \to \infty$.
		+	# Используя формулу обращения Лагранжа, найдите количество корневых лесов, состоящих из $k$ непомеченных деревьев с порядком на детях, порядок деревьев важен.
		+	# Выразите дисперсию средней стоимости комбинаторных объектов веса $n$ через производящую функцию $A(z, u)$.
		+	# Напишите ЭПФ от двух переменных для числа функций из $n$-элементного множества в $m$-элементное.
		+	# Напишите ЭПФ от двух переменных для числа инъекций из $n$-элементного множества в $m$-элементное.
		+	# Напишите ЭПФ от двух переменных для числа сюрьекций из $n$-элементного множества в $m$-элементное.
		+	# Найдите среднюю степень корня в случайном дереве Кэли из $n$ вершин.
		+	# Возрастающе-убывающей перестановкой называется перестановка, которая поочередно возрастает и убывает: $x_1 < x_2 > x_3 < x_4 \ldots$. Обозначим количество возрастающе-убывающих перестановок размера $n$ как $a_n$. Докажите, что экспоненциальной производящей функцией для последовательности $a_n$ является $(1+\sin t)/\cos t$.
		+	# Производящая функция Ньютона. Для последовательности $g_0, g_1, \ldots, g_n, \ldots$ производящая функция Ньютона определена как $\dot G(z) = \sum_n g_n{z \choose n}$. Пусть выполнено равенство: $\dot H(z) = \dot F(z) \cdot \dot G(z)$. Как связаны последовательности $f_i$, $g_i$ и $h_i$?
		+	# Найдите ЭПФ для чисел Эйлера I рода
		+	# Найдите ЭПФ для чисел Эйлера II рода