SylabUZ

Wygeneruj PDF dla tej strony

Grafy i sieci w informatyce - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Grafy i sieci w informatyce
Kod przedmiotu 11.9-WI-INFD-GiSwI
Wydział Wydział Informatyki, Elektrotechniki i Automatyki
Kierunek Informatyka
Profil ogólnoakademicki
Rodzaj studiów drugiego stopnia z tyt. magistra inżyniera
Semestr rozpoczęcia semestr zimowy 2020/2021
Informacje o przedmiocie
Semestr 1
Liczba punktów ECTS do zdobycia 5
Typ przedmiotu obowiązkowy
Język nauczania polski
Sylabus opracował
  • dr inż. Grzegorz Łabiak
Formy zajęć
Forma zajęć Liczba godzin w semestrze (stacjonarne) Liczba godzin w tygodniu (stacjonarne) Liczba godzin w semestrze (niestacjonarne) Liczba godzin w tygodniu (niestacjonarne) Forma zaliczenia
Laboratorium 30 2 18 1,2 Zaliczenie na ocenę
Wykład 30 2 18 1,2 Zaliczenie na ocenę

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

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 dr inż. Grzegorz Łabiak (ostatnia modyfikacja: 26-04-2020 20:38)