Cílem této kapitoly bude srovnání našeho nástroje na detekci tautologie s ostatními implementacemi vyjmenovanými v podkapitolách~\ref{komplement} -~\ref{grafy-popis}. Testování je rozděleno do několika kategorií, ve kterých budeme sledovat vliv konkrétních parametrů na čas potřebný k nalezení řešení u jednotlivých programů.

V grafech budeme na časové ose ve většině případů používat logaritmické měřítko a to kvůli řádovým rozdílům ve výkonnostech jednotlivých programů. U naměřených výsledcích budeme uvádět časy v sekundách. Hodnota \uv{chyb. výsl.} znamená, že program označil řešení za tautologii, i když jí nebyla. Hodnota \uv{$>x$} znamená, že program nenalezl řešení ani po $x$s. Hodnota \uv{chyba} znamená neočekávanou výjimku, která nastala při běhu programu. Měření bylo prováděno na procesoru AMD Athlon XP-M 2800+ 2,12GHz, 512MB RAM s operačním systémem Windows XP SP3. Pro případy, kdy jednotlivé nástroje nalézali řešení v různých časech pro konkrétní vygenerované instance, které se nelišily pouze svými parametry, jsou pak úváděné časy průměrem z takto získaných hodnot. V sloupci nadepsaném symbolem $T$ je uvedeno, zda-li byly instance z dané testované skupiny tautologiemi. Testované programy jsou vyjmenovány v následující tabulce~\ref{tabPrehled}.

\begin{table}[h!t]
\caption{Přehled testovaných programů}
\begin{center}
\begin{tabular}{|c|l|}
\hline
\bf{Název programu}&\bf{Popis}\\
\hline
Kompl.& metoda výpočtu komplementu, kap.~\ref{komplement} \\
\hline
BDD & detekce tautologie pomocí BDD, kap.~\ref{bdd-popis} \\
\hline
Graf & manipulace s funkcemi pomocí grafů, kap.~\ref{grafy-popis} \\
\hline
Graf II & totéž co předchozí + předpříprava PLA, kap.~\ref{grafy-popis} \\
\hline
Knih.-Espresso & knihovna z nástroje Espresso, kap.~\ref{knihovnaEspresso}\\
\hline
Tautology & náše vlastní implementace nástroje na detekci tautologie\\
\hline
\end{tabular}
\end{center}
\label{tabPrehled}
\end{table}


\section{Generátor instancí logických funkcí}

Před samotným testováním bylo třeba získat instance zadání logických funkcí ve formátu Espresso PLA. Pro tyto účely byl použit generátor PLA, který vznikl jako semestrální práce~\cite{chromy} kolegy Radka Chromého. Tento generátor umožňuje vytváření PLA na základě nastavení tří parametrů, kterými jsou: počet proměnných, počet termů a procentuální zastoupení DC symbolů. Testované instance jsou pak součástí CD přílohy této diplomové práce a jsou zařazeny podle jednotlivých kategorií.

\section{Závislost doby výpočtu na počtu proměnných}

Jedním z hlavních parametrů, kterým se vyznačuje logická funkce je počet proměnných, které se v ní vyskytují. Podkapitola~\ref{odhadSlozitosti} uvádí, že obecně asymptotická složitost detekce tautologie roste exponencielně s počtem proměnných logické funkce, neboť pravdivostní tabulka, kterou musíme v nejhorším možném případě celou projít má $2^N$ řádků, kde $N$ představuje počet proměnných. Bude tedy velmi zajímavé sledovat, jaký vliv bude mít tento parametr na výpočetní časy testovaných programů.

Nejprve provedeme testování pro relativně malé instance (do 50 proměnných), aby je bylo možné řešit všemi implementacemi. Větší instance (do 1000 proměnných) jsou pak již řešitelné pouze některými algoritmy. 

Pro malé instance byly zvoleny pevné hodnoty počtu termů - 500 a procentuální zastoupení DC symbolů na 30\%. Jediným pohyblivým parametrem je tedy počet proměnných. V tabulce~\ref{tabProm1} jsou časy potřebné k nalezení řešení u šesti testovaných programů. 

\begin{table}[h!t]
\caption{Závislost doby výpočtu na počtu proměnných}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\bf{var.}&\bf{T}&\bf{Kompl.}&\bf{BDD}&\bf{Graf}&\bf{Graf~II}&\bf{Knih.-Espresso}&\bf{Tautology}\\
\hline
5 & 1 & chyba & 0,08 & 0,01 & 0,02 & 0,001 & 0,001 \\
\hline
10 & 0 & chyba & 0,16 & 0,07 & 0,83 & 0,01 & 0,003 \\
\hline
15 & 0 & 2,32 & 5,08 & 0,07 & 1,24 & 0,02 & 0,003 \\
\hline
20 & 0 & 7,23 & 28,58 & 0,08 & 1,52 & 0,02 & 0,003 \\
\hline
25 & 0 & 12,45 & 38,05 & 0,08 & 1,78 & 0,02 & 0,003 \\
\hline
30 & 0 & 15,34 & 40,28 & 0,09 & 2,01 & 0,02 & 0,003 \\
\hline
35 & 0 & 18,23 & 50,41 & 0,10 & 2,35 & 0,02 & 0,01 \\
\hline
40 & 0 & 22,32 & 77,23 & 0,11 & 2,67 & 0,02 & 0,01 \\
\hline
45 & 0 & 31,34 & 94,57 & 0,12 & 3,01 & 0,02 & 0,01 \\
\hline
50 & 0 & 52,12 & 102,39 & 0,13 & 3,52 & 0,02 & 0,02 \\
\hline
\end{tabular}
\end{center}
\label{tabProm1}
\end{table}

V grafu na obrázku~\ref{grafProm1} je znázorněna závislost doby výpočtu na počtu proměnných.

\begin{figure}[h!t]
\begin{center}
\includegraphics[width=15cm]{obr/graf-pocetPromennych1.PNG}
\caption{Závislost doby výpočtu na počtu proměnných}
\label{grafProm1}
\end{center}
\end{figure}


Pro větší instance byly zvoleny pevné hodnoty počtu termů - 1000 a procentuální zastoupení DC symbolů na 50\%. Jediným pohyblivým parametrem je tedy opět počet proměnných. V tabulce~\ref{tabProm2} jsou časy potřebné k nalezení řešení u šesti testovaných programů. 

\begin{table}[h!t]
\caption{Závislost doby výpočtu na počtu proměnných II}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\bf{var.}&\bf{T}&\bf{Kompl.}&\bf{BDD}&\bf{Graf}&\bf{Graf~II}&\bf{Knih.-Espresso}&\bf{Tautology}\\
\hline
10 & 1 & chyba & 0,25 & 0,09 & 0,23 & 0,001 & 0,01 \\
\hline
20 & 0 & chyba & chyb. výsl. & 0,23 & 6,55 & 0,36 & 0,02 \\
\hline
50 & 0 & $>200$ & $>200$ & 0,30 & 15,81 & 0,33 & 0,02 \\
\hline
100 & 0 & $>200$ & $>200$ & 0,29 & 29,63 & 0,31 & 0,02 \\
\hline
200 & 0 & $>200$ & $>200$ & 0,35 & 64,02 & 0,48 & 0,02 \\
\hline
500 & 0 & $>200$ & $>200$ & 0,79 & $>200$ & 0,65 & 0,03 \\
\hline
1000 & 0 & $>200$ & $>200$ & 1,46 & $>200$ & 0,85 & 0,03 \\
\hline
2000 & 0 & $>200$ & $>200$ & 3,94 & $>200$ & 1,45 & 0,05 \\
\hline
5000 & 0 & $>200$ & $>200$ & 9,07 & $>200$ & 3,43 & 0,12 \\
\hline
10000 & 0 & $>200$ & $>200$ & 20,91 & $>200$ & 7,03 & 0,24 \\
\hline
\end{tabular}
\end{center}
\label{tabProm2}
\end{table}

V grafu na obrázku~\ref{grafProm2} je znázorněna závislost doby výpočtu na počtu proměnných pro relativně větší instance.

\begin{figure}[h!t]
\begin{center}
\includegraphics[width=15cm]{obr/graf-pocetPromennych2.PNG}
\caption{Závislost doby výpočtu na počtu proměnných II}
\label{grafProm2}
\end{center}
\end{figure}

Malé instance byly měřitelné všemi algoritmy, výpočetní čas však výrazně narůstal s rostoucím počtem proměnných u metody {\it komplementu} a {\it BDD}. Program pracující s {\it grafy} poskytoval velmi dobré výsledky, varianta {\it graf II} byla o jeden řád horší. Nejrychlejší byl náš nástroj spolu s knihovnou Espresso, tyto dva programy dosahovaly zhruba stejných a konstantních časů pro tento rozsah proměnných.

Relativně větší instance pak byly řešitelné jen třemi programy a to: naším nástrojem, knihovnou Espresso a nástrojem pracujícím pomocí grafů. Nejrychlejší byl náš nástroj, zhruba 3x pomalejší pak byla knihovna Espresso a zhruba 2-3x pomalejší než knihovna Espresso byl nástroj pracujícím pomocí grafů.

\section{Závislost na počtu termů}
\label{termZavislost}

\begin{table}[h!t]
\caption{Závislost doby výpočtu na počtu termů}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\bf{termů}&\bf{T}&\bf{Kompl.}&\bf{BDD}&\bf{Graf}&\bf{Graf~II}&\bf{Knih.-Espresso}&\bf{Tautology}\\
\hline
10 & 0 & 0,05 & 0,01 & 0,001 & 0,01 & 0,01 & 0,001 \\
\hline
20 & 0 & 0,10 & 0,05 & 0,01 & 0,02 & 0,001 & 0,001 \\
\hline
50 & 0 & 0,02 & 0,28 & 0,001 & 0,05 & 0,001 & 0,001 \\
\hline
100 & 0 & 1,2 & 0,51 & 0,01 & 0,19 & 0,001 & 0,001 \\
\hline
200 & 0 & 1,8 & 2,44 & 0,03 & 0,37 & 0,01 & 0,001 \\
\hline
500 & 0 & 7,5 & 23,61 & 0,06 & 1,61 & 0,01 & 0,001 \\
\hline
1000 & 0 & chyba & 179,61 & 0,14 & 7,84 & 0,5 & 0,01 \\
\hline
\end{tabular}
\end{center}
\label{tabTerm1}
\end{table} 

\begin{figure}[h!t]
\begin{center}
\includegraphics[width=15cm]{obr/graf-pocetTermu1.PNG}
\caption{Závislost doby výpočtu na počtu termů}
\label{grafTerm1}
\end{center}
\end{figure}

Dalším z parametrů, kterým lze charakterizovat danou logickou funkci, je počet jejich součinových termů, nebo-li počet řádků PLA. Víme, že čím více těchto řádků bude, tím vyšší je šance, že daná funkce bude tautologie a tím vyšší by měl být i výpočetní čas na ověření takovéto funkce na tautologii. Následující test byl opět rozdělen pro malé a větší instance.

Pro menší instance byly zvoleny pevné hodnoty počtu proměnných - 20 a procentuální zastoupení DC symbolů na 30\%. Jediným pohyblivým parametrem je tedy počet termů. V tabulce~\ref{tabTerm1} jsou časy potřebné k nalezení řešení u šesti testovaných programů.


V grafu na obrázku~\ref{grafTerm1} je znázorněna závislost doby výpočtu na počtu termů.


Pro větší instance byly zvoleny pevné hodnoty počtu proměnných - 100 a procentuální zastoupení DC symbolů na 50\%. Jediným pohyblivým parametrem je tedy opět počet termů. V tabulce~\ref{tabTerm2} jsou časy potřebné k nalezení řešení u šesti testovaných programů.

\begin{table}[h!t]
\caption{Závislost doby výpočtu na počtu termů II}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\bf{termů}&\bf{T}&\bf{Kompl.}&\bf{BDD}&\bf{Graf}&\bf{Graf~II}&\bf{Knih.-Espresso}&\bf{Tautology}\\
\hline
1000 & 0 & $>200$ & $>200$ & 0,28 & 29,12 & 0,32 & 0,001 \\
\hline
2000 & 0 & $>200$ & $>200$ & 0,51 & 167,17 & 1,001 & 0,01 \\
\hline
5000 & 0 & $>200$ & $>200$ & 3,28 & $>200$ & 7,651 & 0,02 \\
\hline
10000 & 0 & $>200$ & $>200$ & 18,07 & $>200$ & 41,88 & 0,04 \\
\hline
20000 & 0 & $>200$ & $>200$ & 96,04 & $>200$ & $>200$ & 0,07 \\
\hline
50000 & 0 & $>200$ & $>200$ & $>200$ & $>200$ & $>200$ & 0,21 \\
\hline
100000 & 0 & $>200$ & $>200$ & $>200$ & $>200$ & $>200$ & 0,38 \\
\hline
\end{tabular}
\end{center}
\label{tabTerm2}
\end{table} 

V grafu na obrázku~\ref{grafTerm2} je znázorněna závislost doby výpočtu na počtu termů pro větší instance.

\begin{figure}[h!t]
\begin{center}
\includegraphics[width=15cm]{obr/graf-pocetTermu2.PNG}
\caption{Závislost doby výpočtu na počtu termů II}
\label{grafTerm2}
\end{center}
\end{figure}

Malé instance byly měřitelné všemi algoritmy, výpočetní čas však výrazně narůstal s rostoucím počtem termů u metody {\it komplementu} a {\it BDD}. Program pracující s {\it grafy} poskytoval velmi dobré výsledky, varianta {\it graf II} o jeden řád horší. Nejrychlejší byl náš nástroj spolu s knihovnou Espresso, tyto dva programy dosahovaly zhruba stejných a konstantních časů pro tento rozsah proměnných.

Zajímavé výsledky jsme pak obdrželi při testování větších instancí, kde jako nejrychlejší byl ve všech případech náš nástroj na detekci tautologie. U ostatních programů začal čas s rostoucím počtem termů velmi rapidně narůstat a to dokonce i u knihovny Espresso. Velmi zajímavé bude testování v následující podkapitole~\ref{procZavislost}, která se zabývá testováním doby výpočtu v závislosti na procentuální zastoupení DC symbolů a to z toho důvodu, abychom podtvrdili nebo vyvrátili zde vzniklou domněnku, že knihovna Espresso řeší obtížně instance zadání s procentuálním zastoupením DC symbolů kolem 50\%.

\section{Závislost doby výpočtu na procentuálním zastoupení DC symbolů}
\label{procZavislost}

Třetím z parametrů, kterým lze charakterizovat instanci zadání logické funkce, je procentuální zastoupení DC symbolů. V předchozí podkapitole~\ref{termZavislost} jsme z naměřených hodnot vyvodili předpoklad, že knihovna Espresso řeší obtížně instance zadání, kde zastoupení DC symbolů dosahuje kolem 50\%. Zaměříme se tedy podrobnění na testování v tomto rozsahu hodnot. Následující test byl opět rozdělen do tří skupin podle velikosti instancí a do z důvodu možnosti sledování velmi významné závislosti mezi procentuálním zastoupením DC a dobou výpočtu.

Pro první skupinu instancí byly zvoleny pevné hodnoty počtu proměnných - 20 a počtu termů - 600. Jediným pohyblivým parametrem je tedy procentuální zastoupení DC symbolů. V tabulce~\ref{tabProc1} jsou časy potřebné k nalezení řešení u šesti testovaných programů. V grafu na obrázku~\ref{grafProc1} jsou pak tyto výsledky znázorněny graficky.

\begin{table}[h!t]
\caption{Závislost doby výpočtu na procentuálním zastoupení DC}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\bf{DC [\%]}&\bf{T}&\bf{Kompl.}&\bf{BDD}&\bf{Graf}&\bf{Graf~II}&\bf{Knih.-Espresso}&\bf{Tautology}\\
\hline
0 & 0 & 2,07 & 3,41 & 0,10 & 7,01 & 0,01 & 0,001 \\
\hline
20 & 0 & 5,03 & 14,37 & 0,09 & 2,41 & 0,02 & 0,001 \\
\hline
50 & 0 & chyba & 217,22 & 0,01 & 1,89 & 0,25 & 0,02 \\
\hline
55 & 0 & chyba & 101,03 & 0,11 & 1,88 & 0,29 & 0,02 \\
\hline
60 & 0 & chyba & 36,29 & 0,16 & 0,56 & 0,21 & 0,02 \\
\hline
62 & 0 & chyba & 22,32 & 0,13 & 0,46 & 0,17 & 0,02 \\
\hline
64 & 0 & chyba & 19,32 & 0,12 & 0,53 & 0,15 & 0,11 \\
\hline
65 & 1 & chyba & 8,21 & 0,12 & 0,41 & 0,10 & 0,13 \\
\hline
70 & 1 & chyba & 6,85 & 0,39 & 0,33 & 0,04 & 0,03 \\
\hline
90 & 1 & 0,01 & 0,12 & 0,04 & 0,13 & 0,001 & 0,001 \\
\hline
\end{tabular}
\end{center}
\label{tabProc1}
\end{table} 



\begin{figure}[h!t]
\begin{center}
\includegraphics[width=15cm]{obr/graf-procDC1.PNG}
\caption{Závislost doby výpočtu na procentuálním zastoupení DC}
\label{grafProc1}
\end{center}
\end{figure}

Pro druhou skupinu instancí byly zvoleny pevné hodnoty počtu proměnných - 30 a počtu termů - 4096. Jediným pohyblivým parametrem je tedy opět procentuální zastoupení DC symbolů. V tabulce~\ref{tabProc25} jsou časy potřebné k nalezení řešení u šesti testovaných programů.

\begin{table}[h!t]
\caption{Závislost doby výpočtu na procentuálním zastoupení DC II}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\bf{DC [\%]}&\bf{T}&\bf{Kompl.}&\bf{BDD}&\bf{Graf}&\bf{Graf~II}&\bf{Knih.-Espresso}&\bf{Tautology}\\
\hline
0 & 0 & $>300$ & $>300$ & 1,79 & $>300$ & 0,04 & 0,001 \\
\hline
20 & 0 & $>300$ & $>300$ & 1,46 & $>300$ & 0,14 & 0,001 \\
\hline
50 & 0 & $>300$ & $>300$ & 1,35 & $>300$ & 5,05 & 0,01 \\
\hline
55 & 0 & $>300$ & $>300$ & 1,28 & $>300$ & 32,35 & 0,06 \\
\hline
60 & 0 & $>300$ & $>300$ & 1,21 & $>300$ & 60,27 & 0,07 \\
\hline
62 & 0 & $>300$ & $>300$ & 1,43 & $>300$ & 50,21 & 0,08 \\
\hline
64 & 0 & $>300$ & $>300$ & 10,61 & $>300$ & 27,28 & 0,07 \\
\hline
65 & 0 & $>300$ & $>300$ & 16,48 & $>300$ & 16,12 & 0,57 \\
\hline
66 & 0 & $>300$ & $>300$ & $>300$ & $>300$ & 14,52 & 6,52 \\
\hline
67 & 0 & $>300$ & $>300$ & $>300$ & $>300$ & 9,29 & 11,34 \\
\hline
68 & 1 & $>300$ & $>300$ & $>300$ & $>300$ & 10,21 & 30,76 \\
\hline
69 & 1 & $>300$ & $>300$ & $>300$ & $>300$ & 9,37 & 27,11 \\
\hline
70 & 1 & $>300$ & $>300$ & 40,82 & $>300$ & 2,03 & 1,43 \\
\hline
75 & 1 & $>300$ & $>300$ & 1,34 & $>300$ & 1,22 & 0,76 \\
\hline
75 & 1 & $>300$ & $>300$ & 1,34 & $>300$ & 1,22 & 0,76 \\
\hline
80 & 1 & $>300$ & $>300$ & 1,06 & $>300$ & 0,001 & 0,001 \\
\hline
90 & 1 & $>300$ & $>300$ & 0,53 & $>300$ & 0,001 & 0,001 \\
\hline
\end{tabular}
\end{center}
\label{tabProc25}
\end{table} 

V grafu na obrázku~\ref{grafProc25} je znázorněna závislost doby výpočtu na procentuálním zastoupení DC symbolů pro druhou skupinu instancí.

\begin{figure}[h!t]
\begin{center}
\includegraphics[width=15cm]{obr/graf-procDC25.PNG}
\caption{Závislost doby výpočtu na procentuálním zastoupení DC II}
\label{grafProc25}
\end{center}
\end{figure}


Pro třetí skupinu instancí byly zvoleny pevné hodnoty počtu proměnných - 50 a počtu termů - 10000. Jediným pohyblivým parametrem je tedy opět procentuální zastoupení DC symbolů. V tabulce~\ref{tabProc2} jsou časy potřebné k nalezení řešení u šesti testovaných programů.

\begin{table}[h!t]
\caption{Závislost doby výpočtu na procentuálním zastoupení DC III}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\bf{DC [\%]}&\bf{T}&\bf{Kompl.}&\bf{BDD}&\bf{Graf}&\bf{Graf~II}&\bf{Knih.-Espresso}&\bf{Tautology}\\
\hline
0 & 0 & $>780$ & $>780$ & 18,53 & $>780$ & 0,18 & 0,02 \\
\hline
20 & 0 & $>780$ & $>780$ & 27,99 & $>780$ & 0,27 & 0,03 \\
\hline
50 & 0 & $>780$ & $>780$ & 16,13 & $>780$ & 57,22 & 0,03 \\
\hline
60 & 0 & $>780$ & $>780$ & 16,64 & $>780$ & $>780$ & 0,12 \\
\hline
70 & 0 & $>780$ & $>780$ & 17,46 & $>780$ & $>780$ & 0,54 \\
\hline
74 & 0 & $>780$ & $>780$ & 17,65 & $>780$ & $>780$ & 0,69 \\
\hline
75 & 0 & $>780$ & $>780$ & $>780$ & $>780$ & $>780$ & 8,5 \\
\hline
76 & 0 & $>780$ & $>780$ & $>780$ & $>780$ & $>780$ & 15,42 \\
\hline
77 & 0?1 & $>780$ & $>780$ & $>780$ & $>780$ & $>780$ & $>780$ \\
\hline
80 & 0?1 & $>780$ & $>780$ & $>780$ & $>780$ & $>780$ & $>780$ \\
\hline
82 & 0?1 & $>780$ & $>780$ & $>780$ & $>780$ & $>780$ & $>780$ \\
\hline
83 & 1 & $>780$ & $>780$ & 14,71 & $>780$ & 0,001 & 0,03 \\
\hline
84 & 1 & $>780$ & $>780$ & 15,01 & $>780$ & 0,001 & 0,03 \\
\hline
85 & 0 & $>780$ & $>780$ & 14,57 & $>780$ & 0,001 & 0,03 \\
\hline
90 & 0 & chyba & $>780$ & 14,41 & $>780$ & 0,001 & 0,02 \\
\hline
\end{tabular}
\end{center}
\label{tabProc2}
\end{table} 

V grafu na obrázku~\ref{grafProc2} je znázorněna závislost doby výpočtu na procentuálním zastoupení DC symbolů pro větší instance.

\begin{figure}[h!t]
\begin{center}
\includegraphics[width=15cm]{obr/graf-procDC2.PNG}
\caption{Závislost doby výpočtu na procentuálním zastoupení DC III}
\label{grafProc2}
\end{center}
\end{figure}

Z výsledků tohoto testování vyplývají především dvě významné skutečnosti, které jsou nejlépe vidititelné v grafu na obrázku~\ref{grafProc25}. Pro malá procentuální zastoupení DC symbolů nejsou testované instance tautologiemi a programy nemají problémy s nalezením řešení. Začne-li však výskyt DC dosahovat kolem 65\% dojde k efektu, že generované instance začnou být tautologiemi. S roustoucím procentem DC jsou pak již všechny generované instance tautologiemi. Pro kontrolu byl pro generování instancí použit nástroj, který vznikl jako diplomová práce~\cite{mechura} kolegy Tomáše Měchury.

Tento princip lze zobecnit pro každou instanci tak, že pokud neobsahuje dostatečný počet DC symbolů, nemůže být tautologií. Pokud se však pohybujeme na rozmezí, jsou vygenerované instance tzv. \uv{nejhůře detekovatelné}, jejich analýza vyžaduje procházení rekurzivního stromu s nejvyšší hloubkou. Dokonce je možné pro dané rozměry instance (počet proměnných a počet termů) předpovědět, u jaké hranice nastane tento přechod. Vyjdeme přitom z předpokladů třetího speciálního případu\footnote{Viz podkapitola~\ref{realSpecPripady}.}, který definuje spodní mez pro počet DC symbolů. Nebudeme-li uvažovat překryv termů lze tuto hranici spočítat ze vztahu:

 $$ DC = \frac{pocetPromennych - log_{2}(pocetTermu)}{pocetPromennych} $$

Např. u testování středních instancí vychází tato hranice jako 60\%. V grafu na obrázku~\ref{grafProc25} pak můžeme sledovat jaký má tato skutečnost vliv na výpočetní časy testovaných programů. Každá implementace je citlivá na tuto hranici v jiné míře. Knihovna Esppresso má problémy v rozmezí 55-70\% procent, program detekující tautologii pomocí grafů v rozmezí 64-70\% a náš nástroj v intervalu 66-70\%, což významně souvisí s teoreticky vypočtenou hranicí, připočteme-li vliv překryvu termů. Při testování vliv překryvu posouval teoretickou hranici zhruba o 5-6\%. 

\section{Srovnání přístupů k vnitřním reprezentacím}
\label{srovnaniReprezentaci}

V podkapitole~\ref{vnitrniReprezentace} jsme uvedli, že v průběhu vývoje tohoto nástroje na detekci tautologie vznikly dvě verze, z nichž každá používá jinou reprezentaci pro uchování pokrytí zpracovávané logické funkce. Nyní otestujeme výkonnosti obou variant.

V tabulce~\ref{tabSrovnaniReprezentaci} jsou uvedeny časy potřebné pro vyhodnocení řešení dvou verzí nástroje na detekci tautologie. První používá k vnitřní reprezentaci logické funkce strukturu PLA z jádra programu BOOM~II, druhá pak dynamická 2D pole. Graficky je pak toto srovnání vyjádřeno na obrázku~\ref{grafSrovnaniReprezentaci}.

\begin{table}[h]
\caption{Srovnání vnitřních reprezentací}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
\bf{Velikost instance} & & & \\
\bf{proměnných x termů - DC} & \bf{T} & \bf{struktura PLA} & \bf{2D dynamické pole} \\
\hline
30x4096-65 & 0 & 3,72 & 0,51  \\
\hline
50x10000-74 & 0 & 4,46 & 0,76  \\
\hline
50x10000-75 & 0 & 9,36 & 1,78  \\
\hline
30x4096-71 & 1 & 35,76 & 3,07  \\
\hline
30x4096-66 & 0 & 68,91 & 7,07  \\
\hline
\end{tabular}
\end{center}
\label{tabSrovnaniReprezentaci}
\end{table} 

\begin{figure}[h]
\begin{center}
\includegraphics[width=15cm]{obr/graf-srovnaniReprezentaci.PNG}
\caption{Srovnání vnitřních reprezentací}
\label{grafSrovnaniReprezentaci}
\end{center}
\end{figure}

Z naměřených hodnot vyplývá, než přechod na novou reprezentaci pomocí dvourozměrných dynamických přinesl očekávané zrychlení našeho nástroje na detekci tautologie. Toto zrychlení je natolik významné, že se rozhodlo o obdobné změně vnitřní reprezentace v jádru programu BOOM~II, kde se bude pro uchovávání dat logické funkce ve třídě PLA rovněž používat tato efektivnější reprezentace.

\section{Mez pro použití hrubé síly}
\label{odKdyHrubaSila}

V podkapitole~\ref{zakladniSchema}, která se zabývá detekcí speciálních případů, jsme uvedli, že pokud bude testované pokrytí obsahovat sedm a měně proměnných použije se pro jeho vyhodnocení tzv. hrubé síly. Tuto hranici 7 bude nyní chápat jako parametr a ověříme, jak se budou měnit výpočetní časy našeho programu u několika zkušebních instancí. Výsledky jsou shrnuty v tabulce~\ref{tabHrubaSila}.

\begin{table}[h]
\caption{Mez pro použití hrubé síly}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\bf{Velikost instance} & & & & & \\
\bf{proměnných x termů - DC} & \bf{T} & \bf{5} & \bf{7} & \bf{9} & \bf{11} \\
\hline
30x4096-65 & 0 & 0,56 & 0,51 & 0,54 & 0,82  \\
\hline
50x10000-74 & 0 & 0,68 & 0,67 & 0,67 & 0,67  \\
\hline
50x10000-75 & 0 & 1,49 & 1,48 & 1,48 & 1,89  \\
\hline
30x4096-71 & 1 & 3,09 & 3,07 & 3,07 & 3,11  \\
\hline
30x4096-66 & 0 & 7,36 & 7,07 & 7,21 & 11,85  \\
\hline
\end{tabular}
\end{center}
\label{tabHrubaSila}
\end{table}

Tento test potvrdil, že jako nejvýhodnější hranice, od kdy lze použít k vyhodnocení daného pokrytí hrubou sílu, je počet sedmi proměnných. Jiné hranice nepřinášely ve většině případů o mnoho horší výsledky, avšak byla-li by tato mez vyšší jak deset, vedlo by to k zhoršení efektivnosti našeho programu, viz např. poslední řádek v tabulce~\ref{tabHrubaSila} pro mezní hodnotu 11. 

\section{Přínos unátní redukce a redukce komponent}
\label{prinosUnatniAKomponent}

V této podkapitole se zaměříme na unátní redukci a redukci komponent a budeme zjišťovat, jaký mají tyto funkce vliv na efektivnost našeho algoritmu. Test provedeme na čtyřech vygenerovaných instancích s parametry 50 proměnných, 10000 termů a 76\% DC. Analyzovat je budeme naším nástrojem a to ve čtyřech variantách: s unátní redukcí i redukcí komponent (U+K), pouze s unátní redukcí (U-), pouze s redukcí komponent (-K) a nakonec ani s jednou touto funkcí (--). Výsledky tohoto testu jsou v tabulce~\ref{tabUnKomp}. Dále jsou v této tabulce uvedeny i počty komponent, unátních sloupců a rekurzivních volání.

\begin{table}[h]
\caption{Vliv unátní redukce a redukce komponent na výkonnost}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
\bf{instance} & \bf{T} & \bf{U+K} & \bf{U-} & \bf{-K} & \bf{--} & \bf{\# un. sloupců} & \bf{\# komp.} & \bf{\# rekurzí}\\
\hline
I & 0 & 3,54 & 2,70 & 3,53 & 2,63 & 915 & 24 & 41932 \\
\hline
II & 0 & 1,68 & 1,31 & 1,67 & 1,32 & 494 & 16 & 19410 \\
\hline
III & 0 & 1,21 & 0,89 & 1,23 & 0,87 & 234 & 4 & 7110 \\
\hline
IV & 0 & 3,55 & 2,71 & 3,58 & 2,74 & 763 & 26 & 41474 \\
\hline
\end{tabular}
\end{center}
\label{tabUnKomp}
\end{table}

Z výsledků totoho testu vyplývá, že redukce komponent u těchto instancí výkonnost mírně zhoršuje. To je způsobeno zřejmě tím, že dochází pouze k detekci nejvíce dvou komponent z nichž jedna je téměř stejně velká jako celé původní pokrytí, což nepřinese velké zrychlení v důsledku očekávaného snížení počtu rekurzivních volání. Navíc je detekování takovéto komponenty časově náročnější než zrychlení, které nám detekce přinese. Detekci komponent je proto výhodné provádět pouze u některých instancí (s vysokým procentem DC).

Unátní redukce přinesla jen velmi malý nárůst výkonnosti a to zřejmě kvůli tomu, že počet detekovaných unátních sloupců je zhruba 2000 menší než počet rekurzivních volání, proto touto redukcí ušetříme u testovaných instancí jen pouze několik málo procent z celkového počtu rekurzivních volání.

\section{Srovnání kompilací MS Visual Studia a Dev-C++}
\label{srovnaniDevMS}

V podkapitole~\ref{volbaProstredi} jsme uvedli, že podrobíme testu náš nástroj, bude-li zkompilován pomocí vývojového prostředí Dev-C++ a nebo MS Visual Studia. V tabulce~\ref{tabDevMS} jsou pak časy potřebné pro nalezení řešení pro obě varianty našeho programu. Tyto hodnoty jsou pak vyneseny do grafu na obrázku~\ref{grafDevMS}

\begin{table}[h!t]
\caption{Srovnání kompilací MS Visual Studia a Dev-C++}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
\bf{Velikost instance} & & & \\
\bf{proměnných x termů - DC} & \bf{T} & \bf{MS Visual Studio} & \bf{Dev-C++} \\
\hline
30x4096-65 & 0 & 1,21 & 0,51  \\
\hline
50x10000-74 & 0 & 1,45 & 0,76  \\
\hline
50x10000-75 & 0 & 4,73 & 1,78  \\
\hline
30x4096-71 & 1 & 11,59 & 3,07  \\
\hline
30x4096-66 & 0 & 17,82 & 7,07  \\
\hline
\end{tabular}
\end{center}
\label{tabDevMS}
\end{table} 

\begin{figure}[h!t]
\begin{center}
\includegraphics[width=15cm]{obr/graf-MSvsDEV.PNG}
\caption{Srovnání kompilací MS Visual Studia a Dev-C++}
\label{grafDevMS}
\end{center}
\end{figure}

Ukázalo se, že kompilace, kterou jsme vytvořily pomocí MS Visual Studia 2005 je zhruba 3x pomalejší než program přeložený pomocí Dev-C++.

\section{Zhodnocení naměřených výsledků}

Shrneme-li výsledky, které jsme obdrželi v předcházejících kapitolách zabývajících se testováním programů uvedených v tabulce~\ref{tabPrehled}, můžeme tvrdit, že jako nejuniverzálnější nástroj na detekci tautologie je náš program, který dosahoval nejlepších výsledků u drtivé většiny případů. Velmi dobrých výsledků dosahovala i knihovna z nástroje Espresso, která však byla více citlivá na procentuální zastoupení DC, počet termů i počet proměnných. Ostatní programy dosahovaly výrazně horší výkonnosti, výjimečně poskytoval rychlá řešení program detekující tautologii pomocí grafů a to někdy i rychleji než knihovna z nástroje Espresso - viz např. graf~\ref{grafProc25}.

Velmi významným poznatkem z testování byl objev hranice procentuálního zastoupení DC symbolů u níž dochází při generování instancí k přechodu mezi tautologiemi a ne-tautologiemi. V podkapitole~\ref{procZavislost} jsme ukázali způsob, jak tuto hranici vypočítat. Budeme-li generovat instance s procentuálním zastoupením v oblasti blízké ($\pm$ jednotky procent) tomuto přechodu, budeme získávat logické funkce, které budou obtížněji vyhodnotitelné než ty se stejným počtem proměnných a termů. Každý program byl jinak citlivý na tuto hranici, viz graf~\ref{grafProc25}. Nejuzší interval, ve kterém algoritmus potřeboval výrazně vyšší čas, měl náš nástroj na detekci tautologie.

Dalším významným přínosem testování bylo potvrzení efektivnosti nového způsobu vnitřní reprezentace analyzované logické funkce. Toto zrychlení je natolik významné, že se rozhodlo o obdobné změně vnitřní reprezentace v jádru programu BOOM~II.

Zjistilo se také, že kompilace našeho projektu pomocí vývojového prostředí Dev-C++ je zhruba asi 3x rychlejší než pomocí MS Visual Studia 2005.

\clearpage
\section{Možnosti kombinace různých algoritmů}

Podle zadání této diplomové práce jsme měli uvažovat také možnost kombinace různých algoritmů pro detekci tautologie, za účelem optimalizace rychlosti. Jediným případem, kdy náš program nenalézal řešení nejrychleji, byl interval zhruba 5\% v okolí přechodu mezi tautologiemi a ne-tautologiemi, viz podkapitola~\ref{procZavislost}. V těchto případech byla rychlejší knihovna z nástroje Espresso. Zde se nabízejí dva možné postupy, buď se pokusit analyzovat proč je právě knihovna Espresso v této oblasti výkonnější (a to i případným prostudováním zdrojových kódů Esppressa) a doplnit náš nástroj o tyto poznatky a nebo můžeme náš nástroj upravit tak, aby při rozpoznání, že pracuje s instancí, která spadá do tohoto intervalu, použil k její analýze funkci z nástroje Espresso. Identifikace takovýchto logických funkcí by pak probíhala pomocí vztahu, který jsme uvedli v podkapitole~\ref{procZavislost}.
