1. SylabUZ
2. Faculty of Computer Science, Electrical Engineering and Automatics
3. summer term 2016/2017
4. Computer Science / Industrial Information Systems - Second-cycle studies leading to MSc degree
5. Graph and Networks in Computer Science

Generate PDF for this page

Graph and Networks in Computer Science - course description

Aim of the course

• zapoznanie studentów z podstawami teorii grafów i najważniejszymi (w zastosowaniach informatycznych) algorytmami grafowymi
• ukształtowanie podstawowych umiejętności w zakresie zastosowania algorytmów grafowych do problemów informatycznych
• zapoznanie studentów z sieciami Petriego jako modelem procesów współbieżnych oraz ich zastosowaniem w projektowaniu systemów sterowania logicznego

Prerequisites

Save changes

Podstawy programowania, Teoretyczne podstawy informatyki

Scope

Nieformalne wprowadzenie do teorii grafów. Rys historyczny. Zastosowania teorii grafów w informatyce.

Grafy skierowane i nieskierowane. Intuicyjne przykłady i formalne definicje. Podstawowe pojęcia teorii grafów. Rodzaje grafów: grafy planarne, dwudzielne, pełne, drzewa.

Sposoby reprezentacji grafów w pamięcu komputera: macierzowe i listowe reprezentacje grafów.

Najważniejsze algorytmy przeszukiwania grafów: BFS, DFS. Wybrane zastosowania algorytmów przeszukiwania (obliczenie silnie spójnych składowych, sortowanie topologiczne)

Cykle Eulera (warunki istnienia i algorytm konstruowania). Cykle Hamiltona, warunki istnienia.

Metoda PERT, analiza krytycznej ścieżki.

Metody konstruowania minimalnych drzew rozpinających (algorytmy Prima, Kruskala, Boruvki).

Metody obliczania najkrótszych ścieżek w grafach (algorytmy Dijkstry, Bellmana-Forda, Floyda-Warshalla). Zastosowania.

Sieci przepływowe i obliczenie maksymalnego przeplywu w sieciach – metoda Forda-Fulkersona. Zastosowania.

Kolorowanie grafów i jego zastosowania. Heurystyczne metody kolorowania grafów.

Złożoność obliczeniowa algorytmów grafowych. Algorytmy zachłanne. Problemy NP-trudne w kontekście grafów, przykłady.

Binarne diagramy decyzyjne: klasyczny graf BDD, zredukowany binarny diagram ROBDD. Grafy BDD jako efektywny sposób reprezentacji funkcji boolowskich.

Elementy teorii sieci Petriego: podstawy formalne, właściwości behawioralne, metody badania. Sieci Petriego w modelowaniu systemów współbieżnych i projektowaniu współbieżnych algorytmów sterowania.

Algorytmy do zaimplementowania na zajęciach laboratoryjnych:

1. Przeszukiwanie wszerz
2. Przeszukiwanie w głąb
3. Obliczanie silnie spójnych składowych
4. Sortowanie topologiczne
5. Wyznaczenie krytycznej ścieżki
6. Znajdowanie minimalnego drzewa rozpinającego
7. Najkrótsze ścieżki z jednym źródłem (algorytm Dijkstry)
8. Kolorowanie grafów za pomocą wybranego algorytmu zachłannego
9. Obliczanie maksymalnego przepływu w sieciach

Teaching methods

wykład: wykład konwencjonalny, dyskusja, przedstawienie wybranych algorytmów przez studentów

laboratorium: ćwiczenia laboratoryjne z wykorzystaniem sprzętu komputerowego

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

Wykład - warunkiem zaliczenia jest uzyskanie pozytywnej oceny z egzaminu pisemnego lub ustnego.

Laboratorium - warunkiem zaliczenia jest uzyskanie pozytywnych ocen ze wszystkich zadań laboratoryjnych.

Składowe oceny końcowej = wykład: 60% + laboratorium: 40%

Recommended reading

1. Robin Wilson: Wprowadzenie do teorii grafów. Wydawnictwo Naukowe PWN, Warszawa, 2007.
2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów, PWN, Warszawa, 2012 (albo inne wydania).
3. Marek Libura, Jarosław Sikorski: Wykłady z matematyki dyskretnej. Cz. II: Teoria grafów. WSISZ, Warszawa, 2002.
4. Marek Kubala (Red.), Optymalizacja dyskretna: modele i metody kolorowania grafów. WNT, Warszawa, 2002

Further reading

1. Narsingh Deo: Teoria grafów i jej zastosowanie w technice i informatyce, PWN, Warszawa, 1980.
2. Bogdan Korzan: Elementy teorii grafów i sieci. WNT, Warszawa, 1978.
3. Reinhard Diestel: Graph theory. Electronic edition, Springer Verlag New York, 2000.
4. Marcin Szpyrka: Sieci Petriego w modelowaniu i analizie systemów współbieżnych, WNT Warszawa, 2008.

Notes

Modified by dr hab. inż. Andrei Karatkevich, prof. UZ (last modification: 16-09-2016 12:24)