Algorytmy i struktury danych Kierunek studiów: Informatyka stosowana
Kod programu: 03-S1IS14.2014

Nazwa modułu: Algorytmy i struktury danych
Kod modułu: 03-IS-14-AiSD
Kod programu: 03-S1IS14.2014
Semestr: semestr zimowy 2015/2016
Język wykładowy: polski
Forma zaliczenia: egzamin
Punkty ECTS: 5
Opis:
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.
Wymagania wstępne:
Moduł: Algorytmy i programowanie.
Literatura podstawowa:
(brak informacji)
Efekt modułowy Kody efektów kierunkowych do których odnosi się efekt modułowy [stopień realizacji: skala 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]
Typ Opis Kody efektów modułowych do których odnosi się sposób weryfikacji
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
Rodzaj prowadzonych zajęć Praca własna studenta Sposoby weryfikacji
Typ Opis (z uwzględnieniem metod dydaktycznych) Liczba godzin Opis Liczba godzin
wykład [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]
konwersatorium [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]
laboratorium [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]
Załączniki
Opis modułu (PDF)
Informacje o sylabusach mogą ulec zmianie w trakcie trwania studiów.
Sylabusy (USOSweb)
Semestr Moduł Język wykładowy
(brak danych)