\chapter{Bmin -- Boolean minimizer}
\label{chap:bmin}

\bmin{} je implementační částí této diplomové práce. V~následující sekci je popsána analýza výběru prostředku použitých
v~implementaci. Ve~zbytku kapitoly jsou pak popsány jednotlivé části aplikace.

\section{Analýza}
\label{sec:analize}

Zadané požadavky na~aplikaci byly následující:
\begin{itemize}
\item Vytvořit aplikaci pro~vizualizaci běhu algoritmů minimalizace logických funkcí, konkrétně algoritmů
  Quine--McCluskey a Espresso.
\item Zobrazit průběh výše zmíněných algoritmů v~Karnaughově mapě a 3-rozměrné krychli.
\item Oddělit výpočetní jádro od~grafického rozhraní.
\item Nezávislost na~platformě.
\end{itemize}

Nejprve tedy bylo třeba vybrat vhodný programovací jazyk. Z důvodu rychlosti a mých programovacích znalostí jsem zvolil
jazyk C++. Navíc jsem se rozhodl pro použití knihovny STL \cite{stl}. Ta je standardní součástí programového vybavení
každého operační systému a~splňuje tak podmínku nezávislosti na~platformě. Ostatní podpůrné knihovny, kromě grafické
(viz dále), nebyly použity, protože by bylo těžší zaručit zmíněnou nezávislost na platformě.

Podporované platformy byly vybrány pouze dvě, a to Windows a Linux. K~testování na ostatních platformách, především
Mac OS X, jsem bohužel neměl prostředky. Na každé platformě je trochu odlišný způsob instalace. Více informací, včetně
instalačních pokynů, je možné nálezt v~dodatku \ref{chap:install}.

Pro~grafickou část aplikace byla zvolena knihovna Qt \cite{qt} . Hlavní důvod jejího výběru je spíše historický (viz
sekce \ref{sec:vyvoj}). Přesto bych ale knihovnu zvolil, i kdybych s~aplikací začínal znovu. Důvodem je především její
nezávislost na platformě, otevřenost, obsáhlost a~neustálé zdokonalování. Qt totiž patří společnosti Nokia, která
do~jejího vývoje investuje velké prostředky. Navíc nabízí i svoje vývojové prostředí Qt Creator, které velice usnadňuje 
práci.

Bylo zároveň třeba vybrat vhodný grafický způsob zobrazení 3-rozměrné krychle. V~tomto ohledu bylo možné zvolit pouze
knihovnu OpenGL \cite{opengl}, protože knihovna DirectX \cite{directx} není multiplatformní. OpenGL je navíc součástí
Qt.

Při požadavku na~platformě nezávislou aplikaci a použití OpenGL existuje pouze jedna alternativní knihovny místo
Qt. Jedná se o~wxWidgets \cite{wx}. S touto knihovnou mám osobní zkušenosti a i když není špatná, zdaleka nedosahuje
kvalit Qt. Především systém událostí ve~wxWidgets je poněkud těžkopádný. Navíc chybí \emph{model and view framework},
který je velmi užitečný.

Aby došlo k~oddělení výpočetního jádra, byla aplikace rozdělena na tři části:
\begin{itemize}
\item Hlavní částí je jádro aplikace nebo-li \bmink{}. V~něm jsou implementovány oba výše zmíněné minimalizační
  algoritmy. Dále jsou v~něm třídy pro~reprezentaci termu a logické funkce včetně speciálního kontejneru pro~množinu
  termů. Jádro nabízí i poměrně propracovaný systém událostí. Součástí jsou struktury pro~reprezentaci Karnaughovy mapy,
  n-krychle a informací z~průběhu algoritmu Quine-McCluskey a Espressa. 
\item Další částí je tzv. \bmins{}. Jak název napovídá, umožňuje použití aplikace v~příkazovém řádku. Příkazový řádek je
  však podporován pouze v~Linuxu. Důvodem je platformě specifické chování, které je detailněji
  rozebráno v~sekci \ref{sec:konsole}. Konzolové spouštění však není jediný účel části \bmins{}. Jsou v~ní totiž
  zpracovávány uživatelem zadané textové vstupy. Těmi jsou různé příkazy a také zadání funkce ve výčtovém nebo PLA
  formátu. 
\item Poslední a nejrozsáhlejší částí je \bminq{}. Jedná se o~grafické rozhraní, které se stará o veškerou
  vizuální komunikaci s~uživatelem\footnote{Samozřejmě pokud není brána v~úvahu konzolová část.}. Je použita knihovna Qt
  s~podporou OpenGL \cite{opengl}, jenž slouží pro~vykreslení 3D krychle. Grafické rozhraní má mnoho nejrůznějších
  funkcí, které budou všechny popsány v sekci \ref{sec:qtgui}.
\end{itemize} 

\begin{figure}[hbt]
  \centering
  \includegraphics{figures/BminComponentModel}
  %\includegraphics{figures/map1}
  \caption{Závislost částí \bmin{}}
  \label{fig:bmin-comp}
\end{figure}

Vzájemné závislosti mezi všemi částmi v~\bmin{} ukazuje obrázek \ref{fig:bmin-comp}. Na~něm je vidět, že část \bmink{}
je zcela nezávislá. \bmins{} závisí pouze na~části \bmink{}. Může s~ní být zároveň samostatně použita jako konzolová
aplikace (samozřejmě pouze v~Linuxu). Část \bminq{} závisí jak na~\bmink{}, tak na~\bmins{}. 

\newpage

Následující sekce podrobně popisují jednotlivé části.
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  Kernel


\section{\bmink}
\label{sec:kernel}

\bmink{} je hlavní částí aplikace. Obsahuje všechny zabudované  algoritmy pro~minimalizace, různé kontejnery, speciální
struktury a~také vlastní systém událostí. Cílem této kapitoly je popsat architekturu jádra a některé důležité části
(především minimalizační algoritmy). Jejich teoretický základ je popsán v~kapitole \ref{chap:mini}. Tato sekce popíše jejich
implementační specifika v~\bmin{}.  


\subsection{Architektura}
\label{sec:structure}

Architektura části \bmink{} je poměrně komplikovaná. Zjednodušené rozložení hlavních tříd ukazuje Obrázek
\ref{fig:kernel-classes}. V~tomto UML diagramu nejsou obsaženy některé vedlejší třídy a jsou také vynechány některé
nedůležité propojení, které slouží ke zjednodušení implementace.

\begin{figure}[hbt]
  \centering
  \includegraphics{figures/KernelClassModel} 
  \caption{Rozložení tříd v~části \bmink{}}
  \label{fig:kernel-classes}
\end{figure}

Hlavní třídou je \code{Kernel}. Ta existuje pouze v~jediné instanci\footnote{Jedná se tedy o~Singleton pattern
  \cite{wiki-singleton}.} a je zodpovědná za~propojení všech ostatních tříd. Slouží tak jako přístupový bod pro~ostatní
části \bmin{}. Ty mohou buď přímo volat některé metody \code{Kernel}, nebo mohou podědit třídu \code{Events} a
předefinovat některé její virtuální metody, které pak \code{Kernel} volá  automaticky, když nastane některá
událost. Více o~událostech je uvedeno v~sekci \ref{sec:events}. Třída \code{Kernel}  také obsahuje kontejner pro~logické
funkce, přičemž vždy pouze jedna je zvolena jako aktuální. Na ní jsou vykonávány všechny požadované operace. 

Logická funkce je reprezentována třídou \code{Formula}. Ta je zodpovědná především za~manipulaci s~proměnnými. Současný
limit je nastaven na~\textbf{10 proměnných}. Důvodem je hlavně nevyužitelnost většího počtu proměnných ve~vizualizačních
metodách. Pro uchování termů \code{Formula} využívá třídu \code{TermsContainer}. Jedná se o~obecný kontejner, který
umožňuje přidávání, odebírání a zpřístupňování termů. Navíc má důležitou úlohu při~změně reprezentace s~DNF na~KNF
(resp. s~KNF na~DNF). Automaticky dopočítává \offset{} (resp. \onset{}) jako komplement $\onset \cup \dcset$
(resp. $\offset \cup \dcset$). To provádí pouze s~mintermy (resp. maxtermy). Implementačně je \code{TermsContainer}
postaven na třídě \code{std::vector}, ale je napsán tak, aby bylo možné interní kontejner v budoucnu vyměnit. Pro lepší
výkonnost se nabízí třída \code{std::list} nebo vlastní kontejner v~podobě ternárního stromu
\cite{wiki-ternary-tree}. Samotný term je reprezentován třídou \code{Term} a~bude podrobně popsán v~sekci
\ref{sec:term}.  

Oba minimalizační algoritmy jsou v~samostatných třídách. Jedná se o třídy \code{Espresso} a \code{QuineMcCluskey}. Obě
jsou potomky abstraktní třídy \code{MinimizingAlgorithm}, která definuje abstraktní metodu \code{minimize(bool
  debug)}. Ta je volána při požadavku na~minimalizaci. Parametr \code{debug} určuje, zda je třeba generovat dodatečná
data z~průběhu algoritmu, která jsou využívána při jeho zkoumání. Třída \code{MinimizingAlgorithm} zároveň specifikuje,
že po~skončení minimalizace bude logická funkce uložena jak v~úplné, tak v~minimalizované formě. Uchovávají se tedy dvě
funkce. O~výběr a volání algoritmu se stará třída \code{Kernel}. Detailní popis třídy \code{Espresso} je v~sekci
\ref{sec:espresso-class} a třídy \code{QuineMcCluskey} v~sekci \ref{sec:qm-class} 

Poslední dvě třídy, které zaslouží bližší popis jsou \code{Cube} a \code{KMap}. První jmenovaná slouží, jak už název
napovídá, jako interní struktura pro~n-krychli. Kromě toho, že zastřešuje aktuální logickou funkci, nabízí také
speciální kontejner pro označení vybraných termů jak z~minimální, tak z úplné funkce. Třída \code{KMap} má podobný
význam jako \code{Cube} s rozdílem, že je to interní struktura pro~Karnaughovu mapu. Oproti \code{Cube} je však mnohem
propracovanější a obsahuje některé zajímavé prvky. Je jí proto věnována samostatná sekce \ref{sec:kmap-class}.

\newpage

\subsection{Události}
\label{sec:events}

Architektura událostí v~\bmin{} je postavena na~modelu dědičnosti. Pro tyto účely je vytvořena speciální třída
\code{Events}, která obsahuje pouze virtuální metody. Ty slouží jen k~předefinování a nic tedy nedělají. Pokud některá
z~tříd mimo část \code{Kernel} chce být zapojena do~systému událostí, tak stačí, aby podědila třídu \code{Events}
a~předefinovala metody, které potřebuje. Napojení na třídu \code{Kernel} je zajištěno tak, že konstruktor třídy 
\code{Events} vloží odkaz na~svou instanci do~kontejneru s~událostmi v~\code{Kernel}. Když pak nastane nějaká
událost, \code{Kernel} volá dané metody všech instancí v~kontejneru s~událostmi.

Tento způsob je výhodný zejména pokud neexistuje mnoho tříd, které potřebují registrovat pouze jednu nebo několik málo
událostí. Potom by docházelo ke~zbytečnému volání mnoha prázdných metod. Pro~tyto účely je vhodnější architektura
založená na~callback funkcích \cite{wiki-callback}. \bmin{} je však vytvořen tak, že dědičnost událostí je pro~něj
nejvýhodnější.  

Část \bmink{} generuje celkem 14 událostí. Následující seznam vypisuje prototypy a popis funkcí pro každou událost.

\begin{list}{}{%
    \setlength{\leftmargin}{1.5cm}
    \setlength{\rightmargin}{1.0cm}
    \setlength{\itemindent}{0.5cm}
    \newcommand{\desc}[1]{\ \\\textsl{#1}}
    \renewcommand{\makelabel}[1]{\code{#1;}}}
\item[virtual void evtFormulaCanged(Formula *f)] 
  \desc{Událost je vyvolána při~změně aktuální logické funkce. Ta je také předána jako argument \code{f}}. 
\item[virtual void evtFormulaRemoved()] 
  \desc{Událost je vyvolána při~odstranění aktuální logické funkce. Po~této události je aktuální funkce prázdná.}
\item[virtual void evtFormulaMinimized(Formula *f, MinimizeEvent \&evt)] 
  \desc{Událost je vyvolána po~minimalizaci logické funkce. Ta je zároveň předána jako argument \code{f}. Druhým
    argumentem \code{evt} je instance třídy \code{MinimizeEvent}, která obsahuje informace o~provedené
    minimalizaci. Konkrétně jaký algoritmus byl použit, zda se ukládaly dodatečné informace o~minimalizaci a některé
    další informace.} 
\item[virtual void evtMinimalFormulaChanged(Formula *mf)]
  \desc{Událost je vyvolána po změně minimální funkce, což se děje v~podstatě pouze při~krokování Espressa. Nová funkce
    je zároveň předána jako argument \code{mf}.}
\item[virtual void evtFormulasSet(unsigned idx)]
  \desc{Událost je vyvolána, pokud byla vybrána nová aktuální logická funkce z~kontejneru všech uložených funkcí. Zároveň
    je jako argument předáno její číslo.}
\item[virtual void evtAlgorithmChanged(Kernel::Algorithm alg)]
  \desc{Událost je vyvolána při~změně algoritmu, jehož typ je zároveň předán jako argument \code{alg}}
\item[virtual void evtError(std::exception \&exc)]
  \desc{Událost je vyvolána, pokud uživatel provede nějakou nepřípustnou operaci. Těch je poměrně velký počet. Například
    pokud zadá špatný textový formát funkce, požaduje větší počet proměnných než je povoleno a mnoho dalších.}
\item[virtual void evtExit()]
  \desc{Událost je vyvolána těsně před~ukončením aplikace.}
\item[virtual void evtHelp()]
  \desc{Událost je vyvolána, pokud uživatel žádá nápovědu.}
\item[virtual void evtShowEspresso(EspressoData *)]
  \desc{Událost je vyvolána při~požadavku na~krokování průběhu algoritmu Espresso. Data o~průběhu algoritmu jsou předána
    jako argument \code{data}.}  
\item[virtual void evtShowQm(QuineMcCluskeyData *data)]
  \desc{Událost je vyvolána při~požadavku na~zobrazení průběhu algoritmu Quine--McCluskey. Dodatečná data o~průběhu
    algoritmu jsou předána jako argument \code{data}.}
\item[virtual void evtShowKmap(KMap *kmap)]
  \desc{Událost je vyvolána při~požadavku na~zobrazení Karnaughovy mapy. Argument \code{kmap} obsahuje interní
    reprezentaci K-mapy.}
\item[virtual void evtShowCube(Cube *cube)]
  \desc{Událost je vyvolána při~požadavku na~zobrazení Booleovské n-krychle. Argument \code{cube} obsahuje interní
    reprezentaci n-krychle.}
\item[virtual void evtShowFce(Formula *of, Formula *mf)]
  \desc{Událost je vyvolána při~požadavku na~vypsání logické funkce. Argument \code{of} představuje funkci v~úplném tvaru
    a~\code{mf} v~minimalizovaném tvaru. V~případě, že minimalizace neproběhla, je \code{mf} rovna \code{NULL}.}
\end{list}

\subsection{Term}
\label{sec:term}
Třída \code{Term} slouží k~reprezentaci termu. Obsahuje velký počet užitečných metod pro~práci s~termem včetně operací
pro~porovnání, produkt, komplement a inverzi. Jsou zde i metody pro~výpočet kofaktoru a delta vzdálenosti vzhledem
k~jinému termu. Lze také zjistit, zda daný term pokrývá některý jiný a případně i vygenerovat všechny mintermy, které
daný term pokrývá. Samozřejmě nechybí ani metody pro~převod do~textového tvaru. Na~výběr je jak binární výpis, tak
výčtový výpis, v němž jsou uvedeny indexy všech mintermů, které daný term pokrývá.

Vnitřní reprezentace je postavena na dvou číselných maskách. Obě jsou typu \code{term\_t}, což je \code{typedef}
pro~\code{int}. Každé proměnné z~logické funkce náleží jeden bit v~každé masce. Teoretický maximální počet proměnných je
tedy na~většině počítačů 31, což o~21 proměnných převyšuje limit daný třídou \code{Formula}. První maska určuje literály
s~hodnotou 1. Pozice, kde má bit v masce hodnotu 1 znamená, že literál na stejné pozici má hodnotu 1. Druhá maska je
pro~literály s~hodnotou 2, tedy chybějící literály. Například term $x_1\ol{x}_2x_4$ z~funkce o~čtyřech proměnných by měl
první masku rovnu hodnotě $1001_2 = 9_{10}$. Druhá maska by pak byla rovna $0100_2 = 4_{10}$, protože chybí proměnná
$x_3$, která je na~třetí pozici.

\newpage
Pro reprezenataci literálu je zároveň vytvořena třída \code{LiteralValue}, která usnadňuje testování jeho hodnot. Dále
také definuje jejich textovou podobu. Metody pro~získání či uložení hodnoty literálů v~třídě \code{Term} využívají právě
třídy \code{LiteralValue}. Její obdobou pro~výstupní hodnoty logické funkce je třída \code{OutputValue}, která má velmi
podobnou strukturu.  

Třída \code{Term} má navíc speciální rozšíření pro~\textbf{Espresso}. Kromě výše zmíněného výpočtu kofaktoru umožňuje
spočítat výsledek operace $\sqcup$ popsané v~sekci \ref{sec:sccc}. Významně také usnadňuje expanzi termu podle množiny
\setname{L}. Zároveň má metody pro~transformaci termu podle v~argumentu zadaného termu na řádek blokovací matice nebo
matice pokrytí, které jsou použity v~proceduře \eproc{EXPAND} popsané v~sekci \ref{sec:expand}.

\code{Term} má mnoho příznaků. Všechny uvádí Tabulka \ref{tab:term-flags}. Většina, ale ne všechny, slouží k~vykonávání
algoritmu \textbf{Espressa}. U těch, které slouží pouze pro~tyto účely je uvedeno kurzivou v~závorce
\textit{(Espresso)}.

\vspace{5ex}

\begin{table}[hb]
  \centering
  \begin{tabular}{|l|p{10cm}|}
    \hline
    \textbf{Příznak} & \textbf{Význam} \\
    \hline\hline
    \code{ONE} &  Term náleží do~\onset{}. Význam má především ve výpisech termu. Rozlišuje se tak, zda se jedná o~DNF
    či KNF. V~algoritmech je však většinou ignorován.  \\ 
    \hline
    \code{DC} &  Term náleží do~\dcset{}. Často používán, pokud se pracuje s~jednou množinou termů  vzniklou sjednocením
    \onset{} a \dcset{}, tedy pokud se pracuje s~pokrytím $\cover \equiv \onset \cup \dcset$. Umožňuje tak odlišit termy
    z~\dcset{}. \\  
    \hline
    \code{INVALID} & Term je neplatný nebo prázdný (neexistuje). Často používán v~operacích produkt a~kofaktor
    pro~návrat prázdného termu. Term s~tímto příznakem tedy představuje symbol $\emptyset$. \\ 
    \hline
    \code{PRIME} &  Term je přímým implikantem. \textit{(Espresso)}\\
    \hline
    \code{NONESSEN} & Term není nesporný přímý implikant. \textit{(Espresso)}\\
    \hline
    \code{ACTIVE} &  Term je aktivní. Jedná se o~pomocný příznak k~odlišení určitého termu. \textit{(Espresso)}\\
    \hline
    \code{REDUND} &  Term je redundantní. \textit{(Espresso)}\\
    \hline
    \code{COVERED} & Term je pokryt nějakým jiným termem v~pokrytí. \textit{(Espresso)}\\
    \hline
    \code{RELESSEN} & Term je relativní nesporný přímý implikant (viz sekce \ref{sec:expand}). \textit{(Espresso)}\\
    \hline
  \end{tabular}
  \caption{Příznaky třídy \code{Term}}
  \label{tab:term-flags}
\end{table}

\newpage
\subsection{QuineMcCluskey}
\label{sec:qm-class}
Implementace algoritmu Quine--McCluskey je pravděpodobně nejstarší částí v~celém \bmin{}. Původně pařila do~třídy
\code{Formula}. Postupem času se však osamostatnila a byla pro~ni vytvořena nová třída \code{QuineMcCluskey}, která je
potomkem \code{MinimizingAlgorithm}.

Algoritmus Quine--McCluskey byl podrobně popsán v~sekci \ref{sec:qm}. V této sekci bude popsán způsob jeho implementace
a~dále také způsob uchování informací o~jeho průběhu, k~čemuž slouží třída \code{QuineMcCluskeyData}.

\subsubsection{Implementace algoritmu}
\label{sec:qm-class-impl}
Implementace je rozdělena do~dvou kroků. Nejprve jsou nalezeny přímé implikanty a~poté z~nich získáno minimální
pokrytí. Ještě před tím jsou vytvořeny dvě instance logické funkce v úplné formě. První se jmenuje \code{of} a slouží
pro~uchování originální logické funkce. Druhá se jmenuje \code{mf} a představuje novou minimální funkci.

Hledání přímých implikantů začíná vytvořením pole polí nebo-li matice STL listů, která představuje matici seznamů
popsanou v~sekci \ref{sec:qm}. Do~seznamů v~prvním sloupci matice jsou následně rozděleny minterm (resp. maxtermy) podle
počtu  jedniček (resp. nul).  K průchodu tabulkou slouží dvouúrovňový cyklus, jehož vnější cyklus prochází všechny
sloupce a~vnitřní všechny řádky, se kterých se vždy vyberou dva sousední seznamy. V~nich se termy kombinují každý
s~každým. Pokud existuje jejich konsensus, tak se přidá do~seznamu v~sousedním sloupci. Zároveň se z~\code{mf} odstraní
oba kombinované termy a přidá se jejich konsensus. Po~skončení cyklu jsou v~\code{mf} pouze přímé implikanty. Složitost
hledání přímých implikantů je v~této implementaci $O(n \cdot m^2)$, kde $n$ je počet proměnných a $m$ je počet mintermů
(resp. maxtermů).

Získání minimálního pokrytí je zahájeno vytvořením tabulky pokrytí. Jedná se o~matici \code{bool} hodnot, přičemž každý
sloupec reprezentuje jeden minterm (resp. maxterm) a každý řádek jeden přímý implikant. Na~pozici, kde přímý implikant
implikuje minterm je hodnota nastavena na~\code{true}. Všude jinde je hodnota \code{false}. Nejprve se z~tabulky
odstraní nesporné přímé implikanty. To jsou ty, které mají jako jediné v~některém sloupci hodnotu
\code{true}. Odstranění se provádí tak, že se nastaví na~\code{false} celý řádek reprezentující odstraňovaný přímý
implikant a zároveň se na~\code{false} nastaví i~všechny sloupce, ve kterých byla v tomto řádku hodnota 
\code{true}. To značí, že jsou dané mintermy pokryty a nepotřebují tedy být pokryty jinými přímými
implikanty. Po~odstranění nesporných přímých implikantů je třeba vybrat minimální množinu zbylých přímých
implikantů. K~tomuto účelu je zvolena \mbox{\textbf{heuristika}}, která postupně odstraňuje přímé implikanty podle počtu 
hodnot \code{true} ve~svém řádku. Nejprve jsou odstraněny ty, které mají nejvíce hodnot \code{true}. To znamená ty,
které pokrývají nejvíce ještě nepokrytých mintermů (resp. maxtermů). Při odstraňování se každý přímý implikant uloží
do~samostatného seznamu, který reprezentuje finální minimální pokrytí. Vhledem k~použití heuristiky se ale nemusí jednat
o~optimální řešení. Pro funkce do~10 proměnných řešení v~naprosté většině případů optimální je. To je také důvod výběru
heuristiky namísto exaktního řešení.

\newpage
\subsubsection{QuineMcCluskeyData}
\label{sec:qm-class-data}
V~případě že je metoda \code{minimize} volána s~parametrem \code{debug} nastaveným na~\code{true}, tak jsou během
provádění algoritmu ukládána ještě dodatečná data. K~jejich uložení slouží třída \code{QuineMcCluskeyData}. Jedná se
o~speciální kontejner. Nejprve dojde k~jeho inicializaci. Uloží se počet proměnných a určí se, zda se jedná o~DNF či
o~KNF.  V průběhu hledání přímých implikantů se do~něj nejprve vloží všechny mintermy (resp. maxtermy) a během smyčky se
do~něj vkládají všechny nově vzniklé implikanty. K~jejich uložení slouží STL vektor obsahující STL listy s~termy, což se
v~C++ zapíše jako \code{std::vector<std::list<Term> >}. Není tedy již použita matice, místo toho se sloupce a řádky
mapují pomocí mapovací funkce, která je zároveň použita i pro~tabulku pokrytí. Ta je reprezentována množinou
\code{std::set}. Zároveň jsou do~samostatných kontejnerů typu \code{std::vector} uloženy všechny přímé implikanty
a~původní mintermy.

Výhodou třídy \code{QuineMcCluskeyData} je jednoduchý způsob ukládání dat v~průběhu minimalizace. Zároveň je možné
získaná data rychle a přehledně zpřístupnit jiným třídám, čehož také využívají části \bmins{} a \bminq{}.


\subsection{Espresso}
\label{sec:espresso-class}
Espresso, jehož algoritmus je vysvětlen v~sekci \ref{sec:espresso}, je v~\bmin{} implementováno v~poměrně zjednodušené
podobě. Úplně chybí všechny procedury uvedené v sekci \ref{sec:others}, které slouží především k~rychlostnímu vylepšení
heuristiky, což v~\bmin{} není příliš podstatné. Zároveň není implementována ani procedura \eproc{LAST-GASP}. Pro~funkce
o~malém počtu proměnných by se její účinek vůbec neprojevil. To ale platí i~pro~proceduru \eproc{REDUCE}, která ovšem
součástí \bmin{} je. Důvodem je lepší ozřejmění chování algoritmu uživateli, který si může její výsledek prohlédnou
při~krokování algoritmu. Dalšími implementovanými procedurami jsou \eproc{EXPAND} a \eproc{IRREDUNDANT}, které jsou
nezbytné pro správnou minimalizaci. Následující podsekce uvádějí podrobnější popis jednotlivých částí Espressa
v~\bmin{}.     

\subsubsection{Hlavní smyčka}
\label{sec:ec-loop}
Hlavní smyčka je vzhledem k~chybějícím procedurám velmi zjednodušena. Protože procedura \eproc{LAST-GASP} není
implementována, stačí pouze jednoúrovňový cyklus. Ještě před tím než je započat, získají se \onset{}, \dcset{},
\offset{}. Ty jsou ve~formě mintermů. Poté se ještě inicializují ceny a~začíná cyklus. V~něm jsou postupně prováděny
procedury \eproc{EXPAND}, \eproc{IRREDUNDANT} a \eproc{REDUCE}. Po každé je testována, zda se změnila cena od~jejich
posledního vykonání. Pokud ano, je cyklus ukončen. Jinak se pokračuje. Po~skončení cyklu se z~\onset{} vytvoří nová
instance třídy \code{Formula}, která představuje novou minimální funkci. Vše je pro~lepší přehlednost zapsáno formou
pseudokódu na~obrázku \ref{fig:bmin-espresso}. Z~něj je patrné, že smyčka v~\bmin{} se o~proti smyčce uvedené v~sekci
\ref{sec:main-loop} výrazně liší. Možná by šlo říci, že se vlastně nejedná o~Espresso. Je ale třeba podotknout, že
výsledná sekvence procedur bude pro~velkou většinu funkcí do 10 proměnných stejná (samozřejmě s~vynecháním
\eproc{LAST-GASP}).  

\newpage


\begin{figure}[hbt]
  \ttfamily\footnotesize
  \begin{tabular}{ll}
  ESPRESSO(\onset,\dcset) \{\\
  \mbox{\ \ }\offset{} $\gets$ COMPLEMENT(\onset{},\dcset{}) & // Vypočte komplement (počítáno z~mintermů).\\
  \mbox{\ \ }$c_1 \gets c_2 \gets c_3 \gets$ COST(\onset) & // Inicializuje ceny.\\
  \mbox{\ \ }LOOP:\\
  \mbox{\ \ \ \ }$\onset \gets$ EXPAND(\onset,\offset) & // Najde přímé implikanty. \\
  \mbox{\ \ \ \ }if ($c_1 =$ COST(\onset)) & // Pokud se cena nezměnila \\
  \mbox{\ \ \ \ \ \ }goto QUIT & // ukončí průběh \\
  \mbox{\ \ \ \ }$c_1 \gets $ COST(\onset) & // jinak cenu uloží.\\
  \mbox{\ \ \ \ }$\onset \gets$ IRREDUNDANT(\onset,\dcset) & // Najde minimální pokrytí. \\
  \mbox{\ \ \ \ }if ($c_2 =$ COST(\onset)) \\
  \mbox{\ \ \ \ \ \ }goto QUIT  \\
  \mbox{\ \ \ \ }$c_2 \gets $ COST(\onset) \\
  \mbox{\ \ \ \ }$\onset \gets$ REDUCE(\onset,\dcset) & // Dostává řešení z~lokálního optima.  \\
  \mbox{\ \ \ \ }if ($c_3 =$ COST(\onset)) \\
  \mbox{\ \ \ \ \ \ }goto QUIT \\
  \mbox{\ \ \ \ }$c_3 \gets $ COST(\onset) \\
  \mbox{\ \ \ \ }goto LOOP\\
  \mbox{\ \ }QUIT:\\
  \mbox{\ \ \ \ }return Formula(\onset) \\
  \}\\
  \end{tabular}
  \rmfamily
  \caption{Smyčka Espressa v~\bmin{}}
  \label{fig:bmin-espresso}
\end{figure}

Pro~reprezentaci pokrytí je vytvořena speciální třída \code{EspressoCover}, která slouží jako kontejner pro~termy,
k~čemuž interně používá \code{std::list<Term>}. Kromě základních metod pro~zjištění počtu termů, přidání a~odebrání
termu, nabízí ještě speciální iterační makro \code{foreach\_cube}, které velmi zpřehledňuje zápis při iteraci přes
všechny termy v~pokrytí. Definuje také specifické metody pro třídění a mazání podmnožiny termů, které mají zapnutý
konkrétní příznak. Má také metodu pro zjištění unátnosti pokrytí a následné vybrání nejvíce binátní proměnné. Samozřejmě
nechybí ani výpočet ceny daného pokrytí. 

Pro~krokování algoritmu je vytvořena třída \code{EspressoData}. Ta je propojena s~\code{Kernel}, která umožňuje
dočasně změnit aktuální minimální funkci. Toho také přesně \code{EspressoData} využívá a při~každém kroku je aktuální
minimální funkce nahrazena funkcí, která byla aktuální v~daném kroku minimalizace. Každý krok je dán vykonáním jedné
procedury. Vše funguje tak, že během provádění hlavní smyčky se po~každém vykonání nějaké procedury Espressa testuje,
zda je zapnuta volba \code{debug}. Pokud ano, tak se z~aktuálního pokrytí \onset{} vytvoří nová instance třídy
\code{Formula}, která se uloží do~kontejneru v~\code{EspressoData}. Při~krokování jsou pak už jen vybírány uložené
instance z~kontejneru.

\subsubsection{EXPAND}
\label{sec:ec-expand}
Procedura \eproc{EXPAND} je vykonávána metodou \code{expand}. Ta~prochází pomocí makra \code{foreach\_cube} všechny
termy z~\onset{}, které nejsou přímými implikanty a zároveň nejsou pokryty. To se určuje pomocí příznaků, které jsou
při~práci s~pokrytím často využívány. Na každý term se pak volá metoda \code{expand1}, která expanduje term přesně jak
bylo popsáno v~sekci \ref{sec:expand}. Matice \matname{B} a \matname{C} jsou vytvořeny jako pokrytí
\code{EspressoCover}. Využívají tak rozšíření třídy \code{Term}, která může sloužit i jako řádek těchto matic. Množiny
\setname{L} a \setname{R} jsou implementovány jako bitové masky typu \code{term\_t}, což velmi usnadňuje práci. Navíc
třída \code{Term} má v~sobě zabudovanou metodu, která podle masky \code{term\_t} automaticky expanduje term.

\newpage
Pokud zůstanou v~\matname{B} některé sloupce a je třeba najít minimální sloupcové pokrytí, tak je zvolena zjednodušená
heuristika, která není součástí Espressa. Jedná se o~postupné odstraňování sloupců s~největším počtem jedniček. To se
dělá tak dlouho, dokud odstraněné sloupce nepokrývají všechny zbylé řádky v~\matname{B}.  

\subsubsection{IRREDUNDANT}
\label{sec:ec-irredundant}
Procedura \eproc{IRREDUNDANT}, jež je popsána v~sekci \ref{sec:irredund}, se vykonává v~metodě \code{irredundant}. Ta
po sobě volá metody \code{redundant}, \code{partialyRedundant} a \code{minimalIrredundant}, které přesně odpovídají
procedurám \eproc{REDUNDANT}, \eproc{PARTIALY-REDUNDANT} a \eproc{MINIMAL-IRREDUNDANT}.

Pro~odlišení jednotlivých množin \eset{}, \rset{}, \rcset{} a \rpset{} jsou používány příznaky termů. To má velkou
výhodu, protože není třeba neustále kopírovat termy mezi různými instancemi třídy \code{EspressoCover}. Místo toho stačí
pouze jedna instance \code{EspressoCover}, která zároveň reprezentuje pokrytí \onset{}.

V~metodách \code{redundand} a \code{partialyRedundant} se pro~zjišťování, zda je pokrytí tautologií, používá metoda
\code{tautology}. Ta~funguje přesně, jak je popsáno v~sekci \ref{sec:taut}. Není tedy rozšířena na speciální krok
pro~unátní funkce.

Implementace procedury \eproc{MINIMAL-IRREDUNDANT} v~metodě \code{minimalIrredundant} je velmi
zjednodušena. S~algoritmem, který je součástí Espressa nemá nic společného. Jedná se o~velmi primitivní heuristiku,
která nedává příliš optimální výsledek. Funguje tak, že postupně odstraňuje termy v~pořadí v~jakém jdou zrovna
po~sobě. To děla tak dlouho, dokud není nové minimální pokrytí vzniklé z~odstraněných termů ekvivalentní původnímu
pokrytí. Hlavním důvodem takto neoptimálního řešení je především složitost procedury \eproc{MINIMAL-IRREDUNDANT} a
nedostatek času pro její implementaci. Dalším důvodem je však také to, že pro~funkce o~menším počtu proměnných se
ve~většině případu neoptimálnost \eproc{MINIMAL-IRREDUNDANT} neprojeví. Často na ní buď vůbec nedojde (nezbudou žádné
redundantní termy), nebo je třeba rozhodovat mezi stejně velkými termy, což konečný výsledek nijak neovlivní.   


\subsubsection{REDUCE}
\label{sec:ec-reduce}
Implementace procedury \eproc{REDUCE} odpovídá, až na~drobné změny, popisu v~sekci \ref{sec:reduce}. Hlavní část se
nachází v~metodě \code{reduce}. Vše začíná seřazením termů v~\onset{} a dočasným připojením \dcset{}
k~\onset{}. Poté jsou nastaveny počáteční hodnoty příznaků pro~všechny termy. Těch je znovu využíváno pro~usnadnění
práce s~pokrytím. Následné procházení termů funguje přesně tak, jak je popsáno v~sekci \ref{sec:reduce}.

Pozornost si zaslouží akorát subprocedura \eproc{SCCC}. Konkrétně její implementace pro~případ unátnosti zkoumaného
pokrytí \cover{}. Ta je oproti popisu v~sekci \ref{sec:sccc} trochu upravena. Nejdříve je spočítán produkt všech termů   
v~\cover{} (ten bude dále značen jako \tname{p}). Pro~každou pozici $j$ se pak testuje, zda existuje v~\cover{} nějaký
term $t^i$, který po~nastavení $t^i_j = 2$ bude tutologií\footnote{Všechny jeho literály tedy budou mít hodnotu
  2}. Pro~$j$ však zároveň musí platit, že $\tname{p}_j \not= 2$. Oproti popisu v~sekci \ref{sec:sccc} se tedy nehledá
kofaktor pro~každé $\tname{p}_j \not= 2$, místo toho se pozice pouze doplňuje do každého termu. Ve~výsledku je to ale to
samé.


\newpage
\subsection{KMap}
\label{sec:kmap-class}
Třída \code{KMap} slouží pro~reprezentaci Karnaughovy mapy až pro~6 proměnných. Hlavním účelem \code{KMap} je definovat
rozhraní, které umožní mapování jednotlivých termů do~mapy. A to jak základních mintermů\footnote{V dalším textu v~této
  sekci bude hovořeno pouze o~mintermech, i když úplně stejně by vše platilo i~pro~maxtermy.}, které představují jedno
pole v~mapě, tak i~termů o~menším počtu literálů, které pokrývají více polí. 

Mintermy jsou mapovány pomocí Grayova kódu \cite{wiki-gc}. Pro~něj je vytvořena speciální třída \code{GrayCode}, která
obsahuje napevno daných 8 hodnot. To je zcela dostačující, protože mapa může v~každém sloupci a řádku pokrývat
3~proměnné. Tím pádem je maximální počet hodnot pro~určení kombinací všech proměnných v~řádku i sloupci $2^3 =
8$. Výhodou Grayova kódu je jeho symetričnost, která umožňuje jednoduchý převod z~řádkového mapování. Pro~pozici $p$
na~souřadnicích $[x,y]$ v~mapě platí, že
\begin{displaymath}
  p \:=\: x + y \cdot m \:=\: (\mathrm{GC}(x) \;\mathbf{shl}\;  \log_2(m)) \;\mathbf{or}\; \mathrm{GC}(y) \;\;,
\end{displaymath}
kde $m$ je počet sloupců, $\mathbf{or}$ je logický součet, $\mathbf{shl}$ je bitový posun doleva a $\mathrm{GC}$ je
funkce pro~převod do Grayova kódu. Výpočet pozice každého mintermu v~mapě je tedy poměrně rychlý a jednoduchý. Jediný
problém nastává při~vykreslování mapy pro~6 proměnných. První proměnná se totiž pro~přehlednost a lepší vizuální dojem
vpisuje do~řádku s~poslední a předposlední proměnnou. Je tedy třeba první proměnnou přehodit a ve~vzorci tak vzniknou
určité úpravy, což ve výsledku vypadá následovně

\begin{displaymath}
  p \:=\: x + y \cdot 8 \:=\: (\mathrm{GC}(x) \;\mathbf{shl}\;  3) \:\;\mathbf{or}\;\: 
  (\mathrm{GC}(y) \;\mathbf{and}\; 3) \:\;\mathbf{or}\:\; ((\mathrm{GC}(y) \;\mathbf{and}\; 4) \;\mathbf{shl}\;3)\;\;,
\end{displaymath}
kde $\mathbf{and}$ je logický součin a slouží tedy jako odmaskování určitých částí. Ve~vzorci je navíc nahrazeno $m$
hodnotou 8, protože mapa o~6 proměnných má právě 8 sloupců.

Každé pole v~mapě je reprezentováno třídou \code{KMapCell}, která v~sobě obsahuje kromě své pozice také instanci
mintermu, který představuje. Pro~termy o~menším počtu literálů je určena třída \code{KMapCover}, která slouží jako
kontejner pro~instance třídy \code{KMapCell}. Term o~menším počtu literálů totiž pokrývá více polí v~mapě a právě
ty má \code{KMapCover} ve~svém kontejneru. Při jejich vykreslování v~části \bminq{} se používají barevné
obdélníky. V~každém poli je tak třeba určit, zda a případně kudy přes něj vede úsečka či úsečky tvořící obdélník. To se
dá určit podle poziční sousednosti mintermů v~mapě. Kromě pozic zmíněných úseček obsahuje \code{KMapCell} i~další
užitečné informace jako je například výstupní hodnota mintermu.
  

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  Shell

\section{\bmins}
\label{sec:shell}

Část \bmins{} slouží k~několika hlavním účelům:
\begin{itemize}
\item Zpracování voleb zadaných při spouštění aplikace
\item Zpracování zadání logické funkce ve~formátu PLA nebo ve~vlastním výčtovém formátu
\item Vytvoření interaktivního konzolového prostředí s~předem určenou skupinou příkazů
\end{itemize}
V~následujících podsekcích bude popsán způsob implementace jednotlivých účelů.


\subsection{Volby aplikace}
\label{sec:options}
Při~spouštění aplikace lze zadat několik voleb. Všechny jsou uvedeny v~Tabulce \ref{tab:options}. Volby \code{-h}
a~\code{-v} nebo alternativně \code{--help} a \code{--version} mají spíše informační význam. Slouží hlavně k~dodržení
GNU standardu \cite{gnu-std} pro~zadávání voleb. Volba \code{-s} nebo případně \code{--shell} spouští konzolové
prostředí, které bude podrobně popsáno v~následující podsekci.

\begin{table}[hbt]
  \centering
  \begin{tabular}{|l|l|p{8cm}|}
    \hline
    \textbf{Volbal} & \textbf{Alternativa} & \textbf{Význam}\\
    \hline\hline
    \code{-h} & \code{--help} &  Zobrazení nápovědy. \\ 
    \hline
    \code{-v} & \code{--version}  &  Zobrazení verze včetně informací o licenci.  \\ 
    \hline
    \code{-s} &  \code{--shell} &  Spuštění konzolového prostředí místo grafického prostředí. \\ 
    \hline
  \end{tabular}
  \caption{Volby aplikace}
  \label{tab:options}
\end{table}

\subsection{Konzolové prostředí}
\label{sec:konsole}
Konzolové prostředí představuje jakousi terminálovou aplikaci. V~současné době je podporována jen pro~operační systém
Linux. Ve~Windows není možné aplikaci spustit, protože se automaticky otvírá v~novém procesu. Důvodem je~pravděpodobně
načtení grafické knihovny, což způsobí vyvolaní nového procesu. Ten nemá připojen vstup a výstup ke~konzolovému
rozhraní, ze kterého byl vyvolán. Tento problém nebyl řešen z~důvodu malé oblíbenosti práce v~konzolovém prostředí mezi
uživateli Windows.

Po spuštění konzolového prostředí se vypíše několik řádků týkajících se práv a licence. Po nich se vytiskne řádek
začínající znakem \code{>}. Ten uvozuje příkazovou řádku, do níž lze psát příkazy nebo zadat logickou funkci
ve~specifickém výčtovém tvaru. Každý příkaz nebo zadání funkce se předá ke~zpracování po~stisknutí klávesy
\code{Enter}. 


\subsubsection{Výčtový zápis funkce}
\label{sec:fce-format}
Logickou funkci lze zadat v~zápisu, který je v~podstatě shodný s~klasickým výčtovým zápisem uvedeným v~sekci
\ref{sec:defs}. Rozdíl spočívá v~omezení názvu proměnných pouze na~jednopísmenný název. To platí zároveň i~pro~jméno
funkce. Dále jsou nahrazeny matematické symboly za~názvy složené z~běžných znaků (tzn. symboly vyskytující se na
klávesnici). Tabulka \ref{tab:fce-symbols} uvádí všechna nahrazení. 

\begin{table}[hbt]
  \centering
  \begin{tabular}{|l|l|l|}
    \hline
    \textbf{Matematický zápis} & \textbf{Programový zápis} & \textbf{Popis}\\
    \hline\hline
    \fsum{} & \code{sum m} &  Suma mintermů z~\onset{} \\ 
    \hline
    \dsum{} & \code{sum d} &  Suma mintermů z~\dcset{} \\ 
    \hline
    \rprod{} & \code{prod m} &  Produkt maxtermů z~\offset{} \\ 
    \hline
    \dprod{} & \code{prod d} &  Produkt maxtermů z~\dcset{} \\ 
    \hline
    $\cdot$ &  \code{*} & Spojení výčtů \rprod{} a \dprod{}  \\ 
    \hline
  \end{tabular}
  \caption{Nahrazení matematických symbolů ve~výčtovém zápisu funkce}
  \label{tab:fce-symbols}
\end{table}

\newpage
Funkce v~DNF reprezentaci zadaná v~matematickém zápisu jako
\begin{displaymath}
  f(c,b,a) = \fsum(0,2,3) + \dsum(1,6)
\end{displaymath}
se programově zapíše jako
\begin{displaymath}
  \mbox{\code{f(c,b,a) = sum m(0,2,3) + sum d(1,6)}}
\end{displaymath}
Potom je její KNF reprezentace v~matematickém tvaru
\begin{displaymath}
  f(c,b,a) = \rprod(4,5,7) \cdot \dprod(1,6)
\end{displaymath}
a programově se zapíše jako
\begin{displaymath}
  \mbox{\code{f(c,b,a) = prod m(4,5,7) * prod d(1,6)}}
\end{displaymath}

Je třeba poznamenat, že výčet pro~\dcset{} je volitelný a~v~zápisu se objevit nemusí. První výčet pro~\onset{},
resp. \offset{}, je však povinný a musí být tedy vždy uveden, a to i~v~případě, že je prázdný. 

Kontradikce by se v~DNF pro~funkci o~třech proměnných zapsala jako
\begin{displaymath}
  \mbox{\code{f(c,b,a) = sum m()}}
\end{displaymath}

Naopak tautologie se v~KNF zapíše jako
\begin{displaymath}
  \mbox{\code{f(c,b,a) = prod m()}}
\end{displaymath}

\subsubsection{Příkazy}
\label{sec:commands}
Konzolové prostředí rozeznává několik příkazů. Všechny je uvádí Tabulka \ref{tab:commands}. Speciální formu má příkaz
\code{show}, který bez argumentu zobrazí úplnou formu aktuální funkce. Pokud je zminimalizována, tak ještě zobrazí
její minimální formu. V případě, že je příkazu \code{show} předán jeden ze čtyř v tabulce uvedených argumentů, provede
se daná akce. Pro~argument \code{espresso} jsou zobrazena výsledná pokrytí logické funkce po~vykonání jednotlivých
procedur. Pro~ostatní argumenty, kterými jsou \code{qm}, \code{kmap} a \code{cube}, se zobrazí konkrétní akce v~podobě
obrázku vytvořeným v~ASCII Art, což je podrobně popsáno v~podsekci \ref{sec:ascii}. Další příkazy, které přebírají
argument, jsou \code{load} a \code{save}. Je jim předána cesta k~souboru, ze kterého bude funkce načtena, resp. do~něj
uložena v~PLA formátu (viz sekce \ref{sec:pla}). Cesta musí být zadána ve dvojitých uvozovkách, tedy například
\code{"/home/kuba/fce.pla"} 

\begin{table}[hbt]
  \centering
  \begin{tabular}{|l|p{10cm}|}
    \hline
    \textbf{Příkaz} & \textbf{Popis} \\
    \hline\hline
    \code{exit} &  Ukončí program. \\ 
    \hline
    \code{minimize} & Spustí minimalizaci aktuální logické funkce. \\ 
    \hline
    \code{qm} & Přepne algoritmus na Quine-McCluskey. \\ 
    \hline
    \code{espresso} &  Přepne algoritmus na Espresso.\\ 
    \hline
    \code{sop} & Nastaví reprezentaci funkce na DNF. \\ 
    \hline
    \code{pos} & Nastaví reprezentaci funkce na KNF. \\ 
    \hline
    \code{load \textit{path}} & Načte funkci ze~souboru ve~formátu PLA  na cestě \code{\textit{path}}. \\ 
    \hline
    \code{save \textit{path}} & Uloží aktuální funkci do~souboru \code{\textit{path}} ve formátu PLA. \\ 
    \hline
    \code{show} & Zobrazí aktuální funkci  v úplné a minimální formě. \\ 
    \hline
    \code{show qm} & Zobrazí průběh Quine-McCluskey algoritmu v~ASCII Art. \\ 
    \hline
    \code{show espresso} &  Zobrazí průběh Espressa. \\ 
    \hline
    \code{show kmap} &  Zobrazí Karnaughovu mapu v~ASCII Art. \\ 
    \hline
    \code{show cube} &  Zobrazí Booleovskou n-krychli v~ASCII Art. \\ 
    \hline
  \end{tabular}
  \caption{Příkazy pro konzolové prostředí}
  \label{tab:commands}
\end{table}


\subsubsection{ASCII Art}
\label{sec:ascii}
ASCII Art je název pro~obrázek nakreslený pouze pomocí ASCII znaků. Konzolové prostředí používá ASCII art pro~vykreslení
průběhu Quine--McCluskey algoritmu a také pro~zobrazení Karnaughovy mapy a Booleovské n-krychle.

\paragraph{Zobrazení Karnaughovy mapy}\ \newline
K-mapa zobrazuje pouze své rozložení. Není v~ní tedy vidět minimální pokrytí. Proměnných může být až 6 a jejich popis je
uveden v~binárním zápisu. Příklad ukazuje Obrázek \ref{fig:ascii-kmap}. 

\begin{figure}[hbt]
  \small\verbatiminput{figures/ascii-kmap.txt}
  \caption{Konzolové zobrazení Karnaughovy mapy}
  \label{fig:ascii-kmap}
\end{figure}


\paragraph{Zobrazení průběhu algoritmu Quine--McCluskey}\ \newline
Při zobrazení algoritmu Quine--McCluskey se nejdříve vygeneruje tabulka obsahující průběh hledání přímých implikantů,
která se následně zobrazí. Po~ní je zobrazena tabulka pokrytí. Celý průběh i se zadáním funkce ukazuje Obrázek
\ref{fig:ascii-qm}.

\begin{figure}[hbt]
  \small\verbatiminput{figures/ascii-qm.txt}
  \caption{Konzolové zobrazení průběhu algoritmu Quine--McCluskey}
  \label{fig:ascii-qm}
\end{figure}

\newpage
\paragraph{Zobrazení Booleovské n-krychle}\ \newline
Booleovská n-krychle může být zobrazena maximálně pro~3 proměnné. Stejně jako K-mapa zobrazuje pouze své rozložení a
nejsou v~ní zvýrazněna minimální pokrytí. Příklad ukazuje Obrázek \ref{fig:ascii-cube}.

\begin{figure}[hbt]
  \small\verbatiminput{figures/ascii-cube.txt}
  \caption{Konzolové zobrazení Booleovské n-krychle}
  \label{fig:ascii-cube}
\end{figure}


\subsection{PLA formát}
\label{sec:pla}
Berkeley standard PLA format \cite{espresso-pla} je formát pro~zadávání logických funkcí v~programu Espresso
II\footnote{Espresso II je oficiální implementace algoritmů Espressa. Pochází z~roku 1983 a jejím autorem je Richard
  Rudell. Zdrojové kódy jsou k~dispozici na \cite{espresso-src}.}. Umožňuje zadat vícevýstupovou funkci pouze v~DNF,
přičemž má mnoho voleb, které se specifikují v hlavičce. Nicméně \bmin{} podporuje pouze určitou skupinu těchto
voleb. Všechny je uvádí Tabulka \ref{tab:pla-opt}

\begin{table}[hbt]
  \centering
    \begin{tabular}{|l|p{10cm}|}
      \hline
      \textbf{Volba} & \textbf{Význam} \\
      \hline\hline
      \code{.i \textit{n}} & Počet vstupních proměnných, kde \code{\textit{n}} je číslo. \\ 
      \hline
      \code{.o \textit{n}} & Počet výstupních funkcí, kde \code{\textit{n}} je číslo.  \\
       \hline
      \code{.ilb \textit{seznam}} & Názvy vstupních proměnných, kde \code{\textit{seznam}} je výčet mezerou oddělených
      jednopísmenných ASCII znaků abecedy.  \\
      \hline
      \code{.ob \textit{seznam}} & Názvy výstupních funkcí, kde \code{\textit{seznam}} je výčet mezerou oddělených
      jednopísmenných ASCII znaků abecedy.  \\
      \hline
      \code{.p \textit{n}} & Počet produktových termů uvedených ve~výčtu, kde \code{\textit{n}} je číslo.  \\ 
      \hline
      \code{.type \textit{typ}} & Nastavuje logickou interpretaci zadaných termů. Parametr \code{\textit{typ}} může
      nabývat pouze hodnoty \code{fd}.  \\ 
      \hline
      \code{.e (.end)} & Volitelně značí konec skupiny zadaných termů \\
      \hline
    \end{tabular}
    \caption{Volby pro PLA formát}
    \label{tab:pla-opt}
\end{table}

Všechny tyto volby (kromě \code{.e}) musí být uvedeny v~hlavičce, to znamená před zadáním produktových termů (viz
dále). Volby \code{.p}, \code{.type} a \code{.e} jsou zcela přebytečné a slouží jen k~zachování kompatibility
s~klasickým PLA formátem. Počet produktových termů se určí automaticky podle počtu uvedených termů a konec je určen jako
konec souboru. Logická implementace je podporována pouze pro typ \code{fd}, který je v~klasickém PLA formátu implicitní,
takže ho není třeba uvádět.

Přestože \bmin{} podporuje pouze jednovýstupové funkce, je v~PLA formátu možné zadat více výstupních hodnot (tedy
přesněji více výstupních funkcí). \bmin{} pak dá uživateli na~výběr, kterou ze~zadaných funkcí zvolí jako aktuální.

Typ \code{fd} určuje charakter výstupních hodnot. Významy jednotlivých výstupních hodnot uvádí Tabulka \ref{tab:pla-fd}.

\begin{table}[hbt]
  \centering
    \begin{tabular}{|l|p{7.5cm}|}
      \hline
      \textbf{Výstupní hodnota} & \textbf{Význam} \\
      \hline\hline
      \code{1} & Produktový term náleží do~\onset{}. \\ 
      \hline
      \code{-} & Produktový term náleží do~\dcset{}.  \\
      \hline
      \code{0} & Produktový term nemá význam pro~danou výstupní funkci. \\
      \hline
    \end{tabular}
    \caption{Význam výstupních hodnot pro~typ \code{fd}}
    \label{tab:pla-fd}
\end{table}

Každý produktový term je zadán na~jednom řádku. Nejprve jsou zadány vstupní literály, které jsou uvedeny v~binárním
zápisu rozšířeným o~znak \code{-} pro~chybějící literál. Po~zadání literálů je třeba vložit alespoň jednu mezeru či
tabulátor a poté zadat výstupní hodnoty. Ty jsou uvedeny ve stejném zápisu jako literály, přičemž každá hodnota
představuje výstup jedné funkce.

Obrázek \ref{fig:pla-exam} ukazuje příklad zadání funkcí
\begin{displaymath}
  \begin{array}{rcl}
    f(c,b,a) & \equiv & \fsum(2,3) + \dsum(0,1,7) \\
    g(c,b,a) & \equiv & \fsum(1,2,3,7)
  \end{array}
\end{displaymath}

\begin{figure}[hbt]
  \small\verbatiminput{figures/fce.pla}
  \caption{Ukázka zadání logické funkce v PLA formátu}
  \label{fig:pla-exam}
\end{figure}

\subsection{Vnitřní implementace}
\label{sec:konsole-impl}
Implementačně je část \bmins{} složena z~několika málo tříd, z nichž některé jsou závislé na části \bmink{}. Závislost
na~jiné než STL knihovně neexistuje.

Pro konsolové rozhraní slouží třída \code{Konsole}, která se stará o~získání vstupů a předání výstupů uživateli. Je
zároveň potomkem třídy \code{Events}, takže zpracovává všechny události vyvolané jádrem. Veškeré uživatelské vstupy ale
předává třídě \code{Parser}, která podle dané LL gramatiky provádí rekurzivní sestup. Pro~lexikální analýzu používá
třídu \code{LexicalAnalyzer}. 

Pro vykreslování obrázků v~ASCII Art slouží třída \code{AsciiArt}, která je volána instancí \code{Konsole}
při~událostech \code{evtShowQm}, \code{evtShowKMap} a \code{evtShowCube}. Vykreslování n-krychle a K-mapy je poměrně
triviální a není třeba ho rozebírat. Vykreslování průběhu algoritmu Quine--McCluskey, konkrétně hledání přímých
implikantů, je o~něco složitější. Pro~tyto účely byla vytvořena třída \code{Implicants}, která slouží k~rozvržení
tabulky tak, aby mohla být vykreslena po~řádcích a přitom zůstala zachována šířka jednotlivých sloupců.

Zcela nezávislou třídou je \code{Options}, která slouží k~obecnému zpracování voleb. Je to jakási obdoba knihovny
\code{getopt}. Na základě zadaných požadavků zpracovává programové volby.

\newpage
\section{\bminq}
\label{sec:qtgui}

Část \bminq{} tvoří grafické rozhraní aplikace \bmin{}. Ke~svému fungování potřebuje jak \bmink{} tak \bmins{}. Navíc je
závislá na grafické knihovně Qt. 

\bminq{} je spouštěna automaticky, pokud nejsou programu zadány žádné argumenty. Po jejím spuštění se zobrazí hlavní
okno s~menu barem, hlavním layoutem a status barem (viz Obrázek \ref{fig:qt-welcome})\footnote{Na obrázku je z~důvodu
  jeho velikosti vynechán status bar.}. Hlavní layout je rozčleněn na dvě
části -- \textbf{horní} a \textbf{dolní}:

\begin{description}
\item[Horní část] slouží k~zadání Booleovské funkce v~úplné formě a k jejímu zobrazení ve výsledné minimální
  formě. Funkci lze zadat buď přímo do~textového pole ve formátu popsaném v~sekci \ref{sec:fce-format} nebo pomocí
  průvodce pro~vytvoření (viz sekce \ref{sec:qt-dialog}), který se zobrazí po~kliknutí na~tlačítko \code{New...}. Pokud
  je funkce zadána, změní se tlačítko z~\code{New..}. na~\code{Edit...} a~funkci lze po~kliknutí na~něj editovat. Dále
  je možné vybrat reprezentaci logické funkce a minimalizační algoritmus. K~výběru reprezentace slouží výběrové pole
  \code{Representation of logic function}, kde je na~výběr ze~\code{Sum of~Products}, což je DNF, a~\code{Products of
    Sums}, což je KNF. Pro~výběr algoritmu je vytvořeno výběrové pole \code{Algorithm}, které umožňuje vybrat mezi
  \code{Quine-McCluskey} a \code{Espresso}. Ke~spuštění minimalizace slouží tlačítko \code{Minimize}, které
  zminimalizuje zadanou funkci a výsledek zobrazí do textového pole \code{Minimal form}. To je pouze pro~čtení (nejde
  do~něj tedy zapisovat). 
\item[Dolní část] obsahuje na~levé straně čtyři tlačítka pro~přepnutí módu, který je zobrazen vedle panelu s
  tlačítky. Na každém tlačítku je uveden název módu bílým písmem na~šedém pozadí. Pouze tlačítko s~aktuálně zobrazeným
  módem má černé písmo na~bílém pozadí. Následující výčet uvádí význam jednotlivých módů
  \begin{description}
  \item[Welcome] umožňuje vybrat jiný mód nebo vyvolat About dialog, který zobrazuje základní informace o~programu
    a~licenci. Vzhled \textbf{Welcome} módu je zobrazen na~Obrázku \ref{fig:qt-welcome}.
  \item[K-Map] zobrazuje Karnaughovu mapu (viz sekce \ref{sec:qt-kmap}).
  \item[Boolean n-Cube] zobrazuje Booleovskou n-krychli ve 3D (viz sekce \ref{sec:qt-cube}).
  \item[Quine-McCluskey] zobrazuje průběh algoritmu Quine--McCluskey (viz sekce \ref{sec:qt-qm}).
  \end{description}
\end{description}

V následující podsekcích jsou důkladněji popsány jednotlivé módy (kromě \textbf{Welcome}) a~také některé zajímavé části.

\begin{figure}[hbt]
  \centering
  \includegraphics{figures/bmin-welcome}
  \caption{\bminq{} část po~svém spuštění s~aktivním \textbf{Welcome módem}}
  \label{fig:qt-welcome}
\end{figure}

\subsection{Dialog pro zadání logické funkce}
\label{sec:qt-dialog}

\begin{figure}[hbt]
  \centering
  \includegraphics{figures/bmin-qm}
  \caption{Dialog pro zadání logické funkce}
  \label{fig:qt-dialog}
\end{figure}

Logické funkce lze vytvářet a editovat v~dialogu, který je zobrazen na~Obrázku \ref{fig:qt-dialog}. V~něm je
možné zadat název funkce, její reprezentaci a počet proměnných. U~proměnných lze nastavit i jejich názvy, které jsou
při~každé změně jejich počtu automaticky vygenerovány jako abecední posloupnost začínající písmenem \code{a}.

Při změně počtu je zároveň vygenerována pravdivostní tabulka, která uvádí v~prvním sloupci index mintermu, po němž jsou
v~následující sloupcích zobrazeny hodnoty jednotlivých proměnných. V~posledním sloupci jsou pak uvedeny výstupní hodnoty
mintermů. Ty lze měnit dvojím kliknutím\footnote{Stejného účinku se dosáhne i pouze jedním kliknutím a zmáčknutím
  klávesy \code{F2} nebo napsání hodnoty, na kterou má být změněno (např. \code{1}).} na~příslušné pole a zvolením
výstupní hodnoty z~výběrového pole. Další způsob, jak lze měnit výstupní hodnotu, je pomocí kontextového menu vyvolaného
kliknutím pravým tlačítkem myši nad~vybranou skupinou polí v~tabulce a následným zvolením položky \code{Selected output
  values to->1}. Lze tak změnit více výstupních hodnot najednou. Kontextové menu obsahuje ještě položku  \code{All
  output values to},   která umožňuje změnit výstupní hodnotu všem položkám v~pravdivostní tabulce najednou.

Pro~uložení funkce stačí zmáčknout klávesu \code{Enter} nebo případně kliknout na tlačítko \code{Ok}. Pro~zrušení
dialogu bez~uložení funkce naopak stačí zmáčknout klávesu \code{Esc} nebo kliknout na~tlačítko \code{Cancel}. 
\vfill

\begin{figure}[hbt]
  \centering
  \includegraphics{figures/bmin-kmap}
  \caption{Karnaughova mapa}
  \label{fig:qt-kmap}
\end{figure}

\subsection{K-Map}
\label{sec:qt-kmap}

Karnaughova mapa se vykresluje až pro~6 proměnných. Layout je horizontálně rozdělen na dvě části. V~levé je mapa
vykreslována a v~pravé se zobrazují seznamy pro~výpis mintermů\footnote{Je uvažována pouze DNF, pro~KNF by to bylo
  stejné, akorát by se jednalo o~maxtermy.} a pokrytí\footnote{Zde je pokrytím myšlen každý term z minimálního pokrytí
  funkce.} (ta pouze v případě, že je zaškrtnuto políčko \code{Show covers}). Mapa se automaticky vykreslí, jakmile je
zadána funkce. K~popisu proměnných existují dva módy. První ukazuje rozložení v~binární formě a druhý jako čáry
představující negaci. Módy lze měnit vyvoláním kontextového menu (kliknutím pravým tlačítkem) na~popis proměnných. Lze
také měnit výstupní hodnoty mintermů  zmáčknutím levého tlačítka myši nad~příslušným polem  v~mapě. Změny jednotlivých
mintermů se přímo zobrazí v~zadání funkce v textovém poli. Mapa je zároveň propojena s~výpisem mintermů a~pokrytí
na~pravé straně. Každý vybraný minterm v~seznamu změní barvu pole v~mapě, jakmile je vybrán, a~stejně je tomu
i~u~pokrytí, které zvýrazní všechny mintermy, které jsou jím pokryté. Pokrytí je zároveň v~mapě vyznačeno pomocí
barevných čtyřúhelníků. Způsob zápisu mintermů a termů minimální funkce (pokrytí) závisí na zvolené
reprezentaci. V~pravém části pod~seznamy jsou ještě dvě tlačítka pro~krokování Espressa. Ta budou podrobně popsána
v~sekci \ref{sec:qt-espresso}. K-mapu v~\bminq{} ukazuje Obrázek \ref{fig:qt-kmap}.  

\newpage


\begin{figure}[hbt]
  \centering
  \includegraphics{figures/bmin-cube}
  \caption{Booleaovská n-krychle}
  \label{fig:qt-cube}
\end{figure}


\subsection{Boolean n-Cube}
\label{sec:qt-cube}

Booleovská n-krychle na Obrázku \ref{fig:qt-cube} je vytvořena pomocí knihovny OpenGL. Je tedy zobrazena ve~3D prostoru
a nabízí dva pohledy. První je klasický 3D pohled, jenž umožňuje procházet vnitřkem krychle. Druhý je tzv. rotační
pohled a umožňuje krychlí různě natáčet. Je možné zobrazit maximálně n-krychli pro~3 proměnné. Vrcholy jsou zobrazeny
pomocí koulí, přičemž výstupní hodnotu každého mintermu\footnote{Znovu je uvažována pouze DNF, pro~KNF by to bylo
  stejné, akorát by se jednalo   o~maxtermy.} určuje barva koule:

\begin{tabular}[l]{l@{ $\equiv$ }l}
  \textbf{\cyan{azurová}}      & 0 \\
  \textbf{\red{červená}}       & 1 \\
  \textbf{\magenta{purpurová}} & 2 \\
\end{tabular}

Stejně jako u~Karnaughovy mapy je layout horizontálně rozdělen na~dvě části. V~levé je zobrazena výše popsána 3D krychle
a v~pravé jsou seznamy s~mintermy a termy z minimálního pokrytí. Pod nimi jsou ještě dvě tlačítka pro~krokování
Espressa. Tedy vše je úplně stejné jako u~K-mapy. Mintermy se v~krychli zvýrazňují pomocí ztmavnutí koulí
symbolizujících vybraný minterm. Pokrytí se zobrazují pomocí žlutých smyček obíhajících pokryté mintermy. Vybrané
pokrytí změní barvu smyčky na~zelenou.

\subsubsection{Ovládání}
\label{sec:qt-cube-opt}

Ovládání n-krychle je poměrně obsáhlé, a proto je uzavřeno do~samostatné podsekce. Většina akcí se provádí pomocí
klávesnice. Navíc lze použít pro některé akce i kontextové menu a~myš.

Změna výstupních hodnot jednotlivých mintermů se provádí kliknutím pravým tlačítkem myši. Tím se zároveň změní barva
příslušné koule.

Klávesových voleb je velké množství. Je třeba rozlišovat mezi volbami společnými pro~oba módy, které jsou uvedeny
v~Tabulce \ref{tab:cube-opt-both}, a volbami specifickými pro konkrétní mód, které jsou uvedeny v~Tabulkách 
\ref{tab:cube-opt-first}, resp. \ref{tab:cube-opt-second}.

\begin{table}[hbt]
  \centering
    \begin{tabular}{|l|p{10cm}|}
      \hline
      \textbf{Klávesa} & \textbf{Význam} \\
      \hline\hline
      \code{1} & Přepnutí do módu pro 3D průchod krychlí. \\ 
      \hline
      \code{2} & Přepnutí do rotačního módu.  \\
      \hline
      \code{L} & Automatický pohyb světel.  \\
      \hline
      \code{C} & Zobrazení nebo Zakrytí minimalizovaných termů (pokrytí).  \\
      \hline
    \end{tabular}
    \caption{Volby pro Booleovskou n-krychli společné v obou módech}
    \label{tab:cube-opt-both}
\end{table}

\begin{table}[hbt]
  \centering
    \begin{tabular}{|l|l|l|}
      \hline
      \textbf{Klávesa} & \textbf{Alternativa} & \textbf{Význam} \\
      \hline\hline
      \code{W} & šipka dopředu     &  Pohyb dopředu. \\ 
      \hline
      \code{S} & šipka dozadu      &  Pohyb dozadu. \\ 
      \hline
      \code{A} & šipka doleva      &  Natočení doleva. \\ 
      \hline
      \code{D} & šipka doprava     &  Natočení doprava. \\ 
      \hline
      \code{E} & \code{Page Up}    &  Natočení nahoru. \\ 
      \hline
      \code{X} & \code{Page Down}  &  Natočení dolů. \\ 
      \hline
      \code{T} &  & Pohyb nahoru. \\
      \hline
      \code{G} &  & Pohyb dolů. \\
      \hline
      \code{F} &  & Pohyb doleva. \\
      \hline
      \code{H} &  & Pohyb doprava. \\
      \hline
      \code{R} &  & Zapnutí reflektoru. \\
      \hline
    \end{tabular}
    \caption{Volby pro Booleovskou n-krychli ve 3D módu}
    \label{tab:cube-opt-first}
\end{table}

\begin{table}[hbt]
  \centering
    \begin{tabular}{|l|p{10cm}|}
      \hline
      \textbf{Klávesa} & \textbf{Význam} \\
      \hline\hline
      šipky & Natáčení krychlí. \\ 
      \hline
      \code{+} & Přiblížení krychle.  \\
      \hline
      \code{-} & Oddálení krychle.  \\
      \hline
      \code{R} & Automatická rotace.  \\
      \hline
    \end{tabular}
    \caption{Volby pro Booleovskou n-krychli v rotačním módu}
    \label{tab:cube-opt-second}
\end{table}

Kontextové menu má dvě položky. První je \code{Camera}, jenž umožňuje vybrat pohled mezi klasickým 3D pohledem
pro~průchod krychlí označením \code{Camer->3D} a rotačním pohledem označením \code{Camera->Rotated}. Druhou položkou
je \code{Lights}, jenž umožňuje určit, která světla budou svítit. Pro 3D pohled je možné zapnout nebo vypnout zdrojové
světlo, kterým je reflektor, označením \mbox{\code{Lights->Reflector}}. Dále jsou k dispozici dvě směrová světla --
přední a zadní. Pro~ně jsou v~menu volby \mbox{\code{Lights->Light 1}}, resp. \mbox{\code{Lights->Light 2}}.


\subsection{Espresso}
\label{sec:qt-espresso}

Espresso je možné krokovat po jednotlivých procedurách. K~tomu účelu slouží dvě tlačítka:

\begin{tabular}{lp{12.5cm}} \\
\code{Start} & Zahájí krokování algoritmu. Po spuštění se automaticky změní na~\code{Finish}, které slouží
k~ukončení krokování a zobrazení výsledné minimální funkce. Po ukončení se změní \code{Finish} znovu na \code{Start}
a~je možné spustit krokování od~začátku. \\ 

\code{Next} & Zobrazí výslednou funkci po~proběhnutí jedné procedury. Vykoná se tedy jedna procedura v~pořadí určeném
hlavní smyčkou Espressa (viz sekce \ref{sec:espresso}) a poté je zobrazena výsledná funkce. Zároveň se ve~status baru objeví
informace o tom, jaká procedura právě proběhla. \\ \\
\end{tabular}

Krokování je možné spustit jak v~Karnaughově mapě, tak v~Booleovské n-krychli. Průběh je pak nejlépe vidět, pokud je
zapnuta volba \code{Show covers}. 

\subsection{Quine-McCluskey}
\label{sec:qt-qm}
Mód Quine-McCluskey zobrazuje průběh algoritmu Quine--McCluskey. Nejprve je vypsán průběh hledání přímých implikantů,
kde jsou uvedeny termy jak v~binárním zápisu, tak ve~výčtu pokrytých mintermů. Termy označené hvězdičkou jsou přímými
implikanty. Dále je pak uvedena tabulka pokrytí, která je ve standardním formátu. V řádcích jsou tedy uvedeny přímé
implikanty a ve~sloupcích mintermy z~\onset{}.  Při změně funkce se automaticky mění i~obě tabulky. Příklad ukazuje
Obrázek \ref{fig:qt-qm}. 

Pokud je zvolena KNF reprezentace, jsou zobrazeny výčty maxtermů, které symbolizuje velké písmeno \code{M} oproti malému
\code{m} pro~mintermy. Zároveň jsou samozřejmě ve~sloupcích tabulky maxtermy z~\offset{}.

\begin{figure}[hbt]
  \centering
  \includegraphics{figures/bmin-qm}
  \caption{Průběh algoritmu Quine--McCluskey v \bminq{}}
  \label{fig:qt-qm}
\end{figure}

\newpage

\subsection{Hlavní menu bar}
\label{sec:qt-menu}

Hlavní menu bar obsahuje dvě menu, a to \code{File} a \code{Help}. Druhé jmenované obsahuje pouze jednu akci, kterou je
\code{About Bmin}. Ta způsobí zobrazení About dialogu, který obsahuje, jak už bylo uvedeno, základní informace
o~programu a licenci. Zajímavější je první menu, kterým je \code{File}. To obsahuje několik akcí, které uvádí Tabulka
\ref{tab:qt-menu}. Kromě názvu položky a~jejího popisu uvádí Tabulka i klávesovou zkratku pro~vyvolání dané akce.

Je třeba poznamenat, že při načítaní aktuální logické funkce z~PLA souboru může být vytvořeno více výstupních
funkcí. V~tom případě je uživateli zobrazen dialog, ze~kterého si vybere jednu, která se stane aktuální funkcí.

Dále je ještě třeba poznamenat, že uživatelské nastavení, které je využíváno pro~akce \code{Store} a \code{Load}, je
nejčastěji skrytý adresář \code{config} v~uživatelově domácím adresáři, kam se ukládají programová nastavení.

\begin{table}[hbt]
  \centering
    \begin{tabular}{|l|l|p{8cm}|}
      \hline
      \textbf{Položka} & \textbf{Klávesová zkratka} & \textbf{Popis} \\
      \hline\hline
      \code{New...}     & \code{Ctrl+N} & Vyvolá dialog pro vytvoření nové logické funkce. \\ 
      \hline
      \code{Edit...}    & \code{Ctrl+E} & Vyvolá dialog pro editování aktuální logické funkce. Lze provést pouze
      v~případě, že aktuální logická funkce existuje. \\ 
      \hline
      \code{Open...}    & \code{Ctrl+O} & Načte logickou funkci funkci z PLA souboru, který je zvolen pomocí vyvolaného
      dialogu. \\ 
      \hline
      \code{Save As...} & \code{Ctrl+S} & Uloží aktuální logickou funkci ve formátu PLA do souboru zvoleného pomocí
      vyvolaného dialogu. \\ 
      \hline
      \code{Load}       & \code{Ctrl+L} & Načte aktuální logickou funkci uloženou, která je uložena v~uživatelském nastavení. \\ 
      \hline
      \code{Store}      & \code{Ctrl+W} & Uloží aktuální logickou funkci do~uživatelského nastavení. \\ 
      \hline
      \code{Exit}       & \code{Ctrl+Q} & Ukončí program. \\ 
      \hline
    \end{tabular}
    \caption{Položky ve \code{File} menu}
    \label{tab:qt-menu}
\end{table}

\newpage

\subsection{Vnitřní implementace}
\label{sec:qt-impl}

Vnitřní implementace \bminq{} je poměrně komplikovaná. Většina tříd dědí od~základních Qt tříd. Komunikace je pak
postavena na~\emph{signal and slots} frameworku, který v~Qt nahrazuje klasický model událostí. V~mnoha třídách je také
používán \emph{Model and View} framework. Veškeré vykreslování je samozřejmě založeno na~Qt třídách. Pro~bližší popis by
tedy bylo třeba důkladně popsat knihovnu Qt, což je mimo rozsah této práce. Lze však uvést alespoň základní rozdělení
tříd.

O~veškorou komunikaci s~jádrem se stará třída \code{GUIManager}, která zároveň slouží i jako propojovací vrstva mezi
všemi třídami v~\bminq{}. Existuje proto pouze v~jediné instanci. 

O~spravování módů se stará třída \code{ModeManager}, která existuje také pouze v~jediné instanci. Každý mód je
potomkem třídy \code{ModuleWidget}, která obsahuje základní informace jako jméno módu a jeho ID. Jednotlivé módy jsou pak
reprezentovány třídami \code{WelcomeWidget}, \code{KMapWidget}, \code{CubeWidget} a \code{QmWidget}. Třída
\code{CubeWidget} používá pro~OpenGL vykreslování třídu \code{CubeGLDrawer}, která je zároveň i~nejrozsáhlejší třídou
v~celé aplikaci. Vše je pro~přehlednost znázorněno na~obrázku \ref{fig:qtgui-classes}.

 \begin{figure}[hbt]
  \centering
  \includegraphics{figures/QtGUIClassModel} 
  \caption{Rozložení tříd v~části \bminq{}}
  \label{fig:qtgui-classes}
\end{figure}