Informatyka i Ekonometria, st. I, 2009/2010

Algorytmy i struktury danych

TYP PRZEDMIOTU: DODATKOWY A

WYKŁADOWCA dr Florian Fabiś WYMAGANIA WSTĘPNE

Znajomość podstawowego kursu z analiz}' i algebry liniowej. Biegła znajomość obsługi komputera. Umiejętność programowania komputerów w zakresie programowania strukturalnego.

EFEKTY KSZTAŁCENIA

Wiedza i umiejętności w zakresie podstaw analizy algorytmów: złożoność obliczeniowa algory tmu i jego poprawność semantyczna, podstawowe metody konstnrowania efektywnych algorytmów (rekurencja, zasada „dziel i zwyciężaj”, metoda zachłanna).

Znajomość i umiejętność implementacji algorytmów sortowania i selekcji, algorytmów wyszukiwania, podstawowych algorytmów grafowych.

Wiedza na temat problemu NP - zupełności i jego praktycznych aspektów .

PROGRAM NAUCZANIA

Algorytmy i ich złożoność obliczeniowa i pamięciowa, semantyczna poprawność algorytmu.

Rzędy wielkości funkcji. Szacowanie sum.

Metody projektowania efektywnych algorytmów: rekurencja, zasada „dziel i zwyciężaj”, algorytmy zachłanne, programowanie dynamiczne.

Algorytmy sortowania i selekcji.

Algorytmy wyszukiwania: wyszukiwanie liniowe, binarne, interpolacyjne, wektor charakterystyczny.

Struktury danych dla słownika: haszowanie, drzewa poszukiwań binarnych.

Wyszukiwanie zewnętrzne.

Algorytmy grafowe: reprezentacje komputerowe grafów, przechodzenie drzew, przechodzenie grafów, wyznaczanie minimalnego drzewa rozpinającego, najkrótsze ścieżki.

Modele obliczeń. Klasy złożoności obliczeniowej problemów decyzyjnych.

Algorytmy aproksymacyjne.

LITERATURA Literatura podstawow a

1.    Aho A., Hopcroft J.E., Ullman J.D.,: Projektowanie i analiza algorytmów komputerowych, PWN, Warszawa 1983.

2.    Banachow ski L., Diks K., Rytter W., Algorytmy i struktury danych, WNT, W-wa 1996.

3.    Cormen T.H., Leiserson C.E., Rivest R.L., Wprowadzenie do algorytmów, WNT, Warszawa 1997.

Literatura uzupełniająca

1.    Knuth D. : Sztuka programowania, t. 1-3, WNT, Warszawa 2001.

2.    Błażewicz J.: Złożoność obliczeniowa problemów kombinatorycznych, WNT, Warszawa 1988.

3.    P. Wróblew ski: Algorytmy, struktury danych i techniki programowania, wyd. II popr.. Helion, 2001.

WARUNKI ZALICZENIA

Warunkiem zaliczenia wykładu jest zdanie egzaminu. Egzamin odbywa się w formie pisemnej.