1. SylabUZ
2. Wydział Nauk Inżynieryjno-Technicznych
3. semestr letni 2024/2025
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 selected 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 and digraph 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).

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

Algorithms for Euler tour/path and chinese postman problems.

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

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

Selected centrality measures in network analysis.

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. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, 4th ed., The MIT Press Cambridge, 2022.
2. Robin J. Wilson: Introduction to graph theory. Pearson Education Limited, 1996 (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.

Uwagi

Zmodyfikowane przez dr hab. inż. Piotr Borowiecki, prof. UZ (ostatnia modyfikacja: 18-04-2024 17:06)