cheatsheet.tex

\documentclass{article}

\usepackage{amsmath,amsthm,amssymb}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsmath,amsthm,amssymb}
\usepackage[margin=0.1cm]{geometry} 
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{wrapfig}
\usepackage{wasysym}
\usepackage{stackrel} 
\usepackage[noend]{algorithmic}
\usepackage{moreverb}
\usepackage[usenames]{color}
\usepackage{colortbl}
\usepackage{tikz}
\usepackage{hyperref} 


\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}

\newcommand{\then}{\Rightarrow}
\newcommand{\lra}{\Leftrightarrow}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\CO}{\mathbb{C}}

\newcommand{\vars}[2]{\left(#1\right)_{#2}}
\newcommand*{\xor}{\mathbin{\oplus}}

\newenvironment{theorem}[2][Т]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{lemma}[2][Л]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{exercise}[2][Упражнение]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{problem}[2][Задача]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries\large #1}\hskip \labelsep {\bfseries\large #2.}]}{\end{trivlist}}
\newenvironment{question}[2][Вопрос]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{corollary}[2][Corollary]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
\newenvironment{definition}[2][О]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2}]}{\end{trivlist}}

\newenvironment{solution}{\begin{proof}[Решение]}{\end{proof}}

\title{сheatsheet дискра.} 

\begin{document}
%\maketitle
{\center \textbf{\LARGE cheatsheet Дискра} (краткий копипаст из \href{http://rubtsov.su/public/hse/2017/DM-HSE-Draft.pdf}{\underline{учебника}}.)}

\section{Вычислимость}
\begin{theorem}{Поста}
Множество $A \subseteq \N$ разрешимо тогда и только
тогда, когда оба множества $A$ и $\N \setminus A$ перечислимы.
\end{theorem}

\begin{definition}{Универсальная вычислимая функция.}
Функция  $U : \N \times \N \to \N$ называется универсальной вычислимой
функцией для класса вычислимых функций от одной переменной, если
\begin{enumerate}
  \item U вычислима;
  \item для всякой вычислимой функции $f : \N \to \N$ существует такое $n$, что для всякого $x$ верно $f(x) = U(n, x)$.
\end{enumerate}

Она существует.
\end{definition}

\begin{theorem}{Функция без всюду
определённого вычислимого продолжения}
Существует вычислимая функция $f : \N \to \N$, не имеющая всюду
определённого вычислимого продолжения.

Это функция $f(n) = U(n, n) + 1$.
\end{theorem}

\begin{theorem}{Перечислимое неразрешимое множество}
Существует перечислимое неразрешимое множество $K \subseteq N$.

Это область определения $U(n, n)$.
\end{theorem}

\begin{definition}{Проблема остановки}
Рассмотрим множество $Halt \subseteq \N \times \N$, состоящее из таких пар
$(n, x)$, что $U(n, x)$ определено. Проблема остановки состоит в выяснении того, при-
надлежит ли данная пара множеству $Halt$.
\end{definition}

\begin{definition}{УВФ}
Универсальная вычислимая функция $U : \N \times \N \to \N$ для класса вычислимых функций от одной переменной называется главной (или гёделевой),
если для любой вычислимой функции $V : \N \times \N \to \N$ существует такая всюду определённая вычислимая функция $s: \N \to \N$, что для всякого $n \in \N$ и для всякого
$x \in N$ верно $U(s(n), x) = V (n, x)$, или, другими словами, для всякого $n \in N$ верно
$U_{s(n)} = V_n$.

Примеры изменения аргументов и значений:
\begin{itemize}
\item $U(n, x) = U(n, f(x)) \then \exists s(n) : \forall n \in \N \text{ выполн } U_{s(n)} = V_n = U_n \circ f$
\item $V(n, x) = f(U(n, x)) \then \exists s(n) : \forall n \in \N \text{ выполн } U_{s(n)} = V_n = f \circ U_n$
\end{itemize}
\end{definition}

\begin{theorem}{Райса – Успенского}
Пусть $U : \N \times \N \to \N$ — главная универсальная функция. Пусть A — нетривиальное свойство вычислимых функций.
Тогда множество
$
N = \{n~|~ U_n \in A\}
$
не разрешимо
\end{theorem}

\begin{theorem}{Неглавная УФ}
Существует неглавная универсальная функция для класса вычислимых функций одной переменной.
\end{theorem}


\begin{theorem}{Неподвижная точка}
Пусть $U : \N \times \N \to \N$ — главная универсальная функция. Тогда для
всякой всюду определённой вычислимой функции $h: \N \to \N$ существует $n \in \N$, при
котором $U_n = U_{h(n)}$.
\end{theorem}

\begin{definition}{Следствие из неп точки.}
Пусть $U : \N\times\N \to \N$ — главная универсальная функция. Тогда для
всякой вычислимой функции $V : \N \times \N \to \N$ существует $n$, при котором $U_n = V_n$.
\end{definition}

\section{МТ}

\begin{definition}{МТ}
МТ состоит из
\begin{itemize}
\item бесконечной в две стороны ленты, в ячейках которой могут быть записаны
символы алфавита $A$ (некоторого конечного множества);
\item головки, которая может двигаться вдоль ленты, обозревая в каждый данный
момент времени одну из ячеек;
\item оперативной памяти, которая имеет конечный размер (другими словами, со-
стояние оперативной памяти — это элемент некоторого конечного множества,
которое называется множеством состояний МТ $Q$);
\item таблицы переходов (или программы), которая задаёт функцию
\[
\delta : A \times \Q \to A \times \Q \times \{-1, 0, +1\}
\]
\end{itemize}
\end{definition}

\begin{definition}{Проблема остановки}
Даны описание машины Тьюринга и её входа,
нужно узнать, останавливается ли эта машина на этом входе.
\end{definition}

\begin{definition}{Граф подстановок.}
Мы выберем такой способ задания (ор)графа. Множество вершин — это множе-
ство слов в некотором алфавите $\Sigma$. А рёбра задаются правилами подстановки. Каждое правило имеет вид
$L \to R$,
где $L$, $R$ --- слова в алфавите $\Sigma$. Из слова $x$ ведёт ребро в слово $y$ по правилу подстановки $L \to R$, если $x = uLv$, $y = uRv$.
\end{definition}

\begin{definition}{Проблема остановки.}
Задача достижимости. Задан граф на множестве слов в алфавите $\Sigma$ набором
правил подстановки $R = {L_i \to R_i}$ и два слова $u, v \in \Sigma^{*}$. 
Верно ли, что $u \stackrel{*}{\to} v$.
\end{definition}

\section{Разрешаюшие деревья}
\begin{definition}{Сложность}
Сложностью протокола называется глубина дерева 
\end{definition}

\section{Булевы схемы}
\begin{definition}{Размер}
кол-во присваиваний
\end{definition}
\begin{definition}{Схемная cложность}
Схемная сложность булева отображения $f : {\{0, 1\}}^n \to {\{0, 1\}}^m$
(в частности, булевой функции) --- это наименьший размер схемы, вычисляющей это
отображение
\end{definition}

\section{Игры}

\begin{definition}{Согласованность.}
Стратегия для Макса гарантирует результат не менее $c$, если
во всех партиях, согласованных $с$ этой стратегией, результат игры (число в последней позиции этой партии -- напомним, что она заключительная по определению
партии) не меньше $c$. Симметричное определение для Мина: стратегия для Мина
гарантирует результат не более $c$, если во всех партиях, согласованных $с$ этой
стратегией, результат игры не больше $c$.
\end{definition}
\begin{definition}{Конечная комб игра}
Чтобы задать конечную комбинаторную игру, надо:
\begin{itemize}
\item Задать конечное множество $S$, элементы которого называют позициями игры.
\item Присвоить каждой позиции один из трёх типов: в одних ходит Макс, в дру-
гих ходит Мин, в третьих игра закончена. Позиции третьего типа называют
заключительными. Будем обозначать множества позиций первого типа $S_M$,
второго типа $S_m$ (по именам игроков), а множество заключительных позиций
$S_f$.
\item Указать начальную позицию $s_0 \in S$;
\item Для каждой незаключительной позиции указать, в какие вершины может из
неё попасть игрок, которой в ней ходит
\item Задать функцию выигрыша $v : S_f \to R$, которая в каждой заключительной
позиции определяет результат игры (выигрыш Макса, как мы договорились).
\end{itemize}
\end{definition}

\begin{definition}{Цена игры.}
Число $C$ называется ценой игры, если у Макса и у Мина есть
стратегии, гарантирующие выигрыш~$C$.
\end{definition}

\begin{theorem}{Существование цены.}
Для любой антагонистической игры на ациклическом графе суще-
ствует цена.
\end{theorem}

\begin{theorem}{Ним}
Позиция выйгрышна $\lra$ $\xor \neq 0$. 
\end{theorem}

Что делать с играми:
\begin{itemize}
    \item симметричность
    \item с конца
    \item можно использовать для доказательства сложности вычеслений (рассуждение с противником)
\end{itemize}

\section{Оценки на цешки}
$\binom{2n}{n} \geq \frac{2^{2n}}{2n + 1}$;
${\left(\frac{n}{k}\right)}^k \leq \binom{n}{k} < {\left(\frac{en}{k}\right)}^k$

\section{Вероятность}
\textit{Вероятностным пространством}называется конечное множество $U$, его элементы называются возможными \textit{исходами}. На
вероятностном пространстве задана функция $Pr: U \to [0, 1]$, такая что 
$\sum_{x \in U} Pr[x] = 1$. Функция Pr называется \textit{вероятностным распределением}, а число $Pr[x]$ называется \textit{вероятностью} исхода $x \in U$. \textit{Событием} называется произвольное подмножество $A \subseteq U$. Исходы, входящие в событие A, называются \textit{благоприятными} (для события $A$). \textit{Вероятностью} события A называется число~$Pr[A] = \sum_{x\in A} Pr[x]$.

Работает формула вкл-выкл. Следствие: $Pr[\bigcup_{i} A_i] \leq \sum_{i} Pr[A_i]$.

\textit{Условной вероятностью} события $A$ при условии $B$ называется число $Pr[A|B] = \frac{Pr[A \cap B]}{Pr[B]}$.

\begin{theorem}{Байеса}
Если вероятность событий A и B положительна: $Pr[A|B] \cdot Pr[B] = Pr[A] \cdot Pr[B|A]$.
\end{theorem}

Полная вероятность: $Pr[A] = \sum_{i} Pr[A|B_i] \cdot Pr[B_i]$.

\begin{definition}{Мат. ожидание.}
$E[\xi] = \sum_{i} a_i \cdot Pr[\xi = a_i]$. Оно линейно.
\end{definition}

\begin{lemma}{Неравенство Маркова}
$Pr[\xi \geq \alpha] \leq \frac{E[\xi]}{\alpha}$
\end{lemma}

%\section{ТЧ}
%Ну, это не влезло в две страницы.
%Если кому-то нужно, то напишите и сделайте pull request в репозиторий.

%\section{Порядки}
%Здесь можно что-нибудь написать, если место будет.
\end{document}