| 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: |
Krzaczkowski Jacek, dr |
| Forma zajęć: |
wykład |
| Rodzaj zaliczenia: |
egzamin |
| Punkty ECTS: |
5,0 |
| Godzinowe ekwiwalenty punktów ECTS (łączna liczba godzin w semestrze): |
| 0 |
Godziny kontaktowe z prowadzącym zajęcia realizowane w formie konsultacji |
| 30,0 |
Godziny kontaktowe z prowadzącym zajęcia realizowane w formie zajęć dydaktycznych |
| 0 |
Przygotowanie się studenta do zajęć dydaktycznych |
| 0 |
Przygotowanie się studenta do zaliczeń i/lub egzaminów |
| 0 |
Studiowanie przez studenta literatury przedmiotu |
|
| Poziom trudności: |
średnio zaawansowany
|
| Wstępne wymagania: |
Znajomość podstaw algorytmiki i struktur danych. |
| Metody dydaktyczne: |
- dyskusja dydaktyczna
- e-learning
- konsultacje
- wykład informacyjny
- wykład konwersatoryjny
|
| 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: |
- ćwiczenia praktyczne/laboratoryjne
- egzamin pisemny
|
| 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.
|
