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
wykładyW3 30 3,00,40egzamin
laboratoriaL3 30 2,00,40zaliczenie
ćwiczenia audytoryjneA3 15 1,00,20zaliczenie

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
ćwiczenia audytoryjne
T-A-1Ćwiczenia tablicowe na rzecz zadań laboratoryjnych: lista z dowiązaniami, tablica dynamiczna.3
T-A-2Ćwiczenia tablicowe na rzecz zadań laboratoryjnych: drzewo BST, drzewo czerwono-czarne.3
T-A-3Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: kopiec binarny.1
T-A-4Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: tablica mieszająca.1
T-A-5Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: porównanie algorytmów sortujących (sortowanie przez kopcowanie vs sortowanie przez zliczanie vs sortowanie kubełkowe).2
T-A-6Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: algorytm Kruskala + struktura Union-Find.2
T-A-7Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: algorytm Grahama.1
T-A-8Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: algorytm FFT.2
15
laboratoria
T-L-1Implementacja struktury danych: lista z dowiązaniami dwukierunkowa.4
T-L-2Implementacja struktury danych: tablica dynamiczna.2
T-L-3Implementacja struktury danych: drzewo BST.2
T-L-4Implementacja struktury danych: drzewo czerwono-czarne.4
T-L-5Implementacja struktury danych: kopiec binarny.2
T-L-6Implementacja struktury danych: tablica mieszająca.2
T-L-7Implementacja i porównanie trzech algorytmów sortujących: sortowanie przecz kopcowanie vs przez zliczanie vs kubełkowe.4
T-L-8Implementacja algorytmu Kruskala wraz z pomocniczą strukturą Union-Find.4
T-L-9Implementacja algorytmu Grahama.3
T-L-10Implementacja algorytmów DFT i FFT.3
30
wykłady
T-W-1Zaawansowane liniowe struktury danych: tablice dynamiczne, kopce, listy z przeskokami. 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.2
T-W-4Tablice mieszające (tablice z haszowaniem), funkcje skrótu, kolizje, zastosowania.2
T-W-5Zaamortyzowana złożoność struktur danych. Analiza na przykładzie tablicy dynamicznej (operacja wstawiania). Przykłady złożoności zamortyzowanej w: kopcach, drzewach BST, strukturze Union-Find.1
T-W-6Algorytmy sortujące klasy n log n: sortowanie przez scalanie, sortowanie przez kopcowanie, sortowanie szybkie. Analiza złożoności obliczeniowej każdego z algorytmów (w szczególności: reorganizacji kopca top-down, bottom-up; przypadku średniego QuickSort - analiza permutacyjna). Zł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.4
T-W-7Minimalne drzewo rozpinające jako problem grafowy (przykłady rzeczywistych zastosowań). Algorytmy Kruskala i Prima. Dokładna analiza algorytmu Kruskala z wykorzystaniem struktury zbiorów rozłącznych: Union-Find. Analiza własności struktury Union-Find: łączenie według rang, kompresja ścieżki. Złożoność zamortyzowana operacji Find: logartym iterowany z n (wraz z dowodem).4
T-W-8Powłoka wypukła na płaszczyźnie (Convex Hull) jako problem z zakresu geometrii obliczeniowej. Iloczyn wektorowy - pomocnicze narzędzie do porównywania orientacji punktów oraz rozstrzygania kierunku "zakrętów" wektorów. Algorytm Graham Scan wraz z analizą złożoności obliczeniowej.1
T-W-9Programowanie dynamiczne (indukcja) jako podejście bottom-up do budowania algorytmów optymalizacyjnych. Przykłady problemów i alogrytmów: wydawanie reszty, odległość edycyjna (Levensteina), wszystkie najkrótsze ścieżki (all-pairs shotest paths) i algorytm Floyda-Warshalla.2
T-W-10Szereg 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-11Klasy 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 i przykłady redukcji.4
30

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

KODForma aktywnościGodziny
ćwiczenia audytoryjne
A-A-1Uczestnictwo w zajęciach i kolokwium zaliczeniowym.15
A-A-2Praca własna10
25
laboratoria
A-L-1Praca własna - samodzielna implementacja zadań laboratoryjnych (algorytmy, struktury danych).20
A-L-2Konsultowanie z prowadzącym częściowych implementacji podczas zajęć.10
A-L-3Zaliczenie u prowadzącego poszczególnych programów poprzez: osobiste przedstawienie kodu źródłowego, uruchomienie programu dla różnych nastaw, przedstawienie pomiarów czasowych, rozumienie algorytmu / struktury danych (umiejętność odpowiadania na pytania prowadzącego). Po otrzymaniu wstępnej oceny, przesłanie kodu do systemu antyplagiatowego.20
50
wykłady
A-W-1Udział w wykładach.30
A-W-2Praca własna41
A-W-3Udział w egzaminie2
A-W-4Konsultacje2
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
S-4Ocena podsumowująca: Kolokwium zaliczeniowe z ćwiczeń audytoryjnych

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
Itest_1A_C03.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_W02, I_1A_W05, I_1A_W04——C-1, C-2, C-3T-W-10, T-W-11, T-W-2, T-W-6, T-W-9, T-W-7, T-W-8, T-W-1, T-W-3, T-A-5, T-A-1, T-A-2, T-A-4, T-A-3, T-A-7, T-W-5, T-A-8, T-A-6, T-W-4M-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
Itest_1A_C03.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_U09, I_1A_U05——C-4T-L-10, T-L-4, T-L-8, T-L-3, T-L-5, T-L-9, T-L-1, T-L-2, T-L-6, T-L-7M-2S-1, S-2

Kryterium oceny - wiedza

Efekt uczenia sięOcenaKryterium oceny
Itest_1A_C03.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
Itest_1A_C03.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 - ćwiczenia audytoryjne

KODTreść programowaGodziny
T-A-1Ćwiczenia tablicowe na rzecz zadań laboratoryjnych: lista z dowiązaniami, tablica dynamiczna.3
T-A-2Ćwiczenia tablicowe na rzecz zadań laboratoryjnych: drzewo BST, drzewo czerwono-czarne.3
T-A-3Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: kopiec binarny.1
T-A-4Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: tablica mieszająca.1
T-A-5Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: porównanie algorytmów sortujących (sortowanie przez kopcowanie vs sortowanie przez zliczanie vs sortowanie kubełkowe).2
T-A-6Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: algorytm Kruskala + struktura Union-Find.2
T-A-7Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: algorytm Grahama.1
T-A-8Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: algorytm FFT.2
15

Treści programowe - laboratoria

KODTreść programowaGodziny
T-L-1Implementacja struktury danych: lista z dowiązaniami dwukierunkowa.4
T-L-2Implementacja struktury danych: tablica dynamiczna.2
T-L-3Implementacja struktury danych: drzewo BST.2
T-L-4Implementacja struktury danych: drzewo czerwono-czarne.4
T-L-5Implementacja struktury danych: kopiec binarny.2
T-L-6Implementacja struktury danych: tablica mieszająca.2
T-L-7Implementacja i porównanie trzech algorytmów sortujących: sortowanie przecz kopcowanie vs przez zliczanie vs kubełkowe.4
T-L-8Implementacja algorytmu Kruskala wraz z pomocniczą strukturą Union-Find.4
T-L-9Implementacja algorytmu Grahama.3
T-L-10Implementacja algorytmów DFT i FFT.3
30

Treści programowe - wykłady

KODTreść programowaGodziny
T-W-1Zaawansowane liniowe struktury danych: tablice dynamiczne, kopce, listy z przeskokami. 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.2
T-W-4Tablice mieszające (tablice z haszowaniem), funkcje skrótu, kolizje, zastosowania.2
T-W-5Zaamortyzowana złożoność struktur danych. Analiza na przykładzie tablicy dynamicznej (operacja wstawiania). Przykłady złożoności zamortyzowanej w: kopcach, drzewach BST, strukturze Union-Find.1
T-W-6Algorytmy sortujące klasy n log n: sortowanie przez scalanie, sortowanie przez kopcowanie, sortowanie szybkie. Analiza złożoności obliczeniowej każdego z algorytmów (w szczególności: reorganizacji kopca top-down, bottom-up; przypadku średniego QuickSort - analiza permutacyjna). Zł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.4
T-W-7Minimalne drzewo rozpinające jako problem grafowy (przykłady rzeczywistych zastosowań). Algorytmy Kruskala i Prima. Dokładna analiza algorytmu Kruskala z wykorzystaniem struktury zbiorów rozłącznych: Union-Find. Analiza własności struktury Union-Find: łączenie według rang, kompresja ścieżki. Złożoność zamortyzowana operacji Find: logartym iterowany z n (wraz z dowodem).4
T-W-8Powłoka wypukła na płaszczyźnie (Convex Hull) jako problem z zakresu geometrii obliczeniowej. Iloczyn wektorowy - pomocnicze narzędzie do porównywania orientacji punktów oraz rozstrzygania kierunku "zakrętów" wektorów. Algorytm Graham Scan wraz z analizą złożoności obliczeniowej.1
T-W-9Programowanie dynamiczne (indukcja) jako podejście bottom-up do budowania algorytmów optymalizacyjnych. Przykłady problemów i alogrytmów: wydawanie reszty, odległość edycyjna (Levensteina), wszystkie najkrótsze ścieżki (all-pairs shotest paths) i algorytm Floyda-Warshalla.2
T-W-10Szereg 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-11Klasy 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 i przykłady redukcji.4
30

Formy aktywności - ćwiczenia audytoryjne

KODForma aktywnościGodziny
A-A-1Uczestnictwo w zajęciach i kolokwium zaliczeniowym.15
A-A-2Praca własna10
25
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta

Formy aktywności - laboratoria

KODForma aktywnościGodziny
A-L-1Praca własna - samodzielna implementacja zadań laboratoryjnych (algorytmy, struktury danych).20
A-L-2Konsultowanie z prowadzącym częściowych implementacji podczas zajęć.10
A-L-3Zaliczenie u prowadzącego poszczególnych programów poprzez: osobiste przedstawienie kodu źródłowego, uruchomienie programu dla różnych nastaw, przedstawienie pomiarów czasowych, rozumienie algorytmu / struktury danych (umiejętność odpowiadania na pytania prowadzącego). Po otrzymaniu wstępnej oceny, przesłanie kodu do systemu antyplagiatowego.20
50
(*) 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-2Praca własna41
A-W-3Udział w egzaminie2
A-W-4Konsultacje2
75
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta
PoleKODZnaczenie kodu
Zamierzone efekty uczenia sięItest_1A_C03.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_W01Ma 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_W02Ma zaawansowaną i uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu fundamentalnych obszarów informatyki.
I_1A_W05Ma wiedzę o nowoczesnych metodach projektowania, analizowania, wytwarzania, testowania oprogramowania oraz rozwiązywania wybranych zadań inżynierskich obejmujących w szczególności narzędzia wspomagające wytwarzanie oprogramowania na różnych etapach powstawania, eksploatacji i rozwoju systemów informatycznych.
I_1A_W04Ma wiedzę o stanie obecnym i kierunkach rozwoju kluczowych obszarów informatyki i wybranych aspektów dyscyplin z otoczenia 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-10Szereg 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-11Klasy 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 i przykłady redukcji.
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-6Algorytmy sortujące klasy n log n: sortowanie przez scalanie, sortowanie przez kopcowanie, sortowanie szybkie. Analiza złożoności obliczeniowej każdego z algorytmów (w szczególności: reorganizacji kopca top-down, bottom-up; przypadku średniego QuickSort - analiza permutacyjna). Zł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.
T-W-9Programowanie dynamiczne (indukcja) jako podejście bottom-up do budowania algorytmów optymalizacyjnych. Przykłady problemów i alogrytmów: wydawanie reszty, odległość edycyjna (Levensteina), wszystkie najkrótsze ścieżki (all-pairs shotest paths) i algorytm Floyda-Warshalla.
T-W-7Minimalne drzewo rozpinające jako problem grafowy (przykłady rzeczywistych zastosowań). Algorytmy Kruskala i Prima. Dokładna analiza algorytmu Kruskala z wykorzystaniem struktury zbiorów rozłącznych: Union-Find. Analiza własności struktury Union-Find: łączenie według rang, kompresja ścieżki. Złożoność zamortyzowana operacji Find: logartym iterowany z n (wraz z dowodem).
T-W-8Powłoka wypukła na płaszczyźnie (Convex Hull) jako problem z zakresu geometrii obliczeniowej. Iloczyn wektorowy - pomocnicze narzędzie do porównywania orientacji punktów oraz rozstrzygania kierunku "zakrętów" wektorów. Algorytm Graham Scan wraz z analizą złożoności obliczeniowej.
T-W-1Zaawansowane liniowe struktury danych: tablice dynamiczne, kopce, listy z przeskokami. 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.
T-A-5Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: porównanie algorytmów sortujących (sortowanie przez kopcowanie vs sortowanie przez zliczanie vs sortowanie kubełkowe).
T-A-1Ćwiczenia tablicowe na rzecz zadań laboratoryjnych: lista z dowiązaniami, tablica dynamiczna.
T-A-2Ćwiczenia tablicowe na rzecz zadań laboratoryjnych: drzewo BST, drzewo czerwono-czarne.
T-A-4Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: tablica mieszająca.
T-A-3Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: kopiec binarny.
T-A-7Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: algorytm Grahama.
T-W-5Zaamortyzowana złożoność struktur danych. Analiza na przykładzie tablicy dynamicznej (operacja wstawiania). Przykłady złożoności zamortyzowanej w: kopcach, drzewach BST, strukturze Union-Find.
T-A-8Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: algorytm FFT.
T-A-6Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: algorytm Kruskala + struktura Union-Find.
T-W-4Tablice mieszające (tablice z haszowaniem), funkcje skrótu, kolizje, zastosowania.
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ęItest_1A_C03.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_U09Potrafi dobrać właściwe metody i narzędzia do rozwiązywania wybranych zadań informatycznych w warunkach nie w pełni przewidywalnych.
I_1A_U05Potrafi zaplanować i zrealizować eksperymenty w zakresie oceny wydajności, złożoności, efektywności systemów informatycznych i ich składowych.
Cel przedmiotuC-4Nabycie umiejętności wyboru struktur danych odpowiednich dla problemu algorytmicznego i środowiska implementacyjnego
Treści programoweT-L-10Implementacja algorytmów DFT i FFT.
T-L-4Implementacja struktury danych: drzewo czerwono-czarne.
T-L-8Implementacja algorytmu Kruskala wraz z pomocniczą strukturą Union-Find.
T-L-3Implementacja struktury danych: drzewo BST.
T-L-5Implementacja struktury danych: kopiec binarny.
T-L-9Implementacja algorytmu Grahama.
T-L-1Implementacja struktury danych: lista z dowiązaniami dwukierunkowa.
T-L-2Implementacja struktury danych: tablica dynamiczna.
T-L-6Implementacja struktury danych: tablica mieszająca.
T-L-7Implementacja i porównanie trzech algorytmów sortujących: sortowanie przecz kopcowanie vs przez zliczanie vs kubełkowe.
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.