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 Struktury danych i algorytmy - INK9116
 
  menu
  materiały dydaktyczne
  opis kursu
  informacje dodatkowe
 

  ostatnia aktualizacja
5.11.2017 r.
 

 
  ogłoszenia

egzamin
  1. Przykładowe pytania egzaminacyjne.
wyniki eqzaminu
  1. Wyniki z egzaminu z dnia 27.0108r zostaną ogłoszone do dnia 31.01.08r. Wpisy do indeksów - 2.02.08r., 12.00 sala 201C1. Poprawa egzaminu - 2.02.08r., 12.00-14.00 sala 201 C1.
  2. Wyniki egzaminu.
  3. Poprawa egzaminu oraz wpisy do indeksów - 5.02.08r., 11.00-13.00 sala 325 C3. Inny termin zaliczenia do ustalenia drogą e-mail.
  materiały
Wykłady

Program wykładów i ćwiczeń - pierwszy semestr.

  1. Wprowadzenie do algorytmów-algorytmy liniowe, algorytmy z rozgałęzieniami.
  2. Sortowanie bąbelkowe, czasochłonność algorytmu.
    Sortowanie przez zliczanie, czasochłonność algorytmu.
  3. Sortowanie przez kopcowanie, złożoność algorytmu, podsumowanie algorytmów sortowania.
  4. Wyszukiwanie sekwencyjne, wyszukiwanie binarne bez powtórzeń
    Sortowanie pozycyjne (nieobowiązkowe).
  5. Sortowanie zewnętrzne - przez łączenie naturalne.
  6. Abstrakcyjne typy danych - stos. Implementacja stosu za pomocą tablicy i rekurencyjnej struktury danych. Zastosowanie stosu do programów klienckich.
  7. Abstrakcyjne typy danych - kolejka. Implementacja kolejki za pomocą tablicy (nie obowiązuje) i rekurencyjnej struktury danych. Zastosowanie kolejki do programów klienckich.
  8. Abstrakcyjne typy danych - kolejka priorytetowa. Implementacje kolejki za pomocą tablicy nieuporządkowanej oraz tablicy-kopca. Zastosowanie kolejki do programów klienckich.
  9. Abstrakcyjne typy danych - kolejka priorytetowa cd. Implementacja kolejki za pomocą rekurencyjnej struktury danych. Zastosowanie kolejki do programów klienckich.
  10. **Abstrakcyjne typy danych - słowniki (listy symboli). Implementacja słownika za pomocą tablicy indeksowanej kluczem. Zastosowanie słownika do programów klienckich.
    Podsumowanie algorytmów - część 1.
  11. *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
  12. *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.
  literatura
Literatura
  1. N. Wirth - Algorytmy+Struktury Danych = Programy, WNT Warszawa 1999
  2. R. Sedgewick - Algorytmy w C++, Oficyna Wydawnicza READ ME - Warszawa, 1999
  3. T.H. Cormen, Ch E. Leiserson, R.L. Rivest - Wprowadzenie do algorytmów, WNT Warszawa 1997, 1998
  4. L Banachowski, K.Diks, W. Rytter - Algorytmy i struktury danych, WNT Warszawa, 1999
  5. D. Harel - Rzecz o istocie informatyki, Algorytmika, WNT Warszawa, 1992
  6. J. Bentley - Perełki oprogramowania, WNT Warszawa, 1992

 
m.kruczkiewicz@floweb.pl