3813101109

Nazwa przedmiotu: Grafy i sieci w informatyce

Nazwa przedmiotu: Grafy i sieci w informatyce

Kod przedmiotu:

11.9-WE-l-GSI-PK2_S2S

Odpowiedzialni za przedmiot:

Nauczyciel akademicki prowadzący wykład

Prowadzący przedmiot:

Pracownicy WEliT IliE

Forma zajęć	godzin w sem.	godzin w tyg.	semestr	forma zal.	punkty ects	tryb studiów	typ przedmiotu
wykład	30	2	1	egzamin		stacjonarne	obowiązkowy
laboratorium	30	2	1	zal. na ocenę			obowiązkowy
wykład	18	2	1	egzamin		niestacjonarne	obowiązkowy
laboratorium	18	2	1	zal. na ocenę			obowiązkowy

Cel:

-    zapoznanie studentów z podstawami teorii grafów i najważniejszymi (w zastosowaniach informatycznych) algorytmami grafowymi

-    ukształtowanie podstawowych umiejętności w zakresie modelowania grafowego systemów informatycznych oraz 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

Nieformalne wprowadzenie do teorii grafów i sieci: Podstawowe pojęcia. Grafy skierowane i niekierowane. Intuicyjne przykłady. Elementy teorii grafów skierowanych i niekierowanych: drogi, ścieżki, cykle, drzewa, przekroje. Operacje na grafach. 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, 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: wykorzystanie teorii grafów w inżynierii oprogramowania, wykorzystanie teorii grafów w inżynierii komputerowej.

Elementy teorii sieci Petriego: podstawy formalne - definicje, reprezentacje, własności, klasyfikacje. Własności dynamiczne dyskretnych obiektów zdarzeniowych i ich modelowe odpowiedniki - konflikt, blokady, żywotność, aktywność, zachowawczość.

Analiza grafów znaków osiągalnych, P i T niezmienniki.

Interpretowane sieci Petriego: Sieć Petriego jako model współbieżnego sterownika logicznego. Makrosieć. Reprezentacja i analiza przestrzeni stanów lokalnych z wykorzystaniem teorii grafów. Modelowanie wybranych klas procesów dyskretnych.

Metody kształcenia

wykład: wykład konwersatoryjny, wykład konwencjonalny laboratorium: ćwiczenia laboratoryjne

Efekty kształcenia

T2A_W01, T2A_W02 T2A_W04, T2A_W07

Potrafi pracować indywidualnie i w zespole    K2IJ

Potrafi zaimplementować algorytmy grafowe w jednym z uniwersalnych „„i i języków programowania    -

Umie opisać relacje w systemie lub strukturze przy pomocy modeli grafowych, a dynamiczny proces współbieżny, np. sterowania logicznego K2I_

- przy pomocy sieci Petriego

T2A_U09, T2AJJ17, T2AJJ19

T2A_W04, T2A_W07, T2AJJ09, T2AJJ17, T2A_U19

Potrafi prowadzać w razie potrzeby problemy informatyczne do zagadnień _K„. grafowych i stosować algorytmy grafowe do ich rozwiązywania

Zna podstawowe pojęcia teorii grafów oraz najważniejsze algorytmy    K2I_\

grafowe    K2I_

Weryfikacja efektów kształcenia i warunki zaliczenia