\documentclass[b5paper,10pt]{book}
\usepackage{KnuthMarcius20}
\usepackage{mycolortbl}
\usepackage{arabtex}
\usepackage[nocatcodes]{devanagari}


\makeindex

\renewcommand{\sfdefault}{ufu}

\setcounter{chapter}{6}
\setcounter{tocdepth}{4}
\setcounter{section}{5}
\setcounter{subsection}{1}
\setcounter{subsubsection}{3}
\setcounter{figure}{0}
\setcounter{equation}{0}
\setcounter{page}{1}
\font\dnten=dvng8 at 10pt
\font\grkten=kdgr8 at 10pt
\font\arabten=nash14 at 10pt
\font\arab=nash14
  
\begin{document}
\renewcommand\sz[1]{[\textit{#1}]}
\def\figdir{abrak} % ábrakönyvtár átnevezése
\def\CEE/{{\mc C\spacefactor1000}}% the C programming language
\def\MF{{\manfnt META}\-{\manfnt FONT}}%
\def\bool#1{\mathbin{\catcode`\.=12\vcenter{\hbox{$#1$}}}}
\def\nbool#1{\mathbin{\catcode`\.=12     \mkern1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern1.5mu}}
\def\contra{\bool{\bot}} %%% rendben
\def\nimp{\nbool\supset}   %%% rendben
\def\quant{\lower.23ex\hbox{epsfbox{\figdir/v4a.9}}}   %%% ábra kell
\def\lproj{\bool{\epsfbox{\figdir/v4a.10}}}   %%% ábra kell
\def\cnimp{\nbool\subset}    %%% rendben
\def\rproj{\bool{\epsfbox{\figdir/v4a.11}}} %%% ábra kell
\def\xor{\oplus}       %%% rendben
\def\nor{\nbool\lor}   %%% rendben
\def\leqv{\bool\equiv}    %%% rendben
\def\rcomp{\nbool{\rproj}}   %%% ábra kell
\def\cimpl{\bool\subset}   %%% rendben
\def\lcomp{\nbool{\lproj}}   %%% ábra kell
\def\impl{\bool\supset} %%% rendben
\def\nand{\nbool{\land}}  %%% rendben
\def\affirm{\bool{\top}}  %%% rendben
\def\vtiny{\vskip.2pt}    %%% rendben
\def\orie{\rlap{$\,\vec{}$}} % oriented graph modifier
\def\rest{\mathbin{\mid}}

\hyphenation{}

%\newpage
\tableofcontents
  
\hyphenation{
mély-ség-re
}
%%% 1
\ujgyak \label{gyak712-1}\sz{24}
A (\ref{keplet712-6})-os formula által leírt \idez{random} függvény egy 4~költségû, 
4~mélységû\index{mélység = depth} Boole-láncnak felel meg. \index{pí, random = pi, random}%^^{pi, random}
Keressünk olyan 3 mélységû formulát, melynek költsége változatlan.
%%% 2
\ujgyak \label{gyak712-2}\sz{21}
Mutassunk olyan 3 mélységû, 5 költségû formulát, mellyel kiszámítható\index{medián = median}%^^{median} 
(a) $w\xor \left\langle xyz\right\rangle$ illetve 
(b) $w\land \left\langle xyz\right\rangle$.
%%% 3
\ujgyak \label{gyak712-3}\sz{M23}
\cite{Finikov1957}\angolnevindex{Finikov, Borisz Ivanovics ({\rus Finikov, Boris Ivanovich})} 
Bizonyítsuk be, hogy ha egy $f\left(x_1,\ldots,x_n\right)$ Boole-függvény pontosan $k$ pontban igaz, akkor 
$L(f)<2n+\left(k-2\right)2^{k-1}$. Tekintsük a $k=3$, $n=10^6$ esetet.
%%% 4
\ujgyak \label{gyak712-4}\sz{M26}
\cite{Spira1971}\angolnevindex{Spira, Philip Martin}
Igazoljuk, hogy bármely $f$ Boole-függvény esetén a minimális mélységre, illetve formula hosszra teljesül, hogy
$\lg L(f) < D(f) \leq \alpha \lg L(f) +1$, ahol $\alpha = 2 / \lg(\frac{3}{2}) \approx 3.419$. 
\textit{Útmutatás:} Minden $r\geq 3$ belsõ csúcsot tartalmazó bináris fában létezik $s$ belsõ csúcsból álló részfa,
melyre $\frac{1}{3}r \leq s < \frac{2}{3}r$.
%%% 5
\ujgyak \label{gyak712-5}\sz{21}
Az $F_n(x_1,\ldots,x_n)= \left\langle x_1^{F_1} x_2^{F_2}\ldots x_{n-1}^{F_{n-1}} x_n^{F_{n-2}}\right\rangle$
Fibonacci határérték függvényt\index{Fibonacci küszöb-függvény = Fibonacci threshold function},
ahol $n\geq 3$, már elemeztük a \ref{gyak711-101} gyakorlatban. Létezik-e hatékony módszer a kiértékelésére?
%%% 6
\ujgyak \label{gyak712-6}\sz{20}
Igaz vagy hamis: egy $f\left(x_1,\ldots,x_n\right)$ függvény akkor, és csak akkor normalizált,
ha eleget tesz az $f\left(x_1,\ldots,x_n\right)\land y=f\left(x_1\land y,\ldots,x_n\land y\right)$
általános disztribúciós szabálynak.\index{disztribúciós szabály = distributive law}%^{distributive law}
%%% 7
\ujgyak \label{gyak712-7}\sz{20}
Alakítsuk át az `$x_5 = x_1\nor x_4$, $x_6=\bar x_2\lor x_5$, $x_7=\bar x_1\land\bar x_3$' Boole-láncot
egy vele ekvivalens $\left(\hat{x}_5,\hat{x}_6,\hat{x}_7,\hat{x}_8\right)$ lánccá, 
melyben minden lépés normalizált.\index{normalizált = normal}%^{normal}
%%% 8
\ujgyak \label{gyak712-8}\sz{20}
Magyarázzuk meg, hogy a (\ref{keplet712-11})-es kifejezés miért lehet az $x_k$ változó igazságtáblája.
\vspace{-2mm}
%%% 9
\ujgyak \label{gyak712-9}\sz{20}
Az L algoritmu\index{L algoritmus = Algorithm L} tetszõleges $f$ függvényhez megadja a legrövidebb formula hosszát,
de semmilyen további információval nem szolgál. Egészítsük ki az algoritmust úgy, hogy az megadjon egy a 
(\ref{keplet712-6})-oshoz hasonló tényleges minimum hosszúságú formulát.
%%% 10
\ujgyak \label{gyak712-10}\sz{20}
Módosítsuk az L algoritmust oly módon, hogy az $L(f)$ helyett $D(f)$-et számítsa ki.
%%% 11
\ujgyak \label{gyak712-11}\sz{22}
Módosítsuk az L algoritmust úgy, hogy az $L(f)$ helyett az $U(f)$ felsõ korlátot,
valamint a szövegben bemutatott $\phi(f)$~lábnyomot\index{lábnyom = footprint} számítsa ki.
%%% 12
\ujgyak \label{gyak712-12}\sz{15}
Milyen Boole-lánc felel meg a (\ref{keplet712-13})-as minimális-memóriájú
\index{minimális-memória = minimum-memory} sémának.
%%% 13
\ujgyak \label{gyak712-13}\sz{16}
Milyen igazságtáblák tartoznak a (\ref{keplet712-13})-as példa $f_1$, $f_2$, $f_3$, $f_4$ és $f_5$ függvényeihez?
\vspace{-2mm}
%%% 14
\ujgyak \label{gyak712-14}\sz{22}
Hogyan lehet alkalmas módon meghatározni a (\ref{keplet712-17})-es függvénnyel leírt $5n(n-1)$ igazságtáblát, ha ismerjük 
$g$ igazságtábláját? (Használjunk bitenkénti mûveleteket\index{bitenkénti mûvelet = bitwise operation} 
a (\ref{keplet712-15}), illetve (\ref{keplet712-16})-os példákhoz hasonlóan.)
%%% 15
\ujgyak \label{gyak712-15}\sz{28}
Hogyan számíthatóak ki a lehetõ legrövidebb módon az alábbi függvények minimális memória felhasználás mellett:
\index{szimmetrikus függvény = symmetric functions}%^^{symmetric functions}
(a) $S_2(x_1,x_2,x_3,x_4)$;
(b) $S_1(x_1,x_2,x_3,x_4)$;
(c) a (\ref{keplet712-18})-as függvény.

 
\bibliography{KnuthMarcius26}
\bibliographystyle{infalg}
\begin{printindex}
\end{printindex}
\begin{printangolnevindex}
\end{printangolnevindex}
\end{document}
