Algorithms, Data Structures and Numerical Methods Field of study: Technical Physics
Programme code: 03-S1FT12.2017

Module name: Algorithms, Data Structures and Numerical Methods
Module code: 0305-1FT-17-48
Programme code: 03-S1FT12.2017
Semester: winter semester 2019/2020
Language of instruction: Polish
Form of verification: exam
ECTS credits: 4
Description:
Na wykładzie student zapoznaje się z następującymi zagadnieniami: • Elementy analizy algorytmów: koszty realizacji algorytmów. • Rozmiar danych, złożoność czasowa i pamięciowa. • Algorytmy iteracyjne i rekurencyjne: przykłady algorytmów iteracyjnych (obliczanie silni, sumowanie, mnożenie), przykłady algorytmów rekurencyjnych (obliczanie silni, jednoczesne wyszukiwanie minimum i maksimum w ciągu, wieże Hanoi); rozwiązywanie równań rekurencyjnych na potrzeby analizy algorytmów rekurencyjnych; algorytmy oparte na metodzie ,,dziel i zwyciężaj”. • Programowanie dynamiczne: analiza wybranych algorytmów: obliczanie liczb Fibonacciego, problem mnożenia ciągu macierzy, problem najdłuższego wspólnego podciągu. • Wyszukiwanie: analiza wybranych algorytmów: wyszukiwanie liniowe, wyszukiwanie binarne; 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 dowolnego algorytmu sortującego za pomocą porównań; sortowanie w czasie liniowym. Abstrakcyjne struktury danych: stosy, kolejki FIFO, kolejki priorytetowe, słowniki; metody implementacji powyższych struktur (listy, kopce binarne, drzewa poszukiwań binarnych) i ich zastosowania. • Metody numeryczne: algorytmy różniczkowania i całkowania numerycznego, metody interpolacji i aproksymacji, numeryczne rozwiązywanie równań liniowych i nieliniowych, numeryczne rozwiązywanie układów równań liniowych; metody numerycznego całkowania równań różniczkowych; dyskretna i szybka transformata Fouriera; numeryczna algebra macierzy. Na zajęciach laboratoryjnych studenci analizują i matematycznie uzasadniają znane algorytmy, przygotowują własne algorytmy do rozwiązania szczegółowych problemów z zakresu fizyki i techniki. Mają możliwość wykorzystania komputerów do kodowania algorytmów w wybranym języku programowania wysokiego poziomu. Przedmiot obowiązkowy dla specjalności Modelowanie komputerowe, wykład zakończony egzaminem
Prerequisites:
Konieczne moduły: 1FT_07 i 1FT_07. Pomocniczo zaleca się także moduły: 1FT_08, 1FT_10, 1FT_01, 1FT_02 i FT_03.
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 podstawowe algorytmy sortowania, wyszukiwania i obliczeń numerycznych oraz ich matematyczne uzasadnienia [1FT_48_1]
 KFT_W02 [5/5] KFT_W08 [5/5]
zna abstrakcyjne struktury danych wykorzystywane w algorytmach i ich implementacjach [1FT_48_2]
 KFT_W08 [5/5]
ma wiedzę na temat złożoności obliczeniowej algorytmów [1FT_48_3]
 KFT_W08 [5/5]
zna podstawowe zastosowania poznanych algorytmów, w szczególności w fizyce i technice [1FT_48_4]
 KFT_W09 [4/5] KFT_W08 [4/5]
potrafi wykazać poprawność podstawowych algorytmów na gruncie matematyki [1FT_48_5]
 KFT_U02 [5/5]
potrafi zaprojektować odpowiednie struktury danych podstawowych algorytmów [1FT_48_6]
 KFT_U02 [5/5] KFT_U08 [5/5]
potrafi przeanalizować podstawowe algorytmy i oszacować ich złożoność [1FT_48_7]
 KFT_U02 [5/5] KFT_U08 [5/5]
potrafi zapisać podstawowe algorytmy w pseudokodzie i w wybranym języku programowania wysokiego poziomu oraz wybrać odpowiednie metody algorytmiczne do rozwiązania typowych problemów obliczeniowych, ze szczególnym uwzględnieniem zastosowań w fizyce i technice [1FT_48_8]
 KFT_U11 [4/5] KFT_U06 [4/5] KFT_U08 [4/5]
Type Description Codes of the learning outcomes of the module to which assessment is related
kolokwium [1FT_48_w_1]
dwa razy w semestrze; termin kolokwium podany do wiadomości studentów dwa tygodnie wcześniej; zadania podobnego typu do zadań rozwiązywanych w trakcie konwersatorium; skala ocen 2-5; średnia ocen z kolokwiów stanowi podstawę do zaliczenia konwersatorium;
1FT_48_1 1FT_48_2 1FT_48_3 1FT_48_4 1FT_48_5 1FT_48_6 1FT_48_7 1FT_48_8
egzamin pisemny [1FT_48_w_2]
Egzamin obowiązkowy dla sp. Modelowanie komputerowe Warunkiem przystąpienia do egzaminu jest zaliczenie konwersatorium; zakres materiału – wszystkie zagadnienia omawiane na wykładach; skala ocen 2-5;
1FT_48_1 1FT_48_2 1FT_48_3 1FT_48_4 1FT_48_5 1FT_48_6 1FT_48_7 1FT_48_8
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 [1FT_48_fs_1]
wykład wybranych zagadnień 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 pisemny [1FT_48_w_2]
discussion classes [1FT_48_fs_2]
rozwiązywanie zadań na tablicy: analiza i matematyczne uzasadnienie znanych algorytmów, przygotowywanie własnych algorytmów do rozwiązania szczegółowych problemów z zakresu fizyki i techniki - wybór metody, przeprowadzenie analizy i dyskusja zaproponowanego rozwiązania; wyprowadzenie niektórych wzorów i omówienie wybranych przykładów zasygnalizowanych na wykładach, dyskusja; możliwość wykorzystania komputerów do kodowania algorytmów w wybranym języku programowania wysokiego poziomu
30
przygotowanie do konwersatoriów z pomocą udostępnionych materiałów wykładowych oraz dodatkowych materiałów pomocniczych poświęconych problemom analizowanym podczas konwersatoriów; samodzielne ćwiczenie kodowania algorytmów w pseudokodzie i w wybranym języku wysokiego poziomu, w przypadku tego drugiego najlepiej z wykorzystaniem komputera.
 45 kolokwium [1FT_48_w_1]
Attachments
Module description (PDF)
Information concerning module syllabuses might be changed during studies.
Syllabuses (USOSweb)
Semester Module Language of instruction
(no information given)