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 3 & 4 -- podstawy pisania algorytmów i sortowanie
By efektywnie pisać programy, potrzebujemy nauczyć się podstawowego podejścia do algorytmów.
Doskonałym problemem do rozwiązywania są sortowania, stąd nimi będziemy się zajmować jeszcze na następnych zajęciach.
Ludzie naturalnie sortują na kilka sposobów, które przerobiliśmy sobie na ćwiczeniu praktycznym: sortowanie kart.
Najczęściej używane są: insertion sort, selection sort oraz bucket sort. Zależnie od problemu, są one naturalnym podejściem. Będziemy pisać te algorytmy dla wykonania przez komputer, ale przećwiczenie algorytmów wraz z kartami jest użyteczne.
Warto też zobaczyć, że algorytmy te są dostosowane do 'komputerów białkowych': wybrać z kilku kart da się natychmiast, jeżeli jest się człowiekiem -- komputer musi je przeglądnąć pojedynczo.
Sortowanie jest naturalnym problemem, który ma wiele rozwiązań o różnym stopniu kompleksowości, ale i o różnych stronach pozytywnych i negatywnych. Stąd jesteśmy na nich w stanie nauczyć się prawdziwej inżynieryjnej myśli technicznej.
Sortowanie danych pozwala nam je szybciej przeszukać, co bardzo często jest kluczową operacją.
Nieposortowaną tablicę musimy przeszukać element po elemencie, co zajmie sporo czasu.
Gdy tablica jest posortowana, możemy zastosować wyszukiwanie połówkowe - wybieramy środkowy element, jeżeli jest większy od szukanego to możemy odrzucić drugą połowę tablicy i vice versa. Po tym możemy zastosować algorytm ponownie, tym razem na o połowie mniejszej tablicy -- aż do znalezienia elementu bądź dotarcia do jedynego elementu niepasującego do wyszukania.
int binarySearch(int arr[], int size, int target) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1; // Element not found
}
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.
Instrukcja warunkowa pozwala podjąć decyzję na temat kodu. Najczęściej będzie to jakiś warunek logiczny.
if a % 2 == 0:
print("podzielne przez 2")
else if a % 3 == 0:
print("podzielne przez 3, ale nie przez 2")
else:
print("niepodzielne ani przez 2 ani przez 3")
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.
Na zajęciach z C przyzwyczajają się Państwo do tego języka, zatem to w nim będziemy pisać.