Zkouška 3.6.2019

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.
KubP
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 18. 1. 2019 18:38
Typ studia: Informatika Bc.

Zkouška 3.6.2019

Příspěvek od KubP »

Opakovalo se zadání s rozkladem textu na palindromy, viz http://forum.matfyz.info/viewtopic.php?f=247&t=11818

Snad optimální řešení:

Postavíme graf (DAG): vrcholy budou mezi každými dvěma sousedními písmeny a jeden na záčátku a jeden na konci textu. Mezi dvěma vrcholy vede hrana právě tehdy, když text mezi těmito vrcholy tvoří palindrom. Hrany jsou orientované vždy směrem od začátku textu ke konci. Minimální pokrytí palindromy je pak nejkratší cesta v tomto grafu ze začátku textu na konec. Hrany (palindromy) nalezneme tak, že pro každý možný střed palindromu (pozor, ten může být "uvnitř" písmena, ale i mezi dvěma sousedními písmeny, např ABA x ABBA) postupně kontrolujeme písmena vlevo i vpravo od středu, a dokud se jedná o palindrom, tak přidáváme do grafu hrany.

Ústní:

Měl jsem Holana. Nejdřív chtěl ať mu řeknu co jsem napsal do písemky a kontroloval si v písemce, že to tam opravdu je.

Potom se mě ptal co je to externí třídění, což je věc, se kterou jsem se setkal večer předtím ve vlaku letmo na wikipedií. Popsal jsem tu ten "externí mergesort", bavili jsme se o tom docela dlouho, protože já myslel, že mít víc souborů pro setříděné úseky a slévání je stejně špatné jako jeden velký, jsou přece stále na stejném disku a čtou se sekvenčně/musí se mezi nimi seekovat, on mi tvrdil, že to stejné není. Nakonec měl na mysli, že každý soubor je na vlastním samostatném disku/pásce, takže lze číst víc souborů naráz hezky sekvenčně bez seekování. Což je dost důležitý detail, bez něj externí třídění moc nefunguje. Moc nadšený ze mě nebyl.

Nakonec se mě ptal na vnitřnosti C#, konkrétně na rozdíl mezi virtuálními a abstraktními metodami, kde se ukládají pointery na tyto metody, kdy má třída bezparametrový konstruktor a podobné věci. Mám se C# spoustu zkušeností a to stačilo na vydedukování odpovědí.

Nakonec mi dal 1.
Odpovědět

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