Teaching materials
This page contains materials for the classes I teach in this semester, as well as (in the future) links to the archive of past materials I deem viable for archiving.
If you want a guarantee that something won't get removed $n$ years from now, save the HTML. You have been warned.
Zasady zaliczenia oraz najważniejsze informacje
W trakcie semestru będą trzy kolokwia, zgodnie z zasadami podanymi na wykładzie.
Przed zajęciami należy dostarczyć rozwiązania zadań z obowiązującego zestawu zadań. Wystarczy reprezentatywna próbka - z 6 zadań w zestawie można odrobić 3.
Do oceny będzie się liczyć aktywność przy tablicy i na zajęciach. Brak przygotowania zadań będzie oceniany zgodnie z zasadami na wykładzie.
W trakcie semestru będzie kilka zajęć, w czasie których zamiast tradycyjnego spotkania na sali spotkamy się osobiście, by porozmawiać dokładniej o dostarczonych kodach i ocenić Państwa postęp. Oceniany będzie oprócz poprawności programów styl i podejście do problemu. Będzie to też czas dla Państwa.
Konsultacje odbywać się będą w pokoju D-2-33. Proszę wysłać do mnie maila w celu ustalenia godziny.
zajęcia 2 -- kontrola przepływu
By rozwiązywać problemy przy użyciu komputera, potrzebne jest stworzenie listy kroków do wykonania przez komputer. By program mógł podejmować decyzje, potrzebne są sposoby na kontrolę przepływu.
Pętla pozwala powtarzać kod, dopóki nie zajdzie jakiś warunek. Przy pętli while kluczowe jest ustawianie w ostatniej instrukcji czegoś, co pozwoli warunkowi stać się nieprawdą. Często warto zacząć pisać pętlę od napisania jej ostatniego wyrażenia!
x = 2
while x < 16:
print("x = {}", x)
x = x * 2 # instrukcja pozwalająca, by warunek stał się nieprawdą!
Pętla for pozwala z góry ustalić, dla jakiego zakresu będziemy wykonywać operacje. Gdy operujemy niskopoziomowo, powinniśmy korzystać z pętli podobnej jak w C, gdzie komponenty to inicjalizacja, warunek pętli oraz instrukcja zmieniająca warunek.
for (int i = 0; i <= 10; i++) {
<instrukcja powtarzająca się>
...
}
Ale często, gdy piszemy wysokopoziomowo, bardziej obchodzi nas kolekcja, na której wykonujemy operacje. Wtedy możemy zapisać pętle jak w pythonie.
for element in [el_listy_1, el_listy_2]:
do_something_to(element)
Pętli for używamy, gdy jasne są zakresy w jakich operujemy. Najczęściej będzie to jakaś zdefiniowana kolekcja bądź zakres indeksów. Dzięki temu całość opisu 'powtarzania' jest w jednej linijce.
Pętli while używamy, gdy warunek jest bardziej abstrakcyjny, np. dopóki nie zerwiemy połączenia albo nie skończy się plik, który wczytujemy. Używamy jej również wtedy, gdy warunek kończący pętlę może zajść na kilka różnych sposobów. W ten sposób zaznaczamy programiście czytającemu kod po nas, że dla sprawdzenia, kiedy pętla 'wychodzi' musi przeczytać jej całą definicję, a nie tylko pierwszą linijkę.
Zmienne po prostu ustawiamy. W stylu C podalibyśmy ich typ, ale w pseudokodzie nie jest to dla nas interesujące.
Tablice i dostęp do elementów tablic oznaczamy kwadratowymi nawiasami. Indeksujemy tablice od 0; oznacza to, że długość tablicy znajduje się POZA zakresem elementów. Musimy tego pilnować.
lista = [element1, element2]
assert lista[0] == element1
assert lista[1] == element2
(assert oznacza stwierdzenie, że zadany warunek jest taki jak oczekujemy; konstrukcja często używana w testach kodu)
Kod istnieje głównie po to, by łatwo było go odczytać następnemu programiście. Same komputery operują na instrukcjach zdefiniowanych zerami i jedynkami.
A skoro tak, to kod nieczytelny NIE SPEŁNIA swojej funkcji. Czytelny styl będzie zatem wymagany na zajęciach; postaramy się uczyć praktyk, które takim go czynią.
zajęcia 1 -- wprowadzenie
Na zajęciach pierwszych opisałem Państwu zasady zaliczenia. Pokazałem też, w jaki sposób będę uczył na naszych zajęciach.
Poniżej znajdują się krótkie streszczenia informacji, które pokazywałem. W przyszłości posty będą sortowane chronologicznie od najnowszego, na zasadzie bloga.
Carl Friedrich Gauss był jednym z najbardziej wpływowych geometrów (inaczej zwanych 'bumelantami') w historii. Spotkają się Państwo w przyszłości z masą twierdzeń nazwanych jego nazwiskiem -- ich lista ma osobną stronę na wikipedii.
O Gaussie krąży anegdota -- być może apokryficzna, ale nie pozwólmy faktom zepsuć nam wyborną opowieść. W wieku młodzieńczym jego klasie postawiono zadanie dodania $100$ początkowych liczb naturalnych. Żmudne dodawanie $1 + 2 + 3 + ...$ miało zająć klasę na dłużej, jednak Gauss podał prawie natychmiastowo poprawną odpowiedź -- $5050$.
Dokonał tego nie licząc szybciej od innych, a zauważając, że liczby skrajne da się połączyć w pary o sumie $101$. Komprehensywny opis całej historii i wszystkich podejść adekwatnych do tego problemu można znaleźć na stronie American Scientist. Na zajęciach zaprezentowałem wizualny odpowiednik metod oznaczonych w artykule jako 'folding' oraz jako 'averages'; artykuł pokazuje jeszcze fantastyczną metodę algebraiczną oraz całkowicie geometryczny trik.
Tak czy inaczej, wynikiem jest $$\sum^n_{i=1} i = \frac{n}{2}(n+1).$$ Istotą rozwiązywania problemów szybko jest umiejętność abstrakcyjnego myślenia i rozkładania problemów na łatwiejsze. Pomocne w tym są wizualizacje. Właśnie to będę starał się Państwu przekazać w trakcie moich zajęć.
W trakcie kursu będę okazjonalnie korzystał z metod opisanych w książce George'a Pólyi How to Solve It.
By przetworzyć informację, najpierw trzeba ją przechować. Z powodów praktycznych (inkrementacja, dodawanie itp działa jak dla liczb bez znaku) robi się to przy użyciu kodu uzupełnień do dwóch.
Można używać arytmetyki stałoprzecinkowej, gdzie któryś z bitów ma wartość 1/2, mniejszy od niego 1/4 itp. Jednak z reguły korzysta się z reprezentacji zmiennoprzecinkowej w formacie IEEE 754. Proszę na zadanie porównać, jaki zakres mają liczby stałoprzecinkowe z bitem znaku, czterema całkowitymi i trzema ułamkowymi, a jaki zmiennoprzecinkowe z bitem znaku, 4 bitami eksponenty oraz trzema mantysy. Jakim cudem reprezentacja zmiennoprzecinkowa ma większy zasięg?
Dla obeznanych z terminalem stworzyłem aplikację, która pozwala obserwować, jak działa IEEE 754 - link do repozytorium.
Instrukcja warunkowa pozwala podjąć decyzję na temat kodu. Najczęściej będzie to jakiś warunek logiczny.