Marcin Michalski
Katedra Matematyki WMat PWr
Informacje ogólne
Kurs jest przeznaczony dla studentów WMAT. Kod kursu w USOSie: W13MDT-SI2342G.
Wykłady odbywają się w środy 13:15 - 15:00 w C-19 sali A.1.3.
Laboratoria (mojej grupy) są po wykładzie w A.0.4.
Na zajęciach obowiązuje nas język C++ standardu przynajmniej 17 (taki jest domyślny w kompilatorze GCC bez określania innego podczas kompilowania).
Preferowany kompilator to GCC (i taki też jest zainstalowany w salach laboratoryjnych, choć dość dawna wersja). Aby zainstalować GCC na swoim sprzęcie, użyj np. paczki MSYS2 stąd i podążaj za instrukcjami odpowiednimi dla Twojego systemu.
Minimalistyczny zestaw do kompilowania programów, to notatnik podświetlający składnię (np. Notepad++), kompilator i terminal (np. cmd, PowerShell, Git Bash, etc.). Przystępnym IDE jest Code::Blocks, a do tego w pakiecie wraz z instalatorem jest również kompilator. Cięższej wagi IDE jest VSCode, ale mogą być problemy z jego odpowiednią konfiguracją i obsługą bez praw administratora.
Lista 0
Lista 1, deadline: 16.03.2024, 23:59.
Lista 2, deadline: 23.03.2024, 23:59.
Lista 3, deadline: 06.04.2024, 23:59.
Lista 4, deadline: n/a.
Lista 5, deadline: 27.04.2024, 23:59.
Preferowany kompilator to GCC (i taki też jest zainstalowany w salach laboratoryjnych, choć dość dawna wersja). Aby zainstalować GCC na swoim sprzęcie, użyj np. paczki MSYS2 stąd i podążaj za instrukcjami odpowiednimi dla Twojego systemu.
Minimalistyczny zestaw do kompilowania programów, to notatnik podświetlający składnię (np. Notepad++), kompilator i terminal (np. cmd, PowerShell, Git Bash, etc.). Przystępnym IDE jest Code::Blocks, a do tego w pakiecie wraz z instalatorem jest również kompilator. Cięższej wagi IDE jest VSCode, ale mogą być problemy z jego odpowiednią konfiguracją i obsługą bez praw administratora.
Lista 0
Lista 1, deadline: 16.03.2024, 23:59.
Lista 2, deadline: 23.03.2024, 23:59.
Lista 3, deadline: 06.04.2024, 23:59.
Lista 4, deadline: n/a.
Lista 5, deadline: 27.04.2024, 23:59.
Zasady zaliczenia
W ramach zaliczenia odbędą się 2 kolokwia - jedno na laboratoriach (z programowania) oraz jedno na ostatnim wykładzie. Oba będę warte 30 punktów.
Ponadto będą listy zadań, na ogół składające się z 2 części. Zadania z części I będzie można prezentować na zajęciach (za plusy z aktywności), zadania II części będzie trzeba opracować samodzielnie i przesłać/udsotępnić prowadzącemu (prawdopodobnie użyjemy w tym celu GitHuba, instrukcja). W udostępnionym repozytorium rozwiązania powinny być w ścieżkach lista_i/z_j/ li/zj/ (od listy 5), gdzie i, j są odpowiednio numerem listy i zadania. Na przesyłanie rozwiązań będzie deadline, a jego przekroczenie będzie kosztować 1 punkt (za daną listę) za każdy dzień zwłoki. Za nadesłane rozwiązania drugich części list będzie można dostać finalnie 30 punktów. Spodziewajmy się ~10 list. Dla wygody oceniania punktacja za poszczególne listy będzie zmienna, ale przy podsumowaniu punkty zostaną przeskalowane tak, by ostatecznie maksymalna suma punktów za listy (nie licząc zadań dodatkowych) wynosiła 30 i waga każdej listy była taka sama. Oceniane będą: zgodność ze specyfikacją, poprawność działania i schludność kodu.
Na laboratoriach można też się spodziewać kilku kartkówek, które będą nabijały plusy z aktywności. Dodatnia liczba plusów z aktywności będzie przeliczana na punkty wzorem \(\sum_{i=1}^{n}\frac{1}{\log_5(i+4)}\), gdzie \(n\) to liczba plusów.
Ocena końcowa zostanie wystawiona zgodnie z poniższą tabelką, gdzie Punkty \( =K_1+K_2+L+A\) i wyrażenia po prawej oznaczają odpowiednio punkty za kolokwia, listy i aktywność.
Ponadto będą listy zadań, na ogół składające się z 2 części. Zadania z części I będzie można prezentować na zajęciach (za plusy z aktywności), zadania II części będzie trzeba opracować samodzielnie i przesłać/udsotępnić prowadzącemu (
Na laboratoriach można też się spodziewać kilku kartkówek, które będą nabijały plusy z aktywności. Dodatnia liczba plusów z aktywności będzie przeliczana na punkty wzorem \(\sum_{i=1}^{n}\frac{1}{\log_5(i+4)}\), gdzie \(n\) to liczba plusów.
Ocena końcowa zostanie wystawiona zgodnie z poniższą tabelką, gdzie Punkty \( =K_1+K_2+L+A\) i wyrażenia po prawej oznaczają odpowiednio punkty za kolokwia, listy i aktywność.
| Punkty | Ocena |
|---|---|
| \(<50\) | \(2.0\) |
| \([50,60)\) | \(3.0\) |
| \([60,70)\) | \(3.5\) |
| \([70,80)\) | \(4.0\) |
| \([80,90)\) | \(4.5\) |
| \([90,100)\) | \(5.0\) |
| \(\ge 100\) | \(5.5\) |
Omówione tematy
- Wybór kompilatora i środowiska programistycznego.
-
Podstawy składni C++
- Struktura programu, funkcja main.
- Elementy IO, hello.cpp.
- Wbudowane operatory arytmetyczne, bitowe, logiczne, inkrementacji i dekrementacji, etc. Dygresja o kolejności wykonywania instrukcji i ewaluacji wyrażeń; order_ex.cpp, inc_dec_ex1.cpp, order_inc_ex.cpp.
- Podstawowe typy danych.
- Funkcje, przekazywanie argumentów przez wartość i przez referencję; val_vs_ref.cpp.
- Instrukcje: warunkowa if-else if-else: if_ex.cpp, switch: switch_ex.cpp, pętle while, do while oraz for; loops_ex.cpp.
- Beamer wykładu 2.
-
Elementy rekursji
- Przykład funkcji rekurencyjnej w C++.
- Relacje dobrze ufundowane.
- Tw. Relacja jest dobrze ufundowana wtedy, i tylko wtedy, gdy nie istnieją dla tej relacji ściśle malejące nieskończone ciągi.
- Rekursja ogonowa.
-
Wskaźniki
- Definicja, operatory referencji & wyłuskania/dereferencji *; ptr_ex1.cpp.
- Przekazywanie argumentów przez wskaźnik; ptr_pass_by.cpp.
- Wskaźnik na wskaźnik; ptr_on_ptr.cpp.
- Tablice, tablice a wskaźniki; arrays.cpp, arrays_pass.cpp
- Argumenty funkcji main, przekazywanie argumentów do funkcji main ze standardowego wejścia; to_argv.cpp.
- NULL vs nullptr; nullptr_vs_null.cpp.
- Dynamiczna alokacja pamięci, wyrażenia new i delete; dyn_alloc.cpp.
-
Sortowanie.
- Sformułowanie problemu.
- Przykładowe sortowania: bąbelkowe, przez wstawianie, quick sort, merge sort; mergesort.cpp
-
Złożoność obliczeniowa.
- Definicja \(\unlhd\) (czyli notacji \(O(\_)\)) i przykłady.
- Obserwacja: relacja \(\unlhd\) jest preporządkiem, ale nie częściowym porządkiem.
- Tw. Preporządek \((X, \preceq)\) można roszerzyć do porządku częściowego na \(X/\sim\), gdzie \(\sim\) jest relacją równoważności zadaną przez \(x\sim y \iff x\preceq y \land y\preceq x \).
- Zbadaliśmy tempo wzrostu wielomianów i funkcji \(x^n\) oraz pokazaliśmy, że w \(\unlhd\) nie ma elementów maksymalnych.
- Tw. \(f \unlhd g \iff \limsup_{x\to\infty}\frac{|f|}{g}<\infty\).
- Arytmetyka notacji \(O(f)\).
- Rodziny zbiorów parami prawie rozłącznych. Tw. Istnieje rodzina podzbiorów \(\mathbb{N}\) parami prawie rozłącznych mocy \(\mathfrak{c}\).
-
Struktury.
- Składnia, operator (.), wskaźniki na struktury, przykłady prostych struktur, zagnieżdżanie struktur; records.cpp.
- Konstruktor i destruktor struktury.
- Drzewo binarne; btree.cpp.
- Kolejka (FIFO); kolejka.cpp.