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ź.
Przykładowe algorytmy rekurencyjne.Wykład 8 (10.I 2026)
Rekursywne typy danych, listy, stosy, kolejki, drzewa binarne, drzewa rozbioru gramatycznego, notacja polska (beznawiasowa), przeszukiwania drzew binarnych.
Grafy: podstawowe definicje, ścieżki, stopnie, przykłady klas grafów (kliki, linie, cykle).
Drzewa, drzewa rozpinające.
Ścieżki i cykle Eulera i Hamiltona.
Kolorowanie grafów. Grafy dwudzielne, skojarzenia, twierdzenie Halla o reprezentantach.
Wykład 9 (17.I 2026)
Algorytmy grafowe: reprezentacja grafów (macierze incydencji i sąsiedztw, listy sąsiedztw), przeszukiwanie grafów, drzewa rozpinające, ścieżki i cykle Eulera i Hamiltona.
Grafy skierowane, podstawowe definicje (silna spójność, źródło i zlew). Drzewa jako grafy skierowane.
Algorytmy grafowe: szukanie najkrótszej ścieżki, algorytmy dla grafów acyklicznych, z dodatnimi wagami (złożoność O(n2)) oraz ogólny (złożoność O(n3)).Wykład 10 (31.I.2026)
Omówienie wszystkich wykładów.
