Zofia.Kruczkiewicz@pwr.wroc.pl    
Politechnika Wrocławska 
Katedra Informatyki Technicznej (K-9) 
Zespół Inżynierii Oprogramowania i
Inteligencji Obliczeniowej
 
Aktualności  Dydaktyka  Kontakt 
 
   
  strona główna dydaktyka Algorytmy i struktury danych - INK9817
 
  menu
  materiały dydaktyczne
  opis kursu
  informacje dodatkowe
 

  ostatnia aktualizacja
5.11.2017 r.
 

 
  ogłoszenia

Wyniki sprawdzianów z dnia 12.02.2011r.

 
  materiały do zajęć
wykłady
  1. Wstęp do algorytmów i struktur danych.
    Sortowanie bąbelkowe.
    Algorytmy liniowe - sortowanie przez zliczanie.
  2. Algorytmy liniowe c.d. - sortowanie pozycyjne.
    Badanie algorytmów.
    Algorytmy rekurencyjne „dziel i zwyciężaj” - sortowanie przez łączenie.

  3. Algorytmy rekurencyjne „dziel i zwyciężaj” c.d.
    Algorytm sortowania szybkiego.
    Algorytm sortowania przez kopcowanie.
    Analiza algorytmów sortowania - podsumowanie.

  4. Wyszukiwania w tablicach posortowanych.
  5. Sortowanie zewnętrzne naturalne i wielokierunkowe.
    Zmniejszanie liczby serii w plikach dyskowych.
    Sortowanie zewnętrzne polifazowe, podsumowanie algorytmów sortowania zewnętrznego.
  6. Abstrakcyjne typy danych - stos. Implementacja stosu za pomocą tablicy i rekurencyjnej struktury danych (listy wiązanej). Zastosowanie stosu do programów klienckich.
    Abstrakcyjne typy danych - kolejka. Implementacja kolejki za pomocą tablicy i rekurencyjnej struktury danych (listy wiązanej). Zastosowanie kolejki do programów klienckich.
  7. Abstrakcyjne typy danych - koleki priorytetowe. Implementacja kolejki za pomocą modelu tablicy-kopca i rekurencyjnej struktury danych (listy wiązanej). Zastosowanie kolejki priorytetowej do programów klienckich.
  8. Abstrakcyjne typy danych-struktury wiązane. Lista dwukierunkowa uporządkowana.Drzewa. Drzewa poszukiwań binarnych: wstawianie liści, wstawianie do korzenia, obroty w węzłach, wyważanie drzewa, przejście przez drzewo. Złożoność obliczeniowa tablic, drzew i list
  9. Drzewa zrównoważone-zstępujące drzewa 2-3-4, drzewa czerwono-czarne*. Wyszukiwanie zewnętrzne: B-drzewa.
  10. Typy złożoności obliczeniowej. Reprezentacje grafów, algorytmy grafowe: przeszukiwanie grafu „w głąb” DFS - algorytmy „z powrotami”, algorytm przeszukiwania "wszerz" BFS – obliczanie najkrótszej ścieżki z s do wszystkich osiągalnych wierzchołków metodą "podziału i ograniczeń", algorytm Floyda określania najkrótszej ścieżki w grafie metodą programowania dynamicznego.
egzamin
    Przykładowe pytania egzaminacyjne - dodano zapowiadane przejścia przez graf!
laboratorium
  literatura
literatura podstawowa
  1. Cormen T. H., Leiserson Ch. E., Rivest R. L., Wprowadzenie do algorytmów, Warszawa, WNT, 1998
  2. Wirth N., Algorytmy + Struktury Danych = Programy, Warszawa, WNT, 1999
  3. Sedgewick R., Algorytmy w C++, Warszawa, Oficyna Wydawnicza READ ME, 1999
  4. Banachowski L., Diks K., Rytter W., Algorytmy i strukturty danych, Warszawa, WNT, 1999
literatura uzupełniająca
  1. Harel D., Rzecz o istocie informatyki, Algorytmika, Warszawa, WNT, 1992
  2. Bentley J., Perełki oprogramowania, Warszawa, WNT, 1992

 
m.kruczkiewicz@floweb.pl