Wymagania i zalecenia

Na początek kilka ogólnych zaleceń dotyczących sprawozdań:
1. Sprawozdania powinny być wysłane w formacie PDF!
2. Nie produkujemy strony tytułowej, wystarczą dane osobowe, numery indeksów i tytuł zdania.
3. Nie umieszczamy opisu ćwiczenia oraz kodu programu !
4. Najważniejsze są wykresy (odpowiedni dobór parametrów -
punktów pomiarowych, czytelność) oraz wnioski, szczególnie,
dotyczące złożoności obliczeniowej badanych problemów.
WNIOSKI nie opisują tego co wyszło lecz wyjaśnieją DLACZEGO tak wyszło!

A teraz wymagania odnośnie znajomości, omawianych w poszczególnych ćwiczeniach, zagadnień:

1. Sortowanie
Znajomość algorytmów sortowania:
- szybkiego (Quicksort) - QS,
- przez kopcowanie (Heapsort) - HS,
- przez proste wybierania (Selection Sort) - SS,
- przez proste wstawianie (Insertion Sort) - IS,
- przez prostą zamianę (Bubble Sort) - BbS,
- przez zliczanie (Counting Sort) - CS,
- kubełkowego (Bucket Sort) - BS,
- przez scalanie (Merge Sort) - MS,
obejmującą:
- ideę tj. sposób działania algorytmu,
- analizę zachowania metody dla różnych rozkładów danych
wejściowych z uwzględnieniem identyfikacji najlepszego
i najgorszego przypadku,
- złożoność obliczeniową w przypadku średnim, najlepszym
i najgorszym,
- wady, zalety i ograniczenia poszczególnych algorytmów,
- zalecane warunki stosowania metody.

2. Złożone struktury danych
Znajomość struktury listy jednokierunkowej i drzewa poszukiwań binarnych
(ang. Binary Search Tree - BST) ze szczególnym uwzględnieniem:
- tworzenia oraz usuwania listy i drzewa,
- wyszukiwania elementu w liście i drzewie,
- usuwania elementu z listy i drzewa,
- przeglądania drzewa w 3 porządkach: wzdłużnym, poprzecznym i wstecznym,
- definicji drzewa dokładnie i AVL- wyważonego.

3. Algorytmy grafowe
Znajomość:
- definicji grafu skierowanego i nieskierowanego,
- reprezentacji grafu (macierz incydencji, macierz sąsiedztwa wierzchołków, lista krawędzi, listy
incydencji poprzedników i następników), ich złożoności pamięciowej i złożoności procesu pozyskiwania różnych typów informacji o grafie,
- algorytmów przeszukiwania grafu "w głąb" i "wszerz",
- sortowania topologicznego

4. Algorytmy z powracaniem
Znajomość:
- idei działania algorytmów z powracaniem,
- problemów znajdowania cyklu Eulera i Hamiltona w grafie nieskierowanym oraz ich przynależności do odpowiednich klas złożoności obliczeniowej,
- idei algorytmu z powracaniem dla problemu znajdowania cyklu Hamiltona.

5. Programowanie dynamiczne
Znajomość:
- metody programowania dynamicznego oraz zakresu jej stosowalności, możliwej złożoności obliczeniowej,
- sformułowania problemu plecakowego i metod jego rozwiązania,
- algorytmu zachłannego dla problemu plecakowego.