Семинар за рачунарство и примењену математику, 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

Приступ је слободан и није потребно да се слушаоци логују.


Оставите ваш коментар:


(опционо)
(неће бити приказано)



Вести и дешавања


Активности на семинарима

све вести