Zkouška 26.5.2010 13:00 - Mareš

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.
Jookyn
Matfyz(ák|ačka) level III
Příspěvky: 115
Registrován: 13. 9. 2008 21:42
Typ studia: Informatika Mgr.

Zkouška 26.5.2010 13:00 - Mareš

Příspěvek od Jookyn »

1) Dokázat odhad - 2^(n/2) <= R(n) <= 2^(2n)
2) # zobrazení {1...a} na {1...b}
3) Máme KPR, kde místo nultého axiomu (existence čtverce) máme: pro každé p z P: |p| >= 2. Jaké defektní KPR touto záměnou přibudou?
4) Pro každé k: (množinový systém (X,S) má SRR až na k množin <=> každé T podmnožina S |U T| >= |T|-k)
(*) Mohou existovat dvě různé mocniny dvojky, které jsou až na pořadí číslic v desítkové soustavě stejné? Dokázat

Přičemž jsme měli udělat příklad 1 a pak si vybrat 2 příklady z {2,3,4}, * byla spíš něco navíc.
amik
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 18. 1. 2010 21:32
Typ studia: Informatika Bc.

Re: Zkouška 26.5.2010 13:00 - Mareš

Příspěvek od amik »

*SPOILER ALERT* není to složité přijít na to sám

Nástin řešení:
1) máme v sešitě
2) pomocí principu inkluze a exkluze

3) rozebráním nejjednodušších případů se začne rýsovat toto:
a) jedna přímka procházející všechny body
b) -//- až na jeden mimo přímku - z něj vede n-1 přímek velikosti 2, každá do jednoho bodu na "původní" přímce
Stačí ukázat, že více přímek /p/ >= 3 by vytvořilo čtverec a pokud je jen jedna taková, nemůže mimo ní ležet více než 1 bod => postihli jsme všechny případy.

4) stačí X doplnit o k prvků a ty vložit do všech množin v S -> splňuje klasickou Hallovu podmínku -> utvoříme SRR a odebereme ty množiny, které mají jako reprezentanty ony doplněné prvky - těch je nejvýše K - z původních množin zbude alespoň n-k

*) jen napovím, že pořadí číslic nemění zbytek po dělení devíti
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“