ALGORYTMY I STRUKTURY DANYCH,

sem. III, studia stacjonarne, 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

DATA

TEMAT WYKŁADU

1.

05.10.11

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

2.

12.10.11

Rekurencja jako technika kodowania algorytmów. Anatomia wywołania rekurencyjnego. Rodzaje rekurencji. Wady i zalety kodowania rekurencyjnego. Szczegóły. Szczegóły. Konkurs nr 1. Rozwiązanie konkursu nr 1.

3.

19.10.11

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

4.

26.10.11

Technika zachłanna. Przykłady zastosowania. Własność wyboru zachłannego i optymalnej podstruktury. Szczegóły. Konkurs nr 2. Rozwiązanie konkursu nr 2.

5.

16.11.11

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

6,7

23.11.11, 30.11.11

Podstawowe algorytmu grafowe oraz ich zastosowania. Metody przeglądania grafów. Szczegóły. Metody generowania najkrótszej ścieżki w grafie. Szczegóły.

8.

02.12.11

(zamiast 09.11.11), godz.14.15, sala W-23C

Liniowe uporządkowane struktury danych: stos, kolejka. Specyfikacja, przykładowe implementacje i zastosowania. Szczegóły

9.

07.12.11

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

10.

14.12.11

Technika powrotów. Schemat algorytmu i przykłady zastosowania. Szczegóły. Konkurs nr 3 .

11.

21.12.11

Algorytmy przybliżone (aproksymacyjne). Pojęcia: błąd przybliżenia, heurystyka. Przykłady prostych algorytmów przybliżonych. Szczegóły

12.

11.01.12

Problemy trudno rozwiązalne – definicja i przykłady. Klasa NP i NPC. Nieobliczalność i nierozstrzygalność. Szczegóły

13.

18.01.12

Tablice haszujące. Haszowanie łańcuchowe i adresowanie otwarte. Szczegóły

14.

25.01.12

Wprowadzenie do geometrii obliczeniowej. Szczegóły

15.

02.02.12

Repetytorium.