 \lstset
    {
    language=C++,
    frame=,
    framesep=8pt,
    backgroundcolor=\color{VeryLightGray},
    basicstyle=\small,
    keywordstyle=\ttfamily\color{DarkGray}\bfseries,
    identifierstyle=\rmfamily \color{RealGray},
    commentstyle=\rmfamily\color{LightGray}\itshape,
    stringstyle=\rmfamily\color{RealGray},
    showstringspaces=false,
    escapechar=\#,
    morekeywords={uint},
%    numbers=left,                   % where to put the line-numbers
%    numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
%    stepnumber=2,                   % the step between two line-numbers. If it's 1 each line will be numbered
%    numbersep=5pt                  % how fare the line-numbers are from the code
    }

\chapter{Minimalizace logických funkcí}%
\label{kap_minimalizace}%
Jak už bylo řečeno v Úvodu, minimalizace logických funkcí je základním krokem v
návrhu každého logického obvodu. Proto je této oblasti výzkumu věnována poměrně
slušná pozornost.\\

\noindent V této kapitole budou nejdříve připomenuty klasické metody
minimalizace a potom bude zvýšený zájem věnován minimalizaci neúplně určených
logických funkcí pomocí MBD. Závěrem bude provedeno srovnání klasických způsobů
minimalizace s metodou prováděnou na MBD. Ještě jednou je vhodné připomenout,
že pojmem logická funkce se zde myslí disjunktivní normální forma (součin
termů). Ta je jak vstupem pro minimalizaci, tak i jejím výstupem. Jedním dechem
je dobré doplnit, že zminimalizovaný DNF zápis logické funkce nemusí vést
k~nejúspornější fyzické realizaci logického obvodu.

\section{Klasické způsoby minimalizace}%
Prakticky všechny minimalizační metody pracují ve dvou hlavních krocích:
\begin{enumerate}%
    \item Nalezení množiny přímých
    implikantů\footnote{více o přímých implikantech v kapitole
    \ref{kap_uvod}}.
    \item Výběr minimálního počtu přímých implikantů
    nutných pro úplné pokrytí logické funkce.
\end{enumerate}%
\noindent Ať už jednotlivé metody pracují jakýmkoliv způsobem, vždy jde o to
nalézt co nejméně nejmenších přímých implikantů.

\subsection{Minimalizace pomocí Booleovy algebry}%
Tento způsob je vlastně uplatněním základních Boolevých zákonů na funkci
zapsanou pomocí logického výrazu. Nejlépe celý postup představí menší příklad:

\noindent Je zadána funkce:
\begin{center}
$f = x_0x_2\bar{x_3}+\bar{x_0}x_1x_2+\bar{x_2}x_3+x_2x_3$.%
\end{center}
Uplatněním zákona sporu ($ab+\bar{a}b=b$) se upraví dva poslední členy:
\begin{center}
$f = x_0x_2\bar{x_3}+\bar{x_0}x_1x_2+x_3$.
\end{center}
Uplatněním zákona absorbce negace ($a+\bar{a}b=a+b$) se zpracuje první a třetí
člen:
\begin{center}
$f = x_0x_2+\bar{x_0}x_1x_2+x_3$.
\end{center}
\noindent Pomocí distributivního zákona lze z prvních dvou členů vytknout $x_2$
a následně obsah závorky zredukovat užitím zákona absorbce negace:
\begin{center}
$f = (x_0+\bar{x_0}x_1)x_2+x_3 = (x_0+x_1)x_2+x_3$.%
\end{center}
Po roznásobení závorky vznikne konečná minimalizovaná podoba funkce:
\begin{center}
$f = x_0x_2+x_1x_2+x_3$.
\end{center}

\noindent Tento způsob je sice poměrně elegantní, ale není příliš systematický
a nehodí se pro automa-tické zpracování nějakým počítačovým programem.

\subsection{Minimalizace s využitím map}%
Metoda map je poměrně intuitivní grafický přístup, kdy se funkce zapíše do
mapy. Příklad Karnaughovy mapy a minimalizace je na
obrázku~\ref{karnmap_example}. Přímé implikanty se zde vyskytují v~podobě
smyček - účelem je najít co nejmenší počet co největších smyček.\\
\indent Tato metoda je nevhodná pro automatické zpracování a při manuálním
výpočtu začíná být silně nepřehledná od sedmi a více proměnných.

\bfig
    \includegraphics[height=6cm]{img/karn-example.png}
    \caption[Karnaughova mapa logické funkce]{\textbf{Karnaughova mapa logické funkce}
    $f=\bar{x_0}\bar{x_1}\bar{x_2}x_3+\bar{x_0}x_1\bar{x_2}x_3+x_0x_1\bar{x_2}x_3+x_0\bar{x_1}\bar{x_2}x_3
    +\bar{x_0}\bar{x_1}x_2x_3+\bar{x_0}x_1x_2x_3+x_0x_1x_2x_3+x_0\bar{x_1}x_2x_3
    +\bar{x_0}x_1x_2\bar{x_3}+x_0x_1x_2\bar{x_3}+x_0\bar{x_1}x_2\bar{x_3}$.
    Smyčky vybraných přímých implikantů jsou zvýrazněny přerušovanou čarou. Výsledná minimalizovaná
    funkce má tvar $f_{min}=x_3+x_0x_2+x_1x_2$.}
    \label{karnmap_example}
\efig

\subsection{Systematické minimalizace}%
Předchozí metody mohou vypadat elegantně, ovšem ve skutečnosti nejsou příliš
použitelné - nejsou totiž systematické. Za \emph{systematické metody} lze
považovat pouze takové postupy, které pracují přesně podle předem určeného
algoritmu a nespoléhají na dobrý zrak, zkušenosti a~intuici toho, kdo provádí
minimalizaci. Jiný slovy jde o metody, které lze relativně snadno převést do
počítačové podoby.
\paragraph{Metoda Quine-McCluskey} Jde o první systematickou metodu,
která sice není tak elegantní jako mapy, ale za to může pracovat s více
proměnnými. Její velkou výhodou je, že vždy nalezne \emph{přesné}
řešení tj. nejmenší možnou funkci. Na druhé straně je poměrně časově~náročná.\\

\noindent Metoda Quine-McCluskey pracuje takto:
\begin{enumerate}
    \item Nejdříve nalezne množinu přímých implikantů.
    \item Z nich pomocí tzv. \emph{tabulky pokrytí} vybere takové, aby jich byl co
    nejnižší
počet.%
\end{enumerate}%
\noindent Ačkoliv je tato metoda poměrně dobře zpracovatelná na
počítači\footnote{Ostatně k tomuto účelu byla i navržena.}, jde o NP-Těžký
problém \cite{wk_qm}, což ji velmi limituje.%
\paragraph{Heuristika ESPRESSO}%
Jestliže je exaktní metoda špatně použitelná, pak musí dostat slovo heuristický
přístup. Zřejmě nejúspěšnější minimalizační heuristikou je algoritmus nazvaný
ESPRESSO, který byl vyvinutý ve spolupráci firmy IBM a univerzity v Berkeley v
80. letech minulého století. Jako každá heuristika nemá za cíl nalézt nejlepší
možné řešení, ale alespoň nějaké \emph{dobré} či \emph{vyhovující}. ESPRESSO je
určeno pro počítačové zpracování, a tak není příliš vhodné pro
manuální minimalizaci.\\

\noindent Algoritmus pracuje při minimalizaci funkce $f$ ve třech základních
krocích:
\begin{enumerate}%
    \item Nejdříve se vytvoří nějaké (náhodné) pokrytí
    funkce $f$ z několika vybraných (náhodně) přímých implikantů.
    \item Toto pokrytí je pak \emph{nějak} upraveno a následně zredukováno na minimální
    počet přímých implikantů.
    \item Uloží se nejlepší nalezené pokrytí $f$ a pokračuje se znovu v bodu 1, je-li
    potřeba.
\end{enumerate}%
\noindent Kouzlo metody ESPRESSO spočívá v tom, co činí ve druhém bodu
algoritmu. \emph{Úprava} daného pokrytí sestává ze tří kroků:
\begin{enumerate}%
    \item \textbf{Redukce} původního pokrytí.
    \item \textbf{Expanze} pokrytí vytvořeného v bodu 1.
    \item \textbf{Nalezení} minimálního počtu \textbf{přímých implikantů}.
\end{enumerate}
\noindent Celý algoritmus lépe popisuje obrázek \ref{espresso_example}.
Pochopitelně, že tato hrubá kostra algoritmu ESPRESSO nemůže stačit na jeho
úplné pochopení\footnote{Za Redukcí a Expanzí se skrývá řada dalších zajímavých
postupů.}, nicméně jako úvod do moderního způsobu minimalizace by předchozí
řádky stačit měly. Vzhledem k tomu, že ESPRESSO hraje významnou úlohu i v celé
této práci, byla zmínka o něm nezbytná.

\section{Minimalizace pomocí MBD}%
MBD je jen jedním ze způsobů zápisu logické funkce, tudíž i minimalizace
prováděná na něm se svým základním postupem neliší od ostatních metod. To bude
detailněji popsáno na dalších řádcích. Tento přístup je jemně upravenou
variantou metody popsané v \cite{Jac93}.

\bfig
    \includegraphics[height=5.5cm]{img/esp-1.png}\hskip 50pt
    \includegraphics[height=5.5cm]{img/esp-2.png}\\[20pt]
    \includegraphics[height=5.5cm]{img/esp-3.png}\hskip 50pt
    \includegraphics[height=5.5cm]{img/esp-4.png}

    \caption[Základní kroky heuristiky ESPRESSO.]{
    \textbf{Základní kroky heuristiky ESPRESSO.}~Obrázek $a)$ popisuje
    počáteční množinu přímých implikantů. $b)$ ukazuje redukci přímých
    implikantů, při níž nemusí nutně vzniknout \emph{přímé} implikanty,
    nýbrž jen implikanty. $c)$ předvádí expanzi implikantů na přímé
    implikanty. $d)$ zobrazuje výběr minimální množiny přímých implikantů.
    }
    \label{espresso_example}
\efig

\subsection{Využití struktury MBD pro minimalizaci}%
Pokud chceme z MBD dostat zpět množinu termů ($f_{on}$, $ONset$), potom musíme
procházet MBD od terminálního uzlu s hodnotou $1$ do kořene. Všechny cesty,
které projdeme, představují jednotlivé termy.\\
\indent V každém uzlu, kterým se v cestě za kořenem procházíme, se provádí
zpětná verze Shanno-nova expanzního teorému\footnote{tj. syntéza a nikoliv
rozklad}:%
\begin{center}%
$f_u = x_u.f_{high} + \bar{x_u}.f_{low}$,
\end{center}%
kde $x_u$ je proměnná, které patří uzel $u$, a funkce $f_{low}$ a $f_{high}$
jsou získané z podgrafů $high(u)$ a $low(u)$.\\
\indent Tomuto postupu se říká \emph{algebraické procházení MBD}. Bohužel to
však nemá nic společného s minimalizací, jelikož takto vzniklý logický výraz má
často více termů a literálů než ten původní, ze kterého MBD vzniklo\footnote{na
vině je opět \emph{partitioning} - viz kapitola \ref{kap_razeni}}. Aby při
posledním spojení v kořenu vznikla minimalizovaná funkce, je nutné procházet
jej booleovským způsobem - tj. v každém uzlu provádět navíc \emph{booleovskou
minimalizaci} funkce $f_u$. Tento postup dokumentuje obrázek~\ref{mbd_min}. To,
jaká minimalizace se provádí, je věcí volby. V tomto projektu byl použit
externí minimalizátor ESPRESSO, který se volá v každém uzlu pro funkce
$f_u$.\\
\indent Důvodem, proč je použito ESPRESSO a nikoliv vlastní minimalizátor, je
několik. ESPRESSO je vyzkoušený kvalitní algoritmus, který by se jen těžko
podařilo překonat, navíc by práce na vlastním, byť jednoduchém, minimalizátoru
silně přesáhla rámec tohoto projektu. Pochopitelně, že volání externího
programu v programu s časovou složitostí $O(2^n)$\footnote{Počet uzlů může být
$O(2^n)$, ovšem v reálných situacích je mnohem menší.} není nijak opti-mální,
nicméně pokud je nutné prozkoumat skutečné možnosti využití MBD při
minimali-zaci logických funkcí, nebyla jiná cesta možná. Samotné ESPRESSO navíc
posloužilo jako srovnávací program, s jehož výsledky byly porovnávány výsledky
minimalizace dosažené pomocí MBD.

\bfig
    \includegraphics[height=7cm]{img/mbd-min.png}
    \caption[Minimalizace s MBD]{ \textbf{Minimalizace s MBD.}~%
    Booleovské generování termů - procházejí se všechny cesty od terminálu $1$ do
    kořene a v každém uzlu se provádí booleovská minimalizace. Logické výrazy
    vedle uzlů ukazují minimalizovaný logický výraz pro daný podstrom.
    \textcolor{my_red}{Červené} šipky znázorňují směr průchodu MBD.
    }
    \label{mbd_min}
\efig

\subsection{Využití DCsetu při minimalizaci}%
Stejně jako u jiných způsobů zápisu logické funkce, tak i u MBD představuje
DCset užitečnou doplňující informaci, kterou je možné použít například při
minimalizaci. Při minimalizaci pomocí map se DCsetu využívá k vytváření větších
smyček, a tím pádem i menších konečných funkcí \cite{Jan01}. U MBD se
neurčených výstupů využívá podobně, ovšem s přihlédnutím ke specifickým vlastnostem MBD.\\
\indent Stručně řečeno, všechny uzly, které vedou do terminálního uzlu s
hodnotou $X$ (don't care), je možné odstranit, a tím zmenšit velikost celého
MBD a přispět k celkově menší funkci. Odstranění uzlu spočívá v tom, že se
hrana, která vede do $X$, přesměruje do jiného uzlu tak, aby se původní uzel
stal redundantní. Hranu uzlu $u$ vedoucí do $X$ je možné přesměrovat dvěma
způsoby (viz obrázek \ref{mbd_x_change}):%
\begin{itemize}%
    \item Přesměrovat ji do stejného uzlu, do kterého vede druhá hrana uzlu $u$
    (vede-li $high(u)$ to $X$, pak se přesměruje do stejného uzlu jako hrana
    $low(u)$ nebo naopak). Tím, že obě hrany uzlu povedou do jednoho uzlu,
    stane se uzel $u$ redundantním a je možné ho odstranit z~MBD.
    \item Přesměrovat ji do jiného uzlu tak, aby z uzlu $u$ vznikl uzel,
    který se už v MBD vyskytuje, čímž by se jeden z nich stal zbytečným.
\end{itemize}%

\bfig
    \includegraphics[height=7cm]{img/mbd-x-change.png}
    \caption[Možnosti přesměrování hran vedoucích do $X$]{
    \textbf{Možnosti přesměrování hran vedoucích do $X$.}
    \textcolor{my_red}{Červená} hrana
    naznačuje možnost přesměrování hrany \emph{high} do uzlu,
    kam vede hrana \emph{low}. \textcolor{my_green}{Zelená}
    hrana naznačuje přesměrování do jiného
    uzlu tak, aby vznikl stejný uzel, jaký v MBD už existuje.}
    \label{mbd_x_change}
\efig

\noindent Ať se zvolí jakákoliv z těchto možností, vždy z MBD ubude alespoň
jeden uzel. Není to málo, ale každá taková změna může dát vzniknout dalším
redundantním uzlům. Vážnou otázkou tedy je, jaký krok v daném uzlu
učinit\footnote{Samozřejmě, že v MBD jsou také uzly, u nichž je možné provést
jen první způsob nahrazení $X$, jelikož v MBD neexistuje uzel, na který by šlo
původní uzel převést. Na druhé straně může být v MBD několik uzlů, které je
možné převést původní uzel, a pak je znovu složitější si některou z možností
vybrat.}. Bohužel, neexistuje žádná metoda, jež by dokázala zjistit, která
náhrada bude mít větší dopad na velikost MBD. Jedinou možností, jak se dostat k
nejlepšímu možnému výsledku, je vyzkoušet všechny možné náhrady. Problém však
je, že počet všech kombinací má faktoriální charakter, což není příliš vhodné
pro běžné použití.\\
\indent Úkolem této práce nebylo nalézt metodu vhodnou pro výběr náhrady za
hranu vedoucí do $X$, nýbrž prozkoumat možnosti, které tyto náhrady skýtají.
Více o tomto tématu prozradí výsledky experimentů, které jsou prezentovány v
kapitole \ref{kap_experimenty}.



%\newpage
%\section{Experimenty}%
%V tomto oddíle jsou prezentovány výsledky testů týkajících se minimalizace
%logický funkcí. První experiment se zabývá problémem nahrazování DCsetu a druhý
%komplexní minimalizací pomocí MBD.
%
%\btab%
%\caption[Experiment - nahrazování hran vedoucích od uzlu s hodnotu $X$]%
%{\textbf{Experiment - nahrazování hran vedoucích od uzlu s hodnotu $X$.}%
%Pro každou logickou funkci zapsanou v \emph{pla} souboru byly měřeny tři různé
%hodnoty. Ve sloupci \emph{Normal} je uveden počet uzlů MBD po jeho načtení a
%redukci. Sloupec \emph{Brother} uvádí výsledný počet uzlů MBD po přesměrování
%hran vedoucích do $X$ do stejných uzlů, do kterých vedla druhá hrana uzlu.
%Poslední sloupec \emph{Random} uvádí výslednou velikost MBD, pokud byly hrany
%vedoucí do $X$ do náhodně vybraného uzlu (jen do takového uzlu, aby vznikla
%nějaká redundance). Výsledky ve sloupci \emph{Random} jsou průměrnou hodnotu
%získanou z padesáti různých měření. }
%
%\label{dc_subst_tab} \vskip 20pt%
%\begin{tabular}{rcrrr}%
%    \toprule
%    \ttc{Soubor} & X par & Normal & Random & Brother\\
%    \midrule
%%    5i-1o-20t-15dc-20odc.pla & 14 & 3 & 3\\
%%    8i-1o-40t-5dc-20odc.pla & 67 & 50 & 50\\
%%    8i-1o-40t-5dc-50odc.pla & 63 & 37 & 37\\
%%    16i-1o-100t-5dc-20odc.pla & 600 & 464 & 464\\
%%    16i-1o-100t-5dc-50odc.pla & 596 & 362 & 362\\
%%    20i-1o-200t-5dc-50odc.pla & 1642 & 933 & 933\\
%%    20i-1o-200t-5dc-10odc.pla & 1570 & 1373 & 1373\\
%    5i-1o-20t-15dc-20odc.pla & 4 & 14 & 7 & 3\\
%    8i-1o-40t-5dc-20odc.pla & 3 & 67 & 54 & 50\\
%    8i-1o-40t-5dc-50odc.pla & 3 & 63 & 37 & 37\\
%    10i-1o-50t-0dc-20odc.pla & 2 & 109 & 95 & 95\\
%    10i-1o-100t-0dc-50odc.pla & 4 & 160 & 120 & 102\\
%    16i-1o-100t-5dc-20odc.pla & 5 & 600 & 486 & 464\\
%    16i-1o-100t-5dc-50odc.pla & 2 & 596 & 397 & 362\\
%    20i-1o-200t-5dc-50odc.pla & 4 & 1642 & 1061 & 933\\
%    20i-1o-200t-5dc-10odc.pla & 4 & 1570 & 1394 & 1373\\
%    20i-1o-300t-15dc-20odc.pla & 5 & 2985 & 2576 & 2483\\
%    30i-1o-200t-0dc-20odc.pla & 2 & 3334 & 2765 & 2615\\
%    30i-1o-300t-0dc-20odc.pla & 2 & 4617 & 3945 & 3765\\
%    40i-1o-200t-0dc-20odc.pla & 2 & 5297 & 4358 & 4240\\
%    40i-1o-300t-0dc-20odc.pla & 2 & 7681 & 6438 & 6183\\
%    \bottomrule%
%\end{tabular}%
%\etab
%
%\subsection{Minimalizace pomocí DCsetu}%
%Jak bylo napsáno už dříve v této kapitole, při přesměrovávání hran vedoucích do
%terminálního uzlu s hodnotou $X$m je možné si vybrat, zda bude hrana
%přesměrována do stejného uzlu jako její bratská hrana, nebo jiného uzlu tak,
%aby v MBD vznikly dva stejné uzly. Účelem této operace je vytvoření jednoho
%nebo více redundantních uzlů, které by bylo možné odstranit.\\
%\indent Účelem tohoto experimentu bylo zjistit, zda je výhodnější přesměrovávat
%hranu vedoucí do $X$ spíše do uzlu, do něhož vede její bratrská hrana ($1$)
%nebo do jiného uzlu ($2$). Důležité je připomenout, že u každého uzlu s hranou
%vedoucí do $X$ je možné použít přesměrování typu $1$, vedle toho však může
%existovat více možností přesměrování $2$, ale také nemusí existovat vůbec
%žádná.\\
%
%\noindent Experiment, jehož výsledky prezentuje tabulka \ref{dc_subst_tab}
%jasně ukazuje, že je prakticky \emph{lhostejné} jaká substituce hrany vedoucí
%do $X$ bude použita. Výsledky při použití metody $1$ i metody $2$ jsou naprosto
%shodné - výsledný MBD měl po libovolné substituci vždy naprosto stejný počet
%uzlů.\\
%\indent Tento poměrně zajímavý závěr říká, že ve MBD, který je pochopitelně už
%redukovaný, po výměně $X$ vznikají další redundance velmi těžko. Odstraní se
%vždy jeden uzel, který se dané substitucí stal redundantní, ale \emph{vznik
%dalších redundancí je velmi nepravděpodobný}, byť ne nemožný.
%
%\subsection{Celková minimalizace pomocí MBD}%
%Schéma experimentů v této kapitole je velmi jednoduché. Byla testována účinnost
%dříve vysvětlené minimalizace pomocí MBD, která byla porovnána s výsledky, jež
%dosáhl samotný algoritmus ESPRESSO.\\
%\indent Veličinami, jimiž byla kvalita minimalizace měřena je celkový počet
%termů a celkový počet literálů ve všech termech zminimalizované funkce.
%Výsledky toho experimentu jsou zobrazeny v tabulce \ref{mbd_min_exp}.\\
%
%\noindent Dosažené výsledky pomocí metody založené na MBD jsou prakticky
%totožné s těmi, které dosáhl program implementující algoritmus ESPRESSO. To
%není až tolik překvapivé, protože i MBD metoda pracuje s tímto minimalizátorem
%také. U dvou funkcí dosáhl MBD minimalizátor lepšího výsledku než ESPRESSO - v
%obou případech měl o jeden literál méně než ESPRESSO (v tabulce zvýrazněno
%tučným písmem).
%
%
%\btab%
%\caption[Minimalizace pomocí MBD]{\textbf{Minimalizace pomocí
%MBD.} Sloupec \emph{Normal} udává počet literálů a termů v původním
%PLA souboru. Sloupec \emph{ESPRESSO} ukazuje výsledky, které dosáhl
%minimalizátor založený na algoritmu ESPRESSO. Poslední sloupec
%\emph{MBD} seznamuje s výsledky dosaženými pomocí metody používající
%MBD.}%
%\label{mbd_min_exp} \vskip 20pt%
%\begin{tabular}{crrrrrrr}%
%\toprule
%\multirow{2}{*}{Soubor} & \multicolumn{3}{c}{Normal} & \multicolumn{2}{c}{ESPRESSO} & \multicolumn{2}{c}{MBD}\\
%\cmidrule{2-8}
%    & Literály & Termy & $|f_{dc}|$ & Literály & Termy & Literály & Termy\\
%\midrule
%%\ttr{5i-1o-20t-15dc-20odc.pla} & 86 & 20 & 4 & 1 & \textbf{3} & 1\\
%%\ttr{8i-1o-40t-5dc-20odc.pla} & 304 & 40 & 131 & 19 & \textbf{130} & 19\\
%%\ttr{8i-1o-40t-5dc-50odc.pla} & 307 & 40 & 113 & 15 & 113 & 15\\
%%\ttr{16i-1o-100t-5dc-20odc.pla} & 1520 & 100 & 1190 & 78 & 1190 & 78\\
%%\ttr{10i-1o-100t-0dc.pla} & 1000 & 100 & 691 & 72 & 691 & 72\\
%%\ttr{10i-1o-100t-20dc.pla} & 781 & 100 & 495 & 71 & 495 & 71\\
%%\ttr{10i-1o-100t-30dc.pla} & 682 & 100 & 349 & 62 & 349 & 62\\
%%\ttr{20i-1o-200t-0dc.pla} & 4000 & 200 & 3979 & 199 & 3979 & 199\\
%%\ttr{20i-1o-200t-20dc.pla} & 3166 & 200 & 3166 & 200 & 3166 & 200\\
%%\ttr{30i-1o-300t-0dc.pla} & 9000 & 300 & 9000 & 300 & 9000 & 300\\
%
%\ttr{5i-1o-20t-15dc-20odc.pla} & 86 & 20 & 5 & 4 & 1 & 3 & 1\\
%\ttr{8i-1o-40t-5dc-20odc.pla} & 304 & 40 & 9 & 131 & 19 & 130 & 19\\
%\ttr{8i-1o-40t-5dc-50odc.pla} & 307 & 40 & 23 & 113 & 15 & 113 & 15\\
%\ttr{10i-1o-50t-0dc-20odc.pla} & 500 & 50 & 5 & 329 & 34 & 328 & 34\\
%\ttr{10i-1o-100t-0dc-50odc.pla} & 1000 & 100 & 49 & 393 & 40 & 390 & 40\\
%\ttr{16i-1o-100t-5dc-20odc.pla} & 1520 & 100 & 22 & 1190 & 78 & 1190 & 78\\
%\ttr{30i-1o-200t-0dc-20odc.pla} & 6000 & 200 & 42 & 4740 & 158 & 4740 & 158\\
%\ttr{40i-1o-200t-0dc-20odc.pla} & 8000 & 200 & 39 & 6440 & 161 & 6440 & 161\\
%\ttr{6i-1o-10t-10dc.pla} & 54 & 10 & 0 & 33 & 7 & 33 & 7\\
%\ttr{10i-1o-100t-0dc.pla} & 1000 & 100 & 0 & 691 & 72 & 691 & 72\\
%\ttr{10i-1o-100t-20dc.pla} & 781 & 100 & 0 & 495 & 71 & 495 & 71\\
%\ttr{10i-1o-100t-30dc.pla} & 682 & 100 & 0 & 349 & 62 & 349 & 62\\
%\ttr{12i-1o-80t-30dc.pla} & 656 & 80 & 0 & 565 & 73 & 565 & 73\\
%\ttr{12i-1o-100t-10dc.pla} & 1078 & 100 & 0 & 984 & 94 & 984 & 94\\
%\ttr{15i-1o-100t-10dc.pla} & 1345 & 100 & 0 & 1344 & 100 & 1344 & 100\\
%\ttr{15i-1o-200t-25dc.pla} & 2246 & 200 & 0 & 2171 & 196 & 2171 & 196\\
%\ttr{18i-1o-200t-25dc.pla} & 2719 & 200 & 0 & 2687 & 198 & 2687 & 198\\
%\ttr{18i-1o-200t-0dc.pla} & 3600 & 200 & 0 & 3543 & 197 & 3543 & 197\\
%\ttr{20i-1o-200t-0dc.pla} & 4000 & 200 & 0 & 3979 & 199 & 3979 & 199\\
%\ttr{20i-1o-200t-20dc.pla} & 3166 & 200 & 0 & 3166 & 200 & 3166 & 200\\
%\ttr{20i-1o-400t-30dc.pla} & 5584 & 400 & 0 & 5556 & 399 & 5556 & 399\\
%\ttr{30i-1o-300t-0dc.pla} & 9000 & 300 & 0 & 9000 & 300 & 9000 & 300\\
%
%
%\bottomrule
%\end{tabular}%
%\etab
%
%\section{Zhodnocení}%
%V této části práce bylo dosaženo dvou velmi zajímavých výsledků. Fakt, že MBD,
%jenž je redukovaný, je prakticky jedno jakým způsobem se přesměrovávají hrany
%vedoucí do terminálního uzlu s hodnotou $X$, je jistě zaznamenáníhodný a
%zároveň z něho pro další práci plynnou jiné příjemné důsledky. Tuto skutečnost
%lze totiž využít tak, že se budou provádět výhradně přesměrování hran vedoucích
%do $X$ pouze do uzlů, kam vede jejich sesterská hran. Tento postup je
%implementačně mnohem snažší a přitom riziko, že by jiná varianta přesměrování
%byla lepší, je velice malé.\\
%
%\noindent Ačkoliv to není na první pohled tolik zřejmé, tak zajímavých výsledků
%bylo dosaženo i při minimalizaci logických funkcí pomocí MBD. Ano, výsledky MBD
%byly jen o zlomeček lepší než ESPRESSO. Nicméně už fakt, že nebyly ani jednou
%horší je silně povzbuzující. Je nutné si uvědomit, že tato MBD implementace MBD
%má ještě rezervy v dynamickém řazení, kdy by sofistikovanější metoda jako
%prosévání možná dosáhla lepších výsledků.\\
%\indent V neprospěch minimimalizace na druhé straně hovoří velká časová
%náročnost (exponenciální) této operace ve srovnání s ESPRESSEM. Je-li čas
%důležitým parametrem při minimalizaci, tak samotné ESPRESSO je jedinou možnou
%volbou. Nezáleží-li na čase, nýbrž na každém ušetřeném literálu a termu, pak je
%možné i metodu popsanou v tomto oddílu.
