písemka 18.1.2006

Písemka byla zdá se standartní - 4 příklady, z nichž jeden měl a),b),c), jeden důkaz a 2 počítací...

Velmi zhruba to bylo něco jako:

1. a) definice transitivní relace + pár příkladů k určení, jestli jde o trans.
   b) definice stromu + dk. ze strom s vrcholem stupně 4 má alespoň 4 listy
   c) definice barevnosti a pár grafů určit barevnost

2. Formulace a důkaz binom. věty...

3. Máte písmena A,O,K,P,S,T,V,D a máte zjistit kolika způsoby je lze seřadit, aby z nich nešlo sestavit ani jedno ze slov: KOP,PAST,VODA
   pozn.: př. K .... O .... P ... z takové kombinace lze KOP sestavit..

4. To bylo něco na eulerovský tahy, ale nebylo to moc těžký - rozhodně ne tak, jako ta 3 :wink:

Tak hodně štěstí do diskrétky všem!!

Ta trojka je triviální, hodíš na to PIE..

Este uvediem presne znenie 4. ulohy:
Necht pro n >= 1 znaci symbol Gn graf, jehoz vrcholy jsou vsechna slova delky n nad triprvkovou
abecedou {a,b,c} (napr: pro n = 5 jeden takovy vrchol je slovo aacbb) a dva vrcholy tvori hranu,
prave kdyz se dve odpovidajici slova lisi na jedinem miste a jinak se shoduji. Rozhodnete, pro
ktere n = 1,2,... se graf Gn da nakreslit jednim uzavrenym tahem bez opakovani hran.

Inak, znamkovanie bolo mierne. Za kazdy priklad bolo 6 bodov - dokopy teda 24.
< 7b => dovidenia
< 11b => boj o 3ku
...
20 - 24 => jednotka.
Ak sa niekomu nezdala znamka, nasledovalo ustne doskusanie.

Nevite nekdo, jak se delala ta ctyrka? Mam problem zjistit, kdy je takovej graf souvislej. Diky moc!

Anonymous wrote:Nevite nekdo, jak se delala ta ctyrka? Mam problem zjistit, kdy je takovej graf souvislej. Diky moc!

No tak souvisly je snad vzdy (myslim, tu pisemku jsem nepsal ;) ) Jednoduse bych ukazal ze mezi libovolnymi 2 vrcholy existuje cesta -> proste jdu od prvni pozice a koukam az naracim na pismenko ve kterym se vrcholy lisi ->a to pismenko zmenim (napr aabbc -> aabcc) -> takze po max 5 krocich dostanu z libovolneho "slova" jakekoliv jine. :)

Celkem bylo dvacet bodu (kazdy priklad za 5)

Na trojku stacilo mit 11 bodu
Kdo mel 7 tak toho este vyzkousel a <7 si to daj znovu...

** Prince_of_Persia napsal:**

Celkem bylo dvacet bodu (kazdy priklad za 5)

 Na trojku stacilo mit 11 bodu

Teda tu zkoušku sem dělal taky a bodu za každej příklad bylo určitě 6 - dohromady teda 24.
Na tu trojku je ale pravda že stačilo 11 bodů a bylo to bez dozkoušení...

 ** Zdeněk Vilušínský napsal:**
 

Ta trojka je triviální, hodíš na to PIE.

No ono bylo přímo v zadání, že se na to má použít PIE :wink:
Ale pořád si myslim, že to byl nejtěžší příklad z těch 4 i když asi pro někoho těžkej nebyl...hlavně pro ty, co si poctivě dopředu propočítali příklady z minulejch let, kde byl v jedný písemce prakticky stejnej příklad.. :P

Void wrote: Ale pořád si myslim, že to byl nejtěžší příklad z těch 4 i když asi pro někoho těžkej nebyl...hlavně pro ty, co si poctivě dopředu propočítali příklady z minulejch let, kde byl v jedný písemce prakticky stejnej příklad.. :P

No nebyl uplne snadnej, ale nekdo kdo mel uplne totozny priklad v zapoctovy pisemce (akorat jsme meli trochu jiny pismenka) ho musel dat levou zadni! ;)))

Právě, my jsme takový příklad dělali na cvíkách :)
Ale říkám si, že ten předtermín byl takový hezčí než ta písemka..

Zdeněk Vilušínský wrote:Právě, my jsme takový příklad dělali na cvíkách :)
Ale říkám si, že ten předtermín byl takový hezčí než ta písemka..

No nevim, bin. veta byla tam i tam a ten zbytek... U toho predterminu se mi moc nelibi ta trojka - dokazat ze pro souvisly G ex. u,v tz: G-u, G-v i (G-u)-v jsou souvisle. To tahle pisemka byla mnam! Takovou zitra dostat...
(At uz mam diskretku za sebou! :) )