Ahojte,
takze vam vsetkym hrdo ako prvy oznamujem, co sa dialo na skuske z TEA
u uja Durisa. Mal som nasledujuce otazky:

1. Dynamicke programovanie.
   Rypal, ze ci je hento o ono dynprog, niekolko online prikladov,
ktore odo mna chcel :) riesit. No, riesit som to riesil, on vsak chcel
aj dokazat, ze moje riesenie je najspravnejsie. Oooops ;)  So
spravnostou rieseni vsak vacsinou suhlasil, co dava vediet, ze
priklady neboli zase az tak strasne zlozite. Tu su dva:
a) Ako co najefektivnejsie zistit, kolko jedniciek je vo VELKOM
binarnom subore.
b) Mam ruru, na ktorej su diery (zanedb. rozmeny) a mam 1 meter dlhe
zaplaty. Ako co najefektivnejsie zaplatat.

2. k-ty najmensi prvok.
   Vsetko okolo toho, teda rozbor konstant, preco takto a nie inak,
bla bla.

Okrem toho este sondy do celej latky, bol som tam 55 minut...
Ak si vyriesite cvicenia v skriptach, malo b to byt v pohode a dostat
znamku najlepsiu. Da sa to.

-----------------------------------------------------
 Predtermin: 7 ludi - vsetci za jedna, kazdy tam bol aspon hodinu

 dostal som: rozdeluj a panuj + Strassen matice
           a najlacnejsia kostra

 urobil som to strucne, potom sa na nieco popytal, no a potom sme kecali uplne
o niecom inom;
							Mat

P.S.: tipol by som si, ze normalny termin bude trochu iny

-----------------------------------------------------
Cafte fsetci!

Na skuske som dostal nasledovne otazky:
  1.   Union/Find-Set problem
  2.   NP uplne problemy
  2.1. Vrcholove pokrytie grafu

Prakticky sa to neda vsetko povedat za tych kratkych 30-45 minut, takze
odporucam hovorit len o tych veciach, ktore viete najlepsie.
Treba sa tvarit suverenne, ale vsetko s mierou (nie je dobre si robit srandu).
Na Durisovej tvari nie je vidno, ci trepete blbiny alebo nie...

AD 1
  Q: Preco pri pouziti kompresie cesty sa v Unione nevyvazuje 
     podla vysok stromov, ale podla poctu vrcholov v tychto stromoch?
  A: Lebo medved - Find-Set tieto vysky modifikuje a bolo by ich treba
     opakovane preratavat. Pocet vrcholov sa urcuje velmi jednoducho.

AD 2
  Okrem beznych veci, ako NP-uplne jazyky, SAT, CSAT, k-SAT, 3-SAT,
  k-klika, 3-zafarbitelnost, TSP (POC), TSP-OPT, HAM, atd, sa detailnejsie 
  zaujimal o polynomialnu transformovatelnost, ktoru som pekne zhnojil...
  Ponaucenie - ak nieco nahodou nebudete vediet dobre popisat slovami,
               napiste mu to na papier recou matematika.
  
AD 2.1
  Q: Vieme, ze problem zistenia, ci pre dany graf existuje vrcholove
     pokrytie o nanajvys k vrcholoch je NP-uplny.
     Ako je to s problemom zistenia, ci pre dany graf existuje vrcholove
     pokrytie o aspon k vrcholoch?
  A: Asi nie je NP-uplny - staci porovnat cislo k s poctom vrcholov grafu.
     Ja som chcel dokazat, ze je NP-uplny, ale dokaz, ze P=NP bol
     nad moje sily. 

AD Cela skuska
  Myslim, ze ak si den pred skuskou raz precitate nieco k TEA
  a nasledne sa riadne ozeriete, ale nanajvys tak, ze rano budete schopni 
  vstat vcas na skusku, mate sancu dostat jednotku.
 

                                              Rado
-----------------------------------------------------
Caute 5inf!

Vzhladom na to, ze moj predosly mail ku TEA bol oznaceny za provokativny,
tymto mailom sa vam ospravedlnujem a pripajam nieco naviac.

  Dokazte alebo vyvratte:
    Jazyk L = { w | w je prvocislo kodovane binarne } je NP-uplny.

No, a toto bola dalsia provokacia. 
Napriek tomu vam zelam prijemne prezitie sviatkov, 
tym menej narocnym aspon prezitie sviatkov...

                                                   Rado              
----------------------------------------------------------------------
caute

bol som jediny na termine, odpovedal som asi 10 minut a sebakriticky som uznal
ze to sice neviem naspamat ale ze som to pochopil. potom sme sa hodinu bavili o
ekonomii, smerovani ludstva, generalizacii podla narodnostnych kriterii a
podobne.

otazky:
1. najlacnejsia kostra + zlozitost
2. dynamicke programovanie, mozne nevyhody, uviest priklad

vysledok: vyborne

pozdravuje pepe