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í!!:-)

Dodatek: k dispozici je neomezeně místa na disku, ale pouze 3 MB paměti :?

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).

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.

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??? :-)

Jak se mam naucit na tuto zkousku ? :)
Na pisemku asi moc ne, ale co ustni cast ? Z prednasek jsem si moc nepsal :(

Doporucuji ti procist si slajdy z Topferovych prednasek, kde je vse podstatne...a nebo samozrejme jeho knizku urcenou k tomuto predmetu :wink:

Návštěvník wrote:Jak se mam naucit na tuto zkousku ? :)
Na pisemku asi moc ne, ale co ustni cast ? Z prednasek jsem si moc nepsal :(

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.

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 :)

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.