zkouska 25.1.

Návštěvník

zkouska 25.1.

Příspěvek od Návštěvník »

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.
Uživatelský avatar
stviper
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 23. 1. 2005 18:12
Typ studia: Informatika Bc.
Bydliště: Troja
Kontaktovat uživatele:

Příspěvek od stviper »

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:
Odpovědět

Zpět na „2005“