TheoreticalInformatics.tex

\ifdefined\niveldos\else
\documentclass[12pt,letterpaper]{report}

%Russian-specific packages
%--------------------------------------
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage[mathscr]{euscript}
\usepackage{algorithm2e}
\usepackage{amsmath,amsthm,amssymb,latexsym,amsfonts}
\usepackage{lipsum}
\usepackage{soul}
\usepackage{amsmath,amssymb}
\usepackage{parskip}
\usepackage{graphicx}
\usepackage{mathtools}
\usepackage[usestackEOL]{stackengine}
\usepackage{tocloft}
\usepackage{xcolor}
\usepackage{hyperref}
\usepackage{tikz}
\usepackage{thmtools}
\usepackage{amsthm}
\usepackage{algpseudocode}
\usepackage{pdfcomment}
\usepackage{blindtext}
\usepackage{todonotes}
\usepackage{import}
\usepackage{hyphsubst}
\usepackage{bookmark}
\usepackage{pgfplots}
\usepackage{tikzsymbols}
\usepackage{cancel}
\usepackage{enumerate}
\usepackage{wrapfig}
\usepackage{graphicx}
\usepackage{tikz-cd}
%\usepackage{extarrows}
\usepackage{bussproofs}
\usepackage{multicol}
\usepackage{ulem}
\usepackage[inline]{enumitem}  
\usepackage[breakable, theorems, skins]{tcolorbox}

\usetikzlibrary{patterns.meta,
                babel,
                decorations.pathreplacing,
                positioning, 
                quotes,
                intersections,
                calc}

\graphicspath{ {./images/} }
%%

\DeclarePairedDelimiter\abs{\lvert}{\rvert}%
\DeclarePairedDelimiter\norm{\lVert}{\rVert}%

% Swap the definition of \abs* and \norm*, so that \abs
% and \norm resizes the size of the brackets, and the
% starred version does not.
\makeatletter
\let\oldabs\abs
\def\abs{\@ifstar{\oldabs}{\oldabs*}}
%
\let\oldnorm\norm
\def\norm{\@ifstar{\oldnorm}{\oldnorm*}}
\makeatother

\newtheorem*{theorem}{Теорема}
\newtheorem*{theorem-non}{Предложение}
\newtheorem*{lemma}{Лемма}
\theoremstyle{definition}
\newtheorem*{conj}{Определение}
\declaretheorem[numbered=no]{definition}

% Definindo novas cores
\definecolor{verde}{rgb}{0.25,0.5,0.35}
\definecolor{jpurple}{rgb}{0.5,0,0.35}
\definecolor{darkgreen}{rgb}{0.0, 0.2, 0.13}
%\definecolor{oldmauve}{rgb}{0.4, 0.19, 0.28}
% Configurando layout para mostrar codigos Java
\usepackage{listings}

\newcommand\butthole[1]{%
  \mathpalette\assircled{#1}%
}
\newcommand\asscircled[2]{%
  \tikz[baseline=(math.base)] \node[red, draw,circle,inner sep=1pt] (math) {$\m@th#1#2$};%
}

\newcommand{\estiloJava}{
\lstset{
    language=Java,
    basicstyle=\ttfamily\small,
    keywordstyle=\color{jpurple}\bfseries,
    stringstyle=\color{red},
    commentstyle=\color{verde},
    morecomment=[s][\color{blue}]{/**}{*/},
    extendedchars=true,
    showspaces=false,
    showstringspaces=false,
    numbers=left,
    numberstyle=\tiny,
    breaklines=true,
    backgroundcolor=\color{cyan!10},
    breakautoindent=true,
    captionpos=b,
    xleftmargin=0pt,
    tabsize=2
}}

\newcommand{\crel}[1]{%
  \global\setbox1=\hbox{$#1$}%
  \global\dimen1=0.5\wd1
  \mathrel{\hbox to\dimen1{$#1$\hss}}&\mathrel{\mspace{-\thickmuskip}\hbox to\dimen1{}}%
}

\newcommand{\estiloR}{
  \lstset{ %
    language=R,                     % the language of the code
    basicstyle=\footnotesize,       % the size of the fonts that are used for the code
    numbers=left,                   % where to put the line-numbers
    numberstyle=\tiny\color{gray},  % the style that is used for the line-numbers
    stepnumber=1,                   % the step between two line-numbers. If it's 1, each line
                                    % will be numbered
    numbersep=5pt,                  % how far the line-numbers are from the code
    backgroundcolor=\color{white},  % choose the background color. You must add \usepackage{color}
    showspaces=false,               % show spaces adding particular underscores
    showstringspaces=false,         % underline spaces within strings
    showtabs=false,                 % show tabs within strings adding particular underscores
    frame=single,                   % adds a frame around the code
    rulecolor=\color{black},        % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. commens (green here))
    tabsize=2,                      % sets default tabsize to 2 spaces
    captionpos=b,                   % sets the caption-position to bottom
    breaklines=true,                % sets automatic line breaking
    breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
    title=\lstname,                 % show the filename of files included with \lstinputlisting;
                                    % also try caption instead of title
    keywordstyle=\color{blue},      % keyword style
    commentstyle=\color{darkgreen},   % comment style
    stringstyle=\color{red},      % string literal style
    escapeinside={\%*}{*)},         % if you want to add a comment within your code
    morekeywords={*,...}          % if you want to add more keywords to the set
}}

\newcommand{\vertiii}[1]{{\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert #1
    \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}}
\newcommand*{\double}[2][.1ex]{%
  \mathrel{\vcenter{\offinterlineskip%
  \hbox{$#2$}\vskip#1\hbox{$#2$}}}}
\newcommand*{\doublerightarrow}{\double{\rightarrow}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\RR}{\mathcal{R}}
\newcommand{\PP}{\mathcal{P}}
\newcommand{\T}{\mathbb{T}}
\renewcommand{\C}{\mathbb{C}}


\newcommand{\follow}{\textbf{\textit{Следствие:}}}
\newcommand{\notice}{\underline{\textit{Замечание:}}}
\newcommand{\example}{\underline{Пример:}}
\newcommand{\examples}{\underline{Примеры:}}

% algebra defs
\newcommand{\id}{\operatorname{id}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\Lin}{\operatorname{Lin}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\Imm}{\operatorname{Im}}
\newcommand{\Ree}{\operatorname{Re}}
\newcommand{\Ker}{\operatorname{Ker}}
\newcommand{\rk}{\operatorname{rk}}

% matan defs
\newcommand{\Int}{\operatorname{Int}}
\newcommand{\Cl}{\operatorname{Cl}}

% tikz
\newcommand\irregularcircle[2]{% radius, irregularity
  \pgfextra {\pgfmathsetmacro\len{(#1)+rand*(#2)}}
  +(0:\len pt)
  \foreach \a in {10,20,...,350}{
    \pgfextra {\pgfmathsetmacro\len{(#1)+rand*(#2)}}
    -- +(\a:\len pt)
  } -- cycle
}

\newcommand*{\colorboxed}{}
\def\colorboxed#1#{%
  \colorboxedAux{#1}%
}
\newcommand*{\colorboxedAux}[3]{%
  % #1: optional argument for color model
  % #2: color specification
  % #3: formula
  \begingroup
    \colorlet{cb@saved}{.}%
    \color#1{#2}%
    \boxed{%
      \color{cb@saved}%
      #3%
    }%
  \endgroup
}

\makeatletter
\newcommand{\inlineitem}[1][]{%
\ifnum\enit@type=\tw@
    {\descriptionlabel{#1}}
  \hspace{\labelsep}%
\else
  \ifnum\enit@type=\z@
       \refstepcounter{\@listctr}\fi
    \quad\@itemlabel\hspace{\labelsep}%
\fi}
\makeatother
\parindent=0pt

\def\inbelow#1#2{\underset{\displaystyle\overset{\displaystyle\rotatebox{270}{$\in$}}{#2}}{#1}}
\def\subsetbelow#1#2{\underset{\displaystyle\overset{\displaystyle\rotatebox{270}{$\subset$}}{#2}}{#1}}
\def\lessbelow#1#2{\underset{\displaystyle\overset{\displaystyle\rotatebox{270}{$\leqslant$}}{#2}}{#1}}
\def\lessabove#1#2{\overset{\displaystyle\underset{\displaystyle\rotatebox{90}{$\leqslant$}}{#2}}{#1}}
\def\stackbelow#1#2{\underset{\displaystyle\overset{\displaystyle\shortparallel}{#2}}{#1}}
\def\stackabove#1#2{\overset{\displaystyle\underset{\displaystyle\shortparallel}{#2}}{#1}}
\def\tobelow#1#2{\underset{\displaystyle\overset{\displaystyle\rotatebox{90}{$\to$}}{#2}}{#1}}

\newcommand{\rom}[1]{\uppercase\expandafter{\romannumeral #1\relax}}
\newcommand{\vardbtilde}[1]{\widetilde{\raisebox{0pt}[0.85\height]{$\widetilde{#1}$}}}
\newcommand\leftcoleqq{\mathrel{\reflectbox{\ensuremath{\coloneqq}}}}

\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}

\definecolor{linkcolor}{HTML}{47528f} % цвет ссылок
\definecolor{urlcolor}{HTML}{47528f} % цвет гиперссылок
\hypersetup{pdfstartview=FitH,  linkcolor=linkcolor,urlcolor=urlcolor, colorlinks=true}
\newcommand{\RomanNumeralCaps}[1]
  {\MakeUppercase{\romannumeral #1}}
\usepackage{titlesec}
\renewcommand{\thesection}{\arabic{section}}
\renewcommand{\listtheoremname}{Определения и теоремы}
\renewcommand\qedsymbol{$\blacksquare$}
\newcommand\oast{\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}}
\makeatletter
\renewenvironment{proof}[1][\proofname]{%
   \par\pushQED{\qed}\normalfont%
   \topsep6\p@\@plus6\p@\relax
   \trivlist\item[\hskip\labelsep\bfseries#1\@addpunct{.}]%
   \ignorespaces
}{%
   \popQED\endtrivlist\@endpefalse
}
\makeatother
%--------------------------------------
\DeclareMathOperator{\Mr}{M_{\mathbb{R}}}
\addtolength{\oddsidemargin}{-.875in}
	\addtolength{\evensidemargin}{-.875in}
	\addtolength{\textwidth}{1.75in}

	\addtolength{\topmargin}{-.875in}
    \addtolength{\textheight}{1.75in}
%--------------------------------------
\def\calloutsym{%
  \ensurestackMath{%
  \scalebox{1.7}{\color{red}\stackunder[0pt]{\bigcirc}{\downarrow}}}%
}
\def\calloutsymup{%
  \ensurestackMath{%
  \scalebox{1.7}{\color{red}\stackon[0pt]{\bigcirc}{\uparrow}}}%
}
\newcommand\callouttext[1]{%
  \def\stacktype{S}\renewcommand\useanchorwidth{T}\stackText%
  \stackunder{\calloutsym}{\scriptsize\Longstack{#1}}\stackMath%
}
\newcommand\callout[3][2.5pt]{%
  \def\stacktype{L}\stackMath\stackunder[#1]{#2}{\callouttext{#3}}%
}
\newcommand\callouttextup[1]{%
  \def\stacktype{S}\renewcommand\useanchorwidth{T}\stackText%
  \stackon{\calloutsymup}{\scriptsize\Longstack{#1}}\stackMath%
}
\newcommand\calloutup[3][1.5pt]{%
  \def\stacktype{L}\stackMath\stackunder[#1]{#2}{\callouttextup{#3}}%
}
\tikzset{
    box1/.style={%
        draw=black, thick,
        rectangle,
        minimum height=2.5cm,
        minimum width=2.5cm
    },
    box2/.style={%
        draw=black, thick,
        rectangle,
        minimum height=2cm,
        minimum width=3cm
    },
    box3/.style={%
        draw=black, dashed,
        rectangle,
        minimum height=2.5cm,
        minimum width=2.5cm
    },
    box4/.style={%
        draw=black, dashed,
        rectangle,
        minimum height=2.15cm,
        minimum width=3.15cm
    },
}

\catcode`@=11
\def\caseswithdelim#1#2{\left#1\,\vcenter{\normalbaselines\m@th
  \ialign{\strut$##\hfil$&\quad##\hfil\crcr#2\crcr}}\right.}% you might like it without the \strut
\catcode`@=12
%
\def\bcases#1{\caseswithdelim[{#1}}
\def\vcases#1{\caseswithdelim|{#1}}
%

\DeclareRobustCommand{\mybox}[2][gray!20]{%
\begin{tcolorbox}[   %% Adjust the following parameters at will.
        breakable,
        left=0pt,
        right=0pt,
        top=0pt,
        bottom=0pt,
        colback=#1,
        colframe=#1,
        width=\dimexpr\textwidth\relax, 
        enlarge left by=0mm,
        boxsep=5pt,
        arc=0pt,outer arc=0pt,
        ]
        #2
\end{tcolorbox}
}

\makeatletter
\newenvironment{sqcases}{%
  \matrix@check\sqcases\env@sqcases
}{%
  \endarray\right.%
}
\def\env@sqcases{%
  \let\@ifnextchar\new@ifnextchar
  \left\lbrack
  \def\arraystretch{1.2}%
  \array{@{}l@{\quad}l@{}}%
}
\makeatother

%%

\begin{document}

\clearpage
%% temporary titles
% command to provide stretchy vertical space in proportion
\newcommand\nbvspace[1][3]{\vspace*{\stretch{#1}}}
% allow some slack to avoid under/overfull boxes
\newcommand\nbstretchyspace{\spaceskip0.5em plus 0.25em minus 0.25em}
% To improve spacing on titlepages
\newcommand{\nbtitlestretch}{\spaceskip0.6em}
\pagestyle{empty}
\begin{center}
\bfseries
\nbvspace[1]
\Huge
{\nbtitlestretch\huge
КОНСПЕКТ ЛЕКЦИЙ ПО ТЕОРЕТИЧЕСКОЙ ИНФОРМАТИКЕ}

\nbvspace[1]
\normalsize

СПбГУ, МКН, СП, 2 курс\\
ЛЕКТОР: ДМИТРИЙ ИЦЫКСОН
\nbvspace[1]
\\
\Large СОСТАВИТЕЛИ:\\[0.5em]
\footnotesize
Андрей \href{https://github.com/K-dizzled}{K-dizzled} Козырев,
Никита  \href{https://github.com/muldrik}{muldrik} Митцев,
Максим \href{https://github.com/maxmartynov08}{maxmartynov08} Мартынов,\\
Семён \href{https://github.com/SmnTin}{SmnTin} Паненков
Иван \href{https://github.com/klimoza}{klimoza} Климов

\nbvspace[2]

\includegraphics[width=3.8in]{./images/TICover.png}
\nbvspace[3]
\normalsize

\large
ОСЕНЬ 2021
\nbvspace[1]
\end{center}
\newpage
\pagestyle{plain}
\fi
%\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                %
%                                %
%        Table of content        %
%                                %
%                                %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\tableofcontents
%\listoftheorem-nons[ignore={lemma},show={conj, theorem-non}]
% To show Table of contents with
% definitions and lemmas
%----------------------------------------
% \listoftheorem-nons[ignoreall,show={lemma}]
% \listoftheorem-nons[ignoreall,show={conj}]
\newpage
\begin{normalsize}
\import{lectures/}{lecture01.tex}
$ $
\import{lectures/}{lecture02.tex}
$ $
\import{lectures/}{lecture03.tex}
$ $
\import{lectures/}{lecture04.tex}
$ $
\import{lectures/}{lecture05.tex}
$ $
\import{lectures/}{lecture06.tex}
$ $
\import{lectures/}{lecture07.tex}
$ $
\import{lectures/}{lecture08.tex}
$ $
\import{lectures/}{lecture09.tex}
$ $
\import{lectures/}{lecture10.tex}
$ $
\import{lectures/}{lecture11.tex}
$ $
\import{lectures/}{lecture12.tex}
$ $
\import{lectures/}{lecture13.tex}
$ $
\import{lectures/}{lecture14.tex}
$ $
\import{lectures/}{lecture15.tex}
$ $
\import{lectures/}{lecture16.tex}
$ $
\end{normalsize}
\end{document}