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 aktualności
 
  menu
  materiały dydaktyczne
  opis kursu
  informacje dodatkowe
 

  ostatnia aktualizacja
5.11.2017 r.
 

 
  ogłoszenia

  materiały do zajęć

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 zewnętrzne - przez łączenie naturalne.
  5. Abstrakcyjne typy danych - stos. Implementacja stosu za pomocą tablicy i rekurencyjnej struktury danych (listy wiązanej). Zastosowanie stosu do programów klienckich.
  6. 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.
  7. 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.
  8. Algorytmy "dziel i zwyciężaj". Rekurencja, sortowanie szybkie i przez łączenie.
  9. Sortowanie zewnętrzne przez łączenie wielokierunkowe, implementacja w C/C++.
    Sortowanie zewnętrzne polifazowe.
  10. Wyszukiwanie binarne dla ciągów posortowanych z powtórzeniami elementów. Analiza złożoności algorytmów sortowania szybkiego, kopcowego i przez łączenie
  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. Drzewa zrównoważone-zstępujące drzewa 2-3-4, drzewa czerwono-czarne*. Wyszukiwanie zewnętrzne: B-drzewa.
  13. 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.- Dodano wyjaśnienie w algorytmie BFS.
  14. Algorytmy zachłanne - Algorytmy Prima i Dijkstry. Rozszerzono ilustrację algorytmu Prima.
Laboratorium

Ćwiczenia
  1. Wprowadzenie do algorytmów.
  2. Sortowanie przez selekcję i wstawianie.
  3. Sortowanie pozycyjne, wyszukiwanie binarne bez powtórzeń.
  4. Zmniejszanie liczby serii w plikach dyskowych -zmiany w dniu 24.04.07r..
  5. Abstrakcyjne typy danych - kolejka. Implementacja kolejki za pomocą tablicy i rekurencyjnej struktury danych (listy wiązanej). Zastosowanie kolejki do programów klienckich.
  6. Abstrakcyjne typy danych - lista nieuporządkowana. Implementacja listy nieuporządkowanej za pomocą tablicy i rekurencyjnej struktury danych (listy wiązanej).
  7. Abstrakcyjne typy danych - lista uporządkowana. Implementacja listy uporządkowanej za pomocą tablicy i rekurencyjnej struktury danych (listy wiązanej).

Laboratorium z Języków Programowania 1
  1. Wprowadzenie.
  2. Wprowadzenie do programowania w C/C++.
  3. Pętle, instrukcje warunkowe.
  4. Pętle, instrukcje warunkowe, tablice, sekwencyjne zapisywanie i odczytywanie tablicy.
  5. Pętle, instrukcje warunkowe, sekwencyjne i niesekwencyjne zapisywanie i odczytywanie tablicy.
  6. Pętle, instrukcje warunkowe, sekwencyjne i niesekwencyjne zapisywanie i odczytywanie tablicy cd. (Funkcje bez parametrów i z parametrami.)
  7. Sprawdzian.
  8. Tablica dwuwymiarowa znakow, sortowanie pozycyjne. (Funkcje bez parametrów i z parametrami.)
  9. Tablice znaków -łańcuchy. (Funkcje bez parametrów i z parametrami.)
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