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