Uniwersytet Łódzki - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

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)
zobacz reguły punktacji
Język prowadzenia: polski
Efekty kształcenia:

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. wykorzystuje narzędzia informatyczne do wybranego algorytmu

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.

Forma zaliczenia:

E

Forma studiów:

stacjonarne

Wymagania wstępne:

umiejętność programowania

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.

Zajęcia w cyklu "Semestr letni 2016/2017" (w trakcie)

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


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia informatyczne, 28 godzin więcej informacji
Wykład, 28 godzin więcej informacji
Koordynatorzy: Monika Bartkiewicz
Prowadzący grup: Monika Bartkiewicz, Marek Majewski
Lista studentów: (nie masz dostępu)
Zaliczenie: 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

Zajęcia w cyklu "Semestr letni 2015/2016" (zakończony)

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


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia informatyczne, 28 godzin więcej informacji
Wykład, 28 godzin więcej informacji
Koordynatorzy: Monika Bartkiewicz
Prowadzący grup: Monika Bartkiewicz, Marek Majewski
Lista studentów: (nie masz dostępu)
Zaliczenie: 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

Zajęcia w cyklu "Semestr letni 2014/2015" (zakończony)

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


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia informatyczne, 28 godzin więcej informacji
Wykład, 28 godzin więcej informacji
Koordynatorzy: Monika Bartkiewicz
Prowadzący grup: Monika Bartkiewicz, Marek Majewski
Lista studentów: (nie masz dostępu)
Zaliczenie: 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

Zajęcia w cyklu "Semestr letni 2013/2014" (zakończony)

Okres: 2014-02-17 - 2014-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia informatyczne, 28 godzin więcej informacji
Wykład, 28 godzin więcej informacji
Koordynatorzy: Monika Bartkiewicz
Prowadzący grup: Monika Bartkiewicz, Marek Majewski
Lista studentów: (nie masz dostępu)
Zaliczenie: 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

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Łódzki.