Algorytmy i struktury danych

Informacje ogólne

Kod przedmiotu:	1000-213aASD
Kod Erasmus / ISCED:	11.302 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu:	Algorytmy i struktury danych
Jednostka:	Wydział Matematyki, Informatyki i Mechaniki
Grupy:
Punkty ECTS i inne:	(brak) Podstawowe informacje o zasadach przyporządkowania punktów ECTS: roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS; tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h; 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się; tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS; nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta. 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.