\documentstyle[oldlfont,righttag,ctagsplt,11pt]{amsart} \catcode`\@=11 \if@twocolumn \textwidth175mm \marginparsep2.5mm \oddsidemargin-7.9mm \evensidemargin-7.9mm \else \ifcase \@ptsize\relax \textwidth145mm \oddsidemargin7.1mm \evensidemargin7.1mm \or \textwidth154mm \oddsidemargin2.6mm \evensidemargin2.6mm \or \textwidth164mm \oddsidemargin-2.4mm \evensidemargin-2.4mm \fi \marginparsep4mm \fi \ifcase \@ptsize\relax \textheight 52\baselineskip \or \textheight 46\baselineskip \or \textheight 43\baselineskip \fi \addtolength{\textheight}{\topskip} \topmargin-10mm \catcode`\@=12 % emlines.sty Mai 1990, Georg Horn / Eberhard Mattes. % % Makros zum Zeichnen von Linien mit beliebiger Steigung. % % **************************************************************** % * Nur funktionsf„hig mit den dvi-Treibern von Eberhard Mattes * % * ab Version 1.3j. * % **************************************************************** % % Der Makro \emline#1#2#3#4#5#6 verbindet den Punkt mit den % Koordinaten (#1,#2) und den Punkt mit den Koordinaten (#4,#5). % Die Parameter #3 und #6 werden ignoriert. % % TeXcad erzeugt Aufrufe dieses Makros fr mit eingeschalteter % EMLines-Option gezeichnete Linien. % (z.B. \emline{0.0}{0.0}{1}{17.0}{4.0}{2}). % \def\emline#1#2#3#4#5#6{% \put(#1,#2){\special{em:moveto}}% \put(#4,#5){\special{em:lineto}}} % % Der Makro \newpic#1 wird ignoriert, da nicht mehr erforderlich. % \def\newpic#1{} \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