\select@language {english}
\select@language {czech}
\contentsline {chapter}{\numberline {1}\IeC {\'U}vod}{1}{chapter.1}
\contentsline {section}{\numberline {1.1}\IeC {\'U}vod do problematiky}{1}{section.1.1}
\contentsline {section}{\numberline {1.2}C\IeC {\'\i }le pr\IeC {\'a}ce}{1}{section.1.2}
\contentsline {section}{\numberline {1.3}Implementa\IeC {\v c}n\IeC {\'\i } po\IeC {\v z}adavky na \IeC {\v r}e\IeC {\v s}en\IeC {\'\i }}{1}{section.1.3}
\contentsline {section}{\numberline {1.4}Rozd\IeC {\v e}len\IeC {\'\i } textu na kapitoly}{2}{section.1.4}
\contentsline {chapter}{\numberline {2}Definice}{3}{chapter.2}
\contentsline {section}{\numberline {2.1}Opakov\IeC {\'a}n\IeC {\'\i } pojm\IeC {\r u}}{3}{section.2.1}
\contentsline {subsection}{\numberline {2.1.1}Booleova algebra}{3}{subsection.2.1.1}
\contentsline {subsection}{\numberline {2.1.2}Vyj\IeC {\'a}d\IeC {\v r}en\IeC {\'\i } logick\IeC {\'y}ch funkc\IeC {\'\i }}{4}{subsection.2.1.2}
\contentsline {subsection}{\numberline {2.1.3}Pou\IeC {\v z}\IeC {\'\i }van\IeC {\'e} d\IeC {\r u}le\IeC {\v z}it\IeC {\'e} term\IeC {\'\i }ny}{4}{subsection.2.1.3}
\contentsline {section}{\numberline {2.2}Operace pro dekompozici term\IeC {\r u}}{5}{section.2.2}
\contentsline {section}{\numberline {2.3}Form\IeC {\'a}t PLA}{7}{section.2.3}
\contentsline {section}{\numberline {2.4}N\IeC {\'a}stroj BOOM}{7}{section.2.4}
\contentsline {chapter}{\numberline {3}Popis probl\IeC {\'e}mu ortogonalizace}{9}{chapter.3}
\contentsline {section}{\numberline {3.1}Ortogonalizace}{9}{section.3.1}
\contentsline {section}{\numberline {3.2}Ortogonalizace logick\IeC {\'e} funkce}{9}{section.3.2}
\contentsline {section}{\numberline {3.3}Rozlo\IeC {\v z}en\IeC {\'\i } dvou term\IeC {\r u}}{10}{section.3.3}
\contentsline {section}{\numberline {3.4}\IeC {\v C}asov\IeC {\'a} slo\IeC {\v z}itost algoritmu}{10}{section.3.4}
\contentsline {subsection}{\numberline {3.4.1}Optim\IeC {\'a}ln\IeC {\'\i } \IeC {\v r}e\IeC {\v s}en\IeC {\'\i }}{11}{subsection.3.4.1}
\contentsline {chapter}{\numberline {4}Sezn\IeC {\'a}men\IeC {\'\i } s existuj\IeC {\'\i }c\IeC {\'\i }mi implementacemi}{13}{chapter.4}
\contentsline {section}{\numberline {4.1}Espresso}{13}{section.4.1}
\contentsline {section}{\numberline {4.2}DSOP}{13}{section.4.2}
\contentsline {section}{\numberline {4.3}DSOP vyu\IeC {\v z}\IeC {\'\i }vaj\IeC {\'\i }c\IeC {\'\i } maxim\IeC {\'a}ln\IeC {\'\i } binate prom\IeC {\v e}nn\IeC {\'e}}{14}{section.4.3}
\contentsline {chapter}{\numberline {5}Anal\IeC {\'y}za probl\IeC {\'e}mu a n\IeC {\'a}vrh implementace}{17}{chapter.5}
\contentsline {section}{\numberline {5.1}Rozklad term\IeC {\r u}}{17}{section.5.1}
\contentsline {subsection}{\numberline {5.1.1}Postupn\IeC {\'y} rozklad}{17}{subsection.5.1.1}
\contentsline {section}{\numberline {5.2}\IeC {\v R}\IeC {\'\i }zen\IeC {\'\i } rozkladu}{17}{section.5.2}
\contentsline {subsection}{\numberline {5.2.1}Se\IeC {\v r}azen\IeC {\'\i } podle velikosti term\IeC {\r u}}{18}{subsection.5.2.1}
\contentsline {paragraph}{P\IeC {\v r}\IeC {\'\i }klad 5.1}{18}{section*.5}
\contentsline {paragraph}{P\IeC {\v r}\IeC {\'\i }klad 5.2}{18}{section*.6}
\contentsline {subsection}{\numberline {5.2.2}Se\IeC {\v r}azen\IeC {\'\i } term\IeC {\r u} podle po\IeC {\v c}tu protnut\IeC {\'\i } s ostatn\IeC {\'\i }mi termy}{19}{subsection.5.2.2}
\contentsline {paragraph}{P\IeC {\v r}\IeC {\'\i }klad 5.3}{19}{section*.7}
\contentsline {paragraph}{P\IeC {\v r}\IeC {\'\i }klad 5.4}{19}{section*.8}
\contentsline {subsection}{\numberline {5.2.3}S\IeC {\'e}riov\IeC {\'e} pou\IeC {\v z}it\IeC {\'\i } v\IeC {\'\i }ce t\IeC {\v r}\IeC {\'\i }d\IeC {\'\i }c\IeC {\'\i }ch metod}{20}{subsection.5.2.3}
\contentsline {paragraph}{P\IeC {\v r}\IeC {\'\i }klad 5.5}{20}{section*.9}
\contentsline {section}{\numberline {5.3}Slo\IeC {\v z}en\IeC {\'\i } term\IeC {\r u}}{21}{section.5.3}
\contentsline {subsection}{\numberline {5.3.1}Pohlcen\IeC {\'\i } term\IeC {\r u}}{21}{subsection.5.3.1}
\contentsline {subsection}{\numberline {5.3.2}Slou\IeC {\v c}en\IeC {\'\i } term\IeC {\r u}}{21}{subsection.5.3.2}
\contentsline {subsection}{\numberline {5.3.3}Se\IeC {\v r}azen\IeC {\'\i } term\IeC {\r u} podle po\IeC {\v c}tu mo\IeC {\v z}nost\IeC {\'\i } slou\IeC {\v c}en\IeC {\'\i }}{23}{subsection.5.3.3}
\contentsline {section}{\numberline {5.4}P\IeC {\v r}edzpracov\IeC {\'a}n\IeC {\'\i } vstupn\IeC {\'\i }ho seznamu term\IeC {\r u}}{24}{section.5.4}
\contentsline {subsection}{\numberline {5.4.1}Nastaven\IeC {\'\i } v\IeC {\'y}stup\IeC {\r u} term\IeC {\r u}}{24}{subsection.5.4.1}
\contentsline {subsection}{\numberline {5.4.2}Minimalizace term\IeC {\r u}}{25}{subsection.5.4.2}
\contentsline {section}{\numberline {5.5}N\IeC {\'a}vrh algoritmu}{26}{section.5.5}
\contentsline {subsection}{\numberline {5.5.1}Sch\IeC {\'e}ma algoritmu}{26}{subsection.5.5.1}
\contentsline {subsection}{\numberline {5.5.2}Popis f\IeC {\'a}z\IeC {\'\i } algoritmu}{26}{subsection.5.5.2}
\contentsline {chapter}{\numberline {6}Realizace \IeC {\v r}e\IeC {\v s}en\IeC {\'\i }}{29}{chapter.6}
\contentsline {section}{\numberline {6.1}Programov\IeC {\'e} vybaven\IeC {\'\i } pro implementaci algoritmu}{29}{section.6.1}
\contentsline {section}{\numberline {6.2}Pseudok\IeC {\'o}d zjednodu\IeC {\v s}en\IeC {\'e}ho algoritmu}{29}{section.6.2}
\contentsline {section}{\numberline {6.3}Proces dekompozice term\IeC {\r u}}{30}{section.6.3}
\contentsline {subsection}{\numberline {6.3.1}Funkce TermDisjointSharp}{30}{subsection.6.3.1}
\contentsline {section}{\numberline {6.4}Set\IeC {\v r}\IeC {\'\i }zen\IeC {\'\i } term\IeC {\r u}}{30}{section.6.4}
\contentsline {section}{\numberline {6.5}Slou\IeC {\v c}en\IeC {\'\i } term\IeC {\r u} a absorbce}{32}{section.6.5}
\contentsline {subsection}{\numberline {6.5.1}Funkce BackMerge}{32}{subsection.6.5.1}
\contentsline {section}{\numberline {6.6}Eliminace term\IeC {\r u} nepat\IeC {\v r}\IeC {\'\i }c\IeC {\'\i } do ONsetu}{32}{section.6.6}
\contentsline {section}{\numberline {6.7}Minimalizace vstupn\IeC {\'\i }ch term\IeC {\r u} pomoc\IeC {\'\i } Espressa}{32}{section.6.7}
\contentsline {chapter}{\numberline {7}Testov\IeC {\'a}n\IeC {\'\i }}{33}{chapter.7}
\contentsline {section}{\numberline {7.1}Ozna\IeC {\v c}en\IeC {\'\i } testovan\IeC {\'y}ch algoritm\IeC {\r u}}{33}{section.7.1}
\contentsline {section}{\numberline {7.2}Postup testov\IeC {\'a}n\IeC {\'\i }}{34}{section.7.2}
\contentsline {section}{\numberline {7.3}Test funk\IeC {\v c}nosti}{34}{section.7.3}
\contentsline {section}{\numberline {7.4}Srovn\IeC {\'a}vac\IeC {\'\i } testy}{35}{section.7.4}
\contentsline {section}{\numberline {7.5}Porovn\IeC {\'a}n\IeC {\'\i } pr\IeC {\r u}b\IeC {\v e}\IeC {\v z}n\IeC {\'e}ho uspo\IeC {\v r}\IeC {\'a}dan\IeC {\'\i } term\IeC {\r u}}{35}{section.7.5}
\contentsline {subsection}{\numberline {7.5.1}Porovn\IeC {\'a}n\IeC {\'\i } v\IeC {\'y}sledk\IeC {\r u} metod \IeC {\v r}azen\IeC {\'\i }}{35}{subsection.7.5.1}
\contentsline {subsection}{\numberline {7.5.2}Porovn\IeC {\'a}n\IeC {\'\i } \IeC {\v c}asu metod \IeC {\v r}azen\IeC {\'\i }}{36}{subsection.7.5.2}
\contentsline {subsection}{\numberline {7.5.3}Srovn\IeC {\'a}n\IeC {\'\i } algoritmu \textit {WithoutSort} s algoritmy s pr\IeC {\r u}b\IeC {\v e}\IeC {\v z}n\IeC {\'y}m \IeC {\v r}azen\IeC {\'\i }m}{36}{subsection.7.5.3}
\contentsline {subsection}{\numberline {7.5.4}Srovn\IeC {\'a}n\IeC {\'\i } \IeC {\v r}azen\IeC {\'\i } \textit {SizeSortInc} a \textit {SizeSortDec}}{37}{subsection.7.5.4}
\contentsline {subsection}{\numberline {7.5.5}Srovn\IeC {\'a}n\IeC {\'\i } \IeC {\v r}azen\IeC {\'\i } \textit {IntersectionSortInc} a \textit {IntersectionSortDec} }{37}{subsection.7.5.5}
\contentsline {subsection}{\numberline {7.5.6}Srovn\IeC {\'a}n\IeC {\'\i } \IeC {\v r}azen\IeC {\'\i } \textit {SizeSortDec} se s\IeC {\'e}riov\IeC {\'y}m \IeC {\v r}azen\IeC {\'\i }m \textit {SizeIntersectionSortInc} a \textit {SizeIntersectionSortDec}}{37}{subsection.7.5.6}
\contentsline {subsection}{\numberline {7.5.7}Srovn\IeC {\'a}n\IeC {\'\i } \IeC {\v r}azen\IeC {\'\i } \textit {SortByMergeInc} a \textit {SortByMergeDec} s metodou \textit {WithoutSort} }{37}{subsection.7.5.7}
\contentsline {subsection}{\numberline {7.5.8}Zhodnocen\IeC {\'\i } testov\IeC {\'a}n\IeC {\'\i } \IeC {\v r}ad\IeC {\'\i }c\IeC {\'\i }ch metod algoritmu}{37}{subsection.7.5.8}
\contentsline {section}{\numberline {7.6}Porovn\IeC {\'a}n\IeC {\'\i } algoritmu s ciz\IeC {\'\i }mi implementacemi}{38}{section.7.6}
\contentsline {subsection}{\numberline {7.6.1}Porovn\IeC {\'a}n\IeC {\'\i } v\IeC {\'y}sledk\IeC {\r u} algoritm\IeC {\r u}}{38}{subsection.7.6.1}
\contentsline {subsection}{\numberline {7.6.2}Porovn\IeC {\'a}n\IeC {\'\i } \IeC {\v c}as\IeC {\r u} algoritm\IeC {\r u}}{38}{subsection.7.6.2}
\contentsline {subsection}{\numberline {7.6.3}Srovn\IeC {\'a}n\IeC {\'\i } algoritm\IeC {\r u} \textit {SizeSortDec}, \textit {A\_BackMerge}, \textit {A\_EliminateUnde-fined} a \textit {A\_Espresso} }{39}{subsection.7.6.3}
\contentsline {subsection}{\numberline {7.6.4}Srovn\IeC {\'a}n\IeC {\'\i } algoritmu \textit {Espresso -Ddisjoint} s ostatn\IeC {\'\i }mi implementacemi}{39}{subsection.7.6.4}
\contentsline {subsection}{\numberline {7.6.5}Srovn\IeC {\'a}n\IeC {\'\i } algoritm\IeC {\r u} \textit {A\_EliminateUndefined} , \textit {A\_Espresso} a \textit {DSOP}}{39}{subsection.7.6.5}
\contentsline {chapter}{\numberline {8}Z\IeC {\'a}v\IeC {\v e}r}{41}{chapter.8}
\contentsline {chapter}{\numberline {9}Literatura a pou\IeC {\v z}it\IeC {\'e} zdroje}{43}{chapter.9}
\contentsline {chapter}{\numberline {A}Porovn\IeC {\'a}n\IeC {\'\i } metod pr\IeC {\r u}b\IeC {\v e}\IeC {\v z}n\IeC {\'e}ho \IeC {\v r}azen\IeC {\'\i } term\IeC {\r u}}{45}{appendix.A}
\contentsline {chapter}{\numberline {B}Porovn\IeC {\'a}n\IeC {\'\i } \IeC {\v c}as\IeC {\r u} metod pr\IeC {\r u}b\IeC {\v e}\IeC {\v z}n\IeC {\'e}ho \IeC {\v r}azen\IeC {\'\i } term\IeC {\r u}}{49}{appendix.B}
\contentsline {chapter}{\numberline {C}Porovn\IeC {\'a}n\IeC {\'\i } navr\IeC {\v z}en\IeC {\'e}ho algoritmu s ciz\IeC {\'\i }mi implementacemi}{53}{appendix.C}
\contentsline {chapter}{\numberline {D}Porovn\IeC {\'a}n\IeC {\'\i } \IeC {\v c}as\IeC {\r u} navr\IeC {\v z}en\IeC {\'e}ho algoritmu s ciz\IeC {\'\i }mi implementacemi}{57}{appendix.D}
\contentsline {chapter}{\numberline {E}Ovl\IeC {\'a}d\IeC {\'a}n\IeC {\'\i } navr\IeC {\v z}en\IeC {\'e}ho programu}{61}{appendix.E}
\contentsline {chapter}{\numberline {F}Obsah p\IeC {\v r}ilo\IeC {\v z}en\IeC {\'e}ho CD}{63}{appendix.F}
