Teoria grafów w ujęciu algorytmicznym
Informacje ogólne
Semestr:letni
Wymiar zajęć:30 godzin wykładu, 30 godzin ćwiczeń
Program
- Podstawy teorii algorytmów. Problemy algorytmiczne i niealgorytmiczne. Pojęcie złożoności obliczeniowej. Analiza algorytmów rekurencyjnych. Algorytmy niedetermistyczne i probabilistyczne. Problemy NP zupełne. Algorytmy przybliżone.
- Podstawy teorii algorytmów. Pojęcie grafu. Drzewa i grafy planarne. Komputerowa reprezentacja grafu.Wielomianowe problemy teoriografowe. NP trudne problemy teoriografowe. Problemy kolorowania grafów.
Sposób zaliczenia
egzaminLiteratura
- R. Wilson. Wprowadzenie do teorii grafów. PWN, Warszawa, 2000.
- M. Kubale i in., Optymalizacja dyskretna. Modele i metody kolorowania grafów WNT, Warszawa, 2002.
- M. Kubale, Introduction to Computational Complexity and Algorithmic Graph Coloring, GTN, Gdańsk 1998.
