Institutional Repository of Vilnius University
Optimalių abėcėlinių dvejetainių paieškos medžių simuliacija ir tyrimas naudojant duomenų analizės metodus grupinio testavimo kontekste /
Abstract
dc:descriptionThis thesis investigates the problem of optimality in group testing (GT), particularly in the identification of the first defective item. Based on the classical theorem by Hwang and Garey, the problem is modeled via the construction of optimal alphabetic binary search trees (OABST). The Hu–Tucker algorithm was implemented to construct such trees that minimize the expected number of tests, where node weights correspond to defect probabilities. Based on the Yao and Hwang theorem, which provides an explicit form of the first defective item search procedure in the homogeneous case, this procedure was extended to a more general, nonhomogeneous context. Simulation experiments showed that when the defect probabilities satisfy certain conditions, the structural conclusions of Yao and Hwang also hold in the nonhomogeneous case. The main objective of the study was to empirically and statistically analyze when the generated trees exhibit structurally ”simple” forms—namely, when no internal node tests more than two elements. The methodology includes simulation, regression modeling, and machine learning. The analysis resulted in an empirical approximation of the simplicity constant c which was calculated for the case of 2 unique probabilities and for the case of all unique defect probabilities in the starting sequence. When all node probabilities exceed this constant, the resulting trees are structurally simple. These findings provide both theoretical and practical insights for the design of efficient Group testing procedures.
Degree
thesis:*- Grantor dc:publisher
- Institutional Repository of Vilnius University
- Year dc:date
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Cifirov, Anton,
Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- lit
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.vu.lt/VU:ELABAETD239028406&prefLang=en_US