wykład 1 |
wstęp, metody reprezentacji grafów |
wykład 2 |
przeszukiwanie grafów (w głąb, wszerz, ogólne) |
wykład 3 część 1 wykład 3 część 2 |
problem wyznaczania najkrótszych ścieżek w grafach - wstęp, algorytm Forda-Bellmana |
wykład 4 |
problem wyznaczania najkrótszych ścieżek w grafach - algorytm Dijkstry, algorytm A*, porównanie obszarów zbadanych przez algorytmy wyznaczania najkrótszych ścieżek: algorytm Dijkstry algorytm A* |
wykład 5 |
problem wyznaczania najkrótszych ścieżek w grafach - algorytm dla grafów skierowanych bez cykli, wyznaczanie odległości pomiędzy wszystkimi parami wierzchołków - algorytmy Floyda-Warshalla i Johnsona, problem komiwojażera - metoda pełnego przeglądu (z powrotami) |
wykład 6 część 1 wykład 6 część 2 symulacja |
problem komiwojażera - metoda podziału i ograniczeń przebieg wykonania algorytmu |
wykład 7 |
problem komiwojażera - algorytmy przybliżone |
wykład 8 |
przepływy w sieciach - wstęp, definicje, sieć rezydualna, metoda Forda-Fulkersona, metoda Dinica |
wykład 9 |
przepływy w sieciach - metoda przepychania wstępnego przepływu, maksymalny przepływ o minimalnym koszcie |
wykład 10 część 1 wykład 10 część 2 |
geometria obliczeniowa - pojęcia wstępne, iloczyn wektorowy, przecinanie się dwóch odcinków,
problem przynależności punktu do wielokąta |
wykład 11 część 1 wykład 11 część 2 |
geometria obliczeniowa - wyznaczanie otoczki wypukłej (algorytmy Grahama, Jarvisa i QuickHull) |
wykład 12 część 1 wykład 12 część 2 wykład 12 część 3 |
geometria obliczeniowa - problem przecinania się n odcinków wyszukiwanie wzorca w tekście - sformułowanie problemu, algorytm naiwny |
wykład 13 |
wyszukiwanie wzorca w tekście - algorytm Knutha-Morrisa-Pratta |
wykład 14 |
wyszukiwanie wzorca w tekście - algorytm Boyera-Moore'a, algorytm Karpa-Rabina |
wykład 15 |
wyszukiwanie wzorca w tekście - wyszukiwanie ze znakami nieznaczącymmi |