Seminar za računarstvo i primenjenu matematiku, 16. jun 2020.

Naredni sastanak Seminara biće održan na daljinu, u utorak 16. juna 2020. sa početkom u 14:15 časova.

Predavač: doc. dr Nebojša Nikolić, Fakultet organizacionih nauka, Univerzitet u Beogradu

Naslov predavanja: ŠTAJNEROVI SISTEMI I (V, K, T) - POKRIVANjA

Apstrakt: Štajnerov sistem S(t, k, v) je skup koji sadrži v elemenata (v-skup) sa familijom k-podskupova (blokova), takvih da je svaki t-podskup sadržan u tačno jednom bloku. U slučaju (v, k, t) - pokrivanja, svaki t-podskup je sadržan u bar jednom bloku date familije. Problem egzistencije Štajnerovog sistema S(t, k, v) i problem određivanja vrednosti C(v, k, t) (kardinalnost minimalnog (v, k, t) - pokrivanja) su otvoreni problemi, a njihova rešenja su poznata samo u nekim specijalnim slučajevima. U radu je data nova kombinatorna konstrukcija minimalnih (v, 3, 2) - pokrivanja, koja predstavljaju uopštenje Bouzove i Skolemove konstrukcije Štajnerovih sistema trojki STS(6n+ 3) i STS(6n + 1). Preostale konstrukcije (v, k, t) - pokrivanja su heurističke. Koristeći pohlepni algoritam i takozvanu LR proceduru, razvijene su i implementirane tri heuristike: metoda velikih okolina, metoda promenljivog spusta i opšta metoda promenljivih okolina. Njihovom primenom u 23 slučaja su poboljšane do sada najbolje granice vrednosti C(v, k, t).

Praćenje predavanja moguće je isključivo preko linka https://miteam.mi.sanu.ac.rs/asset/qChPcMcAoji9JH5Dc

Pristup je slobodan i nije potrebno da se slušaoci loguju.



Ostavite vaš komentar:


(opciono)
(nece biti prikazano)