Kombinatoryka dla programistów 1000-I2KomProg

https://moodle.mat.umk.pl (w cyklu 2025/26L)

Na wykładzie i podczas ćwiczeń zostaną poruszone takie zagadnienia, jak:
Reprezentacje i generowanie obiektów kombinatorycznych
Własności i generowanie permutacji, generowanie kombinacji, metoda minimalnych zmian. Kompozycje i rozkłady liczb
Metody przeszukiwania przestrzeni rozwiązań
Algorytmy zachłanne i rekurencyjne, algorytmy dokładne dla problemów trudnych obliczeniowo: programowanie dynamiczne, metoda podziału i ograniczeń. Matroidy i ich związek z algorytmami zachłannymi
Planarność i twierdzenie Kuratowskiego. Kolorowanie grafów: metody kolorowania wierzchołków, krawędzi. Przepływy w sieciach i pokrewne zagadnienia: wyznaczanie maksymalnego przepływu w sieci metodą Dinica; wyznaczanie przepływu w sieci z dolnymi ograniczeniami na przepływy łukowe.
Trudność problemów aproksymacji. Problemy optymalizacji kombinatorycznej, dla których istnieją algorytmy wielomianowe.

W ramach ćwiczeń studenci rozwiązują trudniejsze problemy kombinatoryczne. Należy przygotować co najmniej dwie metody rozwiązujące zadany problem: szybką (np. algorytm zachłanny) i konstruującą rozwiązania o dobrej jakości (np. algorytm podziału i ograniczeń, metaheurystykę).

W cyklu 2025/26L:

jak w ogólnym opisie

Całkowity nakład pracy studenta

godziny kontaktowe: 15 godzin wykładu i 15 godzin laboratorium zadania domowe i bieżące przygotowanie się do laboratoriów: 40 godzin przygotowanie się do kolokwiów: 20 godzin Razem 90 godzin, 3 punkty ECTS

Efekty uczenia się - wiedza

W1: Ma pogłębioną wiedzą na temat formalnych modeli obliczeń a także ich własności i znaczenia w praktycznych zastosowaniach informatycznych, K_W01, K_W02 W2: Ma zaawansowaną wiedzę na temat terminologii i zastosowania kombinatoryki przy rozwiązywaniu problemów algorytmicznych, K_W01, K_W02 W3: Ma wiedzę na temat barier obliczalności i trudności obliczeń. Zna metody algorytmicznego rozwiązywania problemów obliczeniowo trudnych (aproksymacja, szybkie algorytmy wykładnicze, heurystyki), K_W03, K_W04

Efekty uczenia się - umiejętności

U1: Projektuje abstrakcyjne struktury danych i tworzy ich wydajne implementacje, K_U02, K_U04 U2: Projektuje, analizuje pod kątem poprawności i złożoności obliczeniowej oraz programuje algorytmy z wykorzystaniem różnych technik programistycznych, K_U01, K_U05 U3: Potrafi zastosować znane algorytmy w konkretnych sytuacjach, K_U03, K_U04 U4: Potrafi efektywnie dobrać rodzaj i sposób wykonania algorytmu w zależności od postawionego problemu, K_U04

Efekty uczenia się - kompetencje społeczne

K1: Jest nastawiony na jak najlepsze wykonanie zadania; dba o szczegół; jest systematyczny, K_K01, K_K04 K2: Stosuje zasady bezpieczeństwa i higieny pracy w zawodzie informatyka, K_K03, K_K06

Koordynatorzy przedmiotu

Anna Kwiatkowska

Metody dydaktyczne

Wykład ma charakter informacyjno-problemowy. Laboratoria, podczas których prowadzone są rozważania teoretyczne, są połączone z praktyczną realizacją algorytmów w laboratorium komputerowym, zastosowana jest metoda klasyczna problemowa, giełda pomysłów

Metody dydaktyczne eksponujące

- drama
- pokaz
- symulacyjna (gier symulacyjnych)

Metody dydaktyczne podające

- opis
- wykład informacyjny (konwencjonalny)

Metody dydaktyczne poszukujące

- klasyczna metoda problemowa
- laboratoryjna
- giełda pomysłów
- ćwiczeniowa
- panelowa

Wymagania wstępne

Matematyka dyskretna – znajomość podstawowych twierdzeń teorii liczb, podstawowych obiektów i technik kombinatorycznych i stosowanie ich do rozwiązywania zadań o charakterze kombinatorycznym, znajomość podstawowych pojęć teorii grafów, algorytmów dla problemów matematycznych i elementów teorii złożoności obliczeniowej. Algorytmy i Struktury danych – znajomość technik i metod programowania: iteracja, rekurencja, dziel i zwyciężaj, zachłanność, dynamiczność, znajomość kluczowych algorytmów i struktur danych, w tym dynamicznych struktur danych (stos, kolejka, lista), grafów i ich implementacji w języku programowania, przepływów w sieciach. Znajomość co najmniej jednego języka programowania.

Kryteria oceniania

Wykład: egzamin pisemny – W1, W2, W3, U2, U4, K1, K2

Laboratoria:
Ocena ciągłej podlegają: bieżące przygotowanie do zajęć, ustne prezentacje wybranych problemów kombinatorycznych, autorskie programy realizujące algorytmy i ich złożoność obliczeniowa, wykonywanie zadań domowych, zestawienia bibliografii
Referat – W1, W2, U3, U4, K1
Autorskie rozwiązania – W3, U1, U2, K1, K2
Kolokwium – W1, W2, W3, U4, K1
Nieobecności powyżej dwóch w semestrze wymagają zaliczenia opuszczonego materiału w formie wskazanej przez prowadzącego.

Praktyki zawodowe

Nie dotyczy

Literatura

Literatura podstawowa:
Corman T.H., Leiserson C.E., Rivest R.L., Wprowadzenie do algorytmów, WNT, Warszawa 1997.
Diestel R., Graph Theory, Springer, Heidelberg 2005.
Korte B., Vygen J., Combinatorial Optimization. Theory and Algorithms. 3rd edition, Springer, Heidelberg 2006.
Lipski W., Kombinatoryka dla programistów, WNT, Warszawa 1982.
Sysło M.M., Deo N., Kowalik J.S., Algorytmy optymalizacji dyskretnej, WN PWN, Warszawa 1993, 1995, 1997.
Vazirani V.V., Algorytmy aproksymacyjne, WNT, Warszawa 2005.
West D.B., Introduction to Graph Theory, 2nd edition, Prentice Hall, 2001

W cyklu 2025/26L:

jak w ogólnym opisie

Uwagi

W cyklu 2025/26L:

jak w ogólnym opisie

Więcej informacji

Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb:

Strona przedmiotu 1000-I2KomProg w USOSweb