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

2008
  • @author@, Studia Informatyczne, 2008
2004
  • Stein C. Cormen T. H., Wprowadzenie do algorytmów, 2004
2003
  • Ullman J.D. Aho A.V. Hopcroft J.E., Algorytmy i Struktury Danychy, 2003
  • Robert Lafore, Java. Algorytmy i Struktury Danych, 2003
2002
  • Donald Knuth, Sztuka programowania, 2002
2001
  • Rytter W. Banachowski L. Diks K., Algorytmy i Struktury Danych, 2001
  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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”
  14. Wykład podsumowywujący