| Przedmiot: |
Algorytmy i struktury danych II |
| Kierunek: |
Informatyka, I stopień [6 sem], stacjonarny, ogólnoakademicki, rozpoczęty w: 2012 |
| Rok/Semestr: |
II/4
|
| Liczba godzin: |
30,0 |
| Nauczyciel: |
Pańczyk Michał, dr |
| Forma zajęć: |
laboratorium |
| Rodzaj zaliczenia: |
zaliczenie na ocenę |
| Poziom trudności: |
średnio zaawansowany
|
| Wstępne wymagania: |
-
Znajomość podstaw algorytmiki i struktur danych.
-
Umiejętność programowania w języku C++.
|
| Metody dydaktyczne: |
- ćwiczenia laboratoryjne
- dyskusja dydaktyczna
- e-learning
- konsultacje
- warsztaty grupowe
- z użyciem komputera
|
| Zakres tematów: |
-
Słowniki, Drzewa BST
-
Drzewa AVL
-
B-drzewa
-
Drzewa poszukiwań cyfrowych
-
Tablice haszujące.
-
Algorytmy selekcji (algorytm Hore'a, algorytm ,,magiczne piątki'').
-
Algorytmy tekstowe (KMP,KMR,KR).
-
Algorytmy geometryczne (metoda miotły, wypukła otoczka).
-
Najkrótsza ścieżka w grafie (algorytm Dijkstry, algorytm Forda-Bellmana, Algortym Floyda).
-
Minimalne drzewo rozpinające (algorytm Prima, algorytm Kruskala).
-
Algorytmy probabilistyczne.
-
P,NP,NP-zupełność.
|
| Forma oceniania: |
- końcowe zaliczenie ustne
- ocena ciągła (bieżące przygotowanie do zajęć i aktywność)
- zaliczenie praktyczne
|
| Literatura: |
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, ,,Wprowadzenie do algorytmów'', WNT, Warszawa 2004
-
Donald E. Knuth, ,,Sztuka programowania t. 1-3'', WNT, Warszawa 2002
-
C.H. Papadimitriou, ,,Złożoność obliczeniowa'',WNT, Warszawa 2002.
|
