Group tests on r-ary trees

Sieg, Volker; Triesch, Eberhard

doi:26433

Group tests on r-ary trees

Sieg, Volker (Author)

2005

Verantwortlichkeitsangabevorgelegt von Volker Sieg

ImpressumAachen : Publikationsserver der RWTH Aachen University 2005

UmfangV, 126 S.

Aachen, Techn. Hochsch., Diss., 2005

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Triesch, Eberhard (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2005-06-01

Online
URN: urn:nbn:de:hbz:82-opus-11129
URL: https://publications.rwth-aachen.de/record/62245/files/Sieg_Volker.pdf

Einrichtungen

Fakultät für Mathematik, Informatik und Naturwissenschaften (100000)

Inhaltliche Beschreibung (Schlagwörter)
Gruppentesten (Genormte SW) ; Baum <Mathematik> (Genormte SW) ; Mathematik (frei) ; group tests (frei) ; r-ary trees (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Die vorliegende Arbeit beschäftigt sich mit Gruppentests auf vollständigen und semi-vollständigen r-Bäumen. Ein vollständiger r-Baum besteht aus einer Wurzel, inneren Ecken und r^k Blättern, wobei alle Blätter den Abstand k zur Wurzel haben. Ein semi-vollständiger r-Baum ist ein vollständiger r-Baum mit zusätzlichen Blättern mit Abstand k+1 zur Wurzel, die von links angefügt werden. Untersucht wurde die Anzahl der Gruppentests, die im worst-case Fall benötigt werden, um d als defekt ausgezeichnete Blätter eines (semi-)vollständigen Baumes B unter den übrigen nicht defekten zu finden. Ein Gruppentest ist ein Test einer Menge T von Blättern von B, wobei T nur alle Blätter eines (semi-)vollständigen r-Teilbaumes von B enthalten darf. Ein solcher Test ist positiv, wenn sich mindestens ein defektes Blatt in T befindet. Im anderen Fall ist der Test negativ. In Kapitel 2 wird die exakte Anzahl der Gruppentests im worst-case Fall bei a priori bekanntem d für vollständige r-Bäume bestimmt und eine Abschätzung bei unbekanntem d vorgestellt (genauer: es wird ein r/(r-1)-competitiver Algorithmus angegeben). Die Anzahl von Tests für alle semi-vollständigen r-Bäume wird in Kapitel 3, dem Hauptteil der Arbeit, bestimmt und es wird wiederum eine Abschätzung für den Fall einer a priori unbekannten Anzahl von defekten Blättern gegeben (ebenfalls ein r/(r-1)-competitiver Algorithmus).

This thesis deals with group tests on complete and semi-complete r-ary trees. A complete r-ary tree consists of a root, some inner nodes and r^k leaves, where all leaves have the same distance k to the root. A semi-complete r-ary tree is a complete r-ary tree with additional leaves, that have distance k+1 to the root, filled in from left. In this work the number of group tests are examined that are needed in the worst-case to identify d defective leaves of a (semi-)complete r-ary tree B among the other non-defective leaves. A group test is a test of a set T of leaves of B, where T consists of all leaves of a (semi-)complete r-ary subtree of B. Such a test is positive, if there is at least one defective leaf that belongs to the set T. If there is no defective leaf in T the test is negative. In Chapter 2 the exact number of group tests in the worst is determined if d is known in advance. Otherwise a boundary for the number of tests is given (precisely: a r/(r-1)-competitive algorithm is presented). In Chapter 3 – which is the main part of this thesis – the number of group tests for all semi-complete r-ary trees is determined in case d is known in advance and a boundary is given if d is a priori unknown (again a r/(r-1)-competitive algorithm is presented).

Fulltext:
PDF
(additional files)