Uniwersytet Kazimierza Wielkiego - Centralny System Uwierzytelniania
Strona główna

Algorytmy i struktury danych 1300-Inf12AiSD-SP
Wykład (WYK) Semestr letni 2018/19

Informacje o zajęciach (wspólne dla wszystkich grup)

Liczba godzin: 30
Limit miejsc: (brak limitu)
Zaliczenie: Egzamin
Rygory zaliczenia zajęć: egzamin
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.
Metody dydaktyczne: metody pracy ze źródłami
metody problemowe
wykład konwersatoryjny
wykład kursowy
wykład w toku problemowym
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).

Grupy zajęciowe

zobacz na planie zajęć

Grupa Termin(y) Prowadzący Miejsca Liczba osób w grupie / limit miejsc Akcje
1 każdy wtorek, 15:30 - 17:00, sala 02
Andrey Grishkevich 73/76 szczegóły
Wszystkie zajęcia odbywają się w budynku:
Budynek przy ulicy M. Kopernika
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Kazimierza Wielkiego.
J.K. Chodkiewicza 30
85-064 Bydgoszcz
tel: +48 52 32 66 429 https://ukw.edu.pl
kontakt deklaracja dostępności USOSweb 7.0.3.0 (2024-03-22)