Literatura uzupelniająca: |
1. Cormen T. H. , Leiserson C. E. , Rivest R. L. , Stein C. Wprowadzenie do algorytmów. Wydawnictwo Naukowo - Techniczne.
2. Jamro M. Struktury danych i algorytmy w języku C#. Projektowanie efektywnych aplikacji.
3. Weiss M. A. , Data Structures and Algorithm Analysis in C++, Pearson Education 2014.
|
Literatura: |
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.
4. Czech Z. Wprowadzenie do obliczeń równoległych. Warszawa.
5. Karbowski A. Programowanie równoległe i rozproszone.
|
Efekty uczenia się: |
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)
|
Metody i kryteria oceniania: |
Egzamin pisemny, sumaryczna liczba uzyskanych punktów (9-24% ocena 3.0; 25-39% ocena 3.5; 40-54% 4.0; 55-69% 4.5; 70-100% 5.0).
Egzamin 0: liczba uzyskanych punktów (1 punkt ocena 3.0; 2 3.5; 3 4.0; 4 4.5; 5 5.0.
Egzamin 1: liczba uzyskanych punktów (3,4 punkt ocena 3.0; 5,6 3.5; 7,8 4.0; 9,10 4.5; 11,12 5.0.
Egzamin 2: liczba uzyskanych punktów (8 punktów ocena 3.0; 9 3.5; 10 4.0; 11 4.5; 12 5.0.
|
Zakres tematów: |
1. Rekurencja (silnia, ciąg Fibonacciego).
2. Algorytmy sortujące (sortowanie bąbelkowe, sortowanie przez wstawianie, sortowanie szybkie, sortowanie przez kopcowanie).
3. Podstawowe pojęcia kombinatoryczne (reguła mnożenia, permutacja, wariacja, kombinacja, dwumian Newtona). Algorytmy kombinatoryczne (algorytmy generujące permutacje, kombinacje).
4. Złożoność obliczeniowa (notacja asymptotyczna). Klasy P i NP. Algorytmy równoległe i rozproszone. Ocena algorytmów równoległych (prawo Amdahla oraz Gustafsona-Barsisa).
5. Struktury danych. Listy (jednokierunkowa, stos, dwukierunkowa, cykliczna), kolejki, sterta.
6. Drzewa i ich reprezentacje. Drzewa binarne i wyrażenia arytmetyczne. Uniwersalna struktura słownikowa
7. Algorytmy grafowe (przechodzenie po grafie, przeszukiwanie grafu w głąb i wszerz, poszukiwanie najkrótszej drogi w grafie – algorytm Dijkstry, minimalne (maksymalne) drzewo rozpinające – algorytmy Prima i Kruskala).
|