Drukuj Eksport do pliku (MS Word)
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. 2018/2019
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:
https://usosweb.usos.pw.edu.pl/kontroler.php?_action=katalog2/przedmioty/pokazPrzedmiot&prz_kod=103A-xxxxx-MSP-GIS
Uwagi:
Przedmiot jest oferowany i realizowany w semetrach zimowym i letnim roku akademickiego.

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka 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 charakterystyki kierunkowe: K_W04, K_W08, K_W09, K_W11, K_W01
Powiązane charakterystyki obszarowe: I.P7S_WG, III.P7S_WG.o

Profil ogólnoakademicki - umiejętności

Charakterystyka 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 charakterystyki kierunkowe: K_U01, K_U02, K_U03, K_U09, K_U13
Powiązane charakterystyki obszarowe: I.P7S_UK, I.P7S_UW, III.P7S_UW.1.o, III.P7S_UW.3.o

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka 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 charakterystyki kierunkowe: K_K01
Powiązane charakterystyki obszarowe: I.P7S_KO