Algorithms and complexity theory Kierunek studiów: Informatyka
Kod programu: W4-S1IN19.2021

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. [AACT_K_7]

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. [AACT_U_4]

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. [AACT_U_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ń. [AACT_U_6]

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). [AACT_W_1]

Ma wiedzę z zakresu metod rozwiązywania równań rekurencyjnych w tym metody przez podstawienie, metod iteracyjnych oraz twierdzenia o rekurencji uniwersalnej. [AACT_W_2]

Ma wiedzę z zakresu podstawowych paradygmatów konstruowania algorytmów, takich jak ,,dziel i zwyciężaj’’, programowania dynamicznego oraz strategii zachłannych. 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. [AACT_W_3]

Rozwiązanie przez studentów zadań przydzielonych na laboratorium i przesłanie w formie sprawozdania w określonym terminie

Weryfikacja wiedzy w oparciu o treści prezentowane na wykładzie. Egzamin składa się z pytań otwartych z teorii oraz przynajmniej dwóch zadań z treścią.

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

Zapoznanie się z tematyką wykładu z wykorzystaniem: przygotowanego skryptu do przedmiotu, wskazanej dodatkowej literatury i źródeł internetowych.

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ą.

Przygotowanie studenta do laboratorium. Samodzielne rozwiązywanie zadań; Przygotowanie sprawozdań z rozwiązanymi zadaniami w wersji papierowej i oddanie ich w wyznaczonym terminie.