Politechnika Warszawska - Centralny System Uwierzytelniania
Nie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Podstawy programowania i przetwarzania danych

Informacje ogólne

Kod przedmiotu: 1120-MD000-LSP-0114 Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Podstawy programowania i przetwarzania danych
Jednostka: Wydział Matematyki i Nauk Informacyjnych
Grupy: Matematyka i analiza danych, I st. - przedmioty obowiązkowe, sem. 1
Matematyka, I st. - przedmioty obowiązkowe, sem. 1
Punkty ECTS i inne: 5.00
Język prowadzenia: polski
Pełny opis:

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

Literatura:

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.

Metody i kryteria oceniania:

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.

Zajęcia w cyklu "rok akademicki 2021/2022 - sem. zimowy" (w trakcie)

Okres: 2021-10-01 - 2022-02-22
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin więcej informacji
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Maciej Bartoszuk, Małgorzata Śleszyńska-Nowak
Prowadzący grup: Łukasz Brzozowski, Anna Cena, Michał Denkiewicz, Michał Dębski, Małgorzata Śleszyńska-Nowak, Michał Własnowolski
Lista studentów: (nie masz dostępu)
Zaliczenie: Zaliczenie na ocenę

Zajęcia w cyklu "rok akademicki 2020/2021 - sem. zimowy" (zakończony)

Okres: 2020-10-01 - 2021-02-19
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin więcej informacji
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Maciej Bartoszuk
Prowadzący grup: Maciej Bartoszuk, Michał Denkiewicz, Michał Dębski, Małgorzata Śleszyńska-Nowak, Zofia Tojek, Piotr Wolszakiewicz
Lista studentów: (nie masz dostępu)
Zaliczenie: Zaliczenie na ocenę

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. zimowy" (zakończony)

Okres: 2019-10-01 - 2020-02-21
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 15 godzin więcej informacji
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Maciej Bartoszuk, Marek Gągolewski
Prowadzący grup: Maciej Bartoszuk, Michał Hadryś, Grzegorz Ostrek, Małgorzata Śleszyńska-Nowak, Zofia Tojek
Lista studentów: (nie masz dostępu)
Zaliczenie: Zaliczenie na ocenę
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.