Zachodniopomorski Uniwersytet Technologiczny w Szczecinie

Wydział Informatyki - Informatyka (S1)

Sylabus przedmiotu Algorytmy 2:

Informacje podstawowe

Kierunek studiów Informatyka
Forma studiów studia stacjonarne Poziom pierwszego stopnia
Tytuł zawodowy absolwenta inżynier
Obszary studiów charakterystyki PRK, kompetencje inżynierskie PRK
Profil ogólnoakademicki
Moduł
Przedmiot Algorytmy 2
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 Włodzimierz Chocianowicz <Wlodzimierz.Chocianowicz@zut.edu.pl>, Tomasz Hyla <Tomasz.Hyla@zut.edu.pl>, Witold Maćków <Witold.Mackow@zut.edu.pl>, Jerzy Pejaś <Jerzy.Pejas@zut.edu.pl>
ECTS (planowane) 6,0 ECTS (formy) 6,0
Forma zaliczenia egzamin Język polski
Blok obieralny Grupa obieralna

Formy dydaktyczne

Forma dydaktycznaKODSemestrGodzinyECTSWagaZaliczenie
laboratoriaL3 30 3,00,50zaliczenie
wykładyW3 30 3,00,50egzamin

Wymagania wstępne

KODWymaganie wstępne
W-1Algorytmy 1
W-2Matematyka dyskretna
W-3Programowanie 2

Cele przedmiotu

KODCel modułu/przedmiotu
C-1Zapoznanie z zasadami tworzenia złożonych struktur danych
C-2Zapoznanie z cechami konstrukcyjnymi najważniejszych struktur danych
C-3Zapoznanie z klasyfikacją i metodami oceny złożoności obliczeniowej
C-4Nabycie umiejętności wyboru struktur danych odpowiednich dla problemu algorytmicznego i środowiska implementacyjnego

Treści programowe z podziałem na formy zajęć

KODTreść programowaGodziny
laboratoria
T-L-1Implementacja liniowych struktur danych: tablica dynamiczna, kopiec binarny, tablica mieszająca.6
T-L-2Implementacje i porównania czasowe algorytmów sortujących - po jednym wybranym algorytmi dla każdej z klas: kwadratowe, n log n, liniowe (przez zliczanie).4
T-L-3Implementacja wybranych elementów (operacji) drzewa czerwono-czarnego.8
T-L-4Implementacja struktury Union-Find. Porównanie czasu pracy bez i z kompresją ścieżki.4
T-L-5Implementacja algorytmu Graham scan (znajdowanie powłoki wypukłej).4
T-L-6Implementacja dwóch algorytmów programowania dynamicznego: odległość edycyjna, łańcuchowe mnożenie macierzy.4
30
wykłady
T-W-1Zaawansowane liniowe struktury danych: tablice dynamiczne, kopce, listy z przeskokami. Zaamortyzowana złożoność stała wstawiania do tablicy dynamicznej. Kopiec zupełny binarny - reprezentacja, indeksowanie, wstawianie i usuwanie (złożoność logarytmiczna). Kopiec dwumianowy i Fibonacciego. Sortowanie przez kopcowanie.3
T-W-2Wyszukiwanie i struktury danych. Drzewa wyszukiwań binarnych - BST. Zagadanienie równoważenia drzew. Drzewa wielokierunkowe: B-drzewa i warianty (B+, B*), R-drzewa, kd-drzewa.4
T-W-3Drzewa czerwono-czarne. Ogólna konstrukcja i własności. Dowód złożoności logartymicznej przy zachowaniu tej konstrukcji. Operacje: dodawanie, usuwanie, rotacje.5
T-W-4Grafy - najkrótsze ścieżki dla wszystkich par wierzchołków. Algorytm Floyda-Warshalla. Zachowanie algorytmu dla ujemnych cykli. Porównanie do innych algorytmów najkrótszych ścieżek.2
T-W-5Struktura zbiorów rozłącznych: Union-Find. Łączenie według rang, kompresja ścieżki. Złożoność zamortyzowana: logartym iterowany z n (wraz z dowodem).2
T-W-6Wybrane algorytmy geometryczne. Przecinanie się odcinków. Powłoka wypukła (Graham scan, agorytm Jarvisa). Związek znajdowania powłoki wypukłej z sortowaniem.2
T-W-7Algorytmy programowania dynamicznego: odległość edycyjna (Levensteina), algorytm Floyda-Warshalla.2
T-W-8Złożoność rzędu n log n jako dolne ograniczenie dla algorytmów sortujących przez porównania - dowód. Sortowanie w czasie liniowym: counting sort, bucket sort, radix sort. Tablice mieszające (tablice z haszowaniem), funkcje skrótu, kolizje, zastosowania.3
T-W-9Szereg Fouriera i szybka transformata Fouriera (FFT) jako przykład podejścia "dziel i zwyciężaj". Funkcje ortogonalne, iloczyn skalarny, twierdzenie o przybliżaniu w normie kwadratowej. Dyskretna transformata Fouriera (DFT) i szybka transformata (FFT). Algorytm Cooleya-Tukeya - złożoność O(n log n). Inne algorytmy FFT.3
T-W-10Klasy problemów: P, NP, NP-zupełne, NP-trudne. Niedeterministyczna maszyna Turinga. Problemy: cykl Hamiltona, klika, spełnialność formuł logicznych, trójkolorowalność grafu. Podstawowe informacje o redukcjach.4
30

Obciążenie pracą studenta - formy aktywności

KODForma aktywnościGodziny
laboratoria
A-L-1Implementacja algorytmów obsługujących struktury danych podczas zajęć laboratoryjnych - udział w zajęciach dydaktycznych30
A-L-2Przygotowanie do rozwiązania wskazanych problemów implementacyjnych28
A-L-3Optymalizacja rozwiązań uzyskanych podczas zajęć laboratoryjnych15
A-L-4Konsultacje2
75
wykłady
A-W-1Udział w wykładach.30
A-W-2Analiza i rozwiązywanie problemów rozszerzających materiał wykładowy (praca własna).25
A-W-3Przygotowanie się do egzaminu.16
A-W-4Udział w egzaminie2
A-W-5Konsultacje2
75

Metody nauczania / narzędzia dydaktyczne

KODMetoda nauczania / narzędzie dydaktyczne
M-1Wykład informacyjno-konwersatoryjny
M-2Ćwiczenia laboratoryjne

Sposoby oceny

KODSposób oceny
S-1Ocena formująca: Sprawdzian przygotowania do zajęć laboratoryjnych
S-2Ocena formująca: Ocena wykonania poszczególnych implementacji
S-3Ocena podsumowująca: Egzamin pisemny

Zamierzone efekty uczenia się - wiedza

Zamierzone efekty uczenia sięOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów uczenia się prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposób oceny
I_1A_C04.2_W01
Student zna zasady tworzenia złożonych typów danych i algorytmy manipulujące określonymi strukturami danych oraz sposoby oceny ich złożoności obliczeniowej.
I_1A_W01, I_1A_W02C-1, C-2, C-3T-W-9, T-W-10, T-W-2, T-W-8, T-W-7, T-W-4, T-W-5, T-W-6, T-W-1, T-W-3M-1S-3

Zamierzone efekty uczenia się - umiejętności

Zamierzone efekty uczenia sięOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów uczenia się prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposób oceny
I_1A_C04.2_U01
Student ma świadomość barier obliczeniowych związanych ze złożonością problemów obliczeniowych i umie dokonać właściwego wyboru struktur danych odpowiednich dla problemu algorytmicznego.
I_1A_U06C-4T-L-2, T-L-4, T-L-6, T-L-1, T-L-3, T-L-5M-2S-1, S-2

Kryterium oceny - wiedza

Efekt uczenia sięOcenaKryterium oceny
I_1A_C04.2_W01
Student zna zasady tworzenia złożonych typów danych i algorytmy manipulujące określonymi strukturami danych oraz sposoby oceny ich złożoności obliczeniowej.
2,0
3,0Uzyskanie wyniku w przedziale [50%, 60%) z egzaminu końcowego.
3,5Uzyskanie wyniku w przedziale [60%, 70%) z egzaminu końcowego.
4,0Uzyskanie wyniku w przedziale [70%, 80%) z egzaminu końcowego.
4,5Uzyskanie wyniku w przedziale [80%, 90%) z egzaminu końcowego.
5,0Uzyskanie wyniku w przedziale [90%, 100%] z egzaminu końcowego.

Kryterium oceny - umiejętności

Efekt uczenia sięOcenaKryterium oceny
I_1A_C04.2_U01
Student ma świadomość barier obliczeniowych związanych ze złożonością problemów obliczeniowych i umie dokonać właściwego wyboru struktur danych odpowiednich dla problemu algorytmicznego.
2,0
3,0Uzyskanie wyniku w przedziale [50%, 60%) za programy i sprawdziany realizowane na zajęciach laboratoryjnych.
3,5Uzyskanie wyniku w przedziale [60%, 70%) za programy i sprawdziany realizowane na zajęciach laboratoryjnych.
4,0Uzyskanie wyniku w przedziale [70%, 80%) za programy i sprawdziany realizowane na zajęciach laboratoryjnych.
4,5Uzyskanie wyniku w przedziale [80%, 90%) za programy i sprawdziany realizowane na zajęciach laboratoryjnych.
5,0Uzyskanie wyniku w przedziale [90%, 100%] za programy i sprawdziany realizowane na zajęciach laboratoryjnych.

Literatura podstawowa

  1. T.H. Cormen, Ch.E.Leiserson, R.I.Rivest, C.Stein, Wprowadzenia do algorytmów, WNT, Warszawa, 2002
  2. M.Sipser, Wprowadzenie do teorii obliczeń, WNT, Warszawa, 2009
  3. T. H. Cormen, Algorytmy bez tajemnic, Helin, 2013
  4. D. E. Knuth, Sztuka programowania, WNT, 2002

Literatura dodatkowa

  1. D.Harel, Rzecz o istocie informatyki - algorytmika, WNT, Warszawa, 2000
  2. N.Wirth, Algorytmy + struktury danych = programy, WNT, Warszawa, 2001
  3. A.V.Aho, J.E.Hopcroft, J.D.Ullman, Algorytmy i struktury danych, Helion, Gliwice, 2003
  4. R.L. Graham, D.E. Knuth, O. Patashnik, Matematyka konkretna, PWN, 2018

Treści programowe - laboratoria

KODTreść programowaGodziny
T-L-1Implementacja liniowych struktur danych: tablica dynamiczna, kopiec binarny, tablica mieszająca.6
T-L-2Implementacje i porównania czasowe algorytmów sortujących - po jednym wybranym algorytmi dla każdej z klas: kwadratowe, n log n, liniowe (przez zliczanie).4
T-L-3Implementacja wybranych elementów (operacji) drzewa czerwono-czarnego.8
T-L-4Implementacja struktury Union-Find. Porównanie czasu pracy bez i z kompresją ścieżki.4
T-L-5Implementacja algorytmu Graham scan (znajdowanie powłoki wypukłej).4
T-L-6Implementacja dwóch algorytmów programowania dynamicznego: odległość edycyjna, łańcuchowe mnożenie macierzy.4
30

Treści programowe - wykłady

KODTreść programowaGodziny
T-W-1Zaawansowane liniowe struktury danych: tablice dynamiczne, kopce, listy z przeskokami. Zaamortyzowana złożoność stała wstawiania do tablicy dynamicznej. Kopiec zupełny binarny - reprezentacja, indeksowanie, wstawianie i usuwanie (złożoność logarytmiczna). Kopiec dwumianowy i Fibonacciego. Sortowanie przez kopcowanie.3
T-W-2Wyszukiwanie i struktury danych. Drzewa wyszukiwań binarnych - BST. Zagadanienie równoważenia drzew. Drzewa wielokierunkowe: B-drzewa i warianty (B+, B*), R-drzewa, kd-drzewa.4
T-W-3Drzewa czerwono-czarne. Ogólna konstrukcja i własności. Dowód złożoności logartymicznej przy zachowaniu tej konstrukcji. Operacje: dodawanie, usuwanie, rotacje.5
T-W-4Grafy - najkrótsze ścieżki dla wszystkich par wierzchołków. Algorytm Floyda-Warshalla. Zachowanie algorytmu dla ujemnych cykli. Porównanie do innych algorytmów najkrótszych ścieżek.2
T-W-5Struktura zbiorów rozłącznych: Union-Find. Łączenie według rang, kompresja ścieżki. Złożoność zamortyzowana: logartym iterowany z n (wraz z dowodem).2
T-W-6Wybrane algorytmy geometryczne. Przecinanie się odcinków. Powłoka wypukła (Graham scan, agorytm Jarvisa). Związek znajdowania powłoki wypukłej z sortowaniem.2
T-W-7Algorytmy programowania dynamicznego: odległość edycyjna (Levensteina), algorytm Floyda-Warshalla.2
T-W-8Złożoność rzędu n log n jako dolne ograniczenie dla algorytmów sortujących przez porównania - dowód. Sortowanie w czasie liniowym: counting sort, bucket sort, radix sort. Tablice mieszające (tablice z haszowaniem), funkcje skrótu, kolizje, zastosowania.3
T-W-9Szereg Fouriera i szybka transformata Fouriera (FFT) jako przykład podejścia "dziel i zwyciężaj". Funkcje ortogonalne, iloczyn skalarny, twierdzenie o przybliżaniu w normie kwadratowej. Dyskretna transformata Fouriera (DFT) i szybka transformata (FFT). Algorytm Cooleya-Tukeya - złożoność O(n log n). Inne algorytmy FFT.3
T-W-10Klasy problemów: P, NP, NP-zupełne, NP-trudne. Niedeterministyczna maszyna Turinga. Problemy: cykl Hamiltona, klika, spełnialność formuł logicznych, trójkolorowalność grafu. Podstawowe informacje o redukcjach.4
30

Formy aktywności - laboratoria

KODForma aktywnościGodziny
A-L-1Implementacja algorytmów obsługujących struktury danych podczas zajęć laboratoryjnych - udział w zajęciach dydaktycznych30
A-L-2Przygotowanie do rozwiązania wskazanych problemów implementacyjnych28
A-L-3Optymalizacja rozwiązań uzyskanych podczas zajęć laboratoryjnych15
A-L-4Konsultacje2
75
(*) 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.30
A-W-2Analiza i rozwiązywanie problemów rozszerzających materiał wykładowy (praca własna).25
A-W-3Przygotowanie się do egzaminu.16
A-W-4Udział w egzaminie2
A-W-5Konsultacje2
75
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta
PoleKODZnaczenie kodu
Zamierzone efekty uczenia sięI_1A_C04.2_W01Student zna zasady tworzenia złożonych typów danych i algorytmy manipulujące określonymi strukturami danych oraz sposoby oceny ich złożoności obliczeniowej.
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_W01Posiada poszerzoną wiedzę w zakresie matematyki stosowanej i obliczeniowej oraz fizyki, niezbędną do formułowania i rozwiązywania problemów w informatyce i dyscyplinach pokrewnych.
I_1A_W02Posiada wiedzę w zakresie projektowania, analizy i implementacji algorytmów, struktur danych oraz konstrukcji programistycznych, zna podstawowe problemy algorytmiczne występujące w obszarze informatyki.
Cel przedmiotuC-1Zapoznanie z zasadami tworzenia złożonych struktur danych
C-2Zapoznanie z cechami konstrukcyjnymi najważniejszych struktur danych
C-3Zapoznanie z klasyfikacją i metodami oceny złożoności obliczeniowej
Treści programoweT-W-9Szereg Fouriera i szybka transformata Fouriera (FFT) jako przykład podejścia "dziel i zwyciężaj". Funkcje ortogonalne, iloczyn skalarny, twierdzenie o przybliżaniu w normie kwadratowej. Dyskretna transformata Fouriera (DFT) i szybka transformata (FFT). Algorytm Cooleya-Tukeya - złożoność O(n log n). Inne algorytmy FFT.
T-W-10Klasy problemów: P, NP, NP-zupełne, NP-trudne. Niedeterministyczna maszyna Turinga. Problemy: cykl Hamiltona, klika, spełnialność formuł logicznych, trójkolorowalność grafu. Podstawowe informacje o redukcjach.
T-W-2Wyszukiwanie i struktury danych. Drzewa wyszukiwań binarnych - BST. Zagadanienie równoważenia drzew. Drzewa wielokierunkowe: B-drzewa i warianty (B+, B*), R-drzewa, kd-drzewa.
T-W-8Złożoność rzędu n log n jako dolne ograniczenie dla algorytmów sortujących przez porównania - dowód. Sortowanie w czasie liniowym: counting sort, bucket sort, radix sort. Tablice mieszające (tablice z haszowaniem), funkcje skrótu, kolizje, zastosowania.
T-W-7Algorytmy programowania dynamicznego: odległość edycyjna (Levensteina), algorytm Floyda-Warshalla.
T-W-4Grafy - najkrótsze ścieżki dla wszystkich par wierzchołków. Algorytm Floyda-Warshalla. Zachowanie algorytmu dla ujemnych cykli. Porównanie do innych algorytmów najkrótszych ścieżek.
T-W-5Struktura zbiorów rozłącznych: Union-Find. Łączenie według rang, kompresja ścieżki. Złożoność zamortyzowana: logartym iterowany z n (wraz z dowodem).
T-W-6Wybrane algorytmy geometryczne. Przecinanie się odcinków. Powłoka wypukła (Graham scan, agorytm Jarvisa). Związek znajdowania powłoki wypukłej z sortowaniem.
T-W-1Zaawansowane liniowe struktury danych: tablice dynamiczne, kopce, listy z przeskokami. Zaamortyzowana złożoność stała wstawiania do tablicy dynamicznej. Kopiec zupełny binarny - reprezentacja, indeksowanie, wstawianie i usuwanie (złożoność logarytmiczna). Kopiec dwumianowy i Fibonacciego. Sortowanie przez kopcowanie.
T-W-3Drzewa czerwono-czarne. Ogólna konstrukcja i własności. Dowód złożoności logartymicznej przy zachowaniu tej konstrukcji. Operacje: dodawanie, usuwanie, rotacje.
Metody nauczaniaM-1Wykład informacyjno-konwersatoryjny
Sposób ocenyS-3Ocena podsumowująca: Egzamin pisemny
Kryteria ocenyOcenaKryterium oceny
2,0
3,0Uzyskanie wyniku w przedziale [50%, 60%) z egzaminu końcowego.
3,5Uzyskanie wyniku w przedziale [60%, 70%) z egzaminu końcowego.
4,0Uzyskanie wyniku w przedziale [70%, 80%) z egzaminu końcowego.
4,5Uzyskanie wyniku w przedziale [80%, 90%) z egzaminu końcowego.
5,0Uzyskanie wyniku w przedziale [90%, 100%] z egzaminu końcowego.
PoleKODZnaczenie kodu
Zamierzone efekty uczenia sięI_1A_C04.2_U01Student ma świadomość barier obliczeniowych związanych ze złożonością problemów obliczeniowych i umie dokonać właściwego wyboru struktur danych odpowiednich dla problemu algorytmicznego.
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_U06Potrafi rozwiązywać podstawowe problemy algorytmiczne z uwzględnieniem ich złożoności posługując się kluczowymi językami programowania.
Cel przedmiotuC-4Nabycie umiejętności wyboru struktur danych odpowiednich dla problemu algorytmicznego i środowiska implementacyjnego
Treści programoweT-L-2Implementacje i porównania czasowe algorytmów sortujących - po jednym wybranym algorytmi dla każdej z klas: kwadratowe, n log n, liniowe (przez zliczanie).
T-L-4Implementacja struktury Union-Find. Porównanie czasu pracy bez i z kompresją ścieżki.
T-L-6Implementacja dwóch algorytmów programowania dynamicznego: odległość edycyjna, łańcuchowe mnożenie macierzy.
T-L-1Implementacja liniowych struktur danych: tablica dynamiczna, kopiec binarny, tablica mieszająca.
T-L-3Implementacja wybranych elementów (operacji) drzewa czerwono-czarnego.
T-L-5Implementacja algorytmu Graham scan (znajdowanie powłoki wypukłej).
Metody nauczaniaM-2Ćwiczenia laboratoryjne
Sposób ocenyS-1Ocena formująca: Sprawdzian przygotowania do zajęć laboratoryjnych
S-2Ocena formująca: Ocena wykonania poszczególnych implementacji
Kryteria ocenyOcenaKryterium oceny
2,0
3,0Uzyskanie wyniku w przedziale [50%, 60%) za programy i sprawdziany realizowane na zajęciach laboratoryjnych.
3,5Uzyskanie wyniku w przedziale [60%, 70%) za programy i sprawdziany realizowane na zajęciach laboratoryjnych.
4,0Uzyskanie wyniku w przedziale [70%, 80%) za programy i sprawdziany realizowane na zajęciach laboratoryjnych.
4,5Uzyskanie wyniku w przedziale [80%, 90%) za programy i sprawdziany realizowane na zajęciach laboratoryjnych.
5,0Uzyskanie wyniku w przedziale [90%, 100%] za programy i sprawdziany realizowane na zajęciach laboratoryjnych.