\documentclass[11pt,twoside,a4paper,czech]{book}%two-page printing
%\usepackage[latin2]{inputenc}

%\documentclass[11pt]{book}
\usepackage[cp1250]{inputenc}
\usepackage[czech]{babel}
%\usepackage{a4wide}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{array}
\usepackage{graphicx}
\usepackage{multirow}
\usepackage{booktabs}

%\usepackage{arev}
%\usepackage[math]{iwona}
%\usepackage[math]{kurier}
%\usepackage[sc]{mathpazo} \linespread{1.05}
%\usepackage{cmbright}
%\usepackage{concmath}
%\usepackage[math]{anttor}
%\usepackage{pandora}
%\usepackage[adobe-utopia]{mathdesign}
%\usepackage{bookman}
%\usepackage[bitstream-charter]{mathdesign}
\usepackage{kmath,kerkis}
\usepackage{color}
\usepackage{listings}
\usepackage{multicol}
\usepackage{hyperref}

\definecolor{Brown}{cmyk}{0,0.81,1,0.60}
\definecolor{OliveGreen}{cmyk}{0.64,0,0.95,0.40}
\definecolor{CadetBlue}{cmyk}{0.62,0.57,0.23,0}
\definecolor{Red}{rgb}{1.0,0.0,0.0}
\definecolor{my_green}{rgb}{0.0,0.6,0.0}
\definecolor{my_red}{rgb}{0.94,0.0,0.0}
\definecolor{RealGray}{gray}{0.22}
\definecolor{LightGray}{gray}{0.55}
\definecolor{VeryLightGray}{gray}{0.92}
\definecolor{DarkGray}{gray}{0.05}


\input diplbakmacro.tex   % specialni makra pro formatovani diplomek

 % muzete si vytvorit i sva vlastni
 % inspirujte se souborem bakmacro.tex
 % najdete tam radu jednoduchych definic, ktere zde ani nejsou pouzity
 % napriklad:
 % \newcommand{\bfig}{\begin{figure}\begin{center}}
 % \newcommand{\efig}{\end{center}\end{figure}}
 % umoznuje pouzit prikaz \bfig namisto \begin{figure}\begin{center} atd.


\newcommand\TypeOfWork{Diplomová práce}
\newcommand\WorkTitle{Minimalizace neúplně určených logických funkcí pomocí modifikovaných binárních rozhodovacích diagramů}
\newcommand\FirstandFamilyName{Jan Bílek}
\newcommand\Month{Leden}
\newcommand\Year{2007}
\newcommand\Supervisor{Ing. Petr Fišer}

\newcommand\StudProgram{Elektrotechnika a informatika kombinovaný magisterský}
\newcommand\StudBranch{Výpočetní technika}
\newcommand\Faculty{Fakulta elektrotechnická}
\newcommand\University{České vysoké učení technické v Praze}

\newcommand\uv[1]{\quotedblbase #1\textquotedblright}%
\renewcommand{\multirowsetup}{\centering}

\newcommand\ttr[1]{\multicolumn{1}{r}{#1}}%
\newcommand\ttc[1]{\multicolumn{1}{c}{#1}}%
\newcommand\ttl[1]{\multicolumn{1}{l}{#1}}%

 \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
    }

\begin{document}

\input{prvni_stranky.tex}
\input{uvod.tex}
\input{definice.tex}
\input{bdd.tex}
\input{mbd.tex}
\input{razeni.tex}
\input{minimalizace.tex}
\input{popis_reseni.tex}
\input{experimenty.tex}
\input{implementace.tex}
\input{vizualizace.tex}



\chapter{Závěr}%
\label{kap_zaver}%
Na tomto místě je nutné potvrdit, že všechny úkoly, které byly vytýčeny v
zadání práce, byly splněny. To znamená, že byla úspěšně implementována
struktura MBD včetně řady dopro-vodných funkcí na řazení vstupních proměnných a
minimalizaci neúplně určených logických funkcí. Provedené experimenty potvrdily
nejen funkčnost implementace, ale odhalily i~řadu zajímavých skutečností o MBD
a jejich použití pro minimalizaci.\\

\noindent Experimenty ukázaly, že rozložení četností výskytu počtu uzlů v MBD
má přibližně tvar Gaussovy křivky, jejíž rozptyl a průměrná hodnota počtu uzlů
je závislá na počtu neurčených vstupních proměnných. Čím je neurčených
vstupních proměnných více, tím je průměrná hodnota počtu uzlů a rozptyl
Gaussovy křivky větší.\\
\indent Z řadících technik se nejvíce prosadilo dynamické prohazování vstupních
proměnných a statická metoda STAT, která je jedním z vedlejších produktů této
práce. Jednoznačně se ukázalo, že nejlepší variantou jak přistoupit k řazení
proměnných, je nejprve použít jednoduchou statickou metodu řazení a po načtení
použít dynamické prohazování. Ačkoliv v práci \linebreak implementovaná
dynamická metoda měla svá omezení (uvíznutí v nejbližším lokálním minimu),
přesto ukázala cestu, kterou by se případní pokračovatelé této práce měli
vydat. Doplněním současné metody prohazování proměnných tak, aby se zabránilo
uvíznutí v lokálním minimu, by se celá práce přiblížila \emph{konkurenčním}
balíkům jako CUDD nebo BuDDy. Možným řešením je použít například metody jako je
simulované ochlazování nebo genetické algoritmy, které už byly na problém
dynamického prohazování vstupních proměnných s úspěchem použity. Velmi snadno
implementovatelná metoda STAT je naproti tomu velmi vhodným doplňkem, který
dokáže razantně snížit počet uzlů
dříve, než dojde na použití dynamických metod.\\

\noindent Ohledně minimalizace logických funkcí pomocí MBD je nutné si položit
otázku, zda se MBD k tomuto účelu hodí a zda by tento postup mohl konkurovat
známým a úspěšným minimalizatorům (především ESPRESSU). Odpovědí je jednoznačné
ANO. Ano, MBD lze využít na minimalizaci logických funkcí a dokonce lze
dosáhnout lehce lepších výsledků než zmiňované ESPRESSO. \emph{ALE!} Vše je
vykoupeno velkou časovou složitosti MBD. Načítání a booleovské (i~algebraické)
procházení MBD implementované v této práci má totiž složitost $O(2^n)$. Ačkoliv
se reálné MBD jen výjimečně přiblíží této složitosti, i tak je čas velkým
minusem metody a nedostatkem oproti heuristice ESPRESSO.\\
\indent Při minimalizaci neúplně určených logických funkcí se naplno projevila
výhoda MBD (oproti klasickému BDD), která spočívá v tom, že jak ONset, tak i
DCset jsou v jednom společném grafu. Díky tomu bylo možné přesměrováním hran
vedoucích do terminálního uzlu s hodnotou $X$ razantně snížit celkovou velikost
MBD. V této souvislosti bylo zjištěno, že hrany vedoucí do terminálu s hodnotou
$X$ stačí přesměrovávat do uzlu, kam vede její sesterská hrana.\\

\noindent Nedostatky této implementace MBD jsou jmenovány na mnoha místech
tohoto textu, ale určitě je vhodné je ještě připomenout.\\
\indent Zásadním problémem je zde rychlost načítání MBD. Ačkoliv zde použitá
metoda není nijak naivní, přesto by potřebovala značně vylepšit nebo vytvořit
znovu na zcela jiném přístupu. Dynamické řadící metodě - prohazování proměnných
by zase prospělo vylepšení v podobě techniky, jež by dokázala
uniknout z lokálního minima.\\
\indent Méně náročnými vylepšeními pak jsou podpora vícehodnotových funkcí a
podpora jiných platforem než Windows.



\input{prilohy.tex}

\begin{thebibliography}{30}
\bibitem{Jac93} R. P. Jacobi: \uv{A Study of the Aplication of Binary Decision Diagrams to
Multi-level Logic Synthesis,} Doktorandská práce, Prosinec~1993.
\bibitem{Bry86} R. E. Bryant: \uv{Graph based algorithms for Boolean function
manipulation,} IEEE Transactions on Computers, 1986.
\bibitem{Fri87} S. J. Friedman, K. J. Supowit: \uv{Finding optimal variable
ordering for binary decision diagrams,} IEEE Transactions on Computers, 1990.
\bibitem{Alo01} F. A. Aloul, I. L. Markov, K. A. Sakallah: \uv{MINCE:
A Static Global Variable-Ordering for SAT and BDD,} IWLS, 2001.
\bibitem{Alo03} F. A. Aloul, I. L. Markov, K. A. Sakallah:
\uv{FORCE: A Fast and Easy-To-Implement Variable-Ordering Heuristic,} GLSVLSI,
2003.
\bibitem{Som06} F. Somenzi: \uv{Colorado University Decision Diagram package
(CUDD),} http://vlsi.colorado.edu/ $\sim$fabio/CUDD, 2006.
\bibitem{Bud06} H. Cohen: \uv{BuDDy: A Binary Decision Diagram
library,} http://sourceforge.net/pro-jects/buddy/, 2006.
\bibitem{Jan01} V. Jáneš, J. Douša: \uv{Logické systémy,} skriptum FEL ČVUT, 2001.
\bibitem{Rud93} R. Rudell: \uv{Dynamic variable ordering for ordered binary
decision diagrams,} Proc. of the International Conference on Computer-Aided
Design, 1993.
\bibitem{Bry89} K. Cho, R. E. Bryant: \uv{Test pattern generation for sequential MOS
circuits by symbolic fault simulation,} Design Automation Conference, 1989.
\bibitem{Cha94} S. Chang, D. Cheng, M. Marek-Sadowska:
\uv{Minimizing ROBDD size of incompletely specified multiple output functions,}
In European Design \& Test Conf., 1994.
\bibitem{Min90} S. Minato, N. Ishiura, and S. Yajima, \uv{Shared binary
decision diagram with attributed edges for efficient Boolean function
manipulation,} Design Automation Conference, 1990.
\bibitem{Sas05} T. Sasao and M. Matsuura, \uv{BDD Representation for Incompletely
Specified Multiple-Output Logic Functions and Its Applications to Functional
Decomposition,} Design Automation Conference, 2005.
\bibitem{Kol06} O. Kološ: \uv{Port programového balíku
CUDD pod platformu Windows,} Bakalářská práce na FEL ČVUT, 2006.
\bibitem{wk_hl} http://cs.wikipedia.org/wiki/Hladový\_algoritmus
\bibitem{wk_qm} http://en.wikipedia.org/wiki/Quine\-McCluskey\_algorithm
\bibitem{grpvz} http://www.graphviz.org
\bibitem{boost} http://www.boost.org/libs/graph/doc
\bibitem{boompla06} http://service.felk.cvut.cz/vlsi/prj/BOOM/pla\_c.html

\end{thebibliography}

\end{document}
