Politechnika Warszawska - Centralny System Uwierzytelniania
Strona główna

Grafy i sieci

Informacje ogólne

Kod przedmiotu: 103A-xxxxx-MSP-GIS
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Grafy i sieci
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Przedmioty techniczne )---EITI
( Przedmioty zaawansowane obieralne )-Inżynieria systemów informatycznych-mgr.-EITI
( Przedmioty zaawansowane obieralne )-Radiokomunikacja i techniki multimedialne-mgr.-EITI
( Przedmioty zaawansowane obieralne )-Systemy informacyjno-decyzyjne-mgr.-EITI
( Przedmioty zaawansowane techniczne )--mgr.-EITI
Punkty ECTS i inne: 5.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.
Język prowadzenia: polski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

GIS

Numer wersji:

1

Skrócony opis:

Przedmiot zaznajamia studenta z pojęciami, metodami i narzędziami analizy i projektowania wykorzystującymi metody teorii grafów i sieci. Wykład obejmuje takie zagadnienia jak: podstawy grafów i sieci, modelowanie problemów dyskretnych za pomocą grafów, algorytmy grafowe, struktury danych, sieci złożone, przepływy w sieciach.
Wykład 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:

  • 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.

Pełny opis:

Przedmiot zaznajamia studenta z pojęciami, metodami i narzędziami
analizy i projektowania wykorzystującymi metody teorii grafów i
sieci. Wykład obejmuje takie zagadnienia jak: podstawy grafów i sieci,
modelowanie problemów dyskretnych za pomocą grafów, algorytmy
grafowe, struktury danych, sieci złożone, przepływy w sieciach.

Wykład 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:

  • 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ść wykładu
(bloki dwugodzinne):

  1. Przykłady zastosowań grafów i sieci. Definicja grafu.

  2. Podstawowe typy grafów. Izomorfizm. Drogi.

  3. Cykl Eulera. Cykl Hamiltona. Zadanie komiwojażera. Operacje na
    grafach.

  4. Operacje na grafach.Reprezentacje grafów:

  5. Drzewa.

  6. Wybrane algorytmy grafowe: badanie wgłąb, spójność, najkrótsza
    ścieżka, najlżejsze drzewo.

  7. Wybrane algorytmy grafowe: badanie wgłąb, spójność, najkrótsza
    ścieżka, najlżejsze drzewo. Architektura sieci złożonych.

  8. Kolorowanie grafów. Cykle/przekroje fundamentalne.

  9. Kolorowanie grafów.

  10. Skojarzenia, pokrycia, podział.

  11. Twierdzenie Mengera.

  12. Sieci. Programowanie liniowe. Twierdzenie minimaksowe o
    przepływach jednotowarowych.

  13. Sieci: Algorytm Forda-Fulkersona.


Zakres projektu
Wykładowi towarzyszy projekt. Studenci rozwiązują w zespołach
dwuosobowych wybrany problem związany z zagadnieniami omawianymi
w czasie wykładu i rozszerzający wybrane fragmenty materiału.
Opracowanie zagadnienia polega na:


  • Zapoznaniu się ze szczegółową literaturą problemu.

  • Zaproponowaniu algorytmu rozwiązania.

  • Implementacji algorytmu.

  • Opracowanie eksperymentu testującego algorytm.

  • Wykonaniu studium numerycznego na wybranych przykładach.

  • Przygotowaniu sprawozdań etapowych i końcowego.

Literatura:

  1. Materiały pomocnicze do wykłady umieszczane na stronie przedmiotu http://berni.ire.pw.edu.pl/GIS/main

  2. Literatura do przedmiotu:

  • N.Deo: Teoria grafów i jej zastosowania w technice i inforamtyce, PWN, 1980.

  • M.Sysło, N.Deo, J.Kowalik: Algorytmy optymalizacji dyskretnej,
    PWN, 1993.

  • E.M.Reingold, J.Nievergelt, N.Deo: Algorytmy kombinatoryczne.
    PWN, 1977.

  • D.Mehdi, M.Pióro, Routing, Flow, and Capacity Design
    Communication and Komputer Networks. Morgan Series in Networking.

  • J.Wilson, Wprowadzenie do teorii grafów. PWN, Warszawa 2004.

  • A.Fronczak, P.Fronczak, Świat sieci złożonych. Od fizyki do
    Internetu. PWN, 2009.

  • N.Christofides, Graph theory: Algorithmic Approach. Academic
    Press, 1975.

Metody i kryteria oceniania:

Dwa kolokwia wykładowe (2x15=30 punktów), projekt: 30 punktów, egzamin końcowy: 40 punktów. Razem 100 punktów. Warunkiem zaliczenia przedmiotu jest uzyskanie z projektu dodatniej liczby punktów. Studenci, którzy z kolokwiów uzyskają co najmniej 20 punktów, a łącznie z projektu i kolokwiów co najmniej 45 punktów mają prawo do zwolnienia z egzaminu końcowego.

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. letni" (zakończony)

Okres: 2020-02-22 - 2020-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Projekt, 30 godzin, 75 miejsc więcej informacji
Wykład, 30 godzin, 75 miejsc więcej informacji
Koordynatorzy: Sebastian Kozłowski
Prowadzący grup: Paweł Bajurko, Dariusz Bursztynowski, Sebastian Kozłowski, Tomasz Miś, Krzysztof Pieńkosz, Kajetana Snopek
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. zimowy" (zakończony)

Okres: 2019-10-01 - 2020-02-21
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Projekt, 30 godzin, 75 miejsc więcej informacji
Wykład, 30 godzin, 75 miejsc więcej informacji
Koordynatorzy: Sebastian Kozłowski
Prowadzący grup: Dariusz Bursztynowski, Sebastian Kozłowski, Krzysztof Pieńkosz
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. letni" (zakończony)

Okres: 2019-02-18 - 2019-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Projekt, 30 godzin, 75 miejsc więcej informacji
Wykład, 30 godzin, 75 miejsc więcej informacji
Koordynatorzy: Sebastian Kozłowski
Prowadzący grup: Sebastian Kozłowski, Krzysztof Pieńkosz
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. zimowy" (zakończony)

Okres: 2018-10-01 - 2019-02-17
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Projekt, 30 godzin, 75 miejsc więcej informacji
Wykład, 30 godzin, 75 miejsc więcej informacji
Koordynatorzy: Sebastian Kozłowski
Prowadzący grup: Dariusz Bursztynowski, Sebastian Kozłowski, Krzysztof Pieńkosz
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.
pl. Politechniki 1, 00-661 Warszawa tel: (22) 234 7211 https://pw.edu.pl kontakt deklaracja dostępności USOSweb 7.0.0.0-7 (2024-03-18)