PředmětyPředměty(verze: 807)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Diskrétní matematika - NMIN105
Anglický název: Discrete Mathematics
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Garant: prof. RNDr. Martin Loebl, CSc.
doc. RNDr. Jiří Fiala, Ph.D.
Třída: M Bc. FM
M Bc. FM > Povinné
M Bc. FM > 1. ročník
M Bc. MMIB
M Bc. MMIB > Povinné
M Bc. MMIB > 1. ročník
M Bc. OM
M Bc. OM > Povinné
M Bc. OM > 1. ročník
Kategorizace předmětu: Informatika > Diskrétní matematika
Matematika > Diskrétní matematika
Neslučitelnost : NDMA005
Záměnnost : NDMA005
Anotace -
Poslední úprava: G_M (16.05.2012)

Základní přednáška z diskrétní matematiky pro všechny odborné obory bakalářského programu Matematika.
Podmínky zakončení předmětu
Poslední úprava: prof. RNDr. Martin Loebl, CSc. (09.10.2017)

Zapocet je nutnou podminkou ucasti u zkousky.

Podminky pro slozeni zapoctu: domaci ukoly celkem 100 bodu, nutno ziskat aspopn 70. Budou 3 pisemky, kazda 100 bodu, nutno ziskat celkove aspon 210 bodu. Navic bude jedna opravna pisemka. Dale je mozne ziskat bonusove body za praci na cviceni: to zalezi na cvicicim.

Povaha kontroly studia predmetu vylucuje opakovani teto kontroly, tedy zapoctu.

Literatura
Poslední úprava: doc. Mgr. Robert Šámal, Ph.D. (12.09.2012)

J.Matoušek, J.Nešetřil: Kapitoly z diskrétní matematiky, MATFYZPRESS 1996

J.Nešetřil: Kombinatorika I, grafy, SPN Praha 1983

P.Štěpánek, B.Balcar: Teorie množin, Academia Praha 1986

Požadavky ke zkoušce
Poslední úprava: prof. RNDr. Martin Loebl, CSc. (09.10.2017)

Zkouska je ustni. Pozadavky u ustni zkousky odpovidaji sylabu predmetu v rozsahu, ktery byl prezentovan na prednasce.

Sylabus -
Poslední úprava: G_M (16.05.2012)

  • Pojem množiny (Cantor), jazyk teorie množin, formule. Popis množiny výčtem nebo jako množiny prvků "dané vlastnosti". Základní operace s množinami (vč. potence a sumy) a jejich vlastnosti.
  • Kartézský součin, (binární) relace, skládání relací. Funkce, funkce prostá a na. Vlastnosti relací (reflexivita, symetrie,...). Relace ekvivalence na množině, rozklad množiny, vzájemný vztah, příklady.
  • Uspořádání, lineární uspořádání, největší/nejmenší, maximální/minimální,... prvek, příklady. Izomorfizmus množin vzhledem k relacím. Dobré uspořádání. Dobré uspořádání přirozených čísel podle velikosti, princip indukce pro přirozená čísla.
  • Kombinatorické počítání. Počet zobrazení (prostých zobrazení) n-prvkové do m-prvkové množiny, počet podmnožin n-prvkové množiny. Variace, permutace, kombinace. Kombinační čísla, binomická věta. Princip inkluze a exkluze.
  • Definice grafu, základní terminologie, izomorfizmus grafů. Stupeň uzlu, skóre grafu. Cesty v grafu, souvislost, komponenty, hledání nejkratší cesty. Metrika v grafu a pojmy z ní odvozené. Stromy, jejich charakterizace a vlastnosti, počet stromů na dané množině, kostra grafu, hledání minimální kostry. Izomorfizmus stromů, kódování stromů. Rovinné grafy, Eulerova formule a její důsledky. Obarvení rovinného grafu pěti barvami.

 
Univerzita Karlova | Informační systém UK