Podstawy programowania i przetwarzania danych 2018/2019
(Introduction to Programming and Data Processing)
Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej, I rok, studia inż., kier. Inżynieria i analiza danych (Data Science)

Informacje ogólne

Wykład: prof. nzw. dr hab. inż. Marek Gągolewski wt., 10-12, s. 102
Ćwiczenia: mgr Anna Cena czw., 16-17, s. 313
mgr Barbara Żogała-Siudem czw., 16-17, s. 316
Laboratoria: mgr Anna Cena czw., 14-16, s. 301,
czw., 17-19, s. 303
mgr Barbara Żogała-Siudem czw., 14-16, s. 302,
czw., 17-19, s. 304

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 z użyciem gotowych, udokumentowanych bibliotek, umiejętność przetestowania programu, jego użycia na konkretnych danych wejściowych, interpretację otrzymanego wyniku. Na wybranych zajęciach laboratoryjnych student rozwiązuje samodzielnie zadania sprawdzające.

Harmonogram zajęć

Wymagane oprogramowanie

Pracujemy w systemie Linux/UNIX i korzystamy z Pythona 3.6+ (nie: 2.7; sugerowana dystrybucja: Anaconda).

Literatura

Podstawowa:

  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.

Uwaga: jako że celem kursu jest m.in. nauka algorytmiki i programowania w ogólności a nie samego języka Python, nie sugerujemy tutaj żadnej literatury dotyczącej tego narzędzia. Podczas zajęć będziemy korzystać ze ściśle określonego podzbioru składni Pythona.

Dodatkowa:

  1. Goldberg D., What every computer scientist should know about floating-point arithmetic, ACM Computing Surveys 23(1), 1991, 5-48
  2. Knuth D.E., Sztuka Programowania. Tom I: Algorytmy Podstawowe, WNT, 2002.
  3. Knuth D.E., Sztuka Programowania. Tom II: Algorytmy seminumeryczne, WNT, 2002.
  4. Knuth D.E., Sztuka Programowania. Tom III: Sortowanie i wyszukiwanie, WNT, 2002.
  5. Knuth D.E., The Art of Computer Programming, Vol. 4, Pre-fascicle 5B: Introduction to Backtracking, Addison-Wesley, 2017.
  6. W. Stallings, Organizacja i architektura systemu komputerowego, WNT, 2000.

Tydzień 1. (2018-10-02)

Pojęcie problemu obliczeniowego,
Typy skalarne, operatory

Materiały pomocnicze i literatura uzupełniająca:

  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. Uwaga: należy „obserwować” (Watch) ww. repozytorium, gdyż inaczej nie będą Państwo otrzymywać wiadomości e-mail nt. aktualizacji, ogłoszeń itp. (sekcja Issues)

Ćwiczenia 1 (2018-10-04): Zestaw zadań 1 (wprowadzenie)

Laboratoria 1 (2018-10-04): Przygotowanie środowiska pracy, praca ze skryptami w języku Python, podstawowe polecenia języka

Tydzień 2. (2018-10-09)

Priorytety operatorów w języku Python,
Reprezentacja znaków drukowanych (US-ASCII, Unicode/UTF-8),
Reprezentacja liczb całkowitych bez znaku

Materiały pomocnicze i literatura uzupełniająca:
  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. Operator Precedence – The Python Language Reference, Sec. 6.16
  3. Stallings W., Organizacja i architektura systemu komputerowego, WNT, 2000, rozdz. 8
  4. What is Unicode? @ Unicode.org
  5. An Informal Introduction to Python – The Python 3 Tutorial

Ćwiczenia 2 (2018-10-11): Zestaw zadań 2 (arytmetyka)

Laboratoria 2 (2018-10-11): Operacje na zmiennych skalarnych (arytmetyczne, logiczne, relacyjne), instrukcja if, wczytywanie danych z klawiatury (stdin)

Tydzień 3. (2018-10-16)

Operacje na bitach,
Reprezentacja liczb całkowitych ze znakiem,
Reprezentacja liczb rzeczywistych,
Błędy arytmetyki FP

Materiały pomocnicze i literatura uzupełniająca:
  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. Goldberg D., What every computer scientist should know about floating-point arithmetic, ACM Computing Surveys 23(1), 1991, 5-48
  3. Knuth D.E., Sztuka Programowania. Tom II: Algorytmy seminumeryczne, WNT, 2002, rozdz. 4
  4. Muller J.-M. i in, Handbook of Floating-Point Arithmetic, Birkhäuser, Basel, 2018
  5. Higham N.J., Accuracy and stability of numerical algorithms, SIAM, Philadelphia, PA, 2002
  6. Stallings W., Organizacja i architektura systemu komputerowego, WNT, 2000, rozdz. 8

Ćwiczenia 3 (2018-10-18): Zestaw zadań 3 (algorytmy iteracyjne; cz. 1/2)

Laboratoria 3 (2018-10-18): Zadanie punktowane 1 (5 p.)

Tydzień 4. (2018-10-23)

Instrukcje sterujące,
Definiowanie i dokumentowanie (docstrings) własnych funkcji,
Listy

Materiały pomocnicze i literatura uzupełniająca:
  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. More Control Flow Tools – The Python 3 Tutorial
  3. Input and Output – The Python 3 Tutorial

Ćwiczenia 4 (2018-10-25): Zestaw zadań 3 (algorytmy iteracyjne; cz. 2/2)

Laboratoria 4 (2018-10-25): Algorytmy iteracyjne, tworzenie własnych funkcji, generowanie liczb pseudolosowych, odczyt i zapis danych z/do plików tekstowych

Tydzień 5. (2018-10-30)

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

Materiały pomocnicze i literatura uzupełniająca:
  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. Knuth D.E., Sztuka Programowania. Tom I: Algorytmy Podstawowe, WNT, 2002, rozdz. 1.
  3. Knuth D.E., Sztuka Programowania. Tom III: Sortowanie i wyszukiwanie, WNT, 2002, rozdz. 6.1, 6.2.1.
  4. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Wprowadzenie do algorytmów (Introduction to Algorithms), PWN, 2017, rozdz. 3.

Tydzień 6. (2018-11-06)

Problem wyszukiwania zadanego elementu w liście uporządkowanej. Relacje porządku liniowego,
Referencje do obiektów,
Kopiowanie płytkie a głębokie

Materiały pomocnicze i literatura uzupełniająca:
  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. Knuth D.E., Sztuka Programowania. Tom III: Sortowanie i wyszukiwanie, WNT, 2002, rozdz. 5.2.

Ćwiczenia 5 (2018-11-08): Zestaw zadań 4 (tablice; cz. 1/2)

Laboratoria 5 (2018-11-08): Zadanie punktowane 2 (5 p.)

Tydzień 7. (2018-11-13)

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

Materiały pomocnicze i literatura uzupełniająca:
  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. Knuth D.E., Sztuka Programowania. Tom III: Sortowanie i wyszukiwanie, WNT, 2002, rozdz. 5.2.

Ćwiczenia 6 (2018-11-15): Dzień PW — godziny rektorskie??

Laboratoria 6 (2018-11-15): Dzień PW — godziny rektorskie??

Tydzień 8. (2018-11-20)

Generowanie permutacji sortującej,
Rekurencja: wprowadzenie; fraktale i żółw,
Sortowanie przez scalanie jako przykład zastosowania techniki dziel i rządź

Materiały pomocnicze i literatura uzupełniająca:
  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. Knuth D.E., Sztuka Programowania. Tom III: Sortowanie i wyszukiwanie, WNT, 2002, rozdz. 5.2, 5.3.
  3. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Wprowadzenie do algorytmów (Introduction to Algorithms), PWN, 2017, rozdz. 2 .
  4. turtle – Python Documentation

Ćwiczenia 7 (2018-11-22): Zestaw zadań 4 (tablice; cz. 2/2)

Laboratoria 7 (2018-11-22): Tablice

Tydzień 9. (2018-11-27)

Dolne ograniczenie złożoności sortowania przez porównywanie,
Sortowanie szybkie

Materiały pomocnicze i literatura uzupełniająca:
  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. Knuth D.E., Sztuka Programowania. Tom III: Sortowanie i wyszukiwanie, WNT, 2002, rozdz. 5.2.
  3. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Wprowadzenie do algorytmów (Introduction to Algorithms), PWN, 2017, rozdz. 7

Kolokwium 1 (2018-11-29): godz. 12:15-13:45 – wszystkie grupy – s. 107

Tydzień 10. (2018-12-04)

Warianty sortowania szybkiego (np. częściowe, wyszukiwanie statystyk pozycyjnych),
Sortowanie małych liczb naturalnych (np. danych jakościowych lub porządkowych): szufladkowe, przez zliczanie, kubełkowe i pozycyjne (LSD, MSD)

Materiały pomocnicze i literatura uzupełniająca:
  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Wprowadzenie do algorytmów (Introduction to Algorithms), PWN, 2017, rozdz. 8

Ćwiczenia 9 (2018-12-06): Zestaw zadań 5 (macierze; cz. 1/2)

Laboratoria 9 (2018-12-06): Zadanie punktowane 3 (10 p.)

Tydzień 11. (2018-12-11)

Tablice dynamiczne. Analiza kosztu zamortyzowanego operacji append() i pop(),
Elementy programowania obiektowego: proste klasy, pola i metody,
Przeciążanie operatorów (metody specjalne). Klasa DynamicArray

Materiały pomocnicze i literatura uzupełniająca:
  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Wprowadzenie do algorytmów (Introduction to Algorithms), PWN, 2017, rozdz. 17.4

Ćwiczenia 10 (2018-12-13): Zestaw zadań 5 (macierze; cz. 2/2)

Laboratoria 10 (2018-12-13): Macierze

Tydzień 12. (2018-12-18)

Lista jednokierunkowa (z dowiązaniami),
Binarne drzewo poszukiwań

Materiały pomocnicze i literatura uzupełniająca:
  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Wprowadzenie do algorytmów (Introduction to Algorithms), PWN, 2017, rozdz. 10.2
  3. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Wprowadzenie do algorytmów (Introduction to Algorithms), PWN, 2017, rozdz. 10.4 i 12

Ćwiczenia 11 (2018-12-20): Zestaw zadań 6 (tablice i macierze – algorytmy bardziej zaawansowane; cz. 1/2)

Laboratoria 11 (2018-12-20): Zadanie punktowane 4 (10 p.)

Tydzień 13. (2019-01-08)

Rekurencja – spamiętywanie, programowanie dynamiczne

Materiały pomocnicze i literatura uzupełniająca:
  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Wprowadzenie do algorytmów (Introduction to Algorithms), PWN, 2017, rozdz. 15

Ćwiczenia 12 (2019-01-03): Zestaw zadań 6 (tablice i macierze – algorytmy bardziej zaawansowane; cz. 2/2)

Laboratoria 12 (2019-01-03): Tablice i macierze – zadanie zaawansowane

Ćwiczenia 13 (2019-01-10): Zestaw zadań 7 (elementy programowania obiektowego i dynamiczne struktury danych; cz. 1/2)

Laboratoria 13 (2019-01-10): Zadanie punktowane 5 (10 p.)

Tydzień 14. (2019-01-15)

Algorytmy z nawrotami

Materiały pomocnicze i literatura uzupełniająca:
  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. Knuth D.E., The Art of Computer Programming, Vol. 4, Pre-fascicle 5B: Introduction to Backtracking, Addison-Wesley, 2017.

Ćwiczenia 14 (2019-01-17): Zestaw zadań 7 (elementy programowania obiektowego i dynamiczne struktury danych; cz. 2/2)

Laboratoria 14 (2019-01-17): Elementy programowania obiektowego

Tydzień 15. (2019-01-22)

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

Materiały pomocnicze i literatura uzupełniająca:
  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Wprowadzenie do algorytmów (Introduction to Algorithms), PWN, 2017, rozdz. 11.
  3. Knuth D.E., Sztuka Programowania. Tom III: Sortowanie i wyszukiwanie, WNT, 2002, rozdz. 6.1.

Kolokwium 2 (2019-01-24): godz. 12:15-13:45 – wszystkie grupy – s. 107

Laboratoria 15 (2019-01-24): Zadanie punktowane 6 (10 p.)

Kolokwium poprawkowe odbędzie się @TBA@.

Laboratorium dodatkowe (zob. regulamin przedmiotu) odbędzie się @TBA@.