# zkouska 25.1.

<{ForumPost(poster="Anonymous", timestamp=2006-01-25 16:25:28)}>
Ahoj!  
Takze dneska byly na pisemce nasledujici ukoly, snad to nekomu pomuze.  
  
1) sestrojit aha-corasick pro slova centrum, cena, vincent, vina  
  
2) najeka silenost s termitama a cistenim budovy prstencovyho tvaru :D  Zadani dost dlouhy, ani si ho poradne nepamatuju. Cepek rikal, ze prej to z asi 20 lidi nedal nikdo.  
  
3) dokazat, ze je tezky problem celociselneho programovani ( s vyuzitim tech 6 problemu z prednasky). Problem celociselneho programovani je to, ze mate celociselnou matici A a celociselny vektor b. A mate najit vektor x, kde jeho slozky jsou 0 a 1 tak, aby platilo A*x <= b.
<{/ForumPost}>

<{ForumPost(poster="stviper", timestamp=2006-01-26 09:57:57)}>
No ja si na te 2.priklad pamatam velmi dobre.   
  
Zadanie:  
Predstavte si ze mate n miestnosti ktore su usporiadane do kruhu. Kazda miestnost je zamorena termitmy. Je nutne vycistit kazdu miestnost a mate   
na to m dni. Vycistenie i-tej miestnosti v j-ty den stoji cij. No lenze problem je v tom ze ked vycistite i+1 miestnost a i-ta este nebola vycistena tak sa moze stat ze termity sa rozsiria na i+1 miestnost. ( Spat sa nemozu sirit. To znamena ze ak je i-1 vycistena a i nie tak to je v pohode). Potom je nutne i+1 miestnost posipat chemikaliami za ktore treba tiez zaplatit. Cena je urcene cislo sij, kde i hovori ze i+1 je cista i-ta este nie a j hovori kolko dni trvalo (od vycistenia i+1) kym sa vycistila aj i-ta.  
Ulohou bolo navrhnut algoritmus ktory navrhne rozvrh cistenia na kazdy den tak aby cena bola co najmensia.  
  
Takze asi tolko k zadaniu. Ako prve ma napadlo riesit to cez toky v sietach ale nevedel som s tym pohonut. Tak som si povedal ze napisem aspon nejake riesenie tak som pouzil aproximacny algoritmus vylepsenej fronty. Toto sa Kucerovi (ktory ma skusal nepacilo) ze oni chceli algoritmus ktory da presne riesenie. Tak som sa ho spytal, ako sa to malo vyriesit. Usmial sa a povedal ze nevie  :lol:  Sa isiel spytat toho druheho a on povedal ze cez toky v sietach. A dodal este ze to nikto nemal a ze to bol velmi tazky priklad.  
No co k tomu dodat.... Myslim si ze tentokrat to s tou optiaznostou dost prehnali  :roll:
<{/ForumPost}>