Jan Bródka - strona główna


Algorytmy i Struktury Danych 2


Drugi termin egzaminu z Algorytmów i Struktur Danych 2 odbędzie się w dniu 24.06.2019 (poniedziałek) o godz. 12.15 w sali 216.


System sprawdzania rozwiazań


Zadanie na laboratorium

Biblioteka TestSet

Regulamin przedmiotu


Wykłady

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*

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
ćwiczenia 13

wyszukiwanie wzorca w tekście - algorytm Knutha-Morrisa-Pratta
najdłuższy wspólny podciąg i odległość edycyjna napisów

wykład 14

wyszukiwanie wzorca w tekście - algorytm Boyera-Moore'a, algorytm Karpa-Rabina

wykład 15 część 1
wykład 15 część 2

wyszukiwanie wzorca w tekście - wyszukiwanie ze znakami nieznaczącymmi
zagadnienia egzaminacyjne, literatura


Biblioteka Graph
Algorytmy tekstowe