Zkouška 9.6.2008
-
- Matfyz(ák|ačka) level I
- Příspěvky: 44
- Registrován: 2. 2. 2008 09:35
- Typ studia: Informatika Bc.
Zkouška 9.6.2008
Máme město M, jehož mapa je mřížka.
- V tomto městě je 999x999 bloků, tedy 1000 x 1000 křižovatek
- Na každé křižovatce je kamera
- máme k dispozici záznamy ze všech kamer
- záznamy jsou ve tvaru :
> jednoznačné ID kamery - 9 znaku
> čas
> jmeno osoby na kameře
> jednoznacne cislo pasu osoby
> obvod pasu osoby
> trvale bydiste osoby
- nekterym kameram jdou hodiny o pet minut napred, nevime kterym
- nevime, ktera kamera kde je
- kamera urci totoznost vsech lidi na krizovatce
- obyvatele mesta ujdou vzdalenost mezi krizovatkami za 5 minut
- obyvatel mesta neni vic nez 1 000 000
- obyvatele muzou i stat, a to vzdy 5, 10, 15.... minut
- jednou za pet minut jsou vsichni obyvatele na nejake krizovatce
Ve meste je muzeum a autobusove nadrazi.
- zname ID kamer na nadrazi a u muzea
- z nadrazi odjizdi v 18:00 autobus s neomezenou kapicitou, kdo byl na nadrazi v 18:00, mohl odjet
- autobus je jedina cesta ven z mesta
- muzeum nekdo vykradl v case Č, lupiči s lupem stali v case Č pred muzeem
Ukolem je zjistit, zda se mohlo stat, ze lupici, za pomoci libovolneho poctu komplicu, mohli stihnout dopravit lup na nadrazi a odjet autobusem v 18:00.
- predani lupu mezi komplici muze probehnout pouze na krizovatce a "trva 0 casu"
- máme k dispozici záznamy kamer 24 před vykradením muzea až do 19:00
Vstup Programu: Cas Č, záznamy kamer
Výstup Programu: Odpoved: Ano / Ne / Nelze urcit
Hodně zábavy při řešení!!:-)
- V tomto městě je 999x999 bloků, tedy 1000 x 1000 křižovatek
- Na každé křižovatce je kamera
- máme k dispozici záznamy ze všech kamer
- záznamy jsou ve tvaru :
> jednoznačné ID kamery - 9 znaku
> čas
> jmeno osoby na kameře
> jednoznacne cislo pasu osoby
> obvod pasu osoby
> trvale bydiste osoby
- nekterym kameram jdou hodiny o pet minut napred, nevime kterym
- nevime, ktera kamera kde je
- kamera urci totoznost vsech lidi na krizovatce
- obyvatele mesta ujdou vzdalenost mezi krizovatkami za 5 minut
- obyvatel mesta neni vic nez 1 000 000
- obyvatele muzou i stat, a to vzdy 5, 10, 15.... minut
- jednou za pet minut jsou vsichni obyvatele na nejake krizovatce
Ve meste je muzeum a autobusove nadrazi.
- zname ID kamer na nadrazi a u muzea
- z nadrazi odjizdi v 18:00 autobus s neomezenou kapicitou, kdo byl na nadrazi v 18:00, mohl odjet
- autobus je jedina cesta ven z mesta
- muzeum nekdo vykradl v case Č, lupiči s lupem stali v case Č pred muzeem
Ukolem je zjistit, zda se mohlo stat, ze lupici, za pomoci libovolneho poctu komplicu, mohli stihnout dopravit lup na nadrazi a odjet autobusem v 18:00.
- predani lupu mezi komplici muze probehnout pouze na krizovatce a "trva 0 casu"
- máme k dispozici záznamy kamer 24 před vykradením muzea až do 19:00
Vstup Programu: Cas Č, záznamy kamer
Výstup Programu: Odpoved: Ano / Ne / Nelze urcit
Hodně zábavy při řešení!!:-)
Wenn ich morgen meinem Gott gegenüberstehe, kann ich sagen:
Ich bin unschuldig,
ich habe niemanden betrogen,
ich habe niemandem weh getan,
ausser mir selbst.
Und das wird er mir wohl verzeihen!
Ich bin unschuldig,
ich habe niemanden betrogen,
ich habe niemandem weh getan,
ausser mir selbst.
Und das wird er mir wohl verzeihen!
-
- Matfyz(ák|ačka) level I
- Příspěvky: 13
- Registrován: 22. 9. 2007 08:23
- Typ studia: Informatika Bc.
- Bydliště: kolej 17. listopadu
Re: Zkouška 9.6.2008
Dodatek: k dispozici je neomezeně místa na disku, ale pouze 3 MB paměti
Re: Zkouška 9.6.2008
Ten příklad ale vůbec není složitý, ba naopak - před zkouškou jsem si zkoušel vyřešit některé příklady z tohoto fóra z minulých let a vůbec jsem s nimi nehnul. Tady stačí jen opravit údaje vadných kamer, vytvořit z dostupných údajů graf a tam už je pomocí BFS snadno vidět výsledek.
Pravda, je to poněkud ošemetné - pokud se ve městě bude pohybovat málo lidí, téměř žádný graf nepostavíte, ale vsadil jsem na to a řešení to evidentně bylo správné (nebo je jich víc? Pochlubte se).
Pravda, je to poněkud ošemetné - pokud se ve městě bude pohybovat málo lidí, téměř žádný graf nepostavíte, ale vsadil jsem na to a řešení to evidentně bylo správné (nebo je jich víc? Pochlubte se).
-
- Matfyz(ák|ačka) level I
- Příspěvky: 3
- Registrován: 28. 5. 2008 17:05
- Typ studia: Informatika Bc.
Re: Zkouška 9.6.2008
No jo, ono to řešení bylo snadné. Bylo hned jasné pustit na to vlnu, jenže ono tenhle příklad nebyl ani tak na to najít algoritmus řešení, ale na to navrhnutí datových struktur a reprezentaci dat.
Ono právě bylo třeba hlavně vyřešit jak si to pamatovat. Já jsem to tam jen tak lehce nastínil a pan RNDr. Holan mi na to řekl, že by se mi to nevešlo do paměti, tak jsem tak mírně zamumlal něco jako, že bych si to asi musel uložit do souboru a hned jsem dostal další kartáč, že "To byste jako chtěl v každém kroku prohledávat ten soubor? To byste se nedočkal !". Takže se to muselo zkutit asi nějakým fikaným způsobem, aby se tot vlezlo do paměti.
Ono právě bylo třeba hlavně vyřešit jak si to pamatovat. Já jsem to tam jen tak lehce nastínil a pan RNDr. Holan mi na to řekl, že by se mi to nevešlo do paměti, tak jsem tak mírně zamumlal něco jako, že bych si to asi musel uložit do souboru a hned jsem dostal další kartáč, že "To byste jako chtěl v každém kroku prohledávat ten soubor? To byste se nedočkal !". Takže se to muselo zkutit asi nějakým fikaným způsobem, aby se tot vlezlo do paměti.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 44
- Registrován: 2. 2. 2008 09:35
- Typ studia: Informatika Bc.
Re: Zkouška 9.6.2008
K te datove reprezentaci:
Pan Dr. Töpfer mi prozradil, že asi nelepsi reprezentace je, udelat si bitove pole s milion prvky, kde kazdy bit reprezentuje jednoho obcana. No, a bit je jedna, pokud je obcan potencialni komplic a 0 pokud ne.
Potom staci v čase Č pustit vlnu a v 18.00 se podivat, jestli nekdo z lidi u nadrazi ma bit nastaven na 1.
akorat mi nebylo jasny, jak si budu pamatovat, ktery policko komu patri..Ze bych hašoval cislo pasu???
Pan Dr. Töpfer mi prozradil, že asi nelepsi reprezentace je, udelat si bitove pole s milion prvky, kde kazdy bit reprezentuje jednoho obcana. No, a bit je jedna, pokud je obcan potencialni komplic a 0 pokud ne.
Potom staci v čase Č pustit vlnu a v 18.00 se podivat, jestli nekdo z lidi u nadrazi ma bit nastaven na 1.
akorat mi nebylo jasny, jak si budu pamatovat, ktery policko komu patri..Ze bych hašoval cislo pasu???
Wenn ich morgen meinem Gott gegenüberstehe, kann ich sagen:
Ich bin unschuldig,
ich habe niemanden betrogen,
ich habe niemandem weh getan,
ausser mir selbst.
Und das wird er mir wohl verzeihen!
Ich bin unschuldig,
ich habe niemanden betrogen,
ich habe niemandem weh getan,
ausser mir selbst.
Und das wird er mir wohl verzeihen!
Re: Zkouška 9.6.2008
Jak se mam naucit na tuto zkousku ?
Na pisemku asi moc ne, ale co ustni cast ? Z prednasek jsem si moc nepsal
Na pisemku asi moc ne, ale co ustni cast ? Z prednasek jsem si moc nepsal
-
- Matfyz(ák|ačka) level I
- Příspěvky: 2
- Registrován: 13. 6. 2008 16:57
- Typ studia: Informatika Bc.
Re: Zkouška 9.6.2008
Doporucuji ti procist si slajdy z Topferovych prednasek, kde je vse podstatne...a nebo samozrejme jeho knizku urcenou k tomuto predmetu
- hkvm
- Matfyz(ák|ačka) level II
- Příspěvky: 50
- Registrován: 3. 6. 2008 20:45
- Typ studia: Informatika Mgr.
- Kontaktovat uživatele:
Re: Zkouška 9.6.2008
Z velké části se požadavky kryjí s Algoritmy (kde je toho ještě dost navíc). Osobně jsem u Töpfera neslyšel žádnou otázku, která by nemohla být položena i v Algoritmech. Jestli už jsi je dělal, tak se toho moc učit nemusíš. Podívej se v SISu do sylabu předmětu a uvidíš na co mrknout.Návštěvník píše:Jak se mam naucit na tuto zkousku ?
Na pisemku asi moc ne, ale co ustni cast ? Z prednasek jsem si moc nepsal
Re: Zkouška 9.6.2008
tak dnes bylo na zkousce opet toto zadani, ma nekdo nejaky napad jak to resit? zda se mi ze je tam dost dulezita ta reprezentace dat kterou jsem moc nezvladl, tak to by mi pomohlo asi nejvice.
a taky by me zajimalo jak vypadala ta ustni cast, na co se profesori ptali a tak...
slajdy jsem si celkem prosel ale stejne si neprijdu ze bych to nejak moc umel, jsou v pohode nebo jak to vypada?
na ustni jdu ve stredu tak mam jeste trochu casu nejak svoje znalosti vylepsit ale moc nevim teda
a taky by me zajimalo jak vypadala ta ustni cast, na co se profesori ptali a tak...
slajdy jsem si celkem prosel ale stejne si neprijdu ze bych to nejak moc umel, jsou v pohode nebo jak to vypada?
na ustni jdu ve stredu tak mam jeste trochu casu nejak svoje znalosti vylepsit ale moc nevim teda
Re: Zkouška 9.6.2008
Můžete mi prosím někdo blíže nastínit, jakým způsobem se vypořádat s případnými chybnými časovými údaji na jednotlivých kamerách? Někdo zde psal, že si nejprve časové údaje opravíme, ale nějak mě nenapadá, jak. Děkuji.