Студент Рачунарског факултета Драгомир Божанић је у среду, 9. јула 2025. године одбранио дипломски рад на тему Паковање кругова: алгоритми и примена пред комисијом коју су чинили ментор др Марко Младеновић и члан др Селена Вукотић.
У уводу свог рада Драгомир је истакао:
Проблеми паковања су део инжењерских наука, као и теоретских, попут математике и рачунарски наука. На пример, у математичкој естетици као и у препознавању геометријских облика код биљака проучавани су још од почетка XX века, нпр. у раду Arnolda Еmcha ([1]). Исти аутор, у раду о Doule-овим спиралама у филотакси1 1910 је први поставио проблем паковања кругова у круг ([2, 3]). За разлику од проблема ранца (енг. knapsack проблем, погледати семинални рад Карпа [4]), који је дискретан, проблеми паковања су континуални и геометријске природе. Неки од проблема паковања могу да гласе:
• колико максимално кругова истог пречника можемо уписати у јединички круг?
• Колико максимално кругова истог пречника можемо уписати у правоугаоник?
• Аналогно за кругове различитих пречника, итд.
…
Дакле као што видимо Circle Packing има широк спектар примена од којих су рецимо неки од основних биологија, медицина, ИТ, агрокултура и још многи други.
У овом раду је приказана разлика у ефикасности 4 алгоритма који су коришћени за проналажење најмањег пречника кружног контејнера за кругове различитих димензија. Иако је греедy оптималан у одредјеним условима овде показујемо да то није случај. Али пошто је ово НП-проблем не постоји гаранција да је то оптимално решење, већ да је то једноставно решење које смо добили. – закључио је Драгомир.
Фотографије са одбарне доступне су у галерији.