Podstawy programowania i przetwarzania danych 2017/2018
(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. 107
Ćwiczenia: mgr Anna Cena wt., 16-17, s. 213
Laboratoria: mgr Anna Cena pt., 16-18, s. 203
mgr Barbara Żogała-Siudem pt., 16-18, s. 219

Kurs jest wprowadzeniem do programowania imperatywnego z użytkowymi elementami technik programowania obiektowego przy użyciu 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 poznanych algorytmów. [pełny opis w USOS PW]

Harmonogram zajęć

Wymagane oprogramowanie

Pracujemy w systemie Linux/UNIX i korzystamy z Pythona 3.6 (nie: 2.7; sugerowana dystrybucja: Anaconda). Zobacz instrukcję, jak zainstalować system Linux i Anacondę na maszynie wirtualnej.

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 programowania w ogóle, 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. Knuth D.E., Sztuka Programowania. Tom I: Algorytmy Podstawowe, WNT, 2002.
  2. Knuth D.E., Sztuka Programowania. Tom II: Algorytmy seminumeryczne, WNT, 2002.
  3. Knuth D.E., Sztuka Programowania. Tom III: Sortowanie i wyszukiwanie, WNT, 2002.

Tydzień 1. (2017-10-03)

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: Zestaw zadań nr 1

Laboratoria: Przygotowanie środowiska pracy, praca ze skryptami w języku Python, podstawowe polecenia języka

Tydzień 2. (2017-10-10)

Priorytety operatorów w języku Python,
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. W. Stallings, Organizacja i architektura systemu komputerowego, WNT, 2000, rozdz. 8
  4. Knuth D.E., Sztuka Programowania. Tom II: Algorytmy seminumeryczne, WNT, 2002, rozdz. 4.
  5. An Informal Introduction to Python – The Python 3 Tutorial

Ćwiczenia: Zestaw zadań nr 2 (arytmetyka; cz. 1/2)

Laboratoria: Operacje na zmiennych skalarnych (arytmetyczne, logiczne, relacyjne), instrukcja if, wczytywanie danych z klawiatury (stdin)

Tydzień 3. (2017-10-17)

Reprezentacja liczb całkowitych ze znakiem (znak-moduł i U2),
rzeczywistych (stało i zmiennoprzecinkowe wg IEEE 754) i znaków drukowanych (Unicode)

Materiały pomocnicze i literatura uzupełniająca:
  1. Wybrane materiały, zestawy zadań na ćwiczenia itp. znajdują się GitHubie
  2. D. Goldberg, What every computer scientist should know about floating-point arithmetic, ACM Computing Surveys 23(1), 1991, 5-48

Ćwiczenia: Zestaw zadań nr 2 (arytmetyka; cz. 2/2)

Laboratoria: Zadanie punktowane nr 1

Tydzień 4. (2017-10-24)

Błędy arytmetyki FP,
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: Zestaw zadań nr 3 (algorytmy iteracyjne; cz. 1/2)

Laboratoria: Algorytmy iteracyjne, tworzenie własnych funkcji, generowanie liczb pseudolosowych, odczyt i zapis danych z/do plików tekstowych

Tydzień 5. (2017-10-31)

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

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.

Ćwiczenia: Zestaw zadań nr 3 (algorytmy iteracyjne; cz. 2/2)

Laboratoria: Zadanie punktowane nr 2

Tydzień 6. (2017-11-07)

Referencje do obiektów,
Kopiowanie płytkie a głębokie,
Problem sortowania i jego zastosowania. Permutacje. Stabilność algorytmów sortowania

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: Zestaw zadań nr 4 (tablice; cz. 1/2)

Laboratoria: Uwaga: 2017-11-10 jest dniem wolnym od zajęć

Tydzień 7. (2017-11-14)

Proste algorytmy sortowania przez porównywanie: bąbelkowe, przez wybór i przez wstawianie,
Rekurencja: Wprowadzenie. Wieże z Hanoi

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: Zestaw zadań nr 4 (tablice; cz. 2/2)

Laboratoria (nr 6): Tablice 1 (listy).

Tydzień 8. (2017-11-21)

Rekurencja: 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

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: Kolokwium nr 1 (16:15-17:45 – obydwie grupy – s. 107)

Laboratoria (nr 7): Zadanie punktowane nr 3

Tydzień 9. (2017-11-28)

Sortowanie szybkie,
Tablice dynamiczne. Analiza kosztu zamortyzowanego operacji append() i pop()

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 , 17.4

Ćwiczenia: (macierze; cz. 1/2)

Laboratoria (nr 8): Macierze 1

Tydzień 10. (2017-12-05)

Sortowanie małych liczb naturalnych (np. danych jakościowych lub porządkowych): szufladkowe, przez zliczanie, kubełkowe i pozycyjne (LSD, MSD),
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. 8.

Ćwiczenia: (macierze; cz. 2/2)

Laboratoria (nr 9): Zadanie punktowane nr 4

Tydzień 11. (2017-12-12)

Lista jednokierunkowa (z dowiązaniami)

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

Ćwiczenia: (tablice i macierze – algorytmy bardziej zaawansowane)

Laboratoria (nr 10): Tablice 2

Tydzień 12. (2017-12-19)

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.4 i 12

Ćwiczenia: Nie ma ćwiczeń – godziny Dziekańskie

Laboratoria (nr 11): Zadanie punktowane nr 5

Tydzień 13. (2018-01-09)

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: (elementy programowania obiektowego i dynamiczne struktury danych; cz. 1/2)

Laboratoria (nr 12, 2018-01-05): Macierze 2

Laboratoria (nr 13, 2018-01-13): Zadanie punktowane nr 6

Tydzień 14. (2018-01-16)

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: (elementy programowania obiektowego i dynamiczne struktury danych; cz. 2/2)

Laboratoria: Elementy programowania obiektowego

Tydzień 15. (2018-01-23)

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.

Ćwiczenia: Kolokwium 2 (16:15-17:45 – obydwie grupy – s. 107)

Laboratoria: Zadanie punktowane nr 7

Kolokwium poprawkowe odbędzie się w piątek 9.02 o godz. 17.15 w s. 103.

Laboratorium dodatkowe (zob. regulamin przedmiotu) odbędzie się w piątek 9.02 o godz. 15.15 w s. 219.