-
Verjetnost v kombinatorični optimizaciji : doktorska disertacijaŽerovnik, JanezV 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 - dissertationPublication and manufacture - Ljubljana : [J. Žerovnik], 1990Language - slovenianCOBISS.SI-ID - 32382720
Author
Žerovnik, Janez
Other authors
Pisanski, Tomaž
Topics
matematika |
računalništvo |
kombinatorična optimizacija |
algoritem |
verjetnostna hevristika |
optimizacijski problem |
barvanje grafa |
verjetnostni problem trgovskega potnika |
algoritem Ohlajanje |
zahtevnost algoritmov |
disertacije |
mathematics |
computer science |
combinatorial optimization |
algorithm |
randomised heuristics |
optimization problem |
graph coloring |
probabilistic traveling salesman problem |
Simulated annealing |
algorithm complexity
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Call number – location, accession no. ... |
Copy status | Reservation |
---|---|---|
Skladišče-Jadranska 21 0000010551/0000000001 Skladišče-Jadranska 21 10551/1 |
available - reading room
|
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Žerovnik, Janez | 03430 |
Pisanski, Tomaž | 01941 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.