Algorytmy i struktury danych Field of study: Applied Computer Science
Programme code: 03-S1IS14.2015

Module name: Algorytmy i struktury danych
Module code: 03-IS-14-AiSD
Programme code: 03-S1IS14.2015
Semester:
  • winter semester 2017/2018
  • winter semester 2016/2017
Language of instruction: Polish
Form of verification: exam
ECTS credits: 5
Description:
Elementy algorytmiki: problem i jego specyfikacja; algorytm i różne sposoby jego zapisu. Elementy analizy algorytmów. Rozmiar danych, złożoność obliczeniowa (czasowa i pamięciowa). Typy złożoności: pesymistyczna, optymistyczna, średnia. Notacja asymptotyczna, rzędy wielkości funkcji. Algorytmy rekurencyjne, przykłady. Rozwiązywanie równań rekurencyjnych na potrzeby analizy algorytmów rekurencyjnych. Wyszukiwanie. Analiza wybranych metod: wyszukiwanie liniowe, wyszukiwanie binarne, wyszukiwanie interpolacyjne. Problem wyboru (selekcja). Sortowanie. Analiza wybranych algorytmów: sortowanie przez wstawianie, przez selekcję, przez scalanie, przez kopcowanie, szybkie. Model drzew decyzyjnych i twierdzenie o dolnym ograniczeniu na czas działania algorytmów sortujących za pomocą porównań. Sortowanie w czasie liniowym. Techniki projektowania algorytmów: dziel i zwyciężaj, programowanie dynamiczne, algorytmy zachłanne, przeszukiwanie z nawrotami. Ilustracja omawianych metod na konkretnych przykładach. Abstrakcyjne struktury danych: stosy, kolejki, kolejki priorytetowe, słowniki. Metody implementacji powyższych struktur (listy, kopce binarne, drzewa, drzewa poszukiwań binarnych) i ich zastosowania.
Prerequisites:
Moduł: Algorytmy i programowanie.
Key reading:
(no information given)
Learning outcome of the module Codes of the learning outcomes of the programme to which the learning outcome of the module is related [level of competence: scale 1-5]
zna pojęcie algorytmu i różne sposoby jego zapisu; zna podstawowe własności algorytmów; rozumie potrzebę dowodzenia poprawności semantycznej algorytmów [AISD_1]
 K_W01 [2/5]
zna i rozumie pojęcie złożoności obliczeniowej (czasowej i pamięciowej) oraz notacji asymptotycznej [AISD_2]
 K_W02 [2/5]
potrafi obliczać złożoność czasową prostych algorytmów, w tym algorytmów rekurencyjnych [AISD_3]
 K_U01 [5/5]
zna i potrafi zapisywać klasyczne algorytmy w postaci schematu blokowego, listy kroków, w pseudokodzie oraz w wybranym języku programowania; zna i omawia sytuacje, w których wykorzystuje się klasyczne algorytmy [AISD_4]
 K_U03 [5/5]
zna i potrafi stosować podstawowe techniki algorytmiczne (metoda ,,dziel i zwyciężaj'', programowanie dynamiczne, programowanie zachłanne, przeszukiwanie z nawrotami) [AISD_5]
 K_U03 [2/5]
zna podstawowe abstrakcyjne typy danych (stos, kolejka, kolejka priorytetowa, słownik) i ich realizacje komputerowe (listy, tablice, kopce binarne, drzewa, drzewa poszukiwań binarnych); potrafi konstruować proste algorytmy z wykorzystaniem poznanych struktur danych [AISD_6]
 K_U03 [3/5]
dostrzega związek pomiędzy czasem działaniem programu komputerowego a doborem różnych struktur danych i algorytmów w jego implementacji [AISD_7]
 K_W02 [4/5]
potrafi w sposób zrozumiały, w mowie i piśmie przedstawić poznaną wiedzę [AISD_8]
 K_U01 [2/5]
Type Description Codes of the learning outcomes of the module to which assessment is related
kolokwium [AISD_w_1]
termin kolokwium podany do wiadomości studentów dwa tygodnie wcześniej; zadania podobnego typu do zadań rozwiązywanych na konwersatorium;
 AISD_2 AISD_3 AISD_4 AISD_5 AISD_6 AISD_8
aktywność na zajęciach [AISD_w_2]
weryfikacja znajomości treści wykładów na podstawie pytań zadawanych przez prowadzącego konwersatorium; rozwiązywanie zadań; udział w dyskusji;
 AISD_1 AISD_2 AISD_3 AISD_4 AISD_5 AISD_6 AISD_7 AISD_8
bieżąca ocena realizacji zajęć [AISD_w_3]
weryfikacja umiejętności na podstawie analizy rozwiązań zadań
 AISD_4 AISD_5 AISD_6 AISD_7
projekt [AISD_w_4]
realizacja projektu zaproponowanego przez prowadzącego laboratorium lub studenta za zgodą koordynatora modułu
 AISD_4 AISD_5 AISD_6 AISD_7
egzamin ustny lub pisemny [AISD_w_5]
warunkiem przystąpienia do egzaminu jest zaliczenie konwersatorium oraz laboratorium; weryfikacja znajomości pojęć i faktów w oparciu o analizę odpowiedzi na pytania egzaminacyjne o charakterze teoretycznym; zakres materiału – wszystkie zagadnienia omawiane na module;
 AISD_1 AISD_2 AISD_4 AISD_5 AISD_8
Form of teaching Student's own work Assessment of the learning outcomes
Type Description (including teaching methods) Number of hours Description Number of hours
lecture [AISD_fs_1]
wykład, z wykorzystaniem pomocy audiowizualnych, prezentujący pojęcia i fakty z zakresu treści programowych wymienionych w opisie modułu i ilustrujący je licznymi przykładami
 30
samodzielne studiowanie wykładów i wskazanej w sylabusie literatury pomocniczej
 20 kolokwium [AISD_w_1] aktywność na zajęciach [AISD_w_2] bieżąca ocena realizacji zajęć [AISD_w_3] egzamin ustny lub pisemny [AISD_w_5]
discussion classes [AISD_fs_2]
konwersatorium, w trakcie którego studenci rozwiązują, pod kierunkiem prowadzącego, zadania kształtujące umiejętności wymienione w zestawie efektów kształcenia modułu
 15
przyswojenie wiedzy z wykładów; praca z podręcznikiem i zbiorami zadań; samodzielne rozwiązywanie zadań domowych ; rozwiązywanie zadań przy tablicy
 15 kolokwium [AISD_w_1] aktywność na zajęciach [AISD_w_2]
laboratory classes [AISD_fs_3]
Laboratorium, w trakcie którego studenci implementują, pod kierunkiem prowadzącego, algorytmy omawiane w trakcie modułu
 30
implementacja algorytmów, omawianych na wykładzie oraz konwersatorium, w wybranym języku programowania wysokiego poziomu. Samodzielne pisanie programów na komputerze.
 30 aktywność na zajęciach [AISD_w_2] bieżąca ocena realizacji zajęć [AISD_w_3] projekt [AISD_w_4]
Attachments
Module description (PDF)
Information concerning module syllabuses might be changed during studies.
Syllabuses (USOSweb)
Semester Module Language of instruction
(no information given)