PAA/main.tex

\documentclass[openany]{book}
\usepackage[T1]{fontenc}
\usepackage{polski}
\usepackage[utf8]{inputenc}
\usepackage[margin=1.25in]{geometry}
\usepackage{alltt}
\usepackage{titling}
\usepackage{pdfpages}
\usepackage{float}
\usepackage{amsmath}
\usepackage{booktabs}
\usepackage{tabularx}
\usepackage{amstext}
\usepackage{tikz}
\usepackage{xspace}
\usepackage{enumerate}
\usepackage{lmodern}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{alphalph}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{wrapfig}
\usepackage[polish]{babel}
\usepackage{braket}
\usepackage{subcaption}
\usepackage{imakeidx}
%\usepackage{showidx}
%\usepackage[bookmarks]{hyperref}
\usepackage{pgfplots}
\makeindex

% opening
\title{Podstawy Analizy Algorytmów dla opornych}
\author{Kacper Donat}

\input{macros.tex}

\begin{document}
%\maketitle
%\tableofcontents

\chapter{Złożoności obliczeniowe}
\input{part-1/intro.tex}
\input{part-1/2018.tex}

\chapter{Problemy w informatyce}
\input{part-2/intro.tex}
\input{part-2/2013.tex}
\input{part-2/2011.tex}
\input{part-2/2018.tex}
\input{part-2/2018.bonus.tex}

\appendix
\input{npc.tex}

\twocolumn
\chapter{Przydatne wzory i twierdzenia}
\section{Sumy wyrażeń} \label{appendix:sum-formulas}
\begin{equation}\label{eqn:sum:1}
    1 + 1 + 1 + \cdots = \sum_{i=1}^n 1 = n
\end{equation}
\begin{equation}\label{eqn:sum:i}
    1 + 2 + 3 + \cdots = \sum_{i=1}^n i = \frac{n(n+1)}{2}
\end{equation}
\begin{equation}\label{eqn:sum:i2}
    1 + 4 + 9 + \cdots = \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}
\end{equation}
\begin{equation}\label{eqn:sum:i3}
    1 + 8 + 27 + \cdots = \sum_{i=1}^n i^3 = \left(\frac{n(n+1)}{2}\right)^2
\end{equation}
\begin{equation}\label{eqn:sum:newton}
    \sum_{i=0}^n {n \choose k} = 2^n
\end{equation}
\begin{equation}\label{eqn:sum:lower-bound}
    \sum_{j=i}^{n} a_j = \sum_{j=1}^n a_j - \sum_{j=1}^{i-1} a_j
\end{equation}

np. dla sumy stałych:
\begin{align}
    \sum_{j=i}^{n} 1 &= \sum_{j=1}^n 1 - \sum_{j=1}^{i-1} 1 = n - (i - 1) \nonumber \\
                     &= n - i + 1
\end{align}

\section{Wzory rekurencyjne}
\subsection{Dziel i zwyciężaj}

Dla funkcji postaci
\begin{equation*}
    T(n) = aT\left(\frac{n}{b}\right) + d(n)
\end{equation*}

\noindent gdzie $d(n)$ jest funkcją multiplikatywną\footnote{tj. spełniającą zależność $f(a \cdot b) = f(a) \cdot f(b)$}, 
wiadomo, że:
\begin{equation} \label{eqn:recursive:divide}
    T(n) = \begin{cases}
        \Theta(n^{\log_b d(b)}) & d(b) > a \\
        \Theta(n^{\log_b a}\log n) & a = d(b) \\
        \Theta(n^{\log_b a})    & a > d(b) \\
    \end{cases}
\end{equation}

\subsection{Jeden krok w tył}
Dla funkcji postaci
\begin{equation*}
    T(n) = aT(n - 1) + d(n) 
\end{equation*}

\noindent wiadomo, że:
\begin{equation} \label{eqn:recursive:1-step}
    T(n) = \begin{cases}
        \Theta(a^n) & d(n) = O(\frac{a^n}{n^\varepsilon}), \varepsilon > 1 \\
        O(na^n)     & d(n) = O(a^n) \\
        O(nd(n))    & d(n) = \omega(a^n) \\
    \end{cases}
\end{equation}

\section{Twierdzenia i własności}
\begin{description}
    \item[tw. Vizinga] Każdy graf można pokolorować krawędziowo $\Delta$ bądź $\Delta + 1$ kolorami. Tj.
        $\chi'(G) = \Delta$ lub $\chi'(G) = \Delta + 1$. \label{theorem:vizing}
    \item[tw. Kuratowskiego] Graf $G$ jest planarny wtedy i tylko wtedy kiedy nie ma w nim podgrafu $K_5$ i $K_3,3$.
        \begin{figure}[H]
            \centering
            \begin{subfigure}[c]{.5\linewidth}
                \centering
                \begin{tikzpicture}[scale=.7]
                    \input{gfx/k5.tex}
                \end{tikzpicture}
                \caption{$K_5$}
            \end{subfigure}%
            \begin{subfigure}[c]{.5\linewidth}
                \centering
                \begin{tikzpicture}[scale=.7]
                    \input{gfx/k3-3.tex}
                \end{tikzpicture}
                \caption{$K_{3,3}$}
            \end{subfigure}%
        \end{figure}
        \label{theorem:kuratowski}
    \item[tw. O 4 kolorach] Każdy graf planarny można pokolorować wierzchołkowo za pomocą $\leq 4$ kolorów. \label{theorem:4-colors}
    \item[lemat o uściskach dłoni] Suma stopni wierzchołków w grafie zawsze jest liczbą parzystą. \label{theorem:handshake}
    \item[Graf Eulerowski] Graf jest Eulerowski wtedy i tylko wtedy gdy wszystkie wierzchołki są stopnia parzystego. \label{theorem:euler}
    \item[tw. Brooksa] Jeżeli graf jest pełny bądź jest cyklem nieparzystym to $\chi(G) = \Delta + 1$, w innym wypadku 
        $\chi(G) \leq \Delta$ \label{theorem:brooks}
    \item Dla każdego grafu $G$ zachodzi $\chi(G) \leq \omega(G)$ gdzie $\omega(G)$ oznacza największą klikę w grafie.
    \item Każdy graf dwudzielny da się pokolorować dwoma kolorami. Dodatkowo - każde drzewo jest grafem dwudzielnym.
\end{description}

\end{document}