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. 2012/2013
Liczba punktów ECTS:
5
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
125 h, w tym: - przygotowanie do wykładów 15 h - przygotwanie do kolokwiów 35 h - egzamin 35 h - projekt (studia literaturowe, wykonanie projektu, raport) 40 h
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
3 punkty, w tym - przygotowanie do wykładu i wykład - konsultacje wykładowe i projektowe - opracowanie tematów projektów - sprawdzenie projektów - przygtowanie i sprawdzenie kolokwiów i egzaminów
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
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_U04, K_U07, K_U08, K_U09, K_U11, K_U13
Powiązane efekty obszarowe: T2A_U01, T2A_U02, T2A_U03, T2A_U05, T2A_U10, T2A_U12, T2A_U11, T2A_U16, 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