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

Kombinatoryka i teoria grafów

Informacje ogólne

Kod przedmiotu: 1100-KG0OMN 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 6.00 LUB 5.00 (w zależności od programu)
zobacz reguły punktacji
Język prowadzenia: polski
Efekty kształcenia:

W wyniku przeprowadzonych zajęć student:

E1. zna i potrafi zastosować podstawowe algorytmy kombinatoryczne (generowania permutacji, podzbiorów zbioru itd.)

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

E3. zna i potrafi zastosować algorytmy grafowe

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

E5. samodzielnie opracowuje i analizuje algorytmy kombinatoryczne lub grafowe

Forma zaliczenia:

E

Forma studiów:

stacjonarne

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.

Zajęcia w cyklu "Semestr zimowy 2017/2018" (w trakcie)

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


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia konwersatoryjne, 28 godzin więcej informacji
Wykład, 28 godzin więcej informacji
Koordynatorzy: (brak danych)
Prowadzący grup: (brak danych)
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena zgodna z regulaminem studiów

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

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


powiększ
zobacz plan zajęć
Typ zajęć: Konwersatorium, 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: Ocena zgodna z regulaminem studiów
Czy ECTS?:

T

Metody dydaktyczne:

wykład konwersatoryjny, pokaz

ćwiczenia praktyczne, referat

Sposoby i kryteria oceniania:

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

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

Oceną końcową jest ocena z wykładu.

Treści kształcenia:

Jest to wykład obejmujący następujące zagadnienia:

- podział liczby, różne algorytmy permutacji, kombinacji z powtórzeniami i bez powtórzeń

-podziały zbiorów, dwumian Newtona i jego własności, liczby Stirlinga drugiego i pierwszego rodzaju, liczba Bella

-funkcje tworzące – przykłady zastosowań

-zasada włączania i wyłączania i jej zastosowania

-własności i rodzaje grafów, działania na grafach, metody reprezentacji grafów

-grafy Eulera i ich zastosowanie, algorytm rozwiązujący problem chińskiego listonosza

-grafy Hamiltona i ich zastosowanie, algorytmy problemu komiwojażera, optymalizacja naturalna, algorytmy mrówkowe,

własności drzew, rodzaje i własności drzew binarnych, optymalne drzewo binarne i ich zastosowania, algorytm Huffmana, zliczanie drzew, algorytmy Prüfer'a, drzewa rozpinające, algorytmy MST, drzewa Steiner'a, algorytmy SMT, drzewa multicast i ich zastosowania

-algorytmy znajdowania najkrótszych ścieżek w grafie( z jednym źródłem, między wszystkimi wierzchołkami, grafy rzadkie),

kolorowanie grafów, algorytm zachłanny kolorowania grafów, zbiory niezależne, grafy planarne, uogólnione grafy Petersena, grafy platońskie

-sieci przepływowe, metoda Forda-Fulkersona, przepływ o minimalnym koszcie

-skojarzenia w grafach

-algorytm znajdowania centrum w grafie, sieci rozległe, sieć Internet

Literatura:

1. W. Lipski; Kombinatoryka dla programistów.

2. T. Cormen, Ch. E. Leiserson, R. L. Rivest; Wprowadzenie do algorytmów.

3. K. A. Ross, Ch. R. B. Wright; Matematyka dyskretna.

4. M. Sysło, N. Deo; Metody optymalizacji dyskretnej z przykładami w Turbo Pascalu.

5. M. Libura, J. Sikorski; Wykłady z matematyki dyskretnej. Cz. I: Kombinatoryka.

6. M. Libura, J. Sikorski; Wykłady z matematyki dyskretnej. Cz. II: Teoria grafów.

7. D. Jungnickel, Graphs; Networks and Algorithms.

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