Zkouška pondělí 7.6.2021 - Euklidovské konstrukce

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.
pheeck
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 13. 6. 2021 14:51
Typ studia: Informatika Bc.

Zkouška pondělí 7.6.2021 - Euklidovské konstrukce

Příspěvek od pheeck »

Písemná část

1 úloha
2 hodiny času
začalo se až když nebyly žádné otázky k zadání (což v našem případě trvalo 50 minut :D)
Holan a Pergel

Člověk se toho snaží sepsat co nejvíc na papír (nebo do markdownu, v mém případě) - každý nápad
a pak papír odevzdá a s Holanem se v ústní části na tom papíru snaží najít alespoň náznak řešení.
Taková je moje zkušenost. S Pergelem to bude asi jiné.

Hledání Euklidovských konstrukcí
Zde je odkaz na pdf: https://ksvi.mff.cuni.cz/~holan/210607_ ... trukce.pdf
Pravděpodobně na Holanově stránce však nebude moc dlouho viset, takže tady je i hůře zformátovaná verze:

edit: došlo mi, jak se na na forum nahrávají soubory, takže tedy je pdf, pokud odkaz už nefunguje:
210607_zk_konstrukce.pdf
(46.44 KiB) Staženo 144 x
Euklidovská konstrukce je množina objektů tří druhů:
 bod
 přímka
 kružnice

Postup konstrukce
je posloupnost kroků, kterými z jedné (vstupní) konstrukce
vytvoříme konstrukci jinou (výstupní).

Kroky přitom mohou být dvou druhů:
 AB sestrojit přímku procházející body A a B
 A(B) sestrojit kružnici se středem A procházející bodem B
Po každém kroku navíc určíme průsečíky vytvořené přímky nebo
kružnice se stávajícími přímkami nebo kružnicemi
a přidáme je do konstrukce jako nové body.
Počet kroků budeme nazývat délka (postupu) konstrukce.

Příklad: Nalezení středu dvou daných bodů A a B:
(1) p1=AB
(2) k2=A(B)
(3) k3=B(A),{C, D}=k2∩k3
(4) p4=CD,{S}=p1∩p4
Znakem ∩ značíme průsečík.

Zadání
Navrhněte program, který pro všechna celá čísla N od 1 do 20
zjistí minimální délku konstrukce potřebnou k tomu, abychom pro
dva různé body A a B sestrojili bod X, který dělí vzdálenost AB
v poměru 1:N, tedy
|AX| = |AB|/(1+N) a |XB| = |AB|*N/(1+N)

Pro N=1 je odpověď 4, protože výše uvedený postup konstrukce úlohu
řeší na čtyři kroky a kratší postup neexistuje.

V odpovědi popište
1) postřehy
2) zdůvodněnou volbu algoritmu
3) representaci dat
4) dekompozici programu
5) diskusi
, v případě potřeby i
0) upřesnění zadání.

Paměť, čas: Přiměřeně, žádná zvláštní omezení.

Řešení písemné části

Prohledávání stavového prostoru do šířky, popř. podle Holana do hloubky, ale s tím,
že omezíme maximální hloubku (zanoření) (tedy chtěl takový hybrid prohledávání do hlouky a do šířky).
Bude potřeba dosadit si vlastní konkrétní vzdálenosti a s nimi počítat.
Pardon, nepodám detailní postup, protože jsem písemnou část měl špatně.

Asymptotická složitost v závislosti na n by nebyla hezká. Šlo ale o to, uvědomit si,
že i tak by pro to n = 1...20 algoritmus alespoň během pár hodin doběhl.
Doporučuju tohle: Když dostanete v úloze až podezdřele malý vstup, přemýšlejte
i nad šíleně neefektivními řešeními.



Ústní část

Na ústní část jsem šel o dva dny později, distančně a měl jsem Holana.

Nějaký čas jsme strávili nad mým papírem, který byl obsáhlý, ale správné
řešení na něm nebylo. Zkoušel jsem hodně věcí. Za konečné řešení jsem
označil nějaké optimalizování algoritmu pro rozdělení přímky na více částí
ze základky/střední. Za to, že jsem v jedné části papíru měl náznaky,
že jsem nad prohledáváním stavového prostoru přemýšel a za to, že jsem
na papíru rozebíral všemožné způsoby (grafy, dynamické p., rozděl a panuj, ...),
jak by se to možná (ne)dalo řešit jsem dostal pomyslné bonusové body, ale
přece jenom jsem to měl špatně.

Holan po mně pak chtěl, abych mu řekl něco o virtuálních a abstraktních metodách.
Dal mi čas na rozmyšlenou a já jsem mu řekl nejen o tom, jak ty metody fungují,
ale i o prototypech a tabulce virtuálních metod a jak konstruktory předků
postupně vyplňují pointery na ty správné funkce.

Tohle mě zachránilo a já odcházel s dvojkou.
Odpovědět

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