Politechnika Warszawska - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

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 ogólne )--dr.-EITI
( Przedmioty zaawansowane techniczne )--mgr.-EITI
Punkty ECTS i inne: 5.00
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" (jeszcze nie rozpoczęty)

Okres: 2020-02-22 - 2020-09-30

Wybrany podział planu:


powiększ
zobacz plan zajęć
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 2019/2020 - sem. zimowy" (w trakcie)

Okres: 2019-10-01 - 2020-02-21
Wybrany podział planu:


powiększ
zobacz plan zajęć
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:


powiększ
zobacz plan zajęć
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:


powiększ
zobacz plan zajęć
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 2017/2018 - sem. letni" (zakończony)

Okres: 2018-02-19 - 2018-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
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 2017/2018 - sem. zimowy" (zakończony)

Okres: 2017-10-01 - 2018-02-18
Wybrany podział planu:


powiększ
zobacz plan zajęć
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
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

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

Okres: 2017-02-20 - 2017-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
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
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

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

Okres: 2016-10-01 - 2017-02-19
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 72 miejsc więcej informacji
Wykład, 30 godzin, 72 miejsc więcej informacji
Koordynatorzy: Sebastian Kozłowski
Prowadzący grup: Sebastian Kozłowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

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

Okres: 2016-02-23 - 2016-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 72 miejsc więcej informacji
Wykład, 30 godzin, 72 miejsc więcej informacji
Koordynatorzy: Sebastian Kozłowski
Prowadzący grup: Sebastian Kozłowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

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

Okres: 2015-10-01 - 2016-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 72 miejsc więcej informacji
Wykład, 30 godzin, 72 miejsc więcej informacji
Koordynatorzy: Sebastian Kozłowski
Prowadzący grup: Sebastian Kozłowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

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

Okres: 2015-02-23 - 2015-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 72 miejsc więcej informacji
Wykład, 30 godzin, 72 miejsc więcej informacji
Koordynatorzy: Jacek Wojciechowski
Prowadzący grup: Jacek Wojciechowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

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

Okres: 2014-09-29 - 2015-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 72 miejsc więcej informacji
Wykład, 30 godzin, 72 miejsc więcej informacji
Koordynatorzy: Jacek Wojciechowski
Prowadzący grup: Jacek Wojciechowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

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

Okres: 2014-02-24 - 2014-09-28
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 72 miejsc więcej informacji
Wykład, 30 godzin, 72 miejsc więcej informacji
Koordynatorzy: Jacek Wojciechowski
Prowadzący grup: Jacek Wojciechowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

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

Okres: 2013-10-01 - 2014-02-23
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 84 miejsc więcej informacji
Wykład, 30 godzin, 84 miejsc więcej informacji
Koordynatorzy: Jacek Wojciechowski
Prowadzący grup: Jacek Wojciechowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

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

Okres: 2013-02-20 - 2013-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 84 miejsc więcej informacji
Wykład, 30 godzin, 84 miejsc więcej informacji
Koordynatorzy: Jacek Wojciechowski
Prowadzący grup: Jacek Wojciechowski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

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

Okres: 2012-10-01 - 2013-02-19
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 84 miejsc więcej informacji
Wykład, 30 godzin, 84 miejsc więcej informacji
Koordynatorzy: Jacek Wojciechowski
Prowadzący grup: Jacek Wojciechowski
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.