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

egzamin

Literatura


  • 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.