1. SylabUZ
2. Faculty of Computer Science, Electrical Engineering and Automatics
3. winter term 2022/2023
4. Computer Science - 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 stosowania grafowych w modelowaniu i rozwiązywaniu problemów informatycznych.

Prerequisites

Save changes

Podstawy programowania, Algorytmy i struktury danych, Teoretyczne podstawy informatyki

Scope

Podstawowe pojęcia teorii grafów. Przegląd obszarów zastosowań. Przykłady istotnych klas grafów.

Wybrane frameworki grafowe (wewnętrzne i zewnętrzne reprezentacje grafów). Generowanie grafów. Izomorfizm grafów. Bazy grafów i sieci.

Algorytmy przeszukiwania grafów i digrafów (wszerz, w głąb, przeszukiwanie z nawrotami). Wyznaczanie silnie spójnych składowych, sortowanie topologiczne.

Wyznaczanie najlżejszych drzew rozpinających (algorytmy Prima i Kruskala).

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

Algorytmy dla problemów obchodu Eulera oraz chińskiego listonosza.

Kolorowanie grafów - wybrane tryby i modele oraz algorytmy kolorowania wierzchołków i krawędzi grafów.

Zagadnienia hamiltonowskie, problem drogi oraz cyklu Hamiltona, problem komiwojażera (algorytmy i zastosowania).

Sieci przepływowe. Wyznaczanie maksymalnego przepływu w sieciach (metoda Forda-Fulkersona).

Problemy grafowe w kontekście sieci Petriego - modelowanie systemów współbieżnych.

Teaching methods

wykład: wykład konwencjonalny, dyskusja

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 kolokwium zaliczeniowego.

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

Przedmiot - warunkiem zaliczenia przedmiotu jest zaliczenie zarówno laboratorium jak i wykładu.

Składowe oceny końcowej = wykład 50% + laboratorium 50%

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. Maciej M. Sysło, N. Deo, Janusz S. Kowalik: Algorytmy optymalizacji dyskretnej, Wydawnictwo Naukowe PWN, Warszawa, 1993.
4. Marek Kubale (red.), Optymalizacja dyskretna: modele i metody kolorowania grafów. WNT, Warszawa, 2002.
5. Marek Libura, Jarosław Sikorski: Wykłady z matematyki dyskretnej. Cz. II: Teoria grafów. WSISZ, Warszawa, 2002.
6. Jacek Wojciecowski, Krzysztof Pieńkosz: Grafy i sieci, PWN, Warszawa, 2013.

Further reading

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

Notes

Modified by dr hab. inż. Piotr Borowiecki, prof. UZ (last modification: 21-04-2022 01:12)