\documentstyle[oldlfont,a4ams,righttag,ctagsplt,emlines2,11pt]{amsart} \title{ABZ\"AHLPROBLEME BEI B\"AUMEN} \author[]{Helmut Prodinger (Wien)} \date{} \def \Reg{\text{\rm Reg}} \begin{document} \maketitle \noindent Es sei ${\cal B}$ die Familie der bin\"aren B\"aume. ${\cal B}$ kann durch eine {\it formale Gleichung} beschrieben werden: \begin{figure}[h] %\input{baum2.pic} \special{em:linewidth 0.4pt} \unitlength .800mm \linethickness{0.4pt} \begin{picture}(117.00,24.36) \put(106.33,21.67){\circle{5.37}} \emline{104.33}{19.67}{1}{98.67}{11.00}{2} \emline{108.00}{19.33}{3}{114.33}{11.33}{4} \put(67.67,13.00){\framebox(6.33,5.67)[cc]{}} \put(96.67,8.00){\makebox(0,0)[cc]{$\cal B$}} \put(117.00,8.00){\makebox(0,0)[cc]{$\cal B$}} \put(86.67,16.33){\makebox(0,0)[cc]{+}} \put(56.67,16.33){\makebox(0,0)[cc]{$\cal B\ \ = \ \ $}} \end{picture} \end{figure} \noindent Dies besagt, da{\ss} ein bin\"arer Baum entweder ein Blatt (externer Knoten) ist, oder eine Wurzel zusammen mit einem linken und einem rechten Teilbaum, welche selbst bin\"are B\"aume sind. Diese formale Gleichung kann \"ubersetzt werden in eine Gleichung f\"ur die erzeugende Funktion $B(z)$: $$ B(z)=1+zB^{2}(z);$$ $$ B(z)=\frac{1-\sqrt{1-4z}}{2z}=\sum_{n\geq 0}\,\frac{1}{n+1}\,{2n\choose n}z^n.$$ Bin\"are B\"aume k\"onnen verwendet werden, um arithmetische Ausdr\"ucke darzustellen: \begin{figure}[h] %\input{baum1.pic} \special{em:linewidth 0.4pt} \unitlength 0.70mm \linethickness{0.4pt} \begin{picture}(170.00,59.09) \put(83.00,54.00){\circle{10.18}} \emline{79.33}{50.33}{1}{65.00}{36.00}{2} \emline{86.00}{50.00}{3}{100.00}{36.00}{4} \put(118.33,3.33){\framebox(10.00,9.67)[cc]{}} \put(55.33,26.33){\framebox(10.00,9.67)[cc]{}} \put(101.00,31.00){\circle{10.18}} \emline{97.33}{27.33}{5}{83.00}{13.00}{6} \emline{104.00}{27.00}{7}{118.00}{13.00}{8} \put(73.33,3.33){\framebox(10.00,9.67)[cc]{}} \put(83.00,54.00){\makebox(0,0)[cc]{$\times$}} \put(101.00,31.00){\makebox(0,0)[cc]{$+$}} \put(60.33,31.00){\makebox(0,0)[cc]{3}} \put(78.33,8.00){\makebox(0,0)[cc]{7}} \put(123.33,8.00){\makebox(0,0)[cc]{4}} \put(139.67,32.00){\makebox(0,0)[cc]{$\longleftrightarrow$}} \put(170.00,32.00){\makebox(0,0)[cc]{$3\, \times \, (\, 7\, +\, 4\, )$}} \end{picture} \end{figure} Die Auswertung kann mit Hilfe von Registern erfolgen; diese werden verwendet, um Zwischen\-ergebnisse zu speichern. Die {\it Registerfunktion {\rm Reg}(t)} ist definiert als die minimale Anzahl von Registern zur Auswertung des Baumes {\it t} unter Verwendung der optimalen Strategie. \newpage Es gilt: $$ {\rm Reg}(\square)=0 $$ \begin{figure}[h] %\input{baum3.pic} \special{em:linewidth 0.4pt} \unitlength 1.00mm \linethickness{0.4pt} \begin{picture}(49.00,19.67) %\vector(27.33,10.00)(32.33,19.33) \put(32.33,19.33){\circle{2.67}} \emline{27.33}{10.00}{1}{32.33}{19.33}{2} %\end \emline{32.67}{18.67}{3}{37.33}{10.67}{4} \put(26.67,6.67){\makebox(0,0)[cc]{$t_1$}} \put(38.00,6.67){\makebox(0,0)[cc]{$t_2$}} \put(19.00,14.33){\makebox(0,0)[cc]{$\Reg\bigg($}} \put(42.67,14.67){\makebox(0,0)[lc]{$\bigg)\quad =\quad \Bigg\{\ $}} \put(65.00,19.67){\makebox(0,0)[lc]{$1+\Reg(t_1)$\quad falls $\Reg(t_1)=\Reg(t_2)$}} \put(65.00,10.00){\makebox(0,0)[lc]{$\max\{\Reg(t_1),\Reg(t_2)\}$\quad sonst}} \end{picture} \end{figure} Es sei ${\cal R}_{p} \ ({\cal S}_{p})$ die Familie der B\"aume mit Registerfunktion $=p \: \ (\geq p);$ $R_{p}(z)$ und $S_{p}(z)$ seien die entsprechenden erzeugenden Funktionen. Man sieht unmittelbar: \begin{figure}[h] %\input{baum5.pic} \special{em:linewidth 0.4pt} \unitlength 1mm \linethickness{0.4pt} \begin{picture}(129.00,22.67) %\vector(50.00,9.00)(57.33,22.00) \put(57.33,22.00){\circle{2.67}} \emline{50.00}{9.00}{1}{57.33}{22.00}{2} %\end \emline{57.67}{21.33}{3}{62.33}{9.33}{4} %\vector(83.33,9.33)(90.67,22.33) \put(90.67,22.33){\circle{2.67}} \emline{83.33}{9.33}{5}{90.67}{22.33}{6} %\end %\vector(116.67,9.67)(124.00,22.67) \put(124.00,22.67){\circle{2.67}} \emline{116.67}{9.67}{7}{124.00}{22.67}{8} %\end \emline{91.00}{21.67}{9}{95.67}{9.67}{10} \emline{124.33}{22.00}{11}{129.00}{10.00}{12} \put(47.33,6.00){\makebox(0,0)[cc]{${\cal R}_{p-1}$}} \put(62.33,5.67){\makebox(0,0)[cc]{${\cal R}_{p-1}$}} \put(27.67,15.67){\makebox(0,0)[cc]{${\cal R}_p$}} \put(41.00,15.67){\makebox(0,0)[cc]{$=$}} \put(75.00,15.67){\makebox(0,0)[cc]{$+$}} \put(108.33,15.67){\makebox(0,0)[cc]{$+$}} \put(81.33,5.33){\makebox(0,0)[cc]{$\sum\limits_{j