Seminarium: Struktury kombinatoryczne

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