Algorytmy i struktury danych
Informacje ogólne
Kod przedmiotu: | 1000-213aASD | Kod Erasmus / ISCED: |
11.302
![]() ![]() |
Nazwa przedmiotu: | Algorytmy i struktury danych | ||
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki | ||
Grupy: | |||
Punkty ECTS i inne: |
(brak)
![]() ![]() |
||
Język prowadzenia: | polski | ||
Rodzaj przedmiotu: | obowiązkowe |
||
Założenia (lista przedmiotów): | Elementy matematyki dyskretnej I 1000-211aMD1 |
||
Skrócony opis: |
Koszt algorytmu (pesymistyczny, oczekiwany, zamortyzowany). Sortowanie. Selekcja. Kolejki priorytetowe. Wyszukiwanie. Drzewa wyszukiwań binarnych. Haszowanie. Wyszukiwanie pozycyjne. B-drzewa. Podstawowe algorytmy grafowe. |
||
Pełny opis: |
1. Metody projektowania algorytmów: dziel i zwyciężaj, programowanie dynamiczne, algorytmy zachłanne, nawracanie, algorytmy randomizacyjne. 2. Analiza algorytmów: modele obliczeń (RAM - maszyna o dostepie swobodnym, drzewa decyzyjne), złożoność czasowa i pamięciowa, złożoność pesymistyczna i oczekiwana, analiza kosztu zamortyzowanego, analiza probalistyczna, dolne ograniczenia (złożonośc problemu a złożoność algorytmu). 3. Sortowanie i wybieranie: sortowanie za pomocą porównań (sortowanie przez wstawianie, sortowanie szybkie, sortowanie stogowe, sortowanie przez scalanie), dolne ograniczenia złożoności sortowania, algorytmy wyboru (algorytm Hoare'a i magisznych piątek), srotowanie pozycyjne i leksykograficzne, sortowanie zewnętrzne, kolejki priorytetowe (kopce binarne, dwumienne i Fibonacciego). 4. Wyszukiwanie: wyszukiwanie binarne, słowniki, drzewa wyszukiwań binarnych, drzewa zrównoważone, (drzewa AVL, drzewa czerwono-czarne), wyszukiwanie zewnętrzne, haszowanie, wyszukiwanie pozycyjne. 5. Problem Find-Union: definicja, struktury danych, koszt zamortyzowany, zastosowania. |
||
Literatura: |
1. Algorytmy i struktury danych, L. Banachowski, K. Diks, W. Rytter, WNT 1996, 2001 2. Wprowadzenie do algorytmów, T.H. Cormen, C. E. Leiserson, R.L. Rivest, WNT 1998 |
| |||||
Właścicielem praw autorskich jest Uniwersytet Warszawski.