Zachodniopomorski Uniwersytet Technologiczny w Szczecinie

Szkoła Doktorska - Szkoła Doktorska
specjalność: technologia żywności i żywienia

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

Forma dydaktycznaKODSemestrGodzinyECTSWagaZaliczenie
wykładyW5 15 2,00,50zaliczenie
projektyP5 10 1,00,50zaliczenie

Wymagania wstępne

KODWymaganie wstępne
W-1Matematyka
W-2Wprowadzenie do informatyki

Cele przedmiotu

KODCel modułu/przedmiotu
C-1Rozwinięcie umiejętności studentów w zakresie zaawansowanej analizy matematycznej algorytmów i struktur danych.
C-2Wykształ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ęć

KODTreść programowaGodziny
projekty
T-P-1Implementacja 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-1Ró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-2Zaawansowane struktury danych: drzewa czerwono-czarne, Union-Find i dowód złożoności zamortyzowanej m log * n (logarytm iterowany).3
T-W-3Sortowanie topologiczne, DFS, BFS, składowe silnie spójne grafu (strongly connected components).2
T-W-4Algorytmy znajdowania powłoki wypukłej (ConvexHull) na płaszczyźnie. Wybrane przykłady algorytmów programowania dynamicznego i zachłannego.3
T-W-5Klasy 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

KODForma aktywnościGodziny
projekty
A-P-1Samodzielna implementacja i pomiary czasowe.30
30
wykłady
A-W-1Uczestnictwo w wykładach.15
A-W-2Praca własna i przygotowanie się do zaliczenia końcowego.45
60

Metody nauczania / narzędzia dydaktyczne

KODMetoda nauczania / narzędzie dydaktyczne
M-1Wykłady informacyjne i problemowe.
M-2Metody programowe z użyciem komputera.
M-3Ocena za test końcowy (wiadomości z wykładu).

Sposoby oceny

KODSposób oceny
S-1Ocena 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 dyscyplinyOdniesienie do efektów zdefiniowanych dla obszaru kształceniaCel przedmiotuTreści programoweMetody nauczaniaSposó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_W01C-1T-W-2, T-W-5, T-W-3, T-W-1, T-W-4M-1, M-3S-1

Zamierzone efekty uczenia się - umiejętności

Zamierzone efekty uczenia sięOdniesienie do efektów kształcenia dla dyscyplinyOdniesienie do efektów zdefiniowanych dla obszaru kształceniaCel przedmiotuTreści programoweMetody nauczaniaSposó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_U01C-2T-P-1M-2S-1

Kryterium oceny - wiedza

Efekt uczenia sięOcenaKryterium 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,0Potrafi 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ęOcenaKryterium 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,0Student 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

  1. T.H. Cormen, Algorytmy bez tajemnic, Helion, 2013

Literatura dodatkowa

  1. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to algorithms, MIT Press, 2009, 3

Treści programowe - projekty

KODTreść programowaGodziny
T-P-1Implementacja w wybranym języku programownia: struktury Union-Find lub algorytmu "magiczne piątki". Pomiary czasowe i weryfikacja złożoności obliczeniowej.10
10

Treści programowe - wykłady

KODTreść programowaGodziny
T-W-1Ró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-2Zaawansowane struktury danych: drzewa czerwono-czarne, Union-Find i dowód złożoności zamortyzowanej m log * n (logarytm iterowany).3
T-W-3Sortowanie topologiczne, DFS, BFS, składowe silnie spójne grafu (strongly connected components).2
T-W-4Algorytmy znajdowania powłoki wypukłej (ConvexHull) na płaszczyźnie. Wybrane przykłady algorytmów programowania dynamicznego i zachłannego.3
T-W-5Klasy 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

Formy aktywności - projekty

KODForma aktywnościGodziny
A-P-1Samodzielna implementacja i pomiary czasowe.30
30
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta

Formy aktywności - wykłady

KODForma aktywnościGodziny
A-W-1Uczestnictwo w wykładach.15
A-W-2Praca własna i przygotowanie się do zaliczenia końcowego.45
60
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta
PoleKODZnaczenie kodu
Zamierzone efekty uczenia sięSD_3-_SzDE03ITT_W01Student 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.
Odniesienie do efektów kształcenia dla dyscyplinySD_3_W01Posiada poszerzoną, podbudowaną teoretycznie wiedzę ogólną, związaną z reprezentowaną dziedziną i dyscypliną naukową oraz wiedzę szczegółową na bardziej zaawansowanym poziomie w zakresie prowadzonych badań naukowych.
Cel przedmiotuC-1Rozwinięcie umiejętności studentów w zakresie zaawansowanej analizy matematycznej algorytmów i struktur danych.
Treści programoweT-W-2Zaawansowane struktury danych: drzewa czerwono-czarne, Union-Find i dowód złożoności zamortyzowanej m log * n (logarytm iterowany).
T-W-5Klasy 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.
T-W-3Sortowanie topologiczne, DFS, BFS, składowe silnie spójne grafu (strongly connected components).
T-W-1Ró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.
T-W-4Algorytmy znajdowania powłoki wypukłej (ConvexHull) na płaszczyźnie. Wybrane przykłady algorytmów programowania dynamicznego i zachłannego.
Metody nauczaniaM-1Wykłady informacyjne i problemowe.
M-3Ocena za test końcowy (wiadomości z wykładu).
Sposób ocenyS-1Ocena podsumowująca: Ocena za program opracowywany na laboratorium i w domu.
Kryteria ocenyOcenaKryterium oceny
2,0
3,0Potrafi wyjaśnić podstawowy sens zadań algorytmów i struktury danych.
3,5
4,0
4,5
5,0
PoleKODZnaczenie kodu
Zamierzone efekty uczenia sięSD_3-_SzDE03ITT_U01Student potrafi wykonać implementację zaawansowanych algorytmów / struktur danych i przeprowadzić eksperyment porównawczy ich złożoności.
Odniesienie do efektów kształcenia dla dyscyplinySD_3_U01Potrafi określać problemy naukowe w zakresie reprezentowanej dziedziny i dyscypliny poprzez: definiowanie celu i przedmiotu badań, formułowanie hipotez badawczych, sądów analitycznych, syntetycznych i oceniających na temat proponowanych rozwiązań w odniesieniu do istniejącego stanu wiedzy, proponowanie metod, technik i narzędzi badawczych, służących do rozwiązania problemu badawczego.
Cel przedmiotuC-2Wykształ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 programoweT-P-1Implementacja w wybranym języku programownia: struktury Union-Find lub algorytmu "magiczne piątki". Pomiary czasowe i weryfikacja złożoności obliczeniowej.
Metody nauczaniaM-2Metody programowe z użyciem komputera.
Sposób ocenyS-1Ocena podsumowująca: Ocena za program opracowywany na laboratorium i w domu.
Kryteria ocenyOcenaKryterium oceny
2,0
3,0Student potrafi wykonać prostą implementację algorytmów / struktur danych i porównać ich złożoność.
3,5
4,0
4,5
5,0