Algorytmy, Struktury Danych i Złożoność Obliczeniowa

Bibliografia

Publications

2008

@author@, Studia Informatyczne, 2008

2004

Stein C. Cormen T. H., Wprowadzenie do algorytmów, 2004

2003

Robert Lafore, Java. Algorytmy i Struktury Danych, 2003

Ullman J.D. Aho A.V. Hopcroft J.E., Algorytmy i Struktury Danychy, 2003

2002

Donald Knuth, Sztuka programowania, 2002

2001

Rytter W. Banachowski L. Diks K., Algorytmy i Struktury Danych, 2001

Plan wykładów

Wprowadzenie
- Co to jest algorytm?
- Co to jest struktura danych?
- Rozumowanie indukcyjne
- Dowód indukcyjny
- Złożoność algorytmu
- Sortowanie przez wstawianie
- Analiza sortowania przez wstawianie
- Notacje asymptotyczne
Sortowanie, Kopiec, Rekurencja
- Metoda „dziel i zwyciężaj”.
- Sortowanie przez scalanie – MergeSort
- Złożoność sortowania przez scalanie
- Rekurencja, obliczanie złożoności rekurencyjnych, rozwiązywanie rekurencji, tw. o rekurencji uniwersalnej
- Kopiec, własność kopca, przywracanie własności kopca, budowanie kopca
- Analiza algorytmów kopcowych
- Sortowanie kopcowe, Kolejki priorytetowe
Kolejki priorytetowe, Quicksort, Sortowanie w czasie liniowym
- Kolejki priorytetowe
- Operacje kopca
- Implementacja kolejek priorytetowych
- Sortowanie szybkie (Quicksort)
  - algorytm
  - analiza Quicksortu
- Model Drzewa Decyzyjnego alg. Sortowania
- Sortowanie przez zliczanie, sortowanie pozycyjne, sortowanie kubełkowe
- Zbiory dynamiczne, Stos, Lista
Struktury danych, Stos, Kolejka, Lista, Drzewa BST i RB
- Zbiory dynamiczne
- Stos
- Kolejka
- Lista
- Drzewo BST
  - operacje przeglądania, wyszukiwania, usuwania
  - złożoność operacji na drzewie BST
- Drzewa dobrze wyważone
  - Drzewo czerwono-czarne (Drzewo RB)
    - wstawianie do drzewa RB
Listy przeskakiwania, Tablice haszujące, Statystyki pozycyjne
- Skip lists (listy przeskakiwania)
- Tablice haszujące
  - adresowanie bezpośrednie
  - adresowanie otwarte
    - adresowanie liniowe, kwadratowe, podwójne
- implementacja listowa, rozwiązywanie kolizji
- Funkcja haszująca
- Statystyki pozycyjne
  - problem selekcji, selekcja w pesymistycznym czasie liniowym
  - dynamiczne statystyki pozycyjne
Dynamiczne statystyki pozycyjne, drzewa przedziałowe, grafy
- Dynamiczne statystyki pozycyjne
  - wyznaczanie elementu o zadanej randze
  - rotacja w drzewie dynamicznych statystyk pozycyjnych
- Drzewa przedziałowe
  - rotacja w drzewie przedziałowym
  - poszukiwanie przedziału w drzewie przedziałowym
- Grafy
  - reprezentacja grafu – macierz sąsiedztwa, listy sąsiedztwa
  - przeszukiwanie grafu – algorytm BFS
Grafy, DFS, drzewo rozpinające grafu, sortowanie topologiczne
- Algorytmy grafowe
  - Przeszukiwanie grafu
    - BFS, DFS
    - tworzenie drzewa rozpinającego
    - klasyfikacja krawędzi
      - krawędź w przód, krawędź poprzeczna, krawędź wsteczna, krawędź drzewowa
- Skierowany Graf Acykliczny
  - sortowanie topologiczne
    - własności sortowania topologicznego
Algorytmy grafowe, poszukiwanie minimalnych ścieżek
- Minimalne drzewo rozpinające
- Obserwacja – struktura optymalna składa się z optymalnych pod-struktur
- Algorytm Prima poszukiwania minimalnego drzewa rozpinającego
- Poszukiwanie minimalnych ścieżek w dowolnym grafie skierowanym – algorytm Forda Bellmana
- Wersja algorytmu Forda-Bellmana dla skierowanych grafów acyklicznych
- Poszukiwanie najkrótszych ścieżek w grafie o nieujemnych wagach krawędzi – algorytm Dijkstry
Algorytmy grafowe, metoda kosztu zamortyzowanego
- Algorytm Dijkstry
  - działanie, złożoność, poprawność
- Drzewa rozpinające
  - algorytm Kruskala
  - poprawność algorytmu Kruskala
- Problem najkrótszych ścieżek między każdą parą wierzchołków w grafie
  - algorytm Warshala-Floyda
- Analiza kosztu zamortyzowanego
  - tablice dynamiczne
  - analiza metodą kosztu sumarycznego
  - analiza metodą księgowania
Sieci przepływowe, algorytmy wyszukiwania wzorca
- Sieci przepływowe
  - algorytm Forda-Fulkersona, sieć residualna, ścieżka powiększająca, funkcja przepływu
  - minimalny przekrój, maksymalny przepływ
- Maksymalne skojarzenia w grafach dwudzielnych
  - sprowadzenie do problemu sieci przepływowej
- Wyszukiwanie wzorca w tekście
  - algorytm „naiwny”, algorytm Rabina-Karpa,
  - automaty skończenie stanowe - wprowadzenie do KMP
Algorytmy tekstowe
- Wyszukiwanie wzorca
  - automaty skończenie stanowe
  - wyszukiwanie wzorca w tekście za pomocą automatu
  - algorytm KMP (redukcja funkcji przejść do tablicy)
  - algorytm Boyera-Moore'a
    - heurystyki
      - niezgodności
      - dobrego sufiksu
Kompresja tekstów, Algorytmy równoległe
- Kompresja tekstów
  - teoria informacji – miara entropii Shannona
  - Kodowanie Huffmana
    - algorytm tworzenia kodowania
  - Kompresja LZW
- Algorytmy równoległe
  - taksonomia systemów równoległych Flynn'a
  - architektury równoległe
- model PRAM
  - EREW, CREW, ERCW, CRCW
- przykłady algorytmów równoległych
  - trójkąt Pascala, wyszukiwanie minimum, statystyki pozycyjne, ustalanie rangi elementu w liście
Algorytmy geometryczne
- podstawowe pojęcia
- określanie położenia punktów względem siebie
- problem przecinania się dwóch odcinków
- techniki konstrukcji algorytmów geometrycznych
- problem znajdowania otoczki wypukłej zbioru punktów
- algorytm Grahama znajdowania otoczki wypukłej zbioru punktów
- szukanie przecinających się odcinków w zbiorze odcinków
- algorytm wyszukiwania przecinających się odcinków metodą zamiatania
- problem znajdowania najmniej odległej pary punktów w zbiorze
  - algorytm metodą „dziel i zwyciężaj”
Wykład podsumowywujący