Tematyka zajęć laboratoryjnych
temat I |
Algorytmy sortowania |
temat II |
Złożone struktury danych 1. Struktura listy jedno- i dwukierunkowej 2. Struktura drzewa poszukiwań binarnych (Binary Search Tree - BST) 3. Tworzenie i usuwanie w/w struktur 4. Wyszukiwanie elementu na liście/ w drzewie 5. Usuwanie pojedynczych elementów listy/ drzewa 6. Przeglądanie drzewa w porządku wzdłużnym (preorder), poprzecznym (inorder) i wstecznym (postorder) 7. Definicja drzewa zrównoważonego (AVL: Adelson-Velski-Landis) i dokładnie wyważonego (DDW) 8. Równoważenie drzewa: rotacje, algorytm DSW (Day-Stout-Warren) |
temat III | Algorytmy grafowe 1. Definicja grafu skierowanego i nieskierowanego 2. Reprezentacje grafu, ich złożoność pamięciowa i złożoność pozyskiwania informacji o grafie z poszczególnych struktur danych 3. Algorytmy przeszukiwania grafu "w głąb" (Depth First Search = DFS) oraz "wszerz" (Breadth First Search = BFS) 4. Algorytm znajdowania cyklu Eulera w grafie, warunki istnienia cyklu Eulera w grafie skierowanym i nieskierowanym, złożoność obliczeniowa procedury poszukiwania cyklu Eulera 5. Metoda poszukiwania minimalnego drzewa rozpinającego w grafie oraz jej złożoność obliczeniowa 6. Algorytm sortowania topologicznego |
temat IV | Algorytmy z powracaniem 1. Idea działania algorytmów z powracaniem 2. Algorytm SPT (Shortest Processing Time first) 3. Problemy znajdowania cyklu Eulera oraz cyklu Hamiltona w grafie nieskierowanym 4. Przynależność decyzyjnych wersji w/w problemów do odpowiednich klas złożoności obliczeniowej 5. Algorytm z powracaniem dla problemu znajdowania cyklu Hamiltona |
temat V | Programowanie dynamiczne 1. Metodyka programowania dynamicznego 2. Metoda przeglądu wyczerpującego 3. Złożoność obliczeniowa w/w metod 4. Zakres stosowalności programowania dynamicznego 5. Sformułowanie problemu plecakowego oraz metoda jego rozwiązania |
temat VI |
Algorytmy zachłanne |