Szkoła Doktorska - Szkoła Doktorska
specjalność: rolnictwo i ogrodnictwo
Sylabus przedmiotu Algorytmy, NP-zupełność, redukcje:
Informacje podstawowe
| Kierunek studiów | Szkoła Doktorska | ||
|---|---|---|---|
| Forma studiów | studia stacjonarne | Poziom | |
| Stopnień naukowy absolwenta | doktor | ||
| Obszary studiów | charakterystyki PRK | ||
| Profil | |||
| Moduł | — | ||
| Przedmiot | Algorytmy, NP-zupełność, redukcje | ||
| Specjalność | informatyka techniczna i telekomunikacja | ||
| 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) | 3,0 | ECTS (formy) | 3,0 |
| Forma zaliczenia | zaliczenie | Język | polski |
| Blok obieralny | — | Grupa obieralna | — |
Formy dydaktyczne
Wymagania wstępne
| KOD | Wymaganie wstępne |
|---|---|
| W-1 | Matematyka |
| W-2 | Wprowadzenie do informatyki |
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 |
|---|---|---|
| projekty | ||
| T-P-1 | Implementacja w wybranym języku programownia: struktury Union-Find lub algorytmu "magiczne piątki". Pomiary czasowe i weryfikacja złożoności obliczeniowej. | 10 |
| 10 | ||
| wykłady | ||
| T-W-1 | Równania rekurencyjne 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 |
|---|---|---|
| projekty | ||
| A-P-1 | Samodzielna implementacja i pomiary czasowe. | 30 |
| 30 | ||
| wykłady | ||
| A-W-1 | Uczestnictwo w wykładach. | 15 |
| A-W-2 | Praca własna i przygotowanie się do zaliczenia końcowego. | 45 |
| 60 | ||
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 uczenia się - wiedza
| Zamierzone efekty uczenia się | 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 |
|---|---|---|---|---|---|---|
| SD_3-_SzDE03ITT_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. | SD_3_W01 | — | C-1 | T-W-2, T-W-5, T-W-3, T-W-1, T-W-4 | M-1, M-3 | S-1 |
Zamierzone efekty uczenia się - umiejętności
| Zamierzone efekty uczenia się | 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 |
|---|---|---|---|---|---|---|
| SD_3-_SzDE03ITT_U01 Student potrafi wykonać implementację zaawansowanych algorytmów / struktur danych i przeprowadzić eksperyment porównawczy ich złożoności. | SD_3_U01 | — | C-2 | T-P-1 | M-2 | S-1 |
Kryterium oceny - wiedza
| Efekt uczenia się | Ocena | Kryterium oceny |
|---|---|---|
| SD_3-_SzDE03ITT_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. | 2,0 | |
| 3,0 | Potrafi wyjaśnić podstawowy sens zadań algorytmów i struktury danych. | |
| 3,5 | ||
| 4,0 | ||
| 4,5 | ||
| 5,0 |
Kryterium oceny - umiejętności
| Efekt uczenia się | Ocena | Kryterium oceny |
|---|---|---|
| SD_3-_SzDE03ITT_U01 Student potrafi wykonać implementację zaawansowanych algorytmów / struktur danych i przeprowadzić eksperyment porównawczy ich złożoności. | 2,0 | |
| 3,0 | Student potrafi wykonać prostą implementację algorytmów / struktur danych i porównać ich złożoność. | |
| 3,5 | ||
| 4,0 | ||
| 4,5 | ||
| 5,0 |
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