- Nazwa przedmiotu:
- Grafy i sieci
- Koordynator przedmiotu:
- prof. dr hab. Jacek Wojciechowski
- Status przedmiotu:
- Obowiązkowy
- Poziom kształcenia:
- Studia II stopnia
- Program:
- Informatyka
- Grupa przedmiotów:
- Przedmioty techniczne - zaawansowane
- Kod przedmiotu:
- GIS
- Semestr nominalny:
- 4 / rok ak. 2015/2016
- Liczba punktów ECTS:
- 5
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- 135 h, w tym:
- uczestnictwo w wykładach 30 h
- przygotowanie do wykładów 15 h
- przygotowanie do kolokwiów 20 h
- przygotowanie do egzaminu 15 h
- spotkania projektowe 15 h
- projekt (studia literaturowe,
wykonanie projektu, raport) 40 h
- Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- - uczestnictwo w wykładach 30 h
- spotkania projektowe 15 h
w sumie 45 h, co daje ok. 2 ECTS
- Język prowadzenia zajęć:
- polski
- Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
- - spotkania projektowe 15 h
- projekt (studia literaturowe,
wykonanie projektu, raport) 40 h
w sumie 55 h, co daje ok. 2 ECTS
- Formy zajęć i ich wymiar w semestrze:
-
- Wykład30h
- Ćwiczenia0h
- Laboratorium0h
- Projekt30h
- Lekcje komputerowe0h
- Wymagania wstępne:
- Matematyka dyskretna
- Limit liczby studentów:
- 72
- Cel przedmiotu:
- Celem przedmiotu jest zaznajomienie studenta z pojęciami, metodami i narzędziami analizy i projektowania wykorzystującymi metody teorii grafów i sieci.
Przedmiot oferuje możliwość współdzielenia doświadczeń przez studentów studiujących różne specjalności (np. telekomunikacja, informatyka, badania operacyjne, itp.). Projekt wykonywany w zespołach dwuosobowych zapewnia możliwość praktycznych doświadczeń i weryfikacji materiału zawartego w programie przedmiotu.
Po zaliczeniu przedmiotu student powinien posiadać następujące umiejętności:
• tworzenie modeli grafowych i sieciowych do opisu zjawisk i procesów,
• formułowanie problemów dyskretnychych w języku teorii grafów,
• wybór algorytmów grafowych ułatwiających rozwiązanie postawionego problemu,
• interpretacja uzyskanych wyników.
Po zaliczeniu przedmiotu student powinien posiadać następujące umiejętności:
• formułowania problemów kombinatorycznych w języku teorii grafów,.
• wyboru algorytmów grafowych ułatwiających rozwiązanie postawionego problemu,
• interpretacji uzyskanych wyników.
Celem przedmiotu jest zaznajomienie studenta z pojęciami, metodami i narzędziami analizy i projektowania wykorzystującymi metody teorii grafów i sieci.
Przedmiot oferuje możliwość współdzielenia doświadczeń przez studentów studiujących różne specjalności (np. telekomunikacja, informatyka, badania operacyjne, itp.). Projekt wykonywany w zespołach dwuosobowych zapewnia możliwość praktycznych doświadczeń i weryfikacji materiału zawartego w programie przedmiotu.
Po zaliczeniu przedmiotu student powinien posiadać następujące umiejętności:
• tworzenie modeli grafowych i sieciowych do opisu zjawisk i procesów,
• formułowanie problemów dyskretnychych w języku teorii grafów,
• wybór algorytmów grafowych ułatwiających rozwiązanie postawionego problemu,
• interpretacja uzyskanych wyników.
Po zaliczeniu przedmiotu student powinien posiadać następujące umiejętności:
• formułowania problemów kombinatorycznych w języku teorii grafów,.
• wyboru algorytmów grafowych ułatwiających rozwiązanie postawionego problemu,
• interpretacji uzyskanych wyników.
Celem przedmiotu jest zaznajomienie studenta z pojęciami, metodami i narzędziami analizy i projektowania wykorzystującymi metody teorii grafów i sieci.
Przedmiot oferuje możliwość współdzielenia doświadczeń przez studentów studiujących różne specjalności (np. telekomunikacja, informatyka, badania operacyjne, itp.). Projekt wykonywany w zespołach dwuosobowych zapewnia możliwość praktycznych doświadczeń i weryfikacji materiału zawartego w programie przedmiotu.
Po zaliczeniu przedmiotu student powinien posiadać następujące umiejętności:
• tworzenie modeli grafowych i sieciowych do opisu zjawisk i procesów,
• formułowanie problemów dyskretnychych w języku teorii grafów,
• wybór algorytmów grafowych ułatwiających rozwiązanie postawionego problemu,
• interpretacja uzyskanych wyników.
Po zaliczeniu przedmiotu student powinien posiadać następujące umiejętności:
• formułowania problemów kombinatorycznych w języku teorii grafów,.
• wyboru algorytmów grafowych ułatwiających rozwiązanie postawionego problemu,
• interpretacji uzyskanych wyników.
- Treści kształcenia:
- Przykłady zastosowań grafów i sieci. Definicja grafu.
Podstawowe typy grafów. Izomorfizm. Drogi.
Cykl Eulera. Cykl Hamiltona. Zadanie komiwojażera.
Drzewa.
Operacje na grafach.
Macierzowy opis grafów.
Reprezentacje grafów w analizie komputerowej.
Wybrane algorytmy grafowe: badanie wgłąb, spójność, najkrótsza ścieżka, najlżejsze drzewo.
Architektura sieci złożonych.
Przestrzenie liniowe w grafach. Cykle/przekroje fundamentalne.
Kolorowanie grafów.
Skojarzenia, pokrycia.
Twierdzenie Mengera.
Sieci przepływowe Algorytm Forda-Fulkersona.
- Metody oceny:
- Elementami oceny są: kolokwia, projekt, egzamin końcowy z następującym podziałem punktów:
- kolokwia 2 x 15 pkt =30 pkt
- projekt 30 pkt
- egzamin końcowy 40 pkt
- Egzamin:
- tak
- Literatura:
- 1.N.Deo, Teoria grafów i jej zastosowania w technice i informatyce. PWN,1980.
2.F.Harary,Graph Theory. Addison-Wesley, 1969.
3.N.Christofides, Graph theory: algorithmic approach. Academic Press, 1975.
4. M.Sysło, N.Deo, J.Kowalik, Algorytmy optymalizacji dyskretnej. PWN, 1993.
5. D.Medhi, M.Pióro, Routing, Flow, and Capacity Design Communication and Komputer Networks. Morgan Series In Networking.
6. J.Wilson, Wprowadzenie do teorii grafów. PWN, Warszawa 2004.
7. A.Fronczak, P.Fronczak, Świat sieci złożonych. Od fizyki do Internetu. PWN, 2009
- Witryna www przedmiotu:
- http://berni.ire.pw.edu.pl/GIS/ (dostęp na hasło)
- Uwagi:
- Przedmiot jest oferowany i realizowany w semetrach zimowym i letnim roku akademickiego.
Efekty uczenia się
Profil ogólnoakademicki - wiedza
- Efekt W1
- Student, po zaliczeniu przedmiotu, powinien znać podstawy teorii grafów, zastosowania grafów w informatyce i telekomunikacji, oraz podstawowe algorytmy grafowe. Powinien umieć redukować praktyczne problemy inżynierskie do modeli i problemów grafowych oraz stosować do ich rozwiązania właściwe algorytmy.
Weryfikacja: 2 kolokwia w ciągu semestru, projekt z ocenami cząstkowymi poszczególnych etapów i egzamin końcowy. Dla studentów, którzy uzyskali wysokie oceny z kolokwiów i projektu przewiduje się możliwość zwolnienia z egzaminu końcowego - praktyka pokazała, że ma to duże znaczenie motywujące.
Powiązane efekty kierunkowe:
K_W01, K_W04, K_W08, K_W09, K_W11
Powiązane efekty obszarowe:
T2A_W01, T2A_W02, T2A_W07, T2A_W03, T2A_W03, T2A_W04, T2A_W07
Profil ogólnoakademicki - umiejętności
- Efekt W2
- Student potrafi dostrzec możliwości i ograniczenia aparatu i algorytmów teorii grafów do rozwiązywania problemów inżynierskich, zwłaszcza z zakresu informatyki i telekomunikacji. Poprzez projekt uzyskuje umiejętność samodzielnego rozwiązywania problemów.
Weryfikacja: Projekt, kolokwia, egzamin końcowy
Powiązane efekty kierunkowe:
K_U01, K_U02, K_U03, K_U09, K_U13
Powiązane efekty obszarowe:
T2A_U01, T2A_U02, T2A_U03, T2A_U11, T2A_U18
Profil ogólnoakademicki - kompetencje społeczne
- Efekt W3
- Projekty są wykonywane w grupach dwuososbowych. Student rozwija umiejętności pracy zespołowej.
Weryfikacja: Ocena projektu, właczając w to ocenę poszczególnych etapów wykonania.
Powiązane efekty kierunkowe:
K_K01
Powiązane efekty obszarowe:
T2A_K06