SRPSKA AKADEMIJA NAUKA I UMETNOSTI
Odeljenje za matematiku, fiziku i geo-nauke
Četvrtak, 3.04.2014. u 12:00h, Svečana sala
SANU:
Slobodan K. Simic, Matematicki institut SANU
SPEKTRALNA TEORIJA GRAFOVA I NJENE PRIMENE
Spektralna teorija grafova je matematicka disciplina koja pre svega pripada
diskretnoj matematici. Medjutim, u cilju proucavanja grafova kao
kombinatornih objekata, nekad je skoro neizbezno koristiti linearnu algebru,
odnosno matricni racun. Pored teorijskih pogodnosti, poseban razlog za to
lezi i u cinjenici da su mnogi algoritmi u teoriji grafova eksponencijalne
slozenosti, za razliku od osnovnih algoritama spektralne teorije matrica
koji su polinomijalni. Time je zacrtana znajna veza izmedju grafova i racunara,
odnosno sire gledano racunarstva. U ovom predavanju bice prikazani glavni
rezultati predavaca ostvareni u oblasti spektralne teorije grafova u
poslednjih desetak godina.
Četvrtak, 3.04.2014. u 12:00h, Svečana sala SANU:
Nenad Mladenovic, Matematicki institut SANU
PROMENA OKOLINA I FORMULACIJA U RESAVANJU PROBLEMA OPTIMIZACIJE
Problemi kombinatorne i kontinualne optimizacije najcesce sadrze veliki broj
lokalnih optimuma, koji se mogu relativno lako naci koriscenjem klasicne
matematicke analize. Sa druge strane, nalazenje globalnog optimuma (zajedno
sa dokazom da bolje resenje ne postoji) vezano je sa numerickim teskocama,
posto ne postoji teorija koja bi dala dovoljne uslove optimalnosti u opstem
slucaju. Ukoliko se
takva procedura i nadje, broj racunskih operacija raste eksponencijalno sa
rastom dimenzije problema. Iz tog razloga krajem proslog veka razvijene su
metode trazenja ili heuristike (ili dosetke), cijom se primenom ne garantuje
optimalno, ali se vrlo brzo nalaze priblizna kvalitetna resenja. U ovom
izlaganju ja cu izneti principe dve generalne heuristike, metode promena
okolina i metode promena formulacija, i navesti neke primere njihovih
primena uz poredjenje sa drugim generalnim heuristickim metodama.