Wydział Informatyki - Informatyka (S3)
Sylabus przedmiotu Algorytmy, NP-zupełność, redukcje - Przedmiot obieralny I:
Informacje podstawowe
| Kierunek studiów | Informatyka | ||
|---|---|---|---|
| Forma studiów | studia stacjonarne | Poziom | trzeciego stopnia |
| Stopnień naukowy absolwenta | doktor | ||
| Obszary studiów | — | ||
| Profil | |||
| Moduł | — | ||
| Przedmiot | Algorytmy, NP-zupełność, redukcje - Przedmiot obieralny I | ||
| Specjalność | przedmiot wspólny | ||
| Jednostka prowadząca | Katedra Metod Sztucznej Inteligencji i Matematyki Stosowanej | ||
| Nauczyciel odpowiedzialny | Przemysław Klęsk <pklesk@wi.zut.edu.pl> | ||
| Inni nauczyciele | |||
| ECTS (planowane) | 1,0 | ECTS (formy) | 1,0 |
| Forma zaliczenia | zaliczenie | Język | polski |
| Blok obieralny | 1 | Grupa obieralna | 1 |
Formy dydaktyczne
Wymagania wstępne
| KOD | Wymaganie wstępne |
|---|---|
| W-1 | matematyka |
| W-2 | algorytmy i struktury danych |
| W-3 | podstawy programowania |
Cele przedmiotu
| KOD | Cel modułu/przedmiotu |
|---|---|
| C-1 | Rozwinięcie umiejętności studentów w zakresie zaawansowanej analizy matematycznej algorytmów i struktur danych. |
| C-2 | Wykształcenie rozumienia klas złożoności problemów: P, NP, NP-zupełne, NP-trudne, Exp-time oraz pokazanie technik redukcji pomiędzy wybranymi problemami. |
Treści programowe z podziałem na formy zajęć
| KOD | Treść programowa | Godziny |
|---|---|---|
| laboratoria | ||
| T-L-1 | Samodzielna implementacja i badanie złożoności wybranej struktury danych / algorytmu (np. drzewo czerwono-czarne, kopiec binarmy, Union-Find, radix-sort vs merge-sort). | 5 |
| 5 | ||
| wykłady | ||
| T-W-1 | Równania redukcyjne dla algorytmów sortujących, w szczególności: merge sort, średni przypadek dla Quicksort (a liczba harmonicznych). Złożoność n log n jako dolne ograniczenie dla algorytmów sortujących poprzez porównania. Sortowanie przez zliczanie z optymistyczną złożonością liniową: counting sort, bucket sort, radix sort. | 3 |
| T-W-2 | Zaawansowane struktury danych: drzewa czerwono-czarne, Union-Find i dowód złożoności zamortyzowanej m log * n (logarytm iterowany). | 3 |
| T-W-3 | Sortowanie topologiczne, DFS, BFS, składowe silnie spójne grafu (strongly connected components). | 2 |
| T-W-4 | Algorytmy znajdowania powłoki wypukłej (ConvexHull) na płaszczyźnie. Wybrane przykłady algorytmów programowania dynamicznego i zachłannego. | 3 |
| T-W-5 | Klasy złożoności: P, NP, P, NP., NP.-zupełne, NP.-trudne, Exp-time. Niedetermistyczna maszyna Turinga. Problemy: Hamiltona, kliki, 3D matching. Redukcja i jej przykłady: sortowanie ≤ Convex Hull, SAT ≤ 3SAT (spełnialność formuł logicznych), trójkolorowalność ≤ SAT, 2SAT ≤ strongly connected components, cykl Hamiltona ≤ TSP, pokrycie wierzchołkowe ≤ zbiór dominujący, 3SAT ≤ pokrycie wierzchołkowe, pokrycie wierzchołkowe ≤ cykl Hamiltona. | 4 |
| 15 | ||
Obciążenie pracą studenta - formy aktywności
| KOD | Forma aktywności | Godziny |
|---|---|---|
| laboratoria | ||
| A-L-1 | Praca na zajęciach. | 5 |
| A-L-2 | Dokończenie implementacji w domu oraz badania / eksperymenty nad złożonością. | 25 |
| 30 | ||
| wykłady | ||
| A-W-1 | Udział w wykładach. | 15 |
| A-W-2 | Przygotowanie się do testu zaliczeniowego. | 15 |
| 30 | ||
Metody nauczania / narzędzia dydaktyczne
| KOD | Metoda nauczania / narzędzie dydaktyczne |
|---|---|
| M-1 | Wykłady informacyjne i problemowe. |
| M-2 | Metody programowe z użyciem komputera. |
| M-3 | Ocena za test końcowy (wiadomości z wykładu). |
Sposoby oceny
| KOD | Sposób oceny |
|---|---|
| S-1 | Ocena podsumowująca: Ocena za program opracowywany na laboratorium i w domu. |
Zamierzone efekty kształcenia - wiedza
| Zamierzone efekty kształcenia | Odniesienie do efektów kształcenia dla dyscypliny | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|
| I_3-_B/01/01_W01 Student potrafi analizować algorytmy i struktury danych w sposób zaawansowany. Student rozumie klasy złożoności problemów: P, NP, NP-zupełne, NP-trudne, Exp-time i zna wybrane redukcje pomiędzy problemami. | I_3A_W01 | — | — | — | — | — |
Zamierzone efekty kształcenia - umiejętności
| Zamierzone efekty kształcenia | Odniesienie do efektów kształcenia dla dyscypliny | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|
| I_3-_B/01/01_U01 Student potrafi wykonać implementację zaawansowanych algorytmów / struktur danych i przeprowadzić eksperyment porównawczy ich złożoności. | I_3A_U01 | — | — | — | — | — |
Literatura podstawowa
- T.H. Cormen, Algorytmy bez tajemnic, Helion, 2013
Literatura dodatkowa
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to algorithms, MIT Press, 2009, 3