ALGORYTMY I STRUKTURY DANYCH

Ocena końcowa jest obliczana jako średnią arytmetyczna wszystkich ocen z laboratorium, konwersatorium oraz egzaminu. Jeżeli któraś z końcowych (ostatecznych) ocen cząstkowych jest oceną niedostateczną (2.0), to ocena końcowa również jest niedostateczna.

Przy założeniu, że ocenom przyporządkowuje się następujące wartości

dostateczny - 3,0

dostateczny plus - 3,5

dobry - 4,0

dobry plus - 4,5

bardzo dobry - 5,0

ocena końcowa obliczona na podstawie wyznaczonej średniej arytmetycznej wszystkich ocen przyporządkowana jest następująco:

do 3,25 – dostateczny;

od 3,26 do 3,75 – dostateczny plus;

od 3,76 do 4,25 – dobry;

od 4,26 do 4,75 – dobry plus;

od 4,76 do 5,00 – bardzo dobry.

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.

Na zajęciach wykorzystuje się język programowania PYTHON, ale wybrane algorytmy pokazuje się również w innych językach.

Ocena końcowa jest obliczana jako średnią arytmetyczna wszystkich ocen z laboratorium, konwersatorium oraz egzaminu. Jeżeli któraś z końcowych (ostatecznych) ocen cząstkowych jest oceną niedostateczną (2.0), to ocena końcowa również jest niedostateczna.

Przy założeniu, że ocenom przyporządkowuje się następujące wartości

dostateczny - 3,0

dostateczny plus - 3,5

dobry - 4,0

dobry plus - 4,5

bardzo dobry - 5,0

ocena końcowa obliczona na podstawie wyznaczonej średniej arytmetycznej wszystkich ocen przyporządkowana jest następująco:

do 3,25 – dostateczny;

od 3,26 do 3,75 – dostateczny plus;

od 3,76 do 4,25 – dobry;

od 4,26 do 4,75 – dobry plus;

od 4,76 do 5,00 – bardzo dobry.

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.

Na zajęciach wykorzystuje się język programowania PYTHON, ale wybrane algorytmy pokazuje się również w innych językach.