Informatyka II

Semestr zimowy

Algorytmy grafowe

Data Temat Wykład Ćwiczenia
17.10.2018 Reprezentacje grafu. Metody przeszukiwania grafu. Spójne składowe. AG01.pdf Zaimplementuj algorytmy DFS i BFS przy reprezentacji macierzowej oraz list sąsiedztwa. Zaimplementuj algorytm do przechodzenia po labiryncie. Zobacz w tym celu. punkt 5
24.10.2018 Sortowanie topologiczne. Badanie acykliczności. Algorytmy zachłanne. Grafy z wagami. Minimalne drzewo rozpinajace grafu. AG02.pdf
AG03.pdf
Zaimplementuj algorytmy prezentowane na wykładzie.
7.11.2018 Ścieżka i cykle Eulera -- mosty królewieckie. Ścieżka i cykle Hamiltona -- problem komiwojażera. AG04.pdf Zaimplementuj algorytmy prezentowane na wykładzie.
21.11.2018 Algorytm Dijkstry oraz Algorytm Bellmana-Forda -- najkrótsze ścieżki z danego wierzchołka źródłowego do wszystkich pozostałych wierzchołków grafie.
Algorytm Floyda-Warshalla oraz Algorytm Johnsona -- najkrótsze ścieżki pomiędzy każdą parą wierzchołków w grafie.
AG05.pdf Zaimplementuj algorytmy prezentowane na wykładzie.
27.11.2018 Teoretyczny test końcowy. Obecność obowiązkowa. Zakres zgodny z podanym na pierwszym wykładzie.