Algorithms and data structers Field of study: Computer Science
Programme code: 08-S1INI12.2015

Module name: Algorithms and data structers
Module code: 08-IO1S-13-AISD
Programme code: 08-S1INI12.2015
Semester: winter semester 2016/2017
Language of instruction: Polish
Form of verification: exam
ECTS credits: 4
Description:
Celem jest wprowadzenie słuchacza w zagadnienia algorytmów i struktur danych. Prezentowane są zagadnienia złożoności obliczeniowej, paradygmaty konstruowania algorytmów (,,dziel i zwyciężaj’’, programowanie dynamiczne), podstawowe algorytmy dla wybranych problemów obliczeniowych, np. sortowanie, wyszukiwanie, a także różne struktury danych (tablice, rekordy, kopce, listy, zbiory) pomocne podczas implementowania algorytmów.
Prerequisites:
(no information given)
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]
Ma świadomość znacznego wpływu cech algorytmów (złożoności, poprawności), na podstawie których zbudowane są elementy składowe (moduły, funkcje, procedury) większych systemów programowych na końcową sprawność , poprawność działania i bezpieczeństwo tych systemów. [AISD_K_9]
 K_1_A_I_K06 [1/5]
Potrafi wyznaczyć złożoności pesymistyczne i średnie (czasowe i pamięciowe) zadanych, niebanalnych algorytmów. Potrafi porównać grupę algorytmów przeznaczonych do rozwiązania wybranego problemu, wybrać algorytm najlepszy oraz odrzucić algorytmy wymagających zbyt dużych zasobów komputera niezbędnych do ich wykonania. [AISD_U_5]
 K_1_A_I_U08 [1/5] K_1_A_I_U18 [4/5]
Potrafi zaprojektować i zaimplementować struktury danych oraz część algorytmiczną rozwiązujące zadany, niebanalny problem obliczeniowy (bądź zaadaptować znany algorytm przeznaczony do rozwiązania podobnego problemu). [AISD_U_6]
 K_1_A_I_U15 [2/5]
Potrafi zaimplementować zadany, niebanalny algorytm podany w pseudokodzie w wybranym języku programowania, projektując właściwe struktury danych. Ma umiejętność prowadzenia badań mających na celu eksperymentalne potwierdzenie poprawności działania algorytmu oraz określenie jego efektywności (czasu działania, wymagań pamięciowych). [AISD_U_7]
 K_1_A_I_U15 [2/5] K_1_A_I_U17 [1/5]
Potrafi dokonać oceny przyjętych rozwiązań algorytmicznych oraz założonych struktur danych w systemie informatycznym o małej i średniej złożoności. Ma umiejętność wskazania zalet i wad przyjętych rozwiązań. [AISD_U_8]
 K_1_A_I_U23 [1/5]
Ma wiedzę za zakresu metod wyznaczania złożoności obliczeniowej algorytmów, w tym złożoności czasowej, pamięciowej, średniej, pesymistycznej. Zna podstawowe notacje (O, Omega, Teta) dla szacowania rzędu funkcji. Zna i rozumie podstawowe klasy złożoności algorytmów, takie jak wielomianowe (P), wykładnicze (NP-zupełne, NP-trudne). [AISD_W_1]
 K_1_A_I_W01 [1/5] K_1_A_I_W02 [2/5]
Ma wiedzę z zakresu podstawowych paradygmatów konstruowania algorytmów, takich jak ,,dziel i zwyciężaj’’ oraz programowania dynamicznego. Zna i rozumie podstawy działania oraz wady i zalety algorytmów konstruowanych za pomocą wymienionych paradygmatów. Potrafi podać przykłady algorytmów opartych na poszczególnych paradygmatach. [AISD_W_2]
 K_1_A_I_W09 [4/5] K_1_A_I_W10 [1/5]
Ma wiedzę z zakresu algorytmów sortowania. Zna i rozumie działanie wybranych algorytmów sortowania o zbożności kwadratowej (sortowanie przez wybieranie, przez wstawianie) oraz o zaawansowanych algorytmów o złożoności liniowo-logarytmicznej (sortowanie szybkie, przez łączenie, przez kopcowanie). [AISD_W_3]
 K_1_A_I_W09 [4/5] K_1_A_I_W10 [1/5]
Ma wiedzę z zakresu podstawowych struktur danych pomocnych do konstruowania algorytmów. W szczególności potrafi scharakteryzować takie struktury danych jak stos, listy liniowe (jedno- i dwukierunkowe), nieco bardziej złożone struktury listowe, struktury do reprezentowania zbiorów, w tym kopce, drzewa wyszukiwań binarnych. [AISD_W_4]
 K_1_A_I_W09 [4/5] K_1_A_I_W10 [1/5]
Type Description Codes of the learning outcomes of the module to which assessment is related
Egzamin [AISD_w_1]
Weryfikacja wiedzy prezentowanej na wykładzie dotyczącej złożoności obliczeniowej algorytmów, paradygmatów konstruowania algorytmów oraz działania wybranych algorytmów. Weryfikacja odbywa się przez odpowiedzi na pytania związane z wymienionymi zagadnieniami. Weryfikacja umiejętności praktycznych dotyczących projektowania struktur danych oraz wyznaczania złożoności obliczeniowej algorytmów przez rozwiązanie dwóch zadań z treścią.
AISD_K_9 AISD_U_5 AISD_U_6 AISD_U_7 AISD_U_8 AISD_W_1 AISD_W_2 AISD_W_3 AISD_W_4
Prace kontrolne [AISD_w_2]
Prace kontrolne dotyczące treści oraz zadań prezentowanych na ćwiczeniach.
 AISD_K_9 AISD_U_5 AISD_U_6 AISD_U_7 AISD_U_8 AISD_W_1 AISD_W_2 AISD_W_3 AISD_W_4
Form of teaching Student's own work Assessment of the learning outcomes
Type Description (including teaching methods) Number of hours Description Number of hours
practical classes [AISD_fs_1]
Szczegółowe przygotowanie studentów do rozwiązywania zadań ze wskazaniem na metodologię postępowania, wskazaniem kolejności wykonywanych czynności. Rozwiązywanie zadań z treścią.
 30
Rozwiązywanie zadań z poszczególnych tematów wraz z analizą rozwiązań już istniejących – w skrypcie i na stronach internetowych.
 30 Prace kontrolne [AISD_w_2]
lecture [AISD_fs_2]
Przekazanie treści kształcenia w formie werbalnej z wykorzystaniem środków audiowizualnych oraz innych pisemnych pomocy dydaktycznych. Zwracanie uwagi na zagadnienia trudniejsze w zrozumieniu oraz o głębszych podstawach teoretycznych. Aktywizacja słuchaczy przez zadawanie pytań dotyczących przekazywanych treści. Odnotowywanie aktywności studentów.
 30
Zapoznanie się z zagadnieniami poruszanymi na wykładzie, korzystając z przygotowanego skryptu, wskazanej literatury źródeł dostępnych w Internecie.
 30 Egzamin [AISD_w_1]
Attachments
Module description (PDF)
Information concerning module syllabuses might be changed during studies.
Syllabuses (USOSweb)
Semester Module Language of instruction
(no information given)