Семинар за рачунарство и примењену математику, 16. јун 2020.
Наредни састанак Семинара биће одржан на даљину, у уторак 16. јуна 2020. са почетком у 14:15 часова.
Предавач: доц. др Небојша Николић, Факултет организационих наука, Универзитет у Београду
Наслов предавања: ШТАЈНЕРОВИ СИСТЕМИ И (V, K, T) - ПОКРИВАЊА
Апстракт: Штајнеров систем S(t, k, v) је скуп који садржи v елемената (v-скуп) са фамилијом k-подскупова (блокова), таквих да је сваки t-подскуп садржан у тачно једном блоку. У случају (v, k, t) - покривања, сваки t-подскуп је садржан у бар једном блоку дате фамилије. Проблем егзистенције Штајнеровог система S(t, k, v) и проблем одређивања вредности C(v, k, t) (кардиналност минималног (v, k, t) - покривања) су отворени проблеми, а њихова решења су позната само у неким специјалним случајевима. У раду је дата нова комбинаторна конструкција минималних (v, 3, 2) - покривања, која представљају уопштење Боузове и Сколемове конструкције Штајнерових система тројки STS(6n+ 3) и STS(6n + 1). Преостале конструкције (v, k, t) - покривања су хеуристичке. Користећи похлепни алгоритам и такозвану LR процедуру, развијене су и имплементиране три хеуристике: метода великих околина, метода променљивог спуста и општа метода променљивих околина. Њиховом применом у 23 случаја су побољшане до сада најбоље границе вредности C(v, k, t).
Праћење предавања могуће је искључиво преко линка https://miteam.mi.sanu.ac.rs/asset/qChPcMcAoji9JH5Dc
Приступ је слободан и није потребно да се слушаоци логују.
Коментари(0)