UP - logo
University of Primorska University Library - all departments (UPUK)
  • Verjetnost v kombinatorični optimizaciji : doktorska disertacija
    Žerovnik, Janez, 1958-
    V zadnjem desetletju je bilo ponovno opaziti naraščajoč interes strokovne javnosti za razvijanje verjetnostnih algoritmov za reševanje determinističnih problemov. Po drugi strani je znano da mnogi ... praktični problemi vsebujejo elemente nepredvidljivosti, ki jo lahko formalno izrazimo s slučajnimi spremenljivkami. V uvodnih poglavjih vpeljemo osnovne koncepte kot je definicija splošnega problema kombinatorične optimizacije in ideja verjetnostnega algoritma. V 4. poglavju obravnavamo algoritem Ohlajanje, v zadnjih letih popularni algoritem za reševanje problemov kombinatorične optimizacije. Dokažemo, da je algoritem asimptotsko slabši od enostavnega algoritma lokalna optimizacija. Primerjavo razširimo na zelo splošni model vzporednega izvajanja. V 5. poglavju obravnavamo problem barvanja grafa. Vpeljemo vzporedno različico verjetnostnega algoritma Petforda in Welsha za 3-barvanje grafov in zanj dokažemo konvergenčno lastnost. Poročamo o poskusih z algoritmi istega tipa na nekaterih vzorcih slučajnih grafov. Dokažemo NP-polnost odločitvenih problemov 3 in 4-barvanja na regularnih grafih dovolj velikih stopenj. V 6. poglavju obravnavamo verjetnostni problem trgovskega potnika. Izpeljemo formulo za postopno računanje stroškovne funkcije, ki nam na naravni način definira razred konstruktivnih hevrističnih algoritmov.
    Type of material - dissertation
    Publication and manufacture - Ljubljana : [J. Žerovnik], 1990
    Language - slovenian
    COBISS.SI-ID - 32382720

Call number – location, accession no. ... Copy status Reservation
Univerzitetna knjižnica skladišče
dis ŽEROVNIK JANEZ Verjetnost
IN: 04000000303 Univerzitetna knjižnica skladišče
dis ŽEROVNIK JANEZ Verjetnost
IN: 04000000303 		available - reading room
loading ...
loading ...
loading ...

Shelf entry