Algorytmy i struktury danych Kierunek studiów: Matematyka
Kod programu: W4-N2MT19.2020

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.

(brak informacji)

(brak informacji)