Algorytmy i struktury danych 1300-Inf12AiSD-SP
Laboratorium (LAB) Semestr letni 2018/19

1. Wróblewski P. Algorytmy struktury danych i techniki programowania. Helion.

2. Banachowski L. , Diks K. , Rytter W. Algorytmy i struktury danych. Wydawnictwo Naukowo - Techniczne.

3. Lipski W. Kombinatoryka dla programistów. Wydawnictwo Naukowo - Techniczne.

WIEDZA:

W1 : Ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie algorytmów rekurencyjnych, sortowania, na grafach i ich złożoności obliczeniowej (K_W06)

W2 : Ma szczegółową wiedzę nt. struktur danych: list (jednokierunkowy, stos, dwukierunkowy, cykliczny), sterta, drzewo, graf (K_W08)

W3 : Zna podstawowe metody, techniki i narzędzia stosowane do przyspieszenia obliczeń (liczby Pi metodą całkowania numerycznego) przy obliczeniach (sekwencyjnych / równoległych) na komputerach (K_W10)

UMIEJĘTNOŚCI:

U1 : Potrafi pozyskiwać opis algorytmów (rekurencyjnych, sortowania, teorii grafów, równoległych) i struktur danych (sterta, list, stos, drzewo, graf) z literatury, Internet, wykładów; potrafi integrować uzyskane informacje, dokonywać ich interpretacji, a także wyciągać wnioski oraz formułować i uzasadniać opinie i na tej podstawie opracowywać programy komputerowe (KU01)

U2 : Potrafi wykorzystać nabytą wiedzę do algorytmicznego opisu procesów w sposób sekwencyjny, rekurencyjny ili równoległy; uzasadnić wykorzystanie struktur danych (tabela, sterta, list, drzewo, graf) w celu zmniejszenia złożoności obliczeniowej (K_U07)

U3 : Ma umiejętność formułowania algorytmów i ich programowania z użyciem C# (K_U11)

U4 : Potrafi ocenić złożoność obliczeniową algorytmów sortowania i zmierzyć czas obliczania liczby Pi za pomocą algorytmu sekwencyjnego / równoległego (K_U13)

Opracowanie programów i sprawozdań w trakcie pracy w laboratorium, sumaryczna liczba (1 program / sprawozdanie ocena 3.0; 2,3 3.5; 4,5 4.0; 6,7 4.5; 8,9 5.0).

1. Czas obliczania liczby Pi metodą całkowania numerycznego (sekwencyjne (różne tryby), równoległe).

2. Rekurencja (silnia, ciąg Fibonacciego, zapis binarna liczby).

3. Sortowanie (bąbelkowe, sortowanie przez wstawianie, sortowanie szybkie, sortowanie przez kopcowanie).

4. Sterta.

5. Lista (jednokierunkowa, stos, dwukierunkowa).

6. Drzewa. Drzewa binarne i wyrażenia arytmetyczne. Uniwersalna struktura słownikowa

7. Grafy (poszukiwanie najkrótszej drogi w grafie – algorytm Dijkstry, minimalne (maksymalne) drzewo rozpinające – algorytmy Prima i Kruskala).