Matematyka dyskretna

Zakres tematyczny

1. Zbiory, relacje i funkcje. Równoliczność, działania nieskończone.

2. Aksjomaty. Dowody konstruktywne i niekonstruktywne.

3. Dowody wprost i nie wprost. Warianty indukcji matematycznej.

4. Prawa i metody zliczania.

5. Wariacje, permutacje, kombinacje, podziały.

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

7. Rozwiązywanie liniowych równań rekurencyjnych. Metoda pierwiastków

równania charakterystycznego.

8. Metoda nieoznaczonych współczynników dla typowych równań

niejednorodnych.

9. Notacje o, O, Ω, Θ.

10. Stopnie wierzchołków w grafach. Twierdzenie Eulera.

11. Izomorfizm i planarność grafów.

12. Multigrafy, ścieżki i cykle Eulera. Ścieżki i cykle Hamiltona.

13. Problem komiwojażera.

14. Algebry Boole'a.

15. Liczby pierwsze, kongruencje, chińskie twierdzenie o resztach.

Po ukończeniu kursu student powinien

- znać i rozumieć prawa i metody zliczania i formuły na liczby wariacji,

permutacji, kombinacji i podziałów przy typowych ograniczeniach,

- znać i rozumieć podane na wykładzie metody rozwiązywania liniowych

równań rekurencyjnych,

- znać i rozumieć podstawowe pojęcia i twierdzenia teorii grafów,

- znać i rozumieć minimalną aksjomatyzację algebry Boole'a i kojarzy ją

z bramkami logicznymi NAND i NOR,

- znać i rozumieć podstawowe twierdzenia dotyczące liczb pierwszych

i chińskie twierdzenie o resztach,

- potrafić rozwiązywać typowe zadania związane z materiałem wykładów

i ćwiczeń.

nie dotyczy

Celem wykładu jest zaznajomienie studentów z zagadnieniami matematyki dyskretnej, które są kluczowe dla kontynuacji studiów I stopnia zarówno na kierunkach matematyka, jak i informatyka.

K.A. Ross, Ch.R.B. Wright, Matematyka dyskretna, PWN 2006.

W. Marek, J. Onyszkiewicz, Elementy logiki i teorii mnogości w zadaniach, PWN 2003.

Elementy logiki i teorii mnogości