Matematyka - plan wykładu (semestr I)

1. Pojęcie zdania logicznego i funkcji zdaniowej (predykatu).

2. Funktory zdaniotwórcze. Definicje sumy logicznej (alternatywy), iloczynu logicznego (koniunkcji), wynikania (implikacji), równoważności i zaprzeczenia (negacji). Przykłady innych funktorów.

3. Wartościowanie zdań logicznych (tabelka wartości).

4. Prawa logiki (tautologie): dla koniunkcji i alternatywy (przemienność, łączność, rozdzielność), dla implikacji (przechodniość), dla przeczenia (prawa: wyłączonego środka, sprzeczności, podwójnego przeczenia, de Morgana). Reguły wnioskowania.

5. Uogólnienie pojęcia sumy i iloczynu logicznego - kwantyfikatory. Przemienność bądź nieprzemienność kwantyfikatorów, przeczenie (prawa de Morgana dla kwantyfikatorów).

6. Antynomie (paradoksy) w logice - przyczyny. Pojęcie systemu formalnego. Niesprzeczność i zupełność systemu.

7. Pojęcia pierwotne algebry zbiorów (zbiór, przynależność do zbioru). Aksjomaty (istnienie, równość, suma, różnica).

8. Pojęcie równości zbiorów, inkluzji (zawierania), przestrzeni zbiorów, zbioru pustego, dopełnienia zbioru.

9. Definicje działań na zbiorach (suma, iloczyn, różnica). Ich własności (łączność, przemienność, rozdzielność, prawa pochłaniania, prawa de Morgana dla zbiorów).

10. Sumy i iloczyny uogólnione zbiorów.

11. Aksjomatyczne ujęcie liczb naturalnych (aksjomaty Peano): pojęcia pierwotne (zbiór, 1, przynależność, następnik), aksjomaty {(a) 1 jest liczbą naturalną; (b) 1 nie jest następnikiem żadnej liczby naturalnej; (c) każda liczba naturalna ma tylko jeden następnik; (d) jeśli liczba naturalna jest następnikiem, to jest następnikiem tylko jednej liczby naturalnej; (e) zasada indukcji zupełnej}.

12. Indukcyjna definicja dodawania i mnożenia liczb naturalnych.

13. Uogólnienie zasady indukcji - dowody indukcyjne.

14. Ujęcie własności jako przynależności elementu do zbioru.

15. Pojęcie iloczynu (produktu) kartezjańskiego. Własności (nieprzemienność, rozdzielność względem sumy, iloczynu i różnicy zbiorów).

16. Definicja relacji dwuczłonowej (dwuargumentowej albo binarnej) sformułowana przy pomocy pojęcia iloczynu kartezjańskiego i własności jako przynależności elementu do zbioru.

17. Własności relacji: zwrotna, przeciwzwrotna, symetryczna, przeciwsymetryczna, antysymetryczna, przechodnia, spójna - definicje i przykłady.

18. Przedstawienie relacji w zbiorze liczb rzeczywistych jako miejsca geometrycznego punktów na płaszczyźnie (wykres relacji). Związki między własnościami relacji a własnościami jej wykresu.

19. Relacja równoważności (zwrotna, symetryczna, przechodnia). Przykłady.

20. Klasy abstrakcji (równoważności) wyznaczane przez relację równoważności. Klasa abstrakcji jako podzbiór zbioru, w którym jest określona relacja; reprezentant klasy. Zastosowanie klas abstrakcji do definiowania pojęć.

21. Funkcje jako relacje.

22. Surjekcje (odwzorowania "na"), injekcje (przekształcenia różnowartościowe), bijekcje (przekształcenia wzajemnie jednoznaczne).

23. Permutacja - bijekcja zbioru o skończonej ilości elementów. Transpozycja, permutacje parzyste i nieparzyste. Ilość funkcji odwzorowujących zbiór skończony w zbiór skończony.

24. Superpozycja przekształceń. Własności (nieprzemienność, łączność), przekształcenie odwrotne, identycznościowe.

25. Równoliczność zbiorów (istnienie bijekcji jednego zbioru w drugi). Własności równoliczności (zwrotność, symetryczność, przechodniość).

26. Moc (liczba kardynalna) zbioru. Moc zbioru liczb naturalnych (alef zero) i rzeczywistych (kontinuum).

27. Przeliczalność zbioru nieskończonego (równoliczność ze zbiorem liczb naturalnych). Przeliczalność zbioru liczb parzystych, nieparzystych, wymiernych (bijekcje w zbiór liczb naturalnych).

28. Nieprzeliczalność zbioru liczb rzeczywistych (dowód nieistnienia ciągu przebiegającego wszystkie liczby z przedziału [0, 1]) i niewymiernych (argument "przekątniowy" Cantora). Hipoteza kontinuum.

29. Zbiór wszystkich podzbiorów (zbiór potęgowy) zbioru. Moc zbioru potęgowego, twierdzenie Cantora, wnioski (istnieją zbiory dowolnie dużych mocy, nie istnieje zbiór wszystkich zbiorów).

30. Pojęcie zbioru uporządkowanego. Relacje porządkujące (zwrotne, antysymetryczne, przechodnie). Uporządkowanie częściowe (istnieje relacja porządkująca), liniowe (relacja porządkująca jest spójna), dobre (w każdym niepustym podzbiorze istnieje element, który wchodzi w relację porządkującą ze wszystkimi elementami podzbioru). Twierdzenie o dobrym uporządkowaniu (dla każdego zbioru istnieje relacja, która go dobrze porządkuje).

31. Elementy maksymalne i minimalne zbioru; oraz kres górny zbioru i kres dolny zbioru.

32. Podobieństwo (izomorfizm) zbiorów liniowo uporządkowanych. Typy porządkowe.

Matematyka - plan wykładu (semestr II)

1. Obiekty (struktury kombinatoryczne), typy zagadnień występujących w kombinatoryce.

2. Elementarne prawa i metody przeliczeniowe obiektów kombinatorycznych, prawo mnożenia, prawo dodawania, ogólne prawo mnożenia, zasada bijekcji, ogólna zasada bijekcji.

3. Schematy wyboru, wariacje z powtórzeniami, wariacje bez powtórzeń, permutacje, permutacje ‘koralikowe’, kombinacje bez powtórzeń, kombinacje z powtórzeniami.

4. Związki między obiektami kombinatorycznymi.

5. Zasada włączeń i wyłączeń.

6. Ciągi binarne i współczynniki dwumianowe.

7. Tożsamości kombinatoryczne.

8. Podziały zbiorów. współczynniki wielomianowe.

9. Zasada szufladkowa Dirichleta.

10. Zależności rekurencyjne, równanie charakterystyczne, podstawowe przykłady liczby Fibonacciego, trójkąt Pascala, wieża Hanoi.

11. Funkcje tworzące i wykładnicze funkcje tworzące.

12. Operacje na funkcjach tworzących, obliczanie postaci zwartej funkcji tworzących, zastosowanie funkcji tworzących do rozwiązywania równań rekurencyjnych.

13. Podstawy teorii kodowania, pojęcie alfabetu ‘A’, słowa ‘a’, problem błędów.

14. Pojęcie metryki w przestrzeni Aⁿ, odległość Hamminga słów.

15. Schemat kodowania, problem detekcji i korekcji błędów, pojęcie kuli S_d(a) o środku w ‘a’ i promieniu ‘d’, warunki konieczne i wystarczające na to by kod wykrywał m błędów, . warunki konieczne i wystarczające na to by kod korygował m błędów.

16. Kody liniowe, pojęcie przestrzeni liniowej, parametry nadmiarowego kodu liniowego, kody liniowe postać ogólna i macierzowa, kody doskonałe, kod Hamminga.

17. Macierze Hadamara.

18. Konfiguracje - wykorzystanie do konstrukcji kodów korygujących błędy.

19. Teoria grafów – podstawowe pojęcia, graf, podgraf, trasy, ścieżki, drogi cykle.

20. Grafy planarne, spójne, eulerowskie, hamiltonowskie.

21. Izomorfizm grafów.

22. Grafy puste, pełne, cykliczne, koła, regularne.

23. Dopełnienie grafu prostego.

24. Spójność grafów, zbiór rozspajający, rozcięcie grafu, mosty, zbiór rozdzielający.

25. Problemy najkrótszych dróg w grafach i grafach skierowanych, reprezentacja macierzowa – macierz sąsiedztwa, macierz incydencji

26. Grafy skierowane z wagami, macierz wag minimalnych grafu, algorytm Warshalla.

27. Przepływy w sieciach, twierdzenia minimaksowe.

28. Asymptotyka funkcji liczbowych, hierarchia, notacja O, przekształcenia typu O.

29. Przestrzeń zdarzeń, podstawowe twierdzenia rachunku prawdopodobieństwa, niezależność zdarzeń, prawdopodobieństwo całkowite.

30. Zmienne losowe dyskretne, rozkład prawdopodobieństwa zmiennej losowej, dystrybuanta rozkładu, zmienne losowe o jednakowym rozkładzie.

31. Wartość oczekiwana, odchylenie standardowe, wariancja zmiennej losowej, rozkłady zmiennej dyskretnej.

32. Zmienne losowe ciągłe, próby, rozkład z próby, estymacja statystyczna.

33. Rozkład zmiennych losowych wielowymiarowy, korelacje.

34. Przykłady zastosowań metod statystycznych.