Na Seminaru za matematičku logiku i osnove matematike i Seminaru za
teorijsko računarstvo, u ponedjeljak 6. ožujka 2017. u 17 sati, u
predavaonici 104, PMF-MO, *Filip Nikšić* (Max Planck, Kaiserslautern) će
održati predavanje
Hitting families of schedules

*Sažetak:* Promotrimo sljedeću zadaću u testiranju istodobnih sustava
(engl. concurrent systems). Zadan je parcijalno uređen skup događaja koji
modelira akcije koje izvodi sustav te njihove međuovisnosti. Potrebno je
odrediti postoji li redoslijed događaja (engl. schedule) koji uzrokuje
grešku. Broj redoslijeda koje je potrebno provjeriti općenito može biti
eksponencijalno ovisan o broju događaja.

Empirijski je utvrđeno da mnoge greške istodobnih sustava imaju ''malu
dubinu'', tj. otkrije ih svaki redoslijed koji poreda nekih d ključnih
događaja na točno određen način, neovisno o redoslijedu drugih događaja, te
je pritom d malen u odnosu na ukupan broj događaja. Za pronalaženje svih
grešaka dubine d dovoljno je provjeriti redoslijede iz d-pogađajuće
familije redoslijeda (engl. d-hitting family of schedules). Skup
redoslijeda je d-pogađajuća familija ako za svaku dozvoljenu d-torku
događaja (e_1, …, e_d) postoji redoslijed u familiji u kojem je e_1 < …
< e_d. Veličina d-pogađajuće familije može biti mnogo manja od ukupnog
broja mogućih redoslijeda. Prirodno pitanje je u kojim okolnostima postoje
male d-pogađajuće familije i kako ih eksplicitno konstruirati.

Pokazuje se da je veličina najmanje d-pogađajuće familije dosad neistražena
generalizacija pojma dimenzije parcijalno uređenog skupa (pojmovi se
podudaraju za d=2). Iz teorije dimenzije znamo da je veličinu najmanje
d-pogađajuće familije teško odrediti već za d=2. No, kao što ćemo pokazati
u predavanju, za određene klase parcijalno uređenih skupova poput stabala i
serijsko-paralelnih uređaja moguće je eksplicitno konstruirati familije
polilogaritamske veličine u odnosu na broj događaja.

Tin Perkov