UNIWERSYTET ŁÓDZKI - Centralny System Uwierzytelniania
Strona główna

Teoria grafów i sieci

Informacje ogólne

Kod przedmiotu: 1100-GF0ZUI
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Teoria grafów i sieci
Jednostka: Wydział Matematyki i Informatyki
Grupy: Przedmioty ZUI1 - sem. letni
Punkty ECTS i inne: 0 LUB 5.00 LUB 7.00 (w zależności od programu) 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.
zobacz reguły punktacji
Język prowadzenia: polski
Forma zaliczenia:

egzamin
Ilość godzin wykładu:

16
Ilość godzin ćwiczeń:

16
Forma studiów:

niestacjonarne (zaoczne)
Wymagania wstępne:

Umiejętność programowania w dowolnym języku.
Skrócony opis:

Celem przedmiotu jest przekazanie i ugruntowanie wiedzy z teorii grafów i sieci. Studenci zostaną zaznajomieni z szerokimi zastosowaniami omawianych zagadnień w informatyce oraz metodami formułowania praktycznych zagadnień w języku teorii grafów.
Efekty uczenia się:

W wyniku przeprowadzonych zajęć student:

E1. rozróżnia klasy grafów na podstawie ich własności,

E2. zna i potrafi zastosować algorytmy grafowe,

E3. potrafi sformułować praktyczne problemy za pomocą pojęć teorii grafów oraz wykorzystuje do nich odpowiednie algorytmy grafowe,

E4. samodzielnie analizuje i stosuje algorytmy grafowe,

E5. potrafi implementować algorytmy grafowe w wybranym języku programowania.

Powyższe efekty kształcenia osiągane w ramach przedmiotu pozwalają na realizację kierunkowych efektów kształcenia, mających następujące oznaczenia w programie Informatyka II stopnia: 1100I-2A_W01, 1100I-2A_W03, 1100I-2A_W04, 1100I-2A_W05, 1100I-2A_W09, 1100I-2A_U01, 1100I-2A_U02, 1100I-2A_U03, 1100I-2A_U04, 1100I-2A_U05, 1100I-2A_U07, 1100I-2A_U10, 1100I-2A_U11, 1100I-2A_U12, 1100I-2A_U14, 1100I-2A_K01, 1100I-2A_K02, 1100I-2A_K06, 1100I-2A_K07.

Zajęcia w cyklu "Semestr letni 2023/2024" (w trakcie)

Okres: 2024-02-26 - 2024-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia informatyczne, 16 godzin więcej informacji
Wykład, 16 godzin więcej informacji
Koordynatorzy: Rafał Kamocki
Prowadzący grup: Rafał Kamocki
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Ocena zgodna z regulaminem studiów
Ćwiczenia informatyczne - Ocena zgodna z regulaminem studiów
Wykład - Ocena zgodna z regulaminem studiów
Metody dydaktyczne:

wykład konwersatoryjny, pokaz

ćwiczenia praktyczne, referat
Sposoby i kryteria oceniania:

Poszczególne efekty kształcenia są weryfikowane w ramach:

podczas zajęć:E2,E4,E5,E6, podczas egzaminu pisemnego E1,E3,E6

Ocena z ćwiczeń jest oceną za omówienie i opracowanie (przed grupą)wybranych algorytmów.

Ocena z wykładu to ocena z egzaminu.

Ocena końcowa wymaga zaliczonych ćwiczeń i zaliczonego egzaminu.

Na ocenę końcową składa się ocena z ćwiczeń (40%), frekwencja (10%) i ocena z egzaminu (50%). Egzamin ma formę pisemną.
Treści kształcenia:

1. Podstawowe definicje teorii grafów, metody przeszukiwania grafów

2. Grafy Eulera, algorytmy rozwiązujące problem chińskiego listonosza

3. Grafy Hamiltona, algorytmy TSP.

4. Własności drzew, rodzaje i własności drzew binarnych, algorytm znajdowania centrum w grafie, optymalne drzewo binarne, algorytm Huffmana, drzewa rozpinające, algorytmy MST, algorytmy znajdowania najkrótszych ścieżek w grafie( z jednym źródłem, między wszystkimi wierzchołkami, grafy rzadkie)

5. Kolorowanie grafów, algorytmy kolorowania grafów, zbiory niezależne

6. Grafy planarne, uogólnione grafy Petersena

7. Skojarzenia w grafach, algorytmy wyznaczania maksymalnego skojarzenia i skojarzenia ważonego

8. Drzewa Steiner'a, algorytmy SMT.

9. Sieci przepływowe, metoda Forda-Fulkersona, algorytmy wyznaczania maksymalnego przepływu.
Literatura:

[1]. T.Cormen, C.Leiserson, R.Rivest Wprowadzenie do algorytmów

[2]. J.Kurose, K.Ross. Sieci komputerowe. Od ogółu do szczegółu z Internetem w tle

[3]. J.Harris, J.Hirst, M.Mossinghoff Combinatorics and Graph Theory

[4]. W.Lipski, Kombinatoryka dla programistów

[5]. D.Jungnickel Graphs, Networks and Algorithms

[6]. D.Medhi, K.Ramasamy Network Routing: Algorithms, Protocols, and Architectures

[7] G.Caldarelli, A.Vespignani Large Scale Structure and Dynamics of Complex Networks

Zajęcia w cyklu "Semestr letni 2022/2023" (zakończony)

Okres: 2023-02-20 - 2023-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia informatyczne, 16 godzin więcej informacji
Wykład, 16 godzin więcej informacji
Koordynatorzy: Rafał Kamocki
Prowadzący grup: Rafał Kamocki
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Ocena zgodna z regulaminem studiów
Ćwiczenia informatyczne - Ocena zgodna z regulaminem studiów
Wykład - Ocena zgodna z regulaminem studiów

Zajęcia w cyklu "Semestr letni 2021/2022" (zakończony)

Okres: 2022-02-21 - 2022-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia informatyczne, 16 godzin więcej informacji
Wykład, 16 godzin więcej informacji
Koordynatorzy: Rafał Kamocki
Prowadzący grup: Rafał Kamocki
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Ocena zgodna z regulaminem studiów
Ćwiczenia informatyczne - Ocena zgodna z regulaminem studiów
Wykład - Ocena zgodna z regulaminem studiów

Zajęcia w cyklu "Semestr letni 2020/2021" (zakończony)

Okres: 2021-03-08 - 2021-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia informatyczne, 16 godzin więcej informacji
Wykład, 16 godzin więcej informacji
Koordynatorzy: Rafał Kamocki
Prowadzący grup: Rafał Kamocki
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Ocena zgodna z regulaminem studiów
Ćwiczenia informatyczne - Ocena zgodna z regulaminem studiów
Wykład - Ocena zgodna z regulaminem studiów
Metody dydaktyczne:

wykład konwersatoryjny, pokaz

ćwiczenia praktyczne, referat
Sposoby i kryteria oceniania:

Poszczególne efekty kształcenia są weryfikowane w ramach:

podczas zajęć:E2,E4,E5,E6, podczas egzaminu pisemnego E1,E3,E3,E6

Ocena z ćwiczeń jest oceną za omówienie i opracowanie (przed grupą)wybranych algorytmów.

Ocena z wykładu to ocena z egzaminu.

Ocena końcowa wymaga zaliczonych ćwiczeń i zaliczonego egzaminu.

Na ocenę końcową składa się ocena z ćwiczeń (40%), frekwencja (10%) i ocena z egzaminu (50%). Egzamin ma formę pisemną.
Treści kształcenia:

1. Podstawowe definicje teorii grafów, metody przeszukiwania grafów

2. Grafy Eulera, algorytmy rozwiązujące problem chińskiego listonosza

3. Grafy Hamiltona, algorytmy TSP.

4. Własności drzew, rodzaje i własności drzew binarnych, algorytm znajdowania centrum w grafie, optymalne drzewo binarne, algorytm Huffmana, drzewa rozpinające, algorytmy MST, algorytmy znajdowania najkrótszych ścieżek w grafie( z jednym źródłem, między wszystkimi wierzchołkami, grafy rzadkie)

5. Kolorowanie grafów, algorytmy kolorowania grafów, zbiory niezależne

6. Grafy planarne, uogólnione grafy Petersena

7. Skojarzenia w grafach, algorytmy wyznaczania maksymalnego skojarzenia i skojarzenia ważonego

8. Drzewa Steiner'a, algorytmy SMT.

9. Sieci przepływowe, metoda Forda-Fulkersona, algorytmy wyznaczania maksymalnego przepływu.
Literatura:

[1]. T.Cormen, C.Leiserson, R.Rivest Wprowadzenie do algorytmów

[2]. J.Kurose, K.Ross. Sieci komputerowe. Od ogółu do szczegółu z Internetem w tle

[3]. J.Harris, J.Hirst, M.Mossinghoff Combinatorics and Graph Theory

[4]. W.Lipski, Kombinatoryka dla programistów

[5]. D.Jungnickel Graphs, Networks and Algorithms

[6]. D.Medhi, K.Ramasamy Network Routing: Algorithms, Protocols, and Architectures

[7] G.Caldarelli, A.Vespignani Large Scale Structure and Dynamics of Complex Networks

Zajęcia w cyklu "Semestr letni 2019/2020" (zakończony)

Okres: 2020-02-24 - 2020-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia informatyczne, 16 godzin więcej informacji
Wykład, 16 godzin więcej informacji
Koordynatorzy: Marek Majewski
Prowadzący grup: Marek Majewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Ocena zgodna z regulaminem studiów
Ćwiczenia informatyczne - Ocena zgodna z regulaminem studiów
Wykład - Ocena zgodna z regulaminem studiów

Zajęcia w cyklu "Semestr letni 2018/2019" (zakończony)

Okres: 2019-02-18 - 2019-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia informatyczne, 16 godzin więcej informacji
Wykład, 16 godzin więcej informacji
Koordynatorzy: Marek Majewski
Prowadzący grup: Marek Majewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Ocena zgodna z regulaminem studiów
Ćwiczenia informatyczne - Ocena zgodna z regulaminem studiów
Wykład - Ocena zgodna z regulaminem studiów

Zajęcia w cyklu "Semestr letni 2017/2018" (zakończony)

Okres: 2018-02-19 - 2018-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia informatyczne, 16 godzin więcej informacji
Wykład, 16 godzin więcej informacji
Koordynatorzy: Marek Majewski
Prowadzący grup: Marek Majewski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Ocena zgodna z regulaminem studiów
Ćwiczenia informatyczne - Ocena zgodna z regulaminem studiów
Wykład - Ocena zgodna z regulaminem studiów
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest UNIWERSYTET ŁÓDZKI.
kontakt deklaracja dostępności USOSweb 7.0.3.0-0