Студент Рачунарског факултета Алекса Плавшић је 29. септембра 2020. године одбранио дипломски рад на тему „Проблем проналажења најдужег пута у неусмереним нетежинским графовима“ пред комисијом коју су чинили: ментор др Драган Урошевић и члан др Ирена Јовановић.
„У овом дипломском раду је описан проблем проналажења најдужег пута у неусмереним нетежинским графовима. Како проблем спада у групу НП-тешких, представљено је неколико неполиномијалних алгоритама различитих сложености за графове опште структуре. Обрађене су поједине класе графова специјалне структуре за које су пронађени полиномијални алгоритми попут стабала, кактус графова и блок графова. Већина алгоритама је заснована на похлепном приступу и динамичком програмирању. На крају рада продискутовани су поједини апроксимативни алгоритми из ове области, као и оцене квалитета решења које они проналазе.“ – наведено је у апстракту.
„Иако је проблем активно изучаван претходних деценија, простор за даљи напредак и допринос постоји. Поред проучавања материјала и области које овом приликом нисмо обрадили, даље истраживање биће засновано на покушају проналаска полиномијалног решења за неку од до сада неистражених класа графова. Као резултат очекујемо да се искристалишу прецизни или апроксимативни алгоритми који ће увести нове границе или побољшати неке од постојећих. Таква открића би највероватније довела до осмишљавања решења и за друге проблеме сличне природе и дала повод за нове покушаје доказа једнакости између скупова НП и П.“ – закључио је Aлекса.
Фотографије са одбране налазе се у галерији.