DOKTORANTŪROS STUDIJŲ KURSO PROGRAMA
Grafų teorija
Kursas skirtas Informatikos specialybės doktorantams.
Kurso tipas: privalomasis.
Apimtis: 60 val.
Atsiskaitymai: seminarai, egzaminas.
Dėstytojas: prof., hab.dr. Eugenijus Manstavičius
Anotacija: Kurse nagrinėjami fundamentalūs grafų teorijos uždaviniai bei pateikiami jų sprendimo algoritmai, skirti tiesiogiai realizuoti kompiuteriais. Kartu griežtai įrodomas visų pateiktų algoritmų korektiškumas bei išanalizuojamas ir asimptotiškai įvertinamas jų efektyvumas.
Tematika
- Elementarūs grafų algoritmai
- Grafų vaizdavimas kompiuteryje
- Paieška į plotį
- Paieška į gylį
- Topologinis rūšiavimas
- Tampriai susieti komponentai
- Minimalūs jungiantieji medžiai
- Minimalaus jungiančiojo medžio auginimas
- Kruskalio ir Primo algoritmai
- Trumpiausi atstumai nuo vienos viršūnės
- Trumpiausias kelias ir relaksacija
- Dijkstros algoritmas
- Belmano-Fordo algoritmas
- Trumpiausias kelias orientuotuose grafuose be ciklų
- Skirtuminiai apribojimai ir trumpiausi keliai
- Trumpiausi atstumai tarp viršūnių porų
- Trumpiausi keliai ir matricų daugyba
- Floydo-Varšalo algoritmas
- Džonsono algoritmas išretintiems grafams
- Bendra schema orientuotų grafų kelių problemų sprendimui
- Maksimalus srautas
- Srautų tinklai
- Fordo-Fulkersono metodas
- Maksimalus dvidalių grafų suporavimas
- Priešsraučio stūmimo algoritmai
- Perkėlimo į priekį algoritmai
Literatūra
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms; McGraw-Hill Book Company, 1993.
- Béla Bollobás: Graph Theory; An Introductory Course; Springer-Verlag New York Inc., 1979.
- Reinhard Diestel: Graph Theory; Springer-Verlag New York, 1997.
Pradinis puslapis |
Main page