Algorithms and data structures Field of study: Mathematics
Programme code: W4-S2MT19.2022

Module name: Algorithms and data structures
Module code: W4-MT-S2-22-AiSD
Programme code: W4-S2MT19.2022
Semester: winter semester 2022/2023
Language of instruction: Polish
Form of verification: exam
ECTS credits: 5
Description:
Celem modułu jest zapoznanie studentów z wybranymi strukturami danych oraz omówienie wybranych algorytmów i metod konstruowania algorytmów. W trakcie laboratoriów, które będą odbywały się w pracowni komputerowej, studenci będą mieli możliwość napisania programów wykorzystujących omawiany materiał. Natomiast w trakcie konwersatoriów, odbywających się w klasycznej sali tablicowej, będzie możliwość głębszego i teoretycznego omówienia stosownego materiału. 1. Elementy algorytmiki: problem i jego specyfikacja; algorytm i różne sposoby jego zapisu. 2. 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. 3. Algorytmy iteracyjne i rekurencyjne; metoda dziel i zwyciężaj. 4. Porównanie programowania strukturalnego i obiektowego w rozwiązywaniu problemów. 5. Rozwiązywanie równań rekurencyjnych na potrzeby analizy algorytmów rekurencyjnych. 6. Omówienie wybranych problemów i algorytmów w tym m.in. tych wymienionych w Podstawie programowej kształcenia ogólnego przedmiotu Informatyka w szkole ponadpodstawowej, w szczególności: - obliczania wartości wielomianu za pomocą schematu Hornera, - algorytmy Euklidesa w wersji iteracyjnej i rekurencyjnej wraz z zastosowaniami, - operujące na liczbach (generowania liczb pierwszych metodą sita Eratostenesa, badania pierwszości liczby, rozkładania liczby na czynniki pierwsze, zamiany reprezentacji liczb między pozycyjnymi systemami liczbowymi, działań na ułamkach z wykorzystaniem NWD i NWW), - operujące na tekstach (porównywania tekstów, wyszukiwania wzorca w tekście metodą naiwną, szyfrowania tekstu metodą Cezara i przestawieniową), - wyszukiwania elementów w dowolnej tablicy (wyszukiwanie sekwencyjne) oraz w tablicy uporządkowanej (wyszukiwanie binarne), - sortujące (sortowanie przez wstawianie, przez wybieranie, bąbelkowe, przez scalanie, szybkie), - znajdowania określonego elementu w zbiorze: maksymalnego, lidera oraz idola, - jednoczesnego wyszukiwania elementu najmniejszego i największego, - szybkiego potęgowania, - badania przecinania się odcinków, przynależności punktu do wielokąta wypukłego, - rekurencyjnego tworzenia fraktali: zbiór Cantora, drzewo binarne, dywan Sierpińskiego, płatek Kocha, - metodę Monte Carlo (obliczanie przybliżonej wartości liczby π, symulacja ruchów Browna). 7. Różne metody i techniki programowania: - podejście zachłanne (wydawania reszty najmniejszą liczbą nominałów, pakowanie plecaka), - programowanie dynamiczne (pakowanie plecaka, szukania najdłuższego wspólnego podciągu). 8. Abstrakcyjne struktury danych: stosy, kolejki, kolejki priorytetowe, słowniki. Metody implementacji powyższych struktur (tablice, listy dowiązane, kopce binarne, drzewa, drzewa poszukiwań binarnych) i ich zastosowania (np. do zamiany klasycznego wyrażenia na postać w odwrotnej notacji polskiej i obliczanie jego wartości na podstawie tej postaci). 9. Wybrane algorytmy grafowe. 10. Model drzew decyzyjnych i twierdzenie o dolnym ograniczeniu na czas działania algorytmów sortujących za pomocą porównań. Sortowanie w czasie liniowym.
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]
zna i zapisuje klasyczne algorytmy, w postaci iteracyjnej oraz rekurencyjnej, za pomocą listy kroków, schematu blokowego lub pseudokodu oraz implementuje je wybranym języku programowania; zna i omawia sytuacje, w których wykorzystuje się klasyczne algorytmy [AiSD_1]
 NI_W04 [3/5] NI_U05 [5/5]
zna podstawowe własności algorytmów; prezentuje przykłady zastosowań algorytmiki w innych dziedzinach nauki [AiSD_2]
 NI_W04 [3/5]
zna i rozumie pojęcie złożoności obliczeniowej (czasowej i pamięciowej) oraz notacji asymptotycznej [AiSD_3]
 NI_W04 [3/5]
porównuje działanie różnych algorytmów dla wybranego problemu, analizuje algorytmy na podstawie ich gotowych implementacji [AiSD_4]
 NI_U04 [5/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_5]
 NI_W04 [4/5] NI_U04 [4/5]
dostrzega związek pomiędzy czasem działaniem programu komputerowego a doborem różnych struktur danych i algorytmów w jego implementacji; do realizacji rozwiązania problemu dobiera odpowiednią metodę lub technikę algorytmiczną i struktury danych [AiSD_6]
 NI_W04 [4/5]
projektuje i tworzy rozbudowane programy w procesie rozwiązywania problemów, wykorzystuje w programach dobrane do algorytmów struktury danych, w tym struktury dynamiczne i korzysta z dostępnych bibliotek dla tych struktur [AiSD_7]
 KN_U05 [2/5] NI_U04 [2/5]
Type Description Codes of the learning outcomes of the module to which assessment is related
kolokwium na konwersatorium [AiSD_w_1]
Kolokwium pisemne; zadania podobnego typu do zadań rozwiązywanych w trakcie zajęć konwersatoryjnych
 AiSD_1 AiSD_3 AiSD_5
kolokwia na laboratorium [AiSD_w_2]
Kolokwium dotyczące zadań programistycznych; zadania podobnego typu do zadań rozwiązywanych w trakcie zajęć laboratoryjnych
 AiSD_1 AiSD_5 AiSD_6
zadania domowe [AiSD_w_3]
ocena zadań domowych; możliwość odpytania z wybranych zagadnień/zadań zadanych na pracę w domu
 AiSD_1 AiSD_2 AiSD_3 AiSD_4 AiSD_5 AiSD_6 AiSD_7
egzamin [AiSD_w_4]
Egzamin pisemny lub ustny. 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
 AiSD_1 AiSD_2 AiSD_3 AiSD_5
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_fpz1]
wykład z wykorzystaniem pomocy audiowizualnych
 15
przyswojenie wiadomości z wykładu przy pomocy udostępnionych materiałów wykładowych; lektura uzupełniająca podręczników
 30 egzamin [AiSD_w_4]
laboratory classes [AiSD_fpz_2]
praca w laboratorium z wykorzystaniem komputera w oparciu o otwarte środowiska programistyczne
 15
praca własna z wykorzystaniem ogólnodostępnego oprogramowania, doskonalenie umiejętności zdobytych podczas zajęć
 50 kolokwia na laboratorium [AiSD_w_2] zadania domowe [AiSD_w_3]
discussion classes [AiSD_fpz_3]
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 i konwersatorium, samodzielna praca ze zbiorami zadań
 25 kolokwium na konwersatorium [AiSD_w_1] zadania domowe [AiSD_w_3]
Attachments
Module description (PDF)
Information concerning module syllabuses might be changed during studies.
Syllabuses (USOSweb)
Semester Module Language of instruction
(no information given)