\select@language {czech}
\contentsline {chapter}{\numberline {}{Seznam obr\'azk\r u}}{xvii}{chapter*.6}
\contentsline {chapter}{\numberline {}{Seznam tabulek}}{xix}{chapter*.7}
\contentsline {chapter}{\numberline {1}\'Uvod}{1}{chapter.1}
\contentsline {section}{\numberline {1.1}\'U\v cel projektu a jeho pozad\IeC {\'\i }}{1}{section.1.1}
\contentsline {chapter}{\numberline {2}Z\'akladn\IeC {\'\i } definice}{3}{chapter.2}
\contentsline {section}{\numberline {2.1}Booleova algebra}{3}{section.2.1}
\contentsline {section}{\numberline {2.2}Vyj\'ad\v ren\IeC {\'\i } logick\'ych funkc\IeC {\'\i }}{3}{section.2.2}
\contentsline {paragraph}{liter\'al}{4}{section*.8}
\contentsline {paragraph}{term}{4}{section*.9}
\contentsline {paragraph}{logick\'y v\'yraz}{4}{section*.10}
\contentsline {paragraph}{logick\'e prom\v enn\'e}{5}{section*.11}
\contentsline {paragraph}{ONset, OFFset, DCset}{5}{section*.12}
\contentsline {paragraph}{implikant logick\'e funkce}{5}{section*.13}
\contentsline {paragraph}{p\v r\IeC {\'\i }m\'y implikant}{5}{section*.14}
\contentsline {paragraph}{Shannon\r uv expanzn\IeC {\'\i } teor\'em}{5}{section*.15}
\contentsline {paragraph}{if-then-else norm\'alov\'a forma}{5}{section*.16}
\contentsline {section}{\numberline {2.3}Form\'at PLA}{6}{section.2.3}
\contentsline {paragraph}{.i [\v c\IeC {\'\i }slo]}{6}{section*.17}
\contentsline {paragraph}{.o [\v c\IeC {\'\i }slo]}{6}{section*.18}
\contentsline {paragraph}{.p [\v c\IeC {\'\i }slo]}{6}{section*.19}
\contentsline {paragraph}{.type [typ]}{6}{section*.20}
\contentsline {paragraph}{.e}{6}{section*.21}
\contentsline {chapter}{\numberline {3}Bin\'arn\IeC {\'\i } rozhodovac\IeC {\'\i } diagramy}{7}{chapter.3}
\contentsline {section}{\numberline {3.1}Bin\'arn\IeC {\'\i } rozhodovac\IeC {\'\i } diagramy}{7}{section.3.1}
\contentsline {subsection}{\numberline {3.1.1}Konstrukce BDD}{8}{subsection.3.1.1}
\contentsline {section}{\numberline {3.2}OBDD - uspo\v r\'adan\'e BDD}{8}{section.3.2}
\contentsline {section}{\numberline {3.3}ROBDD - redukovan\'e uspo\v r\'adan\'e BDD}{9}{section.3.3}
\contentsline {subsection}{\numberline {3.3.1}Vlastnosti ROBDD}{9}{subsection.3.3.1}
\contentsline {section}{\numberline {3.4}Operace s ROBDD}{11}{section.3.4}
\contentsline {subsection}{\numberline {3.4.1}Operace APPLY}{11}{subsection.3.4.1}
\contentsline {subsection}{\numberline {3.4.2}Operace RESTRICT}{11}{subsection.3.4.2}
\contentsline {section}{\numberline {3.5}Zp\r usoby vyj\'ad\v ren\IeC {\'\i } ne\'upln\v e ur\v cen\'ych funkc\IeC {\'\i } pomoc\IeC {\'\i } BDD}{11}{section.3.5}
\contentsline {subsection}{\numberline {3.5.1}Z\'akladn\IeC {\'\i } zp\r usoby reprezentace ne\'upln\v e ur\v cen\'ych funkc\IeC {\'\i } pomoc\IeC {\'\i } ROBBD}{12}{subsection.3.5.1}
\contentsline {paragraph}{Ne\'upln\v e ur\v cen\'e funkce pomoc\IeC {\'\i } dvou ROBDD}{12}{section*.22}
\contentsline {paragraph}{Ne\'upln\v e ur\v cen\'e funkce pomoc\IeC {\'\i } t\v ret\IeC {\'\i } termin\'aln\IeC {\'\i } hodnoty}{12}{section*.23}
\contentsline {paragraph}{Ne\'upln\v e ur\v cen\'e funkce se zaveden\IeC {\'\i }m speci\'aln\IeC {\'\i } prom\v enn\'e \emph {z}}{12}{section*.24}
\contentsline {subsection}{\numberline {3.5.2}Reprezentace ne\'upln\v e ur\v cen\'ych logick\'ych funkc\IeC {\'\i } pomoc\IeC {\'\i } BDD\_for\_CF}{13}{subsection.3.5.2}
\contentsline {chapter}{\numberline {4}Modifikovan\'y bin\'arn\IeC {\'\i } diagram}{15}{chapter.4}
\contentsline {section}{\numberline {4.1}MBD}{15}{section.4.1}
\contentsline {subsection}{\numberline {4.1.1}Vlastnosti MBD}{15}{subsection.4.1.1}
\contentsline {subsection}{\numberline {4.1.2}Zvl\'a\v stnosti MBD}{17}{subsection.4.1.2}
\contentsline {chapter}{\numberline {5}\v Razen\IeC {\'\i } vstupn\IeC {\'\i }ch prom\v enn\'ych}{19}{chapter.5}
\contentsline {section}{\numberline {5.1}Metody pou\v z\IeC {\'\i }van\'e pro \v razen\IeC {\'\i } prom\v enn\'ych}{19}{section.5.1}
\contentsline {subsection}{\numberline {5.1.1}Statick\'e metody \v razen\IeC {\'\i }}{19}{subsection.5.1.1}
\contentsline {paragraph}{Metoda FORCE}{20}{section*.25}
\contentsline {paragraph}{Metoda STAT}{21}{section*.26}
\contentsline {subsection}{\numberline {5.1.2}Dynamick\'e metody \v razen\IeC {\'\i }}{21}{subsection.5.1.2}
\contentsline {paragraph}{Hladov\'y p\v r\IeC {\'\i }stup}{22}{section*.27}
\contentsline {chapter}{\numberline {6}Minimalizace logick\'ych funkc\IeC {\'\i }}{23}{chapter.6}
\contentsline {section}{\numberline {6.1}Klasick\'e zp\r usoby minimalizace}{23}{section.6.1}
\contentsline {subsection}{\numberline {6.1.1}Minimalizace pomoc\IeC {\'\i } Booleovy algebry}{23}{subsection.6.1.1}
\contentsline {subsection}{\numberline {6.1.2}Minimalizace s vyu\v zit\IeC {\'\i }m map}{24}{subsection.6.1.2}
\contentsline {subsection}{\numberline {6.1.3}Systematick\'e minimalizace}{24}{subsection.6.1.3}
\contentsline {paragraph}{Metoda Quine-McCluskey}{24}{section*.28}
\contentsline {paragraph}{Heuristika ESPRESSO}{25}{section*.29}
\contentsline {section}{\numberline {6.2}Minimalizace pomoc\IeC {\'\i } MBD}{25}{section.6.2}
\contentsline {subsection}{\numberline {6.2.1}Vyu\v zit\IeC {\'\i } struktury MBD pro minimalizaci}{27}{subsection.6.2.1}
\contentsline {subsection}{\numberline {6.2.2}Vyu\v zit\IeC {\'\i } DCsetu p\v ri minimalizaci}{27}{subsection.6.2.2}
\contentsline {chapter}{\numberline {7}Popis \v re\v sen\IeC {\'\i }}{31}{chapter.7}
\contentsline {section}{\numberline {7.1}Posloupnost operac\IeC {\'\i } p\v ri minimalizaci logick\'e funkce pomoc\IeC {\'\i } MBD}{31}{section.7.1}
\contentsline {section}{\numberline {7.2}Na\v c\IeC {\'\i }t\'an\IeC {\'\i } a redukce MBD}{32}{section.7.2}
\contentsline {section}{\numberline {7.3}Dynamick\'e \v razen\IeC {\'\i } prom\v enn\'ych}{33}{section.7.3}
\contentsline {section}{\numberline {7.4}P\v resm\v erov\'an\IeC {\'\i } hran vedouc\IeC {\'\i }ch do termin\'aln\IeC {\'\i }ho uzlu s hodnotou $X$}{33}{section.7.4}
\contentsline {section}{\numberline {7.5}Boolevsk\'a minimalizace}{33}{section.7.5}
\contentsline {section}{\numberline {7.6}Probl\'em p\v rekr\'yvaj\IeC {\'\i }c\IeC {\'\i }ch se term\r u}{34}{section.7.6}
\contentsline {chapter}{\numberline {8}Experimenty}{35}{chapter.8}
\contentsline {section}{\numberline {8.1}\v Razen\IeC {\'\i } prom\v enn\'ych}{35}{section.8.1}
\contentsline {subsection}{\numberline {8.1.1}\v Cetnost v\'yskytu po\v ctu uzl\r u}{35}{subsection.8.1.1}
\contentsline {subsection}{\numberline {8.1.2}\v Casov\'a slo\v zitost na\v c\IeC {\'\i }t\'an\IeC {\'\i } MBD}{36}{subsection.8.1.2}
\contentsline {subsection}{\numberline {8.1.3}\'U\v cinnost \v rad\IeC {\'\i }c\IeC {\'\i }ch technik}{36}{subsection.8.1.3}
\contentsline {subsection}{\numberline {8.1.4}Zhodnocen\IeC {\'\i }}{39}{subsection.8.1.4}
\contentsline {section}{\numberline {8.2}Minimalizace logick\'ych funkc\IeC {\'\i }}{40}{section.8.2}
\contentsline {subsection}{\numberline {8.2.1}Minimalizace pomoc\IeC {\'\i } DCsetu}{40}{subsection.8.2.1}
\contentsline {subsection}{\numberline {8.2.2}Celkov\'a minimalizace pomoc\IeC {\'\i } MBD}{41}{subsection.8.2.2}
\contentsline {subsection}{\numberline {8.2.3}Zhodnocen\IeC {\'\i }}{41}{subsection.8.2.3}
\contentsline {chapter}{\numberline {9}Implementace}{43}{chapter.9}
\contentsline {section}{\numberline {9.1}Pou\v zit\'e n\'astroje a filozofie programu}{43}{section.9.1}
\contentsline {subsection}{\numberline {9.1.1}Podporovan\'e platformy}{43}{subsection.9.1.1}
\contentsline {section}{\numberline {9.2}Struktura programu}{43}{section.9.2}
\contentsline {subsection}{\numberline {9.2.1}Node}{44}{subsection.9.2.1}
\contentsline {paragraph}{var\_id}{44}{section*.30}
\contentsline {paragraph}{node\_id}{44}{section*.31}
\contentsline {paragraph}{hi a lo}{44}{section*.32}
\contentsline {paragraph}{parents}{44}{section*.33}
\contentsline {paragraph}{Node}{44}{section*.34}
\contentsline {paragraph}{is\_parent}{44}{section*.35}
\contentsline {paragraph}{rem\_parent}{44}{section*.36}
\contentsline {paragraph}{is\_term}{45}{section*.37}
\contentsline {subsection}{\numberline {9.2.2}MBD}{45}{subsection.9.2.2}
\contentsline {paragraph}{root}{45}{section*.38}
\contentsline {paragraph}{term0}{45}{section*.39}
\contentsline {paragraph}{term1}{45}{section*.40}
\contentsline {paragraph}{termX}{45}{section*.41}
\contentsline {paragraph}{input\_num}{45}{section*.42}
\contentsline {paragraph}{order2var}{45}{section*.43}
\contentsline {paragraph}{var2order}{45}{section*.44}
\contentsline {paragraph}{map}{45}{section*.45}
\contentsline {paragraph}{load\_pla\_row}{46}{section*.46}
\contentsline {paragraph}{get\_node}{46}{section*.47}
\contentsline {paragraph}{swap\_vars}{46}{section*.48}
\contentsline {paragraph}{save\_to\_dot}{46}{section*.49}
\contentsline {paragraph}{get\_pla}{46}{section*.50}
\contentsline {paragraph}{cleanup}{47}{section*.51}
\contentsline {paragraph}{MBD}{47}{section*.52}
\contentsline {paragraph}{$\sim $MBD}{47}{section*.53}
\contentsline {subsection}{\numberline {9.2.3}MBDLIB}{48}{subsection.9.2.3}
\contentsline {paragraph}{static\_ordering\_method}{48}{section*.54}
\contentsline {paragraph}{x\_subst\_method}{48}{section*.55}
\contentsline {paragraph}{load\_from\_pla}{49}{section*.56}
\contentsline {paragraph}{apply}{49}{section*.57}
\contentsline {paragraph}{apply\_OR}{49}{section*.58}
\contentsline {paragraph}{reduce}{49}{section*.59}
\contentsline {paragraph}{ord\_stat}{49}{section*.60}
\contentsline {paragraph}{ord\_force}{49}{section*.61}
\contentsline {paragraph}{ord\_random}{49}{section*.62}
\contentsline {paragraph}{order\_vars\_static}{49}{section*.63}
\contentsline {paragraph}{order\_vars\_dynamic}{49}{section*.64}
\contentsline {paragraph}{get\_span}{49}{section*.65}
\contentsline {paragraph}{minimize\_X}{49}{section*.66}
\contentsline {subsection}{\numberline {9.2.4}PLA}{49}{subsection.9.2.4}
\contentsline {paragraph}{input\_num}{49}{section*.67}
\contentsline {paragraph}{output\_num}{49}{section*.68}
\contentsline {paragraph}{PLA}{49}{section*.69}
\contentsline {paragraph}{load}{49}{section*.70}
\contentsline {paragraph}{save}{50}{section*.71}
\contentsline {paragraph}{get\_histogram}{50}{section*.72}
\contentsline {paragraph}{get\_stats}{50}{section*.73}
\contentsline {chapter}{\numberline {10}Vizualizace MBD}{51}{chapter.10}
\contentsline {section}{\numberline {10.1}Jazyk DOT}{51}{section.10.1}
\contentsline {paragraph}{digraph}{52}{section*.74}
\contentsline {paragraph}{size}{52}{section*.75}
\contentsline {paragraph}{node}{52}{section*.76}
\contentsline {paragraph}{rank}{52}{section*.77}
\contentsline {paragraph}{edge}{52}{section*.78}
\contentsline {section}{\numberline {10.2}Graphviz}{52}{section.10.2}
\contentsline {section}{\numberline {10.3}Nic nen\IeC {\'\i } dokonal\'e}{54}{section.10.3}
\contentsline {section}{\numberline {10.4}Jin\'e zp\r usoby vizualizace}{54}{section.10.4}
\contentsline {chapter}{\numberline {11}Z\'av\v er}{55}{chapter.11}
\contentsline {paragraph}{P\v r\IeC {\'\i }klad}{57}{section*.81}
