3582428277

ALGORYTMY i STRUKTURY DANYCH

Dr inż. Dokimuk Jerzy

KAE (K-26), gmach Ali, IVp. pok. 409, tel. [phone]

jdokimuk@p. lodz.pl

1.    Pojęcie algorytmu: klasyfikacje, metody zapisu, operacje dominujące, przykłady.

2.    Analiza algorytmów: pojęcie złożoności, notacje, klasa algorytmu, opis matematyczny.

3.    Rekurencja: definicje, problemy, typy rekurencji.

4.    Projektowania algorytmów: dziel i zwyciężaj, programowanie dynamiczne, algorytmy

zachłanne, algorytmy z powrotami.

5.    Sortowanie: przez wstawianie, bąbelkowe, Shella. QuickSort, przez zliczanie, pozycyjne.

kubełkowe, i inne, drzewa decyzyjne.

6.    Wyszukiwanie wzorca: Brute Force. Knutha-Morrisa-Pratta. Rabina-Karpa.

7.    Haszowanie: idealna funkcja haszująca, kolizje, haszowanie łańcuchowe.

8.    Abstrakcyjne struktury danych: stos, kolejka, lista, przykłady implementacji i zastosowań.

9.    Drzewa: binarne, BST, wstawianie/usuwanie kluczy, przechodzenie, równoważenie,

algorytm DSW. drzewa AVL.

10.    Kopiec: operacje, implementacja, sortowanie przez kopcowanie, zastosowanie.

11.    B-drzewa: tworzenie, wstawianie i usuwanie kluczy.

12.    Grafy: definicje, przeszukiwanie BFS/DFS, algorytm Kruskala. Dijkstry.

13.    Wstęp do kompresji danych: kodowanie prefiksowe, metoda Huffmana.

14.    Zarys Problemów NP - zupełnych

LITERATURA

[1]    Cormen T. HLeiserson C. E., Rivest R. L.: Wprowadzenie do algorytmów.

WNT, Warszawa, 2006.

[2]    Drozdek A.: C+ + . Algorytmy i struktury danych. Helion, Gliwice, 2004.

[3]    Neapolitan R., Naimipour K.: Podstawy algorytmów z przykładami w C+ + .

Helion, Gliwice, 2004.

[4]    Harris S., Ross J.: Od podstaw Algorytmy. Helion, Gliwice, 2006.

[5]    Adamski T., Ogrodzij J.: Algorytmy komputerowe i struktury danych. PW, Warszawa 2005

[6]    Drozdek A., Simon D. L.: Struktury danych w języku C. WNT, Warszawa, 1996.

[7]    Sedgewick R.: Algorytmy w C++. RM, Warszawa, 1999.

[8]    Sedgewick R.: Algorytmy w C++. Grafy. RM, Warszawa, 2003.

[9]    Aho Alfred V._# Hopcroft John E., Ullman Jeffrey D.: Projektowanie i analiza alqorytmów. Hełion, Gliwice, 2003 (1974).

[10]    Wróblewski P.: Algorytmy, struktury danych i techniki programowania. Helion, Gliwice, 2003.

[11]    Wirth N.: Algorytmy+struktury danych=programy. WNT, Warszawa, 1989.

[12]    Banachowski L., Diks K., Rytter W.: Algorytmy i struktury danych. WNT, Warszawa, 1996.

[13]    Sysło M. M.: Algorytmy. Wydawnictwa szkolne i pedagogiczne, Warszawa, 1997.