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

Teoria grafów i sieci

Informacje ogólne

Kod przedmiotu: 1100-GF0UII
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Teoria grafów i sieci
Jednostka: Wydział Matematyki i Informatyki
Grupy:
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
Forma studiów:

stacjonarne
Wymagania wstępne:

umiejętność programowania, znajomość języka R
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 algorytmy grafowe

E3. zna własności sieci złożonych

E4. analizuje i stosuje algorytmy grafowe

E5 zna możliwości zastosowania teorii grafów w eksploracji danych

E6. wykorzystuje narzędzia informatyczne do wybranego zagadnienia metod eksploracji danych

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

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, 28 godzin więcej informacji
Wykład, 28 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, optymalizacja naturalna, algorytmy mrówkowe

4. Własności drzew, rodzaje i własności drzew binarnych, algorytm znajdowania centrum w grafie, optymalne drzewo binarne, algorytm Huffmana, zliczanie drzew, algorytmy Prüfer'a, 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. Różne rodzaje spójności grafu, algorytm wyznaczania dwuspójnych składowych grafu

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

7. Grafy planarne, uogólnione grafy Petersena

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

9. Drzewa Steiner'a, algorytmy SMT, drzewa multicast

10. Algorytmy routingu w sieciach

11. Sieci przepływowe, metoda Forda-Fulkersona, algorytmy wyznaczania maksymalnego przepływu, przepływy o minimalnym koszcie, modele przepływów w sieci

12. Sieci złożone, ich budowa i własności, sieć Internet
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, 28 godzin więcej informacji
Wykład, 28 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, 28 godzin więcej informacji
Wykład, 28 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
Czy ECTS?:

T
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ń (50%) 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, optymalizacja naturalna, algorytmy mrówkowe

4. Własności drzew, rodzaje i własności drzew binarnych, algorytm znajdowania centrum w grafie, optymalne drzewo binarne, algorytm Huffmana, zliczanie drzew, algorytmy Prüfer'a, 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. Różne rodzaje spójności grafu, algorytm wyznaczania dwuspójnych składowych grafu

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

7. Grafy planarne, uogólnione grafy Petersena

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

9. Drzewa Steiner'a, algorytmy SMT, drzewa multicast

10. Algorytmy routingu w sieciach

11. Sieci przepływowe, metoda Forda-Fulkersona, algorytmy wyznaczania maksymalnego przepływu, przepływy o minimalnym koszcie, modele przepływów w sieci

12. Sieci złożone, ich budowa i własności, sieć Internet
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 2020/2021" (zakończony)

Okres: 2021-03-08 - 2021-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia informatyczne, 28 godzin więcej informacji
Wykład, 28 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
Czy ECTS?:

T
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, optymalizacja naturalna, algorytmy mrówkowe

4. Własności drzew, rodzaje i własności drzew binarnych, algorytm znajdowania centrum w grafie, optymalne drzewo binarne, algorytm Huffmana, zliczanie drzew, algorytmy Prüfer'a, 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. Różne rodzaje spójności grafu, algorytm wyznaczania dwuspójnych składowych grafu

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

7. Grafy planarne, uogólnione grafy Petersena

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

9. Drzewa Steiner'a, algorytmy SMT, drzewa multicast

10. Algorytmy routingu w sieciach

11. Sieci przepływowe, metoda Forda-Fulkersona, algorytmy wyznaczania maksymalnego przepływu, przepływy o minimalnym koszcie, modele przepływów w sieci

12. Sieci złożone, ich budowa i własności, sieć Internet
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, 28 godzin więcej informacji
Wykład, 28 godzin więcej informacji
Koordynatorzy: Monika Bartkiewicz
Prowadzący grup: Monika Bartkiewicz
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
Czy ECTS?:

T
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, optymalizacja naturalna, algorytmy mrówkowe

4. Własności drzew, rodzaje i własności drzew binarnych, algorytm znajdowania centrum w grafie, optymalne drzewo binarne, algorytm Huffmana, zliczanie drzew, algorytmy Prüfer'a, 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. Różne rodzaje spójności grafu, algorytm wyznaczania dwuspójnych składowych grafu

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

7. Grafy planarne, uogólnione grafy Petersena

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

9. Drzewa Steiner'a, algorytmy SMT, drzewa multicast

10. Algorytmy routingu w sieciach

11. Sieci przepływowe, metoda Forda-Fulkersona, algorytmy wyznaczania maksymalnego przepływu, przepływy o minimalnym koszcie, modele przepływów w sieci

12. Sieci złożone, ich budowa i własności, sieć Internet
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 2018/2019" (zakończony)

Okres: 2019-02-18 - 2019-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia informatyczne, 28 godzin więcej informacji
Wykład, 28 godzin więcej informacji
Koordynatorzy: Monika Bartkiewicz
Prowadzący grup: Monika Bartkiewicz, 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
Czy ECTS?:

T
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 opracowanie i omówienie (przed grupą)wybranych algorytmów.

Oceną z wykładu jest ocena z egzaminu.

Ocena końcowa może być zwiększona o 0.5 oceny za frekwencję i aktywność na wykładzie oraz o 0.5 oceny za bardzo dobrą ocenę z ćwiczeń.
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, optymalizacja naturalna, algorytmy mrówkowe

4. Własności drzew, rodzaje i własności drzew binarnych, algorytm znajdowania centrum w grafie, optymalne drzewo binarne, algorytm Huffmana, zliczanie drzew, algorytmy Prüfer'a, 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. Różne rodzaje spójności grafu, algorytm wyznaczania dwuspójnych składowych grafu

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

7. Grafy planarne, uogólnione grafy Petersena

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

9. Drzewa Steiner'a, algorytmy SMT, drzewa multicast

10. Algorytmy routingu w sieciach

11. Sieci przepływowe, metoda Forda-Fulkersona, algorytmy wyznaczania maksymalnego przepływu, przepływy o minimalnym koszcie, modele przepływów w sieci

12. Sieci złożone, ich budowa i własności, sieć Internet
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 2017/2018" (zakończony)

Okres: 2018-02-19 - 2018-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia informatyczne, 28 godzin więcej informacji
Wykład, 28 godzin więcej informacji
Koordynatorzy: Monika Bartkiewicz
Prowadzący grup: Monika Bartkiewicz, Rafał Kamocki, 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
Czy ECTS?:

T
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 opracowanie i omówienie (przed grupą)wybranych algorytmów.

Na ocenę z wykładu składa się ocena z ćwiczeń (40%), frekwencja (10%) i ocena z egzaminu (50%). Egzamin ma formę pisemną.

Oceną końcową jest ocena z wykładu.
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, optymalizacja naturalna, algorytmy mrówkowe

4. Własności drzew, rodzaje i własności drzew binarnych, algorytm znajdowania centrum w grafie, optymalne drzewo binarne, algorytm Huffmana, zliczanie drzew, algorytmy Prüfer'a, 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. Różne rodzaje spójności grafu, algorytm wyznaczania dwuspójnych składowych grafu

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

7. Grafy planarne, uogólnione grafy Petersena

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

9. Drzewa Steiner'a, algorytmy SMT, drzewa multicast

10. Algorytmy routingu w sieciach

11. Sieci przepływowe, metoda Forda-Fulkersona, algorytmy wyznaczania maksymalnego przepływu, przepływy o minimalnym koszcie, modele przepływów w sieci

12. Sieci złożone, ich budowa i własności, sieć Internet
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
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