Také sem hodím své postřehy ze zkoušky.
Zadání jsem předem neznal a napadlo mě jen toto.
Pomocí Floyd-Warshalla spočítat vzdálenost mezi každými dvěma městy. Když začnete popisovat svůj program s Floyd-Warshallem, určitě tím Pergela a Holana potěšíte, při nejmenším já tím Pergela potěšil.
Na backtracking v tomto případě zapomeňte, za to by vás prý rovnou vyhodili. Mě nenapadlo nic lepšího, než si vytvořit jakousi tabulku (dynamické programování), kvůli které jsem bohužel několikanásobně překročil povolenou paměť.
Začal jsem s posledním meetingem a u něj jsem si poznamenal, jak se na něj můžu dostat, respektive z jakých meetingů se na něj mohu dostat. To udělám jednoduše tak, že projedu prostě všechny meetingy před tímto a k času konce toho meetingu připočítám vzdálenost mezi oběma meetingy. To je jednoduché ...
Do prvního meetingu se nemohu dostat nijak.
Pak jsem jen od konce hledal nejdelší cestu...
Pergelovi se to celkem líbilo, tedy až na tu paměť, kvůli tomu mi snížil hodnocení písemky na 2. Ale tak mimo soutěž mi řekl, že kdyby tu písemku zadával on, nechal by nám kubickou paměť, nebo by to dal bez omezení.
Asi to není optimální řešení, takže se ho rozhodně nepokoušejte napodobovat. Ale můžete se tím inspirovat a nějak to vylepšit. Řešení v prvním příspěvku bude určitě lepší.
Z teorie mi vybral třídění založené na porovnávání dvou prvků.
Dostal jsem otázky:
1) Definice O,
,
2) Definice složitosti problému
3) Dolní odhad složitosti třídění (chtěl i důkaz !)
4) Horní odhad složitosti třídění (dokáže se nějakým alg., třeba mergesortem nebo heapsortem)
Zkoušel mě tedy Pergel a to jsem opravdu vyhrál. Byl strašně v pohodě. V písemce se vůbec nešťoural, během dvou minut jsme to prolítli. Skoro mě ani nepustil ke slovu, abych mu vysvětlil Floyd-Warshalla
Oproti tomu Holan, co jsem tak slyšel, se v písemce docela šťoural. Co jsem taky slyšel bylo to, že docela dost lidí na tom mém termínu vyletělo. Ale tím nikoho nechci strašit.
Má rada je, nepodceňujte přípravu na teorii, jako jsem to udělal já. Zkouška se zdá býti lehká - a ona i "lehká" je, ale pouze tehdy, když se na ni pečlivě připravíte. Ve finále jsem byl rád, že mě Pergel poslal domů s trojkou.
Také sem hodím své postřehy ze zkoušky.
Zadání jsem předem neznal a napadlo mě jen toto.
Pomocí Floyd-Warshalla spočítat vzdálenost mezi každými dvěma městy. Když začnete popisovat svůj program s Floyd-Warshallem, určitě tím Pergela a Holana potěšíte, při nejmenším já tím Pergela potěšil.
Na backtracking v tomto případě zapomeňte, za to by vás prý rovnou vyhodili. Mě nenapadlo nic lepšího, než si vytvořit jakousi tabulku (dynamické programování), kvůli které jsem bohužel několikanásobně překročil povolenou paměť.
Začal jsem s posledním meetingem a u něj jsem si poznamenal, jak se na něj můžu dostat, respektive z jakých meetingů se na něj mohu dostat. To udělám jednoduše tak, že projedu prostě všechny meetingy před tímto a k času konce toho meetingu připočítám vzdálenost mezi oběma meetingy. To je jednoduché ...
Do prvního meetingu se nemohu dostat nijak.
Pak jsem jen od konce hledal nejdelší cestu...
Pergelovi se to celkem líbilo, tedy až na tu paměť, kvůli tomu mi snížil hodnocení písemky na 2. Ale tak mimo soutěž mi řekl, že kdyby tu písemku zadával on, nechal by nám kubickou paměť, nebo by to dal bez omezení.
Asi to není optimální řešení, takže se ho rozhodně nepokoušejte napodobovat. Ale můžete se tím inspirovat a nějak to vylepšit. Řešení v prvním příspěvku bude určitě lepší.
Z teorie mi vybral třídění založené na porovnávání dvou prvků.
Dostal jsem otázky:
1) Definice O, [latex]\Omega[/latex], [latex]\Theta[/latex]
2) Definice složitosti problému
3) Dolní odhad složitosti třídění (chtěl i důkaz !)
4) Horní odhad složitosti třídění (dokáže se nějakým alg., třeba mergesortem nebo heapsortem)
Zkoušel mě tedy Pergel a to jsem opravdu vyhrál. Byl strašně v pohodě. V písemce se vůbec nešťoural, během dvou minut jsme to prolítli. Skoro mě ani nepustil ke slovu, abych mu vysvětlil Floyd-Warshalla :D
Oproti tomu Holan, co jsem tak slyšel, se v písemce docela šťoural. Co jsem taky slyšel bylo to, že docela dost lidí na tom mém termínu vyletělo. Ale tím nikoho nechci strašit.
Má rada je, nepodceňujte přípravu na teorii, jako jsem to udělal já. Zkouška se zdá býti lehká - a ona i "lehká" je, ale pouze tehdy, když se na ni pečlivě připravíte. Ve finále jsem byl rád, že mě Pergel poslal domů s trojkou.