1. SylabUZ
2. Wydział Informatyki, Elektrotechniki i Automatyki
3. semestr zimowy 2022/2023
4. Informatyka - drugiego stopnia z tyt. magistra inżyniera
5. Grafy i sieci w informatyce

Wygeneruj PDF dla tej strony

Grafy i sieci w informatyce - opis przedmiotu

Cel przedmiotu

• 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.

Wymagania wstępne

Zapisz zmiany

Podstawy programowania, Algorytmy i struktury danych, Teoretyczne podstawy informatyki

Zakres tematyczny

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.

Metody kształcenia

wykład: wykład konwencjonalny, dyskusja

laboratorium: ćwiczenia laboratoryjne z wykorzystaniem sprzętu komputerowego

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

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

Warunki zaliczenia

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%

Literatura podstawowa

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.

Literatura uzupełniająca

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.

Uwagi

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