Zkouška 9.6.2008

Pokračování základního kursu programování pro studenty 1. ročníku bakalářského studia informatiky a učitelství informatiky. Výuka bezprostředně navazuje na předmět PRG030 Programování I výkladem dalších algoritmů a jejich programové realizace, postupů a technik užívaných při tvorbě programů. Posluchači se seznámi se základy objektového programování a práce v současných vývojových prostředích. Předpokládají se vstupní znalosti v rozsahu předmětu PRG030 Programování I.
JiriD
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

Příspěvek od JiriD »

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

Příspěvek od OndraC »

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

Re: Zkouška 9.6.2008

Příspěvek od Turista »

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

Příspěvek od Tempest »

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

Příspěvek od JiriD »

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??? :-)
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!
Návštěvník

Re: Zkouška 9.6.2008

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

Jak se mam naucit na tuto zkousku ? :)
Na pisemku asi moc ne, ale co ustni cast ? Z prednasek jsem si moc nepsal :(
htfm
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

Příspěvek od htfm »

Doporucuji ti procist si slajdy z Topferovych prednasek, kde je vse podstatne...a nebo samozrejme jeho knizku urcenou k tomuto predmetu :wink:
Uživatelský avatar
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

Příspěvek od hkvm »

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 :(
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.
kua

Re: Zkouška 9.6.2008

Příspěvek od kua »

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

Re: Zkouška 9.6.2008

Příspěvek od asdfghjkl »

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

Zpět na „PRG031 Programování II“