1. SylabUZ
2. Wydział Informatyki, Elektrotechniki i Automatyki
3. semestr zimowy 2022/2023
4. Informatyka - Program Erasmus drugiego stopnia
5. Graphs and networks in computer science

Wygeneruj PDF dla tej strony

Graphs and networks in computer science - opis przedmiotu

Cel przedmiotu

• gaining basic skills and competences in the field of algorithmic graph theory.
• acquiring the ability to use graphs for modeling and solving real life problems.

Wymagania wstępne

Zapisz zmiany

Basics of programming, Algorithms and data structures, Theoretical foundations of computer science.

Zakres tematyczny

Basic concepts of graph theory. Overview of application areas. Examples of important graph classes.

Selected graph frameworks (graph representations). Generating random graphs. Graph isomorphism. Graph and network datasets.

Graph searching algorihtms (breadth-first and depth-first searches, backtracking). Computing strongly connected components, topological sorting.

Minimum spanning trees (the algorithms of Prim and Kruskal).

Shortest paths in graphs (Dijkstra's, Bellman-Ford and Floyd-Warshall algorithms).

 Algorithms for Euler tour/path and chinese postman problems.

 Graph coloring - selected models, variants and algorithms for vertex and edge colorings.

 Hamiltonian cycle/path and traveling salesperson problems (algorithms and applications).

 Flow networks - determinig maximum flow (Ford–Fulkerson algorithm).

 Graph problems in the context of Petri net theory - modeling parallel systems.

Metody kształcenia

Lectures: conventional lectures and discussions
Laboratories: computer laboratory exercises

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu	Symbole efektów	Metody weryfikacji	Forma zajęć

Warunki zaliczenia

Lectures – the passing condition is to obtain a positive grade from the final test.

Laboratories – the passing condition is to obtain a positive grade from all laboratory assignments.

Course - it is necessary to pass both lectures and laboratories.

Calculation of the final grade: lecture 50% + laboratory 50%

Literatura podstawowa

1. Robin Wilson: Introduction to graph theory. Pearson Education Limited, 1996 (or other editions).
2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. MIT Press and McGraw-Hill, 1990 (or other editions).
3. Maciej M. Sysło, N. Deo, Janusz S. Kowalik: Discrete optimization Algorithms, Prentice-Hall, 1983.
4. Marek Kubale (Ed.), Graph Colorings. Contemporary Mathematics 352, American Mathematical Society, 2004

Literatura uzupełniająca

1. Narsing Deo: Graph Theory with Application to Engineering and Computer Science, Prentice-Hall, Englewood Cliffs, N.J., 1974
2. Reinhard Diestel: Graph theory. Electronic edition, Springer Verlag New York, 2000.
3. Wolfgang Reisig: A Primer in Petri Net Design. Springer-Verlag, 1992.

Uwagi

Zmodyfikowane przez dr hab. inż. Piotr Borowiecki, prof. UZ (ostatnia modyfikacja: 21-04-2022 01:11)