Informacje dla studentów >> Algorytmy i struktury danych (Informatyka) >>

Tematyka zajęć laboratoryjnych



temat I

Algorytmy sortowania
1. Sposób działania następujących algorytmów:
- sortowanie szybkie (quicksort) = QS
- sortowanie przez kopcowanie (heapsort) = HS
- sortowanie przez proste wybieranie (selection sort) = SS
- sortowanie przez proste wstawianie (insertion sort) = IS
- sortowanie przez prostą zamianę (bubble sort) = BbS
- sortowanie za pomocą malejących przyrostów (shell sort) = ShS
- sortowanie przez zliczanie (counting sort) = CS
- sortowanie pozycyjne (radix sort) = RS
- sortowanie kubełkowe (bucket sort) = BS
- sortowanie przez scalanie (merge sort) = MS
2. Analiza zachowania poszczególnych metod sortowania dla różnych rozkładów danych wejściowych z uwzględnieniem identyfikacji najlepszego i najgorszego przypadku
3. Złożoność obliczeniowa algorytmów w przypadku średnim, najlepszym i najgorszym
4. Zalety, wady i ograniczenia poszczególnych algorytmów
5. Zalecane warunki stosowania poszczególnych metod 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
1. Zasada działania algorytmów zachłannych
2. Kiedy algorytmy zachłanne są algorytmami dokładnymi a kiedy przybliżonymi
3. Definicja problemu komiwojażera (Travelling Salesman Problem = TSP) oraz jego przynależność do odpowiednich klas złożoności w wersji decyzyjnej i optymalizacyjnej
4. Algorytm zachłanny dla problemu plecakowego