Semestr zimowy 2007/08
Semestr zimowy 2008/09
Semestr zimowy 2009/10
Semestr zimowy 2010/11
Semestr zimowy 2011/12
Semestr zimowy 2012/13
Semestr zimowy 2013/14
Algorytmy i struktury danych I23022
Treści programowe:
Poprawność algorytmu.Złożoność obliczeniowa algorytmu. Rekurencja jako technika kodowania algorytmów.Techniki:"dziel i zwyciężaj",zachłanna, programowania dynamiczne.Implementacje drzewiaste słownika.Tablice haszujące. Struktury danych do reprezentacji grafu.Algorytmy grafowe. Algorytmy przybliżone (aproksymacyjne).Technika powrotów. Problemy trudno rozwiązalne–definicja i przykłady. Klasa NP i NPC.
Efekty kształcenia:
Student rozumie i potrafi wyznaczyć lub oszacować złożoność obliczeniową algorytmu. Student potrafi stwierdzić, czy dany problem komputerowy można rozwiązać jedną ze standardowych technik projektowania algorytmów, tj: "dziel i zwycieżaj", technika zachłanna, programowanie dynamiczne czy backtracking-u. Student zna warunki stosowania i efktywność wybranych struktur danych liniowych i drzewiastych, zna struktury danych do reprezentacji grafu i podstawowe algorytmy grafowe. Student wie co to znaczy, że problem jest trudny obliczeniowo
Rodzaj przedmiotu
Koordynatorzy przedmiotu
W cyklu 2013Z: | W cyklu 2009Z: | W cyklu 2010Z: | W cyklu 2012Z: | W cyklu 2011Z: |
Literatura
a) podstawowa:
1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Wprowadzenie do algorytmów, 2. R. Neapolitan, K. Namipour, Podstawy algorytmów z przykładami w C++.
b) uzupełniająca:
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. A. Drozdek, D. L. Simon Struktury danych w języku C, 4. N. Wirth, Algorytmy + struktury danych = programy