ALGORYTMY I STRUKTURY DANYCH,

sem. III, studia niestacjonarne, kierunek informatyka

WYKŁAD

Literatura

1. A. V. Aho, J. E. Hopcroft, J. D. Ullman, Projektowanie i analiza algorytmów  komputerowych

2. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych

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

4. A. Drozdek, D. L. Simon Struktury danych w języku C

5. R. Neapolitan, K. Namipour, Podstawy algorytmów z przykładami w C++ 

6. N. Wirth, Algorytmy + struktury danych = programy

NR ZJAZDU

TEMAT WYKŁADU

I

Poprawność całkowita i częściowa algorytmu. Złożoność obliczeniowa algorytmu. Złożoność czasowa średnia i pesymistyczna. Szczegóły

II

Technika "dziel i zwyciężaj".  Przykłady zastosowania. Analiza kosztu rozwiązań opartych na technice „dziel i zwyciężaj”. Szczegóły

III

Technika zachłanna. Przykłady zastosowania. Własność wyboru zachłannego i optymalnej podstruktury. Szczegóły

IV

Programowania dynamiczne. Przykłady zastosowania.  Szczegóły

V, VI

Struktury słownika. Implementacje drzewiaste słownika na drzewach binarnych ( drzewa BST i AVL) . Szczegóły

VII

Struktury danych do reprezentacji grafu. Metody przeglądania grafu i ich zastosowanie. Szczegóły

VIII

Technika powrotów. Schemat algorytmu i przykłady zastosowania. Szczegóły Problemy trudno rozwiązalne – definicja i przykłady. Klasa NP i NPC. Szczegóły.