Podstawy programowania i przetwarzania danych

Kurs jest wprowadzeniem do programowania imperatywnego z użytkowymi elementami technik programowania obiektowego na przykładzie języka Python 3. Student poznaje pojęcie algorytmu, funkcji, programu, rekurencji, tablicy (listy), a także najbardziej podstawowe algorytmy i struktury danych, które mogą być wykorzystywane w przetwarzaniu danych, m.in. algorytmy wyszukiwania, sortowania i działania na wektorach oraz macierzach (także w podgrupach generowanych przez zmienne typu czynnikowego) oraz tablice dynamiczne, listy jednokierunkowe i drzewa binarne. Ponadto zapoznaje się z wybranymi funkcjami z biblioteki pakietów dla środowiska Python, np. służącymi do generowania wykresów, liczb pseudolosowych z wybranych rozkładów itp. Nabywa także umiejętności analizy złożoności obliczeniowej i pamięciowej poznanych algorytmów.

Na zajęciach ćwiczeniowych student rozwija umiejętności analizy zagadnień problemowych i tworzenia algorytmów służących do ich rozwiązania z wykorzystaniem poznanych na wykładzie wiadomości teoretycznych.

Na zajęciach laboratoryjnych student uczy się praktycznych umiejętności tworzenia pełnych programów, które są oparte na poznanych algorytmach. Szczególną uwaga zwraca się więc na: implementację programu przy użyciu gotowych, udokumentowanych bibliotek, umiejętność przetestowania programu, jego wykonania na konkretnych danych wejściowych, oraz interpretację otrzymanego wyniku. Na wybranych zajęciach laboratoryjnych student rozwiązuje samodzielnie zadania sprawdzające.

Treści kształcenia:

1. Pojęcie problemu obliczeniowego

2. Typy skalarne, podstawowe operatory i ich priorytety

3. Reprezentacja liczb całkowitych, zmiennopozycyjnych oraz znaków drukowanych. Błędy arytmetyki zmiennopozycyjnej

4. Instrukcja warunkowa i pętle. Definiowanie i dokumentowanie własnych funkcji

5. Listy (tablice)

6. Złożoność obliczeniowa i pamięciowa algorytmów, Notacje asymptotyczne: O, Θ, Ω. Przykłady rzędów wielkości funkcji, Szacowanie złożoności różnych algorytmów w problemie wyszukiwania zadanego elementu w liście

7. Referencje do obiektów, Kopiowanie płytkie a głębokie,

8. Problem sortowania i jego zastosowania. Permutacje. Stabilność algorytmów sortowania. Proste algorytmy sortowania przez porównywanie: bąbelkowe, przez wybór i przez wstawianie

9. Rekurencja: Wprowadzenie. Wieże z Hanoi; Fraktale i żółw, Sortowanie przez scalanie jako przykład zastosowania techniki dziel i rządź, Dolne ograniczenie złożoności sortowania przez porównywanie; Sortowanie szybkie,

10. Tablice dynamiczne. Analiza kosztu zamortyzowanego operacji append() i pop()

11. Sortowanie małych liczb naturalnych (np. danych jakościowych lub porządkowych): szufladkowe, przez zliczanie, kubełkowe i pozycyjne (LSD, MSD),

12. Elementy programowania obiektowego: proste klasy, pola i metody, Przeciążanie operatorów (metody specjalne). Klasa DynamicArray

13. Lista jednokierunkowa (z dowiązaniami); Binarne drzewo poszukiwań

14. Rekurencja – spamiętywanie, programowanie dynamiczne; Algorytmy z nawrotami

15. Tablice z haszowaniem. Abstrakcyjny typ danych słownik i zbiór

1. Harel D., Feldman Y., Rzecz o istocie informatyki. Algorytmika (Algorithmics: The Spirit of Computing), WNT, 2008.

2. Wirth N., Algorytmy + struktury danych = programy (Algorithms + Data Structures = Programs), WNT, 2004.

3. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Wprowadzenie do algorytmów (Introduction to Algorithms), PWN, 2017.

4. Bentley J., Perełki programowania (Programming Pearls), Helion, 2012.

2 kolokwia;

6-7 laboratoryjnych zadań punktowanych;

Do zdobycia maks. 100 p. Ocena końcowa wynika z sumy punktów; ≤50 p. - 2,0; (50,60] – 3,0; (60,70] – 3,5; (70,80] – 4,0; (80,90] – 4,5; >90 – 5,0.

Szczegółowy regulamin zaliczenia podawany jest na początku semestru.