Serwisy internetowe Uniwersytetu Warszawskiego | USOSownia - uniwersyteckie forum USOSoweNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Algorytmy i struktury danych

Informacje ogólne

Kod przedmiotu: 1000-213aASD Kod Erasmus / ISCED: 11.302 / (0612) Database and network design and administration
Nazwa przedmiotu: Algorytmy i struktury danych
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy:
Punkty ECTS i inne: (brak)
zobacz reguły punktacji
Język prowadzenia: polski
Rodzaj przedmiotu:

obowiązkowe

Założenia (lista przedmiotów):

Elementy matematyki dyskretnej I 1000-211aMD1
Elementy matematyki dyskretnej II 1000-212aMD2
Metody programowania (podejście imperatywne) 1000-212aMPRI
Wstęp do programowania (podejście imperatywne) 1000-211aWPI

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

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.