1437212953

Matematyka, st. I, 2009/2010

Algorytmy i struktury danych

TYP PRZEDMIOTU: DODATKOWY A

FORMA ZAJĘĆ	W	L
LICZBA GODZIN	30	30
FORMA ZALICZENIA	E	O
ECTS	6

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 algorytmu i jego poprawność semantyczna, podstawowe metody konstruowania efektywnych algorytmów (rekurencja, zasada „dziel i zwyciężaj”, metoda zachłanna).

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

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

PROGRAM NAUCZANIA

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

2.    Asymptotyka. Rzędy wielkości funkcji. Szacowanie sum.

3.    Metody projektowania efektywnych algorytmów. Rekurencja, zasada „dziel i zwyciężaj”, algorytmy

zachłanne, programowanie dynamiczne.

4.    Algorytmy sortowania i selekcji.

5.    Algorytmy wyszukiwania. Wyszukiwanie: liniowe, binarne, interpolacyjne. Wektor charakterystyczny.

6.    Struktury danych dla słownika. Haszowanie, drzewa poszukiwań binarnych.

7.    Wyszukiwanie zewnętrzne. B - drzewa.

8.    Algorytmy grafowe. Reprezentacje komputerowe grafów'. Przechodzenie drzew, przechodzenie grafów, wyznaczanie minimalnego drzewa rozpinającego. Najkrótsze ścieżki.

9.    Modele obliczeń.

10.    Klasy złożoności obliczeniowej problemów decyzyjnych.

11.    Algorytmy aproksymacyjne.

LITERATURA

Literatura podstawowa

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

2.    Banachowski 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.    KnuthD. : Sztuka programowania, t. 1-3, WNT, Warszawa2001.

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. Pięć poprawnych odpow iedzi na pięć postawionych pytań to ocena bdb, cztery' to dobry, trzy to dost.

Warunkiem zaliczenia laboratorium jest zaliczenie trzech projektów indywidualnych. Ponadto na ocenę końcową z laboratorium wpływ mają także oceny uzyskane ze sprawdzianów odbywających się w trakcie zajęć.

7