Celem modułu jest nabycie umiejętności tworzeniem i zarządzaniem testami.
- Statyczna inspekcja i przeglądy kodu: Wykrywanie błędów inicjalizacji, deklaracji,
obliczeniowych, przepływu sterowania w interfejsach, wejścia-wyjścia.
- Projektowanie przypadków testowych: Podział na klasy równoważności, analiza
wartości brzegowych, zależności przyczyna-skutek oraz zgadywanie błędów, pokrycie
instrukcji, decyzji i warunków.
- Testy jednostkowe.
- Wprowadzenie do zasad TDD.
- Przygotowanie planu testów i raportu testów.
- Wersje oprogramowania i testy akceptacyjne.
- Testowanie aplikacji internetowych i systemów rozproszonych.
Celem laboratorium jest implementacja i analiza algorytmów wprowadzonych na wykładzie.
Treści programowe - laboratorium:
1. Implementacja algorytmów oraz problemów algorytmicznych prezentowanych na wykładzie w wybranym języku programowania.
2. Analiza złożoności wykonywanych implementacji.
Treści Programowe - wykład:
1. Złożone struktury danych i ich implementacje:
(a) B‐drzewa.
(b) Kopce dwumianowe.
(c) Kopce Fibonacciego.
(d) Struktury danych dla zbiorów rozłącznych.
2. Zaawansowane algorytmy grafowe:
(a) Skojarzenia w grafach dwudzielnych ‐ algorytmy Hopcrofta‐Karpa.
(b) Skojarzenia w grafach dowolnych ‐ algorytm Edmondsa.
(c) Maksymalny przepływ: algorytm Forda‐Fulkersona, algorytm Edmondsa‐Karpa, algorytm Dinica.
(d) Problemy ścieżkowe: Algorytm Dijkstry i jego uogólnienia, algorytm Johnsona.
3. Zaawansowane algorytmy tekstowe: algorytm Boyera Moore’a, wyszukiwanie wzorca w pamięci stałej, regularności w tesktach ‐ symetrie, powtórzenia.
4. Geometria obliczeniowa: przynależność punktu do wielokąta, technika zamiatania, znajdowanie wypukłej otoczki, znajdowanie pary najmniej
odległych punktów.
5. Wielomiany i FFT: mnożenie wielomianów, dzielenie wielomianów, obliczanie wartości, interpolacja.
6. Randomizacja: algorytmy Monte Carlo i Las Vegas, problem maksymalnego przekroju, problem długiej ścieżki.
7. Algorytmy rozwiązujące problem pakowania pojemników.