Analiza złożoności algorytmów Field of study: Biomedical Engineering
Programme code: 08-S1IB12.2015

Module name: Analiza złożoności algorytmów
Module code: 08-IBIMB-S1-AZA
Programme code: 08-S1IB12.2015
Semester: summer semester 2017/2018
Language of instruction: Polish
Form of verification: exam
ECTS credits: 1
Description:
Celem jest wprowadzenie słuchacza w zagadnienia związane z analizą algorytmów. Prezentowane są zagadnienia złożoności obliczeniowej ze szczególnym uwzględnieniem równań rekurencyjnych oraz paradygmaty konstruowania algorytmów (,,dziel i zwyciężaj’’, programowanie dynamiczne).
Prerequisites:
Podstawy matematyki dyskretnej, podstawy algorytmów i złożoności oraz podstawy programowania.
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 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). [k_1]
 W01 [4/5]
Ma wiedzę z zakresu metod rozwiązywania równań rekurencyjnych. [k_2]
 W12 [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. [k_3]
 W13 [2/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. [k_4]
 U24 [3/5]
Potrafi wyznaczyć złożoność obliczeniową algorytmów rekurencyjnych i zapisać ich złożoność w postaci równania rekurencyjnego. Potrafi rozwiązywać proste równania rekurencyjne. [k_5]
 U21 [3/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ń. [k_6]
 U01 [2/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. Potrafi planować i realizować terminowo różne zadania. [k_7]
 U25 [2/5]
Type Description Codes of the learning outcomes of the module to which assessment is related
Sprawozdania [k_w_1]
Rozwiązanie przez studentów zadań przydzielonych na laboratorium i przesłanie w formie sprawozdania w określonym terminie
 k_1 k_2 k_3 k_4 k_5 k_6 k_7
Form of teaching Student's own work Assessment of the learning outcomes
Type Description (including teaching methods) Number of hours Description Number of hours
laboratory classes [k_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ą.
 15
Samodzielne rozwiązywanie zadań; Przygotowanie sprawozdań z rozwiązanymi zadaniami w wersji elektronicznej i przesłanie ich w wyznaczonym terminie.
 15 Sprawozdania [k_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)