| Pole | KOD | Znaczenie kodu |
|---|
| Zamierzone efekty uczenia się | 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. |
|---|
| Odniesienie do efektów kształcenia dla kierunku studiów | I_1A_W01 | Ma 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_W02 | Ma zaawansowaną i uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu fundamentalnych obszarów informatyki. |
| I_1A_W04 | Ma wiedzę o stanie obecnym i kierunkach rozwoju kluczowych obszarów informatyki i wybranych aspektów dyscyplin z otoczenia informatyki. |
| I_1A_W05 | Ma 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. |
| Cel przedmiotu | C-1 | Zapoznanie z zasadami tworzenia złożonych struktur danych |
|---|
| C-2 | Zapoznanie z cechami konstrukcyjnymi najważniejszych struktur danych |
| C-3 | Zapoznanie z klasyfikacją i metodami oceny złożoności obliczeniowej |
| Treści programowe | T-W-10 | Szereg 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-11 | Klasy 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-2 | Wyszukiwanie 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-6 | Algorytmy 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-9 | Programowanie 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-7 | Minimalne 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-8 | Powł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-1 | Zaawansowane 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-3 | Drzewa 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-W-5 | Zaamortyzowana 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-W-4 | Tablice mieszające (tablice z haszowaniem), funkcje skrótu, kolizje, zastosowania. |
| 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-3 | Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: kopiec binarny. |
| T-A-4 | Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: tablica mieszająca. |
| 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-6 | Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: algorytm Kruskala + struktura Union-Find. |
| T-A-8 | Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: algorytm FFT. |
| T-A-7 | Ćwiczenia tablicowe na rzecz zadania laboratoryjnego: algorytm Grahama. |
| Metody nauczania | M-1 | Wykład informacyjno-konwersatoryjny |
|---|
| Sposób oceny | S-3 | Ocena podsumowująca: Egzamin pisemny |
|---|
| Kryteria oceny | Ocena | Kryterium oceny |
|---|
| 2,0 | |
| 3,0 | Uzyskanie wyniku w przedziale [50%, 60%) z egzaminu końcowego. |
| 3,5 | Uzyskanie wyniku w przedziale [60%, 70%) z egzaminu końcowego. |
| 4,0 | Uzyskanie wyniku w przedziale [70%, 80%) z egzaminu końcowego. |
| 4,5 | Uzyskanie wyniku w przedziale [80%, 90%) z egzaminu końcowego. |
| 5,0 | Uzyskanie wyniku w przedziale [90%, 100%] z egzaminu końcowego. |