Back to search

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:description

This 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, non­homogeneous context. Simulation experiments showed that when the defect probabilities satisfy certain conditions, the structural conclusions of Yao and Hwang also hold in the non­homogeneous 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.*

Chain of custody

source
Harvested from
Vilnius University
Base URL
epublications.vu.lt/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Cifirov, Anton,. Optimalių abėcėlinių dvejetainių paieškos medžių simuliacija ir tyrimas naudojant duomenų analizės metodus grupinio testavimo kontekste /. Institutional Repository of Vilnius University, 2025. https://repository.vu.lt/VU:ELABAETD239028406&prefLang=en_US