\documentclass[11pt,oneside,a4paper]{article}
\usepackage[margin=2cm]{geometry}
\usepackage{fancyhdr}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{graphicx}
\usepackage{hyperref}

\usepackage{mathtext}
\usepackage[T1,T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,bulgarian]{babel}
\usepackage{setspace}
\usepackage{verbatim}

%\usepackage{array}

%\usepackage[chapter]{algorithm}
%\usepackage[noend]{algpseudocode}
%\usepackage{float}
%\floatname{algorithm}{Алгоритъм}

%\usepackage{myalg}

\setlength{\parindent}{10pt} 
\setlength{\parskip}{1ex}

\begin{document}

\paragraph{Тема 1 a} 
Дефинирайте релация и релация на еквивалентност. 
Докажете, че всяка релация на еквивалентност разбива областта си на класовете на еквивалентност.

\paragraph{Тема 1 b} Докажете, че неориентиран граф е свързан, точно когато има покриващо дърво.

\vspace{25ex}

\paragraph{Тема 2 a} 
Дефинирайте крайно, безкрайно и изброимо множество.
Докажете, че съществува безкрайно множество, което не е изброимо.

%няма биекция $f: \mathbb{N} \to 2^\mathbb{N}$. Твърдението е известно като \emph{Диагонален метод на Кантор}.

\paragraph{Тема 2 b} Докажете, че е вярна следната формула на Нютон:
\[ (x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k \]

\vspace{24ex}

\paragraph{Тема 3 a} 
%Докажете, че има биекция $f: \mathbb{N} \to \mathbb{N} \times \mathbb{N}$.
Докажете, че декартовото произведение на две изброими безкрайни множества е изброимо.


\paragraph{Тема 3 b} Докажете, че всяка булева функция може да се представи като формула над елементарните функции отрицание, конюнкция и дизюнкция. Твърдението е известно като \emph{Теорема на Бул}.

\vspace{25ex}

\paragraph{Тема 4 a} Дайте дефиниция на крайна и безкрайна редица. 
Дефинирайте крайно, безкрайно и изброимо множество.
Формулирайте принципа на Дирихле.

\paragraph{Тема 4 b} Докажете, че всяка булева функция може да се представи по единствен начин чрез полином на Жегалкин.
%\end{document}

\newpage

\paragraph{Тема 5 a} Дефинирайте частична наредба, верига и контур в релация. 
Докажете, че една рефлексивна и транзитивна релация е частична наредба точно когато не съдържа контури.

\paragraph{Тема 5 b} Дефинирайте функциите $n!$ и $\binom{n}{k}$. \\
Нека $A$ и $B$ са крайни множества и $|A|=n, |B|=m$.\\
Изведете формули за броя на функциите $f: A \to B$, при допълнително изискване:\\
(a) $f$ е тотална.\\
(b) $f$ е частична.\\
(c) $f$ е инекция.\\

\vspace{15ex}

\paragraph{Тема 6 a} Дефинирайте минимален и максимален елемент в частична наредба.
Докажете, че всяка крайна частична наредба може да се разшири до пълна.

\paragraph{Тема 6 b} Дефинирайте понятията импликанта и проста импликанта. 
Дайте пример на булева функция на 3 променливи, която има 4 единици в табличното си изписване,
такава че минималната й ДНФ съвпада със СъвДНФ.

\vspace{20ex}

\paragraph{Тема 7 a} Докажете, че няма биекция $f: \mathbb{N} \to 2^\mathbb{N}$. Твърдението е известно като \emph{Диагонален метод на Кантор}.

\paragraph{Тема 7 b} Дефинирайте графа на n-мерния хиперкуб. 
Дайте обоснован отговор на въпросите:\\
(a) За кои стойности на $n$ в този граф има хамилтонов цикъл?\\
(b) За кои $n$ в графа има ойлеров цикъл?

\vspace{20ex}

\paragraph{Тема 8 a} Докажете, че има биекция $f: \mathbb{N} \to \mathbb{N} \times \mathbb{N}$.

\paragraph{Тема 8 b} Опишете задачите, които решават алгоритмите на Прим и Дейкстра.
Посочете прилики и разлики между тия задачи и между съответните алгоритми.

\newpage

\paragraph{Тема 9 a} 
Дефинирайте релация на частична наредба. 
Дефинирайте понятието път в граф.
Разгледайте релацията 'има път от връх $u$ до връх $v$'.
Кога тази релация е частична наредба и кога е релация на еквивалентност?

\paragraph{Тема 9 b} Дефинирайте графа на n-мерния хиперкуб. 
Дайте обоснован отговор на въпросите:\\
(a) За кои стойности на $n$ в този граф има хамилтонов цикъл?\\
(b) За кои $n$ графът е двуделен?


\vspace{20ex}

\paragraph{Тема 10 a} 
%Дефинирайте крайно, безкрайно и изброимо множество.
Докажете, че няма биекция $f: A \to 2^A$ за произволно множество $A$. 
Твърдението е известно като \emph{Диагонален метод на Кантор}.

\paragraph{Тема 10 b} 
Изведете формула за броя на редиците от естествени числа $x_1,x_2,\ldots,x_k$, 
за които $\displaystyle\sum_{i=1}^{k}x_i=n$ и $x_i\ge 0$.


\vspace{24ex}

\paragraph{Тема 11 a} 
%Докажете, че има биекция $f: \mathbb{N} \to \mathbb{N} \times \mathbb{N}$.
Докажете, че декартовото произведение на две изброими безкрайни множества е изброимо.


\paragraph{Тема 11 b} 
Дефинирайте понятието 'свързана компонента' в неориентиран граф.
Дефинирайте понятието 'силно свързана компонента' в ориентиран граф.


\vspace{25ex}

\paragraph{Тема 12 a} Докажете теоремата на Ойлер, описваща необходимите и достатъчни условия за съществуване на ойлеров цикъл в граф.

\paragraph{Тема 12 b} Формулирайте принципа на Дирихле. Формулирайте принципа за включване и изключване.
%Предложете доказателство.

\end{document}

\newpage

\paragraph{Тема Rel$_1$} 
Дефинирайте релация и релация на еквивалентност. 
Докажете, че всяка релация на еквивалентност разбива областта си на класовете на еквивалентност.

\paragraph{Тема Fun$_1$} Докажете, че няма биекция $f: \mathbb{N} \to 2^\mathbb{N}$. Твърдението е известно като \emph{Диагонален метод на Кантор}.


\paragraph{Тема Fun$_2$} Докажете, че има биекция $f: \mathbb{N} \to \mathbb{N} \times \mathbb{N}$.

\paragraph{Тема Fun$_3$} Дайте дефиниция на крайна и безкрайна редица. 
Дефинирайте крайно, безкрайно и изброимо множество.
Формулирайте принципа на Дирихле.

\paragraph{Тема Rel$_2$} Дефинирайте частична наредба, верига и контур в релация. 
Докажете, че една рефлексивна и транзитивна релация е частична наредба точно когато не съдържа контури.

\paragraph{Тема Rel$_3$} Дефинирайте минимален и максимален елемент в частична наредба.
Докажете, че всяка крайна частична наредба може да се разшири до пълна.

\paragraph{Тема Comb$_1$} Докажете, че е вярна следната формула на Нютон:
\[ (x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k \]

\paragraph{Тема Comb$_2$} Дефинирайте функциите $n!$ и $\binom{n}{k}$. \\
Нека $A$ и $B$ са крайни множества и $|A|=n, |B|=m$.\\
Изведете формули за броя на функциите $f: A \to B$, при допълнително изискване:\\
(a) $f$ е тотална.\\
(b) $f$ е частична.\\
(c) $f$ е инекция.\\

\paragraph{Тема Graph$_1$} Докажете, че неориентиран граф е свързан, точно когато има покриващо дърво.

\paragraph{Тема Graph$_2$} Докажете теоремата на Ойлер, описваща необходимите и достатъчни условия за съществуване на ойлеров цикъл в граф.

\paragraph{Тема Graph$_3$} Дефинирайте графа на n-мерния хиперкуб. 
Дайте обоснован отговор на въпросите:\\
(a) За кои стойности на $n$ в този граф има хамилтонов цикъл?\\
(b) За кои $n$ в графа има ойлеров цикъл?

\paragraph{Тема Graph$_4$} Опишете задачите, които решават алгоритмите на Прим и Дейкстра.
Посочете прилики и разлики между тия задачи и между съответните алгоритми.

\paragraph{Тема Graph$_5$} 
Дефинирайте понятието 'свързана компонента' в неориентиран граф.
Дефинирайте понятието 'силно свързана компонента' в ориентиран граф.

\paragraph{Тема Bool$_1$} Докажете, че всяка булева функция може да се представи като формула над елементарните функции отрицание, конюнкция и дизюнкция. Твърдението е известно като \emph{Теорема на Бул}.

\paragraph{Тема Bool$_2$} Докажете, че всяка булева функция може да се представи по единствен начин чрез полином на Жегалкин.

\paragraph{Тема Bool$_3$} Дефинирайте понятията импликанта и проста импликанта. 
Дайте пример на булева функция на 3 променливи, която има 4 единици в табличното си изписване,
такава че минималната й ДНФ съвпада със СъвДНФ.


\end{document}