Algoritmy pro rozsáhlá data Mgr. Adéla Laštovičková

Zápočet

• Pro splnění zápočtu je třeba vypracovat tři úkoly zadané v průběhu semestru. Řešení úkolů se bude odevzdávat na cvičení rukou psané na papíře, nebude-li řečeno jinak.

První zápočtový úkol

Stáhněte si dataset Chicago crime. Naivně vyřešte:

1. Postupně v datasetu najděte případy s číslem: JK405272, HM620674 , JK403555, HJ160895, HT431595, JF199429, HS529388, G600951, JK405655, HP279915.
2. Zjistěte, kolik bylo úspěšných zlodějů aut a úspěšných žhářů.
3. Zjistěte, kolik různých případů řešil policejní okrsek 007 v roce 2004. (Různých ve smyslu, že mají různé case number.).

Při řešení nesmíte načíst do paměti celý soubor najednou.
Ideu řešeních spolu s odhadem jejich časových a prostorových složitostí odevzdejte čitelně rukou na papíře napsané nejpozději do 6.10.2026. Své řešení si také můžete naprogramovat v jazyce Python (doporučuji).

Druhý zápočtový úkol

S využitím struktur a algoritmů, jenž se naučíte/jste se naučili v průběhu semestru vyřešte problémy prvního úkolu, tedy:

1. Najít připad s daný Case_id.
   Pak vyhledejte postupně případy s čísly: JK405272, HM620674 , JK403555, HJ160895, HT431595, JF199429, HS529388, G600951, JK405655, HP279915.
2. Zjistit počet úspěšných (nezatčených) zlodějů/žhářů/projedců drog/...
   Pak zjistěte počet úspěšných zlodějů aut a počet úspěšných žhářů.
3. Zjistěte, kolik různých případů řešil policejní okrsek 007 v roce 2004. (Různých ve smyslu, že mají různé case number.)

U všech řešení odhadněte jejich časovou, prostorovou a I/O složitost. Pokud v řešení použijete strukturu, kterou je třeba nějak nastavit, uveďte jak jste ji nastavili a proč zrovna tímto způsobem. Dále do svých naivních řešeních zakomponujte mé připomínky z prvního úkolu a doplňte k nim jejich I/O složitost. Na závěr porovnejte nová a naivní řešení, např. jak se zlepšila časová složitost na úkor jakého prostoru. Zamyslete se také nad tím, co byste museli u jednotlivých řešení (jak naivních tak nových) udělat a jak náročné by to bylo, kdyby se Vám k datasetu mělo přidat dalších 100 000 záznamů, ne nutně aktuálního data.
Své řešení mi přijďte vysvětlit na konzultaci nejpozději do konce zápočtového týdne (18.12.2026), přitom mi také odevzdejte své řešení napsané rukou na papíře. Na konzultaci se, prosím, domluvte dopředu.