Wykład 1 (4.X 2025)
-
Przegląd zagadnień.
Zbiory i relacje. Relacje równoważności.
Funkcje, grafy, drzewa, słowa.
Wykład 2 (18.X 2025)
-
Wielomiany, notacja asymptotyczna.
Systemy liczenia, operacje arytmetyczne.
Reprezentacja liczb całkowitych w komputerze. Wykład 3 (25.X 2025)
- Reprezentacja liczb rzeczywistych.
- Drzewa przeszukiwań binarnych, drzewa algorytmów.
- Liczenie, zasada Dirichleta
Wykład 4 (15.XI 2025)
-
Zliczanie: sumy, iloczyny, ciągi, funkcje, permutacje.
Podzbiory, dwumian Newtona. Wykład 5 (22.XI 2025)
-
Kombinacje z powtórzeniami, rozmieszczenia, podziały,
wielozbiory, generowanie obiektów kombinatorycznych.
-
Algebra Boole'a, wyrażenia boolowskie.
Funkcje boolowskie, bramki nand i nor. Wykład 6 (6.XII 2025)
-
Sieci boolowskie, sumator.
Operacje na wektorach, mapy bitowe, odciski, podział sekretu, gra "NIM". - Teoria liczb, arytmetyka modularna, algorytm Euklidesa.
Wykład 7 (13.XII 2025)
- Teoria liczb: Chińskie twierdzenie o~resztach, szyfr RSA.
Rekurencja:
Indukcja matematyczna. Rekursywne typy danych. Dowody i definicje przez indukcję strukturalną.
Przykłady algorytmów rekurencyjnych: wieże z Hanoi, sortowanie przez scalanie.
Obliczanie funkcji zdefiniowanych rekurencyjne, rekurencja liniowa.
Złożoność algorytmów rekurencyjnych, zasada dziel i rządź.
