Diskrétní matematika

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra matematiky

Anotace:

Cílem kursu je uvést studenty do některých oblastí matematiky

mimo běžně probíranou spojitou matematiku. Společným jmenovatelem

je diskrétní přístup, kombinatorické myšlení a náhled do způsobu

myšlení a zápisu v matematice. Kurs přiblíží témata mohutnosti

množin a vlastnosti přirozených čísel, relace na množině,

binomickou větu a kombinatoriku, matematickou indukci a rekursi.

Požadavky:

Informace viz http://math.feld.cvut.cz/habala/teaching/dma.htm

Osnova přednášek:

1. Množiny a zobrazení, mohutnost, spočetné a nespočetné množiny.

2. Matematická indukce a rekurze.

3. Binární relace na množině, relace ekvivalence.

4. Relace uspořádání, dobře uspořádané množiny.

5. Dělitelnost, (rozšířený) Eukleidův algoritmus.

6. Kongruence, počítání modulo s celými čísly.

7. Binární operace a grupy.

8. Pokročilejší počítání modulo.

9. Kombinatorika, princip inkluze a exkluze.

10. Rekurentní rovnice. Homogenní lineární případ.

11. Řešení nehomogenních rekurentních rovnic s konstantními koeficienty.

12. The Master theorem.

13. Odpadne.

Osnova cvičení:

1. Množiny, kombinatorika.

2. Množiny, zobrazení a spočetnost s důkazy.

3. Důkazy matematickou indukcí.

4. Vlastnosti binárních relací.

5. Uspořádání, důkazy faktů o relacích.

6. (Rozšířený) Eukleidův algoritmus, důkazy s dělitelností.

7. Počítání modulo n.

8. Důkazy s relacemi a operacemi.

9. Řešení rovnic modulo.

10. Princip inkluze a exkluze.

11. Řešení homogenních lineárních rekurentních rovnic.

12. Řešení nehomogenních lineárních rekurentních rovnic.

13. Rezerva.

Cíle studia:

Studijní materiály:

[1] Skripta na fakultních stránkách přednášejícího.

[2] K.H.Rosen: Discrete matematics and its aplications, McGraw-Hill, 1998.

Poznámka:

Rozsah výuky v kombinované formě studia: 14p+6s

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Otevřená informatika - Počítačové systémy (povinný předmět programu)
• Otevřená informatika - Informatika a počítačové vědy (povinný předmět programu)
• Otevřená informatika - Softwarové systémy (povinný předmět programu)
• Otevřená informatika, před rozřazením do oborů (povinný předmět programu)