Combinatorial Search in Trees

German Title: Kombinatorische Suche in Bäumen

German Summary: Die kombinatorische Suche beschäftigt sich mit der Anzahl der notwendigen Fragen, um in einer Menge $S$ ein oder mehrere sogenannte defekte Elemente zu finden.
Das Thema dieser Arbeit ist die Fragestellung:
\begin{quotation} \noindent Wie verändert sich die Suchkomplexität, wenn die Menge $S$ aus den Blät\-tern eines Wurzelbaumes~$T$ besteht und Testmengen nur komplette Teil\-bäu\-me sein dürfen? \end{quotation}
Die Anzahl der Fragen in einem Baum~$T$, die ausreichen ein Blatt zu finden, hängt von der Struktur des Baumes $T$ ab. Unter allen $q$-Bäu\-men, die eine vorgegebene Anzahl von Fragen erfordern, läßt sich ein Baum mit minimaler Blattanzahl rekursiv berechnen. Kapitel~\ref{eindef} beschreibt die Rekursionsvorschrift.
Sind mehrere Blät\-ter defekt, so existiert zu jedem $n\in{\Bbb N}$ ein bi\-nä\-rer Baum mit $n$~Blät\-tern, bei dem $n-1$ Fragen notwendig sind. Zum Suchproblem von mehreren defekten Blät\-tern in voll\-stän\-di\-gen $q$-regulären Bäu\-men steht in Kapitel~\ref{mehrdef} und~\ref{mehq} die exakte Formel für die Suchkomplexität.Ein paralleler Suchalgorithmus, der ein defektes Blatt sucht, muß bei $n$~Blät\-tern $n-1$~Fragen stellen. In den Kapiteln~\ref{parkap} und~\ref{paqkap} steht die exakte Suchkomplexität, wenn die Fragen in mehreren Runden gestellt werden, wobei die Fragen jeder einzelnen Runde parallel beantwortet werden.
Wird in einem voll\-stän\-di\-gen bi\-nä\-ren Baum der Tiefe~$m$ ein Blatt gesucht, so beträgt die Suchkomplexität~$m$. Kann aber eine der Antworten falsch sein, so wächst die Suchkomplexität auf $$m+\left\lceil\sqrt{2m+\frac{1}{4}}+\frac{1}{2}\right\rceil.$$

Keywords: combinatorial search, search complexity, error correcting codes

Mathematics Subject Classification (MSC91): 68P10 Searching and sorting , 05C05 Trees

Language: GER

Date of Disputation: 1997-07-01

First Referee = Advisor: Aigner, Martin

Second Referee: Triesch, Eberhard

Publisher: Freie Universität Berlin, Fachbereich Mathematik und Informatik

Online Available: ftp://ftp.math.fu-berlin.de/pub/math/publ/thes/1997/Diss-Recker.ps

Contact (Candidate): frank.recker@detmold.netsurf.de

Contact (Advisor): aigner@math.fu-berlin.de

- Created: 1998-03-30