Předmět je zakončen testem, na jehož základě bude udělen klasifikovaný zápočet.

Z: Turzík, Pavlíková: Diskrétní matematika, skripta, VŠCHT Praha, 2007, ISBN:978-80-7080-667-8

R: Turzík, Pavlíková: Diskrétní matematika, skripta, VŠCHT Praha, 2007, ISBN:978-80-7080-667-8

Přednášky a cvičení.

Lectures and seminars

1.Množiny, relace, uspořádané množiny.

2.Základní kombinatorické pojmy.

3.Počítání objektů.

4.Základy logiky. Booleovské funkce.

5.Číselné soustavy a konečná tělesa.

6.Základní pojmy teorie grafů.

7.Stromy.

8.Cesty v grafech. Úloha nejkratší cesty.

9.Eulerovské a Hamiltonovské grafy.

8.Kostra grafu. Hladový algoritmus.

9.Rychlé třídění.

10.Rovinné grafy a jejich charakteristika.

11.Barevnost.

12.Problém 4 barev.

13.Teorie složitosti. Problémy třídy P a NP. Dobrá charakteristika.

14. Aplikace grafů v teorii her. Jádro grafu. Vyhrávající strategie. Hra NIM.

1.Sets, relations, posets.

2.Basic combinatorial notions.

3.Counting of objects.

4.Logics. Boolean functions.

5.Finite fields

6.Basic notions of graph theory.

7.Trees.

8.Paths in graphs. The shortest path in a graph.

9.Euler and Hamiltonian graphs.

8.Spanning tree and greedy algorithm.

9.Quick sorting.

10.Plannar graphs and their charecterization.

11.Coloring of graphs.

12.Four colors problem.

13.Polynomial and exponential algorithms. Classes P, NP and co-NP.

14.Application of graph theory in theory of games. Game NIM and winning strategy.

http://www.vscht.cz/mat/ZMO/Kap3.mws

http://teorie-grafu.cz/

http://www.vscht.cz/mat/ZMO/Kap3.mws

http://teorie-grafu.cz/

Měkké kompetence:

1. Zvládnutí základních pojmů diskrétní matematiky

2. Znalost a pochopení základních postupů

General skills:

1. basic terms in discrete mathematics

2. knowledge and understanding of basic algorithms

3. individual problem solving

Matematika I nebo Matematika A

Mathenatics I or Mathenatics A