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
15.07.2018 r.
 

 
  autor kursu
dr inż. Zofia Kruczkiewicz
 
  zespół dydaktyczny
dr inż. Marek Piasecki
dr inż. Paweł Rogaliński
dr inż. Robert Wójcik
 
  semestralny wymiar godzin
wykład - 20 godzin
laboratorium - 20 godzin
 
  wymagania wstępne
Podstawy informatyki - INK9011
Praktyka programowania - INK9100
Pracownia programowania - INK9114
 
  opis kursu
Przedmiot dotyczy tworzenia koncepcji, projektu i implementacji algorytmów z uwzględnieniem analizy ich złożoności strukturalnej i obliczeniowej oraz dowodu poprawności. W ramach kursu omawiane są podstawowe algorytmy przetwarzające struktury danych o dostępie indeksowanym, sekwencyjnym oraz rekurencyjnym. Dla każdej z grup są prezentowane kolejno algorytmy: sortowania tablic i wyszukiwania w tablicach, sortowania plików, przetwarzania dynamicznych struktur nieuporządkowanych (stosy, kolejki. listy) i struktur uporządkowanych (listy, drzewa) oraz algorytmy grafowe.
 
  zawartość tematyczna kursu
wykład
  1. Wprowadzenie do algorytmów i struktur danych - 1h
  2. Abstrakcyjna koncepcja algorytmu, projekt i implementacja algorytmu, przykład sortowania bąbelkowego - 1h
  3. Algorytmy sortowania w czasie liniowym: przez zliczanie, pozycyjne - 2h
  4. Algorytmy sortowania typu "dziel i zwyciężaj": przez scalanie, szybkie - 2h
  5. Algorytm sortowania przez kopcowanie, kolejki priorytetowe - 1h
  6. Algorytmy wyszukiwania: sekwencyjnego, binarnego - 1h
  7. Algortmy sortowania zewnętrznego przez: łączenie naturalne, łączenie wielokierunkowe, łączenie polifazowe - 3h
  8. Algorytm zmniejszania liczby serii - 1h
  9. Rekurencyjne nieuporządkowane struktury danych: stosy, kolejki, listy jedno- i dwukierunkowe - 2h
  10. Rekurencyjne uporządkowane struktury danych: listy, drzewa poszukiwań binarnych - 2h
  11. Wyważanie drzew poszukiwań binarnych, drzewa wielokierunkwe - 2h
  12. Algorytmy grafowe: przeszukiwanie wszerz, przeszukiwanie wgłąb - 2h
laboratorium

Laboratorium obejmuje zestaw ćwiczeń dotyczących:
  1. implementacji algorytmów sortowania tablic zawierających różne typy elementów oraz pomiar czasu ich trwania
  2. implementacji algorytmów sortowania plików o różnej zawartości oraz pomiar czasu ich trwania
  3. implementacji algorytmów przetwarzania dynamicznych nieuporządkowanych struktur danych: stosów, kolejek i list oraz pomiar czasu ich trwania
  4. implementacji algorytmów przetwarzania dynamicznych uporządkowanych struktur danych: list oraz drzew binarnych i wielokierunkowych oraz pomiar czasu ich trwania
  5. implementacji algorytmów grafowych

 
m.kruczkiewicz@floweb.pl