Algorytmy i struktury danych

Algorithms and data structures

2018Z

Kod przedmiotu2317S1-ALISTD
Punkty ECTS 4,5
Typ zajęć Wykład
Ćwiczenia laboratoryjne
Przedmioty wprowadzającewstęp do programowania, programowanie strukturalne, matematyka dyskretna, analiza matematyczna, algebra liniowa
Wymagania wstępneznajomość podstawowych pojęć matematycznych, elementów grafów, podstawowe struktury w programowaniu, umiejętność użycia pętli, instrukcji warunkowych
Opis ćwiczeńPowtórzenie podstawowych informacji z programowania. Rekurencje. Operacje na tablicach, notacja Ο, Ω, Θ. Podstawowe algorytmy sortowania i porównanie czasu ich działania. Stos, kolejka, lista. Tablica haszująca. Podstawowe operacje na drzewach binarnych, przechodzenie preorder, inorder, postorder. Struktury grafowe. Przechodzenie wszerz i w głąb. Programowanie zachłanne.
Opis wykładówPojęcia algorytmu na przykładzie prostego algorytmy sortowania. Złożoność algorytmiczna. Notacja Ο, Ω, Θ. Idea dziel i zwyciężaj na przykładzie sortowania przez scalanie. Rekurencje, rozwiązywanie równań rekurencyjnych. Elementarne struktury danych: listy, kolejki, stosy. Kopce, kolejki priorytetowe, sortowanie z wykorzystaniem kopca. Sortowanie quicksort. Dolna granica złożoności dla sortowania przez porównanie wartości. Sortowanie w czasie liniowym. Tablice haszujące, funkcja skrótu. Rozwiązywanie kolizji: metoda łańcuchowa, adresowanie otwarte. Haszowanie doskonałe. Drzewa, drzewa binarne. Drzewa przeszukiwań binarnych, podstawowe operacje elementarne dla drzew binarnych. Drzewa czerwono-czarne. Struktury grafowe, przeszukiwanie wszerz i w głąb. Problemy najkrótszych ścieżek i minimalnych drzew rozpinających. Idea algorytmów zachłannych: problem wydawania reszty, plecakowy, kodowanie Huffmana. Programowanie dynamiczne.
Cel kształceniaPrzekazanie studentom zasobu wiedzy o algorytmach i strukturach danych rozumianego jako kanon wiedzy algorytmicznej zawierający teorię podstawowych struktur danych, operacji na nich oraz podstawowych, klasycznych algorytmów o niskiej złożoności wielomianowej. Przekazanie studentom informacji o problemach dla których nie znaleziono algorytmów deterministycznych o złożoności wielomianowej, wraz z informacją o metodach przybliżonych ich rozwiązywania.
Literatura podstawowa1) S. Dasgupta, C. Papadimitriou, U. Vazirani, , Algorytmy, PWN, 2012
Literatura uzupełniająca
Uwagi