518321790

GRAFY I SIECI W INFORMATYCE

Kod przedmiotu: 11.9-WE-INFD-GSI Typ przedmiotu: obowiązkowy Język nauczania: polski

Odpowiedzialny za przedmiot: Dr hab. inż. Andrzej Karatkiewicz, prof. UZ Dr hab. inż. Andrzej Karatkiewicz, prof. UZ, Prowadzący: dr inż. Grzegorz Łabiak, dr inż. Iwona Grobelna

Forma zajęć	Liczb a godzi n w sem estrze	Liczb a godzi n w tyg odniu	Seme str	Forma zaliczenia	Punkty ECTS
Studia stacjonarne
Wykład	30	2		Egzamin
Laboratorium	30	2	'	Zaliczenie na ocenę	5
		Studia ni		estacjonarne
Wykład	18	2		Egzamin
Laboratorium	18	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

ZAKRES TEMATYCZNY PRZEDMIOTU:

Nieformalne wprowadzenie do teorii grafów i sieci: Podstawowe pojęcia. Grafy skierowane i niekierowane. Intuicyjne przykłady. Podstawowe pojęcia teorii grafów skierowanych i niekierowanych: drogi, ścieżki, cykle, drzewa. Klasyfikacje grafów: grafy planarne, dwudzielne, pełne, drzewa. Macierzowe reprezentacje grafów. Komputerowe reprezentacje grafów.

Wybrane własności grafów i metody ich badania. Najważniejsze algorytmy grafowe: BFS, DFS, metody konstruowania minimalnego drzewa rozpinającego, obliczania najkrótszych ścieżek w grafach, maksymalnego przepływu w grafach, kolorowania grafów. Grafy Eulera i Hamiltona. Złożoność obliczeniowa algorytmów grafowych. Przykłady zastosowań metod teorii grafów w algorytmach optymalizacji dyskretnej.

Binarne diagramy decyzyjne: klasyczny graf BDD, uporządkowany diagram OBDD, zredukowany binarny diagram ROBDD. Graf BDD jako efektywna struktura danych. Przykłady zastosowań wybranych algorytmów teorii grafów w informatyce.

Wydział Elektrotechniki, Informatyki i Telekomunikacji Kierunek: Informatyka

6