Mamy dziewięć pozornie jednakowych monet. Wiemy, że jedna z nich jest fałszywa
i waży mniej niż pozostałe. Do dyspozycji mamy wagę szalkową, na której możemy
porównywać wagę wybranych grup monet. Ile ważeń potrzeba aby wykryć fałszywą
monetę?
Jaki związek ma powyższy problem z testami na obecność chorób zakaźnych u
rekrutów do amerykańskiej armii i projektowaniem algorytmów rozproszonych? W
każdym przypadku interesuje nas zaprojektowanie eksperymentu, który w
rozsądnym czasie pomoże nam rozwiązać problem. Eksperymentem tym będzie
zazwyczaj jakiś rodzaj struktury kombinatorycznej (np. rodzina podzbiorów
ustalonego zbioru lub graf).
Seminarium będzie dotyczyło struktur oraz technik kombinatorycznych, ich
konstrukcji oraz zastosowań m. in. w algorytmach rozproszonych, biologii
obliczeniowej, bezpieczeństwie sieciowym.
słowa kluczowe: combinatorial design theory, group testing, selector,
selective set family, disjunct matrix, disperser, expander
[1] Applications of Combinatorial Designs to Communications, Cryptography, and
Networking - C.J. Colbourn, J.H. Dinitz, D.R. Stinson
[2] Optimal Two-Stage Algorithms for Group Testing Problems - A. De Bonis, L.
Gąsieniec, U. Vaccaro
[3] Explicit Non-Adaptive Combinatorial Group Testing Schemes - E. Porat, A.
Rotschild
[4] Combinatorial Group Testing and Applications - Ding-Zhu Du, F. K. Hwang
[5] Distributed broadcast in radio networks of unknown topology - A. E. F.
Clementi, A. Monti, R. Silvestri
[6] A Lower Bound for Radio Broadcast - N. Alon, A. Bar-Noy, N. Linial, D.
Peleg
[7] Group Testing Theory in Network Security: An Advanced Solution - M. T.
Thai
