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

Module name: Algorithms and Programming
Module code: 03-MO1S-19-AiP
Programme code: W4-S1MT19.2019
Semester: summer semester 2020/2021
Language of instruction: Polish
Form of verification: exam
ECTS credits: 6
Description:
1. Wprowadzenie do języków programowania; podział języków programowania; sposób wykonywania (kompilacja a interpretacja). 2. Podstawy programowania w języku Python. Instrukcje wejścia/wyjścia, wyrażenia arytmetyczne i logiczne, instrukcje warunkowe, instrukcje iteracyjne oraz zmienne i tablice (listy). 3. Podprogramy w języku Python - funkcje i procedury. 4. Elementy algorytmiki: problem i jego specyfikacja; algorytm i różne sposoby jego zapisu. 5. 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. 6. Algorytmy iteracyjne i rekurencyjne; metoda dziel i zwyciężaj. 7. Algorytmy klasyczne w tym m.in.: - obliczania wartości 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. 8. 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). 9. Implementacja poznanych algorytmów w języku Python.
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 podstawy wybranego języka programowania wyższego rzędu; projektuje, programuje i testuje programy w procesie rozwiązywania problemów; w programach stosuje: instrukcje wejścia/wyjścia, wyrażenia arytmetyczne i logiczne, instrukcje warunkowe, instrukcje iteracyjne, funkcje z parametrami i bez parametrów oraz zmienne i tablice, rekurencje [AiP_1]
 K_W08 [5/5] K_U26 [5/5] K_U27 [5/5] NI_W04 [5/5] NI_U04 [5/5]
zna różne metody i techniki programowania: podejście zachłanne, programowanie dynamiczne [AiP_10]
 K_W08 [3/5] NI_W03 [3/5] NI_U03 [3/5]
posiada umiejętność oceny ograniczeń narzędzi komputerowych [AiP_11]
 K_W08 [5/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_2]
 K_U26 [5/5] NI_U04 [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_3]
 K_W08 [5/5] K_U25 [5/5] K_U26 [5/5] NI_W03 [5/5]
zna i zapisuje klasyczne algorytmy 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 [AiP_4]
 K_W08 [5/5] NI_W03 [5/5] NI_U03 [5/5] NI_U04 [5/5]
zna podstawowe własności algorytmów; prezentuje przykłady zastosowań algorytmiki w innych dziedzinach nauki [AiP_5]
 K_W08 [3/5] NI_W03 [3/5] NI_U03 [3/5]
rozwija znajomość algorytmów i wykonuje eksperymenty z algorytmami; rozumie potrzebę programowania z użyciem zaawansowanych algorytmów [AiP_6]
 K_U25 [3/5] K_U27 [3/5] NI_W03 [3/5] NI_U03 [3/5] NI_K02 [3/5]
zna i rozumie pojęcie złożoności obliczeniowej (czasowej i pamięciowej) oraz notacji asymptotycznej [AiP_7]
 K_W08 [4/5] NI_W03 [4/5] NI_U03 [3/5]
zapisuje wybrane algorytmy klasyczne w postaci iteracyjnej oraz rekurencyjnej [AiP_8]
 K_U26 [5/5] NI_W03 [5/5] NI_U03 [5/5] NI_U04 [5/5]
porównuje działanie różnych algorytmów dla wybranego problemu, analizuje algorytmy na podstawie ich gotowych implementacji [AiP_9]
 K_U26 [4/5] K_U27 [4/5] NI_W03 [4/5] NI_U03 [4/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_10 AiP_3 AiP_4 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_2 AiP_4 AiP_8 AiP_9
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_11 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_1 AiP_10 AiP_4 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
 30
przyswojenie wiadomości z wykładu przy pomocy udostępnionych materiałów wykładowych; lektura uzupełniająca podręczników;
 20 egzamin [AiP_w_4]
laboratory classes [AiP_fs_2]
praca w laboratorium z wykorzystaniem komputera w oparciu o otwarte środowiska programistyczne
 30
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ń,
 25 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)