Algorytmy i struktury danych

Liczba godzin wykładu: 30 ćwiczeń: 15 laboratoriów: 15

Wymagania przedmiotowe

Podstawowe pojęcia i narzędzia informatyki Matematyka dyskretna Podstawy programowania

Sylabus

Moduł 1 -- Przykłady i analiza złożoności algorytmów

-- twierdzenie o rekurencji uniwersalnej -- poprawność algorytmów -- klasy złożoności algorytmów -- procedury rekurencyjne

Moduł 2 -- Techniki projektowania algorytmów

-- metoda dziel i zwyciężaj -- programowanie dynamiczne - problem plecakowy - problem minimalnej ścieżki -- metoda zachłanna - problem minimalnego drzewa rozpinającego - problem plecakowy

Moduł 3 -- Selekcja

-- statystyki pozycyjne - jednoczesne wyznaczanie minimum i maksimum - wyznaczanie k-tego co do wielkości elementu tablicy

Moduł 4 -- Sortowanie

-- sortowanie przez scalanie -- sortowanie szybkie -- sortowanie przez zliczanie -- sotowanie kubełkowe -- sortowanie topologiczne

Moduł 5 -- Stosy, kolejki, listy

-- operacje na zbiorach dynamicznych -- tablicowe implementacje

Moduł 6 -- Drzewa

-- drzewa ukorzenione i uporządkowane -- drzewa binarne -- algorytmy z nawrotami - problem n królowych - problem plecakowy

Moduł 7 -- Kopce i kolejki piorytetowe

-- kopce binarne -- sortowanie przez kopcowanie

Moduł 8 - Wyszukiwanie

-- wyszukiwanie liniowe -- wyszukiwanie binarne i B-drzewa -- drzewa wyszukiwań binarnych -- technika haszowania

Moduł 9 - Stabilność algorytmów

-- przykłady algorytmów numerycznie niestabilnych -- eliminacja kulminacji błędów

Moduł 10 -- Problemy obliczeniowo trudne

-- klasy złożoności P i NP -- problem P=NP -- algorytmy redukcji

Moduł 11 -- Schematy aproksymacyjne

-- problem plecakowy -- problem podziału zbioru

Cel przedmiotu

Poznanie podstawowych technik algorytmicznych. Wyrobienie umiejętności konstruowania algorytmów oraz oceny ich poprawności i złożoności czasowej. Wskazanie na istotny związek między strukturami danych a efektywnością algorytmów.

Literatura

1. L.Banachowski, K.Diks, W.Rytter, Algorytmy i struktury danych, WNT, Warszawa 2006 2. T.Cormen, Ch.Leiserson, R.Rivest, C.Stein, Wprowadzenie do algorytmów, WNT, Warszawa 2004 3. D.Knuth, Sztuka programowania, Tom 3: Sortowanie i wyszukiwanie, WNT, Warszawa 2002 4. R.Neapolitan, K.Naimipour, Podstawy algorytmów z przykładami w C++, Helion, Gliwice 2004 5. N.Wirth, Algorytmy + struktury danych = programy, WNT, Warszawa

Nazwa przedmiotu w języku angielskim

Wymagania przedmiotowe (w j. angielskim)

Sylabus (w j. angielskim)

Cel przedmiotu (w j. angielskim)


KategoriaPrzedmiot

Sylabus: Algorytmy i struktury danych (ostatnio edytowane 2011-05-24 10:13:02 przez localhost)