1. SylabUZ
2. Wydział Nauk Inżynieryjno-Technicznych
3. semestr zimowy 2021/2022
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 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

Wymagania wstępne

Zapisz zmiany

Podstawy programowania, Teoretyczne podstawy informatyki

Zakres tematyczny

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 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 grafu wszerz
2. Przeszukiwanie grafu 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

Metody kształcenia

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

laboratorium: ćwiczenia laboratoryjne z wykorzystaniem sprzętu komputerowego - implementacja algorytmów grafowych w środowisku programistycznym Microsoft Visual Studio lub innym podobnym.

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 egzaminu pisemnego lub ustnego.

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

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

Literatura uzupełniająca

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.

Uwagi

Zmodyfikowane przez prof. dr hab. inż. Andrzej Obuchowicz (ostatnia modyfikacja: 20-04-2021 08:48)