Algorytmy, struktury danych i metody numeryczne Kierunek studiów: Fizyka techniczna
Kod programu: 03-S1FT12.2017

Nazwa modułu: Algorytmy, struktury danych i metody numeryczne
Kod modułu: 0305-1FT-17-48
Kod programu: 03-S1FT12.2017
Semestr: semestr zimowy 2019/2020
Język wykładowy: polski
Forma zaliczenia: egzamin
Punkty ECTS: 4
Opis:
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
Wymagania wstępne:
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.
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 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]
Typ Opis Kody efektów modułowych do których odnosi się sposób weryfikacji
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
Rodzaj prowadzonych zajęć Praca własna studenta Sposoby weryfikacji
Typ Opis (z uwzględnieniem metod dydaktycznych) Liczba godzin Opis Liczba godzin
wykład [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]
konwersatorium [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]
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)