Kombinatoryka i teoria grafów
Informacje ogólne
| Kod przedmiotu: | 1100-KT0VDLM |
| Kod Erasmus / ISCED: | (brak danych) / (brak danych) |
| Nazwa przedmiotu: | Kombinatoryka i teoria grafów |
| Jednostka: | Wydział Matematyki i Informatyki |
| Grupy: | |
| Punkty ECTS i inne: |
0 LUB
4.00
(w zależności od programu)
|
| Język prowadzenia: | polski |
| Forma zaliczenia: | zaliczenie |
| Poziom studiów: | Studia pierwszego stopnia |
| Forma studiów: | stacjonarne |
| Wymagania wstępne: | brak |
| Skrócony opis: |
Celem przedmiotu jest przekazanie i ugruntowanie wiedzy z teorii grafów oraz optymalizacji kombinatorycznej. Studenci zostaną zaznajomieni z szerokimi zastosowaniami omawianych zagadnień w informatyce, ekonomii oraz metodami formułowania praktycznych zagadnień w języku teorii grafów oraz rozwiązywania problemów optymalizacyjnych. |
| Efekty uczenia się: |
W wyniku przeprowadzonych zajęć student: E1. zna i potrafi zastosować podstawowe algorytmy kombinatoryczne i grafowe E2. rozróżnia klasy grafów na podstawie ich własności E3. potrafi rozwiązać zadania z teorii grafów. |
Zajęcia w cyklu "Semestr letni 2025/2026" (jeszcze nie rozpoczęty)
| Okres: | 2026-02-23 - 2026-09-30 |
 
PN WT ŚR CZ PT |
| Typ zajęć: |
Ćwiczenia konwersatoryjne, 24 godzin
Wykład, 24 godzin
|
|
| Koordynatorzy: | Rafał Kamocki | |
| Prowadzący grup: | (brak danych) | |
| Lista studentów: | (nie masz dostępu) | |
| Zaliczenie: |
Przedmiot -
Ocena zgodna z regulaminem studiów
Ćwiczenia konwersatoryjne - Ocena zgodna z regulaminem studiów Wykład - Ocena zgodna z regulaminem studiów |
|
| Metody dydaktyczne: | wykład, pokaz ćwiczenia praktyczne, referat |
|
| Sposoby i kryteria oceniania: | Ocena z ćwiczeń jest oceną za omówienie i opracowanie (przed grupą) wybranych algorytmów. Ocena z wykładu to ocena ze sprawdzianu. Ocena końcowa wymaga zaliczonych ćwiczeń i zaliczonego sprawdzianu. Na ocenę końcową składa się ocena z ćwiczeń (50%) oraz ocena ze sprawdzianu (50%). |
|
| Metody weryfikacji i oceny stopnia osiągnięcia założonych efektów uczenia się: | referat - weryfikacja efektu E1 sprawdzian pisemny - weryfikacja efektów E2 i E3 |
|
| Szczegółowe 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, 4. Własności drzew, rodzaje i własności drzew binarnych, optymalne drzewo binarne, algorytm Huffmana, zliczanie drzew, drzewa rozpinające, algorytmy MST, algorytmy znajdowania najkrótszych ścieżek w grafie( z jednym źródłem, między wszystkimi wierzchołkami) 5. Różne rodzaje spójności 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 9. Drzewa Steiner'a, algorytmy SMT, drzewa multicast 10. Różne algorytmy permutacji, kombinacji z powtórzeniami i bez powtórzeń 11. Sieci przepływowe, metoda Forda-Fulkersona, algorytmy wyznaczania maksymalnego przepływu, przepływy o minimalnym koszcie, modele przepływów w sieci |
|
| 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 |
|
Właścicielem praw autorskich jest UNIWERSYTET ŁÓDZKI.
