Algorithms and Programming Field of study: Mathematics
Programme code: W4-S1MT19.2022

Module name: Algorithms and Programming
Module code: W4-MT-S1-21-AiP
Programme code: W4-S1MT19.2022
Semester: summer semester 2023/2024
Language of instruction: Polish
Form of verification: exam
ECTS credits: 7
Description:
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. Algorytmy klasyczne w tym m.in.: - obliczania pochodnej wielomianu za pomocą schematu Hornera, - algorytmy Euklidesa w wersji iteracyjnej i rekurencyjnej wraz z zastosowaniami, - operujące na liczbach (badania pierwszości liczby, 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 (algorytm sekwencyjny) oraz w tablicy uporządkowanej (metoda wyszukiwania binarnego) - sortujące (sortowanie przez wstawianie, przez wybieranie, bąbelkowe, przez scalanie, szybkie), - znajdowania określonego elementu w zbiorze: maksymalnego, lidera oraz idola, - generowania liczb pierwszych metodą sita Eratostenesa, - jednoczesnego wyszukiwania elementu najmniejszego i największego (algorytm iteracyjny oraz rekurencyjny wykorzystujący metodę dziel i zwyciężaj), - szybkiego potęgowania liczb w wersji iteracyjnej i rekurencyjnej, - problem wież z Hanoi (rozwiązanie rekurencyjne). 5. 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), - algorytmy z nawrotami (problem n-hetmanów). 6. Implementacja poznanych algorytmów w wybranym języku programowania wysokiego poziomu.
Prerequisites:
Brak
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]
testuje na komputerze swoje programy pod względem zgodności z przyjętymi założeniami i ewentualnie je poprawia, objaśnia przebieg działania programów [AiP_1]
 K_U26 [5/5] KN_I_U04 [5/5]
posiada umiejętność oceny ograniczeń narzędzi komputerowych [AiP_10]
 K_W08 [5/5]
formułuje problem w postaci specyfikacji (czyli opisuje dane i wyniki) i wyróżnia kroki w algorytmicznym rozwiązywaniu problemów; zna pojęcie algorytmu i stosuje różne sposoby przedstawiania algorytmów, w tym w języku naturalnym, w postaci schematów blokowych, listy kroków, w pseudokodzie oraz w wybranym języku programowania [AiP_2]
 K_W08 [5/5] K_U25 [5/5] K_U26 [5/5] KN_I_W03 [5/5] KN_I_U03 [5/5] KN_I_U04 [5/5]
zna i zapisuje klasyczne algorytmy za pomocą listy kroków, schematu blokowego lub pseudokodu oraz implementuje je w wybranym języku programowania; zna i omawia sytuacje, w których wykorzystuje się klasyczne algorytmy [AiP_3]
 K_W08 [5/5] KN_I_W03 [5/5] KN_I_U03 [5/5] KN_I_U04 [5/5]
zna podstawowe własności algorytmów; prezentuje przykłady zastosowań algorytmiki w innych dziedzinach nauki [AiP_4]
 K_W08 [3/5] KN_I_W03 [3/5] KN_I_U03 [3/5]
rozwija znajomość algorytmów i wykonuje eksperymenty z algorytmami; rozumie potrzebę programowania z użyciem zaawansowanych algorytmów [AiP_5]
 K_U25 [3/5] K_U27 [3/5] KN_I_W03 [3/5] KN_I_U03 [3/5] KN_I_K02 [3/5]
zna i rozumie pojęcie złożoności obliczeniowej (czasowej i pamięciowej) oraz notacji asymptotycznej [AiP_6]
 K_W08 [4/5] KN_I_W03 [4/5] KN_I_U03 [4/5]
zapisuje wybrane algorytmy klasyczne w postaci iteracyjnej lub/oraz rekurencyjnej [AiP_7]
 K_U26 [5/5] KN_I_W03 [5/5] KN_I_U03 [5/5] KN_I_U04 [5/5]
porównuje działanie różnych algorytmów dla wybranego problemu, analizuje algorytmy na podstawie ich gotowych implementacji [AiP_8]
 K_U26 [4/5] K_U27 [4/5] KN_I_W03 [4/5] KN_I_U03 [4/5]
zna różne metody i techniki programowania: podejście zachłanne, programowanie dynamiczne, programowanie z nawrotami [AiP_9]
 K_W08 [3/5] KN_I_W03 [3/5] KN_I_U03 [3/5]
Type Description Codes of the learning outcomes of the module to which assessment is related
kolokwium na konwersatorium [AiP_w_1]
Kolokwium pisemne na ostatnich lub przedostatnich zajęciach; zadania podobnego typu do zadań rozwiązywanych w trakcie zajęć konwersatoryjnych
 AiP_2 AiP_3 AiP_6 AiP_7 AiP_8 AiP_9
kolokwia na laboratorium [AiP_w_2]
Dwa kolokwia w semestrze; zadania podobnego typu do zadań rozwiązywanych w trakcie zajęć laboratoryjnych
 AiP_1 AiP_3 AiP_7 AiP_8
zadania domowe [AiP_w_3]
ocena zadań domowych; możliwość odpytania z wybranych zagadnień/zadań zadanych na pracę w domu
 AiP_1 AiP_10 AiP_2 AiP_3 AiP_4 AiP_5 AiP_6 AiP_7 AiP_8 AiP_9
egzamin [AiP_w_4]
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
 AiP_3 AiP_6 AiP_7 AiP_8 AiP_9
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 [AiP_fs_1]
wykład z wykorzystaniem pomocy audiowizualnych
 25
przyswojenie wiadomości z wykładu przy pomocy udostępnionych materiałów wykładowych; lektura uzupełniająca podręczników;
 25 egzamin [AiP_w_4]
laboratory classes [AiP_fs_2]
praca w laboratorium z wykorzystaniem komputera w oparciu o otwarte środowiska programistyczne
 20
praca własna z wykorzystaniem ogólnodostępnego oprogramowania, doskonalenie umiejętności zdobytych podczas zajęć
 50 kolokwia na laboratorium [AiP_w_2] zadania domowe [AiP_w_3]
discussion classes [AiP_fs_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, samodzielna praca ze zbiorami zadań,
 40 kolokwium na konwersatorium [AiP_w_1] zadania domowe [AiP_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)