Open Access

Oliver Gebhard

• Although everyone is familiar with using algorithms on a daily basis, formulating, understanding and analysing them rigorously has been (and will remain) a challenging task for decades. Therefore, one way of making steps towards their understanding is the formulation of models that are portraying reality, but also remain easy to analyse. In this thesis we take a step towards this way by analyzing one particular problem, the so-called group testing problem. R. Dorfman introduced the problem in 1943. We assume a large population and in this population we find a infected group of individuals. Instead of testing everybody individually, we can test group (for instance by mixing blood samples). In this thesis we look for the minimum number of tests needed such that we can say something meaningful about the infection status. Furthermore we assume various versions of this problem to analyze at what point and why this problem is hard, easy or impossible to solve.
• Obwohl wir alle mit der Nutzung von Algorithmen vertraut sind, stellt sich deren mathematische Analyse oft als schwierig heraus. Da unsere moderne Welt ein sich schnell entwickelndes, komplexes System darstellt, ist die Analyse in diesem Kontext so gut wie aussichtslos. Deshalb haben Wissenschaftler begonnen, Modelle zu entwickeln, die einzelne Aspekte der realen Welt abbilden, aber durch vereinfachende Annahmen leicht zu analysieren bleiben. Nun stellt man schnell fest, dass einige Probleme zwar auf den ersten Blick leicht wirken, aber am Ende doch schwerer zu lösen sind als gedacht. In dieser Thesis tragen wir unseren Teil dazu bei, Problemstellungen zu finden, bei denen die Lösung leicht, schwer oder unmöglich ist. Wir nehmen uns ein spezielles Problem heraus und analysieren, ob und warum dieses Problem algorithmisch lösbar ist oder nicht. Das Problem unserer Wahl ist das Group Testing Problem. Im Jahre 1943 wurde das Problem von R. Dorfman erstmals eingeführt. Angenommen wir haben eine Gruppe von Personen und einige von ihnen sind erkrankt. Anstatt jeden einzeln zu testen, können wir Gruppen testen. Dies kann zum Beispiel durch das Vermischen von mehreren Speichel-Proben erreicht werden. Ein solcher Gruppen-Test ist positiv genau dann, wenn mindestens ein Infizierter in der Gruppe ist und negativ, wenn alle Teilnehmerinnen gesund sind. Die Frage ist nun, was die minimale Anzahl an Tests ist, die nötig ist, sodass das Problem algorithmisch leicht, schwer oder unmöglich zu lösen ist. In dieser Arbeit betrachten wir verschiedene Abwandlungen dieses Problems.