Zachodniopomorski Uniwersytet Technologiczny w Szczecinie

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

Forma dydaktycznaKODSemestrGodzinyECTSWagaZaliczenie
wykładyW3 15 0,70,50zaliczenie
laboratoriaL3 5 0,30,50zaliczenie

Wymagania wstępne

KODWymaganie wstępne
W-1matematyka
W-2algorytmy i struktury danych
W-3podstawy programowania

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
laboratoria
T-L-1Samodzielna 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-1Ró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-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
laboratoria
A-L-1Praca na zajęciach.5
A-L-2Dokończenie implementacji w domu oraz badania / eksperymenty nad złożonością.25
30
wykłady
A-W-1Udział w wykładach.15
A-W-2Przygotowanie się do testu zaliczeniowego.15
30

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 kształcenia - wiedza

Zamierzone efekty kształceniaOdniesienie do efektów kształcenia dla dyscyplinyOdniesienie do efektów zdefiniowanych dla obszaru kształceniaCel przedmiotuTreści programoweMetody nauczaniaSposó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łceniaOdniesienie do efektów kształcenia dla dyscyplinyOdniesienie do efektów zdefiniowanych dla obszaru kształceniaCel przedmiotuTreści programoweMetody nauczaniaSposó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

  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 - laboratoria

KODTreść programowaGodziny
T-L-1Samodzielna 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

Treści programowe - wykłady

KODTreść programowaGodziny
T-W-1Ró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-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 - laboratoria

KODForma aktywnościGodziny
A-L-1Praca na zajęciach.5
A-L-2Dokończenie implementacji w domu oraz badania / eksperymenty nad złożonością.25
30
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta

Formy aktywności - wykłady

KODForma aktywnościGodziny
A-W-1Udział w wykładach.15
A-W-2Przygotowanie się do testu zaliczeniowego.15
30
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_3-_B/01/01_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 dyscyplinyI_3A_W01Absolwent posiada zaawansowaną wiedzę o charakterze podstawowym dla dziedziny Informatyka związana z obszarem prowadzonych badań naukowych obejmująca najnowsze osiągnięcia
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_3-_B/01/01_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 dyscyplinyI_3A_U01Absolwent posiada umiejętność prowadzenia badań naukowych w zakresie Informatyka z wykorzystaniem najnowszej wiedzy.