ELFT HÍRADÓ

[StatFizSzeminar <statfiz AT glu.elte.hu>]

                      #    #    #    #    #    #

                       ELTE TTK Fizikai Intézet
                   STATISZTIKUS FIZIKAI SZEMINÁRIUM
                  

                         2012. március 7.
                          szerda 11 óra

                       Ercsey-Ravasz Mária
                           
             Babeş-Bolyai Tudományegyetem, Fizika Kar
                       Kolozsvár, Románia
                     
  "Korlátozás kielégítési feladatok megoldása folytonos idejű 
   dinamikus rendszerekkel: az optimalizálás nehézsége mint 
                       tranziens káosz"

Az egyik leggyakrabban tanulmányozott korlátozás kielégítési feladat a 
k-SAT probléma. NP-teljes feladat lévén, sok más nehéz optimalizálási 
feladat könnyen átalakíható SAT formába. Jelenlegi módszerekkel digitális 
számítógépeken ezek a feladatok nem oldhatók meg hatékonyan: a legnehezebb 
feladatokban a megoldáshoz szükséges idő a feladatok méretével 
exponenciálisan nő. A k-SAT és a spinüveg modellek közötti párhuzam miatt 
az utóbbi évtizedben sok statisztikus fizikai tanulmány is született ebben 
a témában. Az előadásban a dinamikus rendszerek szemszögéből közelítjük meg 
ezt a feladatot. Olyan determinisztikus differenciálegyenleteket mutatunk 
be, amelyeknek az attraktorai és a feladat megoldásai között egyedi 
megfeleltetés létezik. Analitikus és szimulációs eredmények azt mutatják, 
hogy a rendszer a legnehezebb feladatokban is megtalálja a megoldást 
anélkül, hogy lokális minimumokba ragadna be. A korlátozások számát növelve 
a feladatok nehézsége a dinamikában tranziens káoszként jelentkezik. Mint 
kiderül, folytonos idejű rendszerekben a feladatok komplexitását is másképp 
kell értelmezni. A digitális számítógépekkel ellentétben energia 
befektetéssel időt nyerhetünk: exponenciálisan nagy energia fluktuációk 
árán az NP-teljes feladatok is megoldhatók polinomiális folytonos időben.

            1117. Budapest, Pázmány P. sétány 1/A, Északi tömb
                                 2.54

                                honlap:
                      http://glu.elte.hu/~statfiz

                      #    #    #    #    #    #