Programování II – Zkouška LS 2007

Pisemna cast: napred je hodina na maly priklad z okruhu : spojaky (mergovani, zasobniky, fronty.......), stromy (vypisy, vytvareni, prochazeni, ....), neco malo z dlouhych cisel,... V zasade jde v malych prikladech o praci s dynamickymi strukturami a jejich konkretni pouziti (pascal) – dereferencovani, atp; tedy prakticke programovaci skills.

pak 5 minut pauza a dve hodiny na velky priklad.

Pro konkrétní představu: Já měl třeba napsat proceduru Replace(a;b;c), kde a, b, c jsou řetězce reprezentované spojovými seznamy znaků, jež má nahradit první výskyt řetězce b v řetězci a řetězcem c. Na přímý dotaz my bylo Töpferem potvrzeno, že nahrazenou část řetězce je vhodné dealokovat. Měl jsem také ošetřené prázdné řetězce a a c, z náhrady jsem ale navytvářel kopii (což by dávalo smysl, ale nechtělo se mi), a dodatečně mě napadlo, že jsem místo Dispose asi napsal Dealloc a jednou jsem přistupoval do uvolněné paměti. Tyto nuance ovšem zůstaly bez povšimnutí a dostal jsem jedničku s tím, že je to bez chyby. Myslím, že tohle byla tak asi středně těžká úloha, nečekejte žádné operace na AVL-stromech:). — Adam
ja sem mel zase nasobeni dvou dlouhych cisel (cislo jako spojovy seznam), uplne staci “skolni algoritmus” par pomocnych procedur na otaceni cisla, pricteni buferu k vysledku atd. neni to tezky ale sotva sem to stihnul, byl to co sem slysel asi nejpracnejsi priklad. jediny na vymejsleni na tom bylo ze to byli cely cisla takze sem mel rict jak bude to znaminko reprezentovany (vcelku trivialita) KF

Ustni zkouska probiha ( moje tak probehla ) tak ze nejdriv projde maly priklad zepta se na nejasnosti, necha vas abyste vymysleli napravu pripadnych chyb,... Pak prejde k velkemu – diskuse, ....

Já jsem třeba u dynamického programování měl předvést uzávorkování matic pro konkrétní zadání součinu čtyř matic. Tzn. popsal jsem algoritmus, jak se počítá cena násobení, a pak jsem si podle toho vyplnil pole cenami. S mými aritmetickými schopnostmi to chvíli trvalo, ale nakonec to vyšlo:). — Adam
u ustni jsme probrali nejasnosti (jeho ne moje) ohledne malyho prikladu, velky priklad jsem mu prevykladal celej a rek mi at mu dam index ze se me na nic jinyho ptat nebude ze by mi jednicku musel dat stejne... ale nevim jestli to nebylo tim ze sem sel na ustni v pul paty jako posledni...kazdopadne mi pan Töpfer udelal radost KF

A nakonec se taze na nektere veci typu : reknete mi neco o : haldach, objektech, dynamickem programovani, ...

25.6. koncerty

dneska jsem to zahlíd na tabuli (pri jine zkousce) předpokládám že je to tohle:

http://forum.matfyz.info/viewtopic.php?t=1885

18.6. lovec autogramů

na grafy :) casem doplnim zadani bud ja nebo nekdo jinej

12.6. burza

Velky priklad: Napsat program pro stanoveni kurzu pro fixingove obchodovani na prazske burze. Zadani bylo strasne dlouhy, podstatny bylo, ze se pracovalo se “spoustou dat” (<=100M zaznamu) a “malem pameti” (1MB na data).

Vstup

soubor pokynů, textový, na každém řádku:

ID klienta: 10 znaků (např. KOMM8674 )

ID makléře: 10 znaků (např. KOMK526400)

ISIN (ident. cenného papíru): 12 znaků (např. CZ0168451265)

Název CP: 20 znaků (např. ČESKÝ TELECOM)

Pokyn: N nebo P (nakup, prodej)(např. N)

Limitní cena: real, (pro nákup maximální, pro prodej minimální) (např. 750)

Počet: longint (např. 10 000)

Výstup

soubor kursů, textový, na každém řádku:

ISIN

Název CP

Kurs (cena za 1 CP)

Počet obchodovaných

Omezení

různých CP <=3000

pokynů <=100 000 000

makléřů <=10 000

klientů <=10 000 000

min. cena 0,01(1 hal)

max. cena 43 000

paměť 1MB

disk rozumně neomezeně

Úkol

Stanovit kurs cenných papírů tak, aby se zobchodovalo co nejvíc CP. Pokud by se obchodoval maximální počet pro nějaký interval kursů, stanoví se kurs na střed intervalu.

Řešení: i pan Töpfer potvrdil ze byla v podstate dve (uvedl jsem obe a udelal sem dobre)

obe reseni zacinala stejne, rozdelit vstupni soubor do souboru jednotlivych cennych papiru, pro kazdy urcit nejlepsi kurz a pak to setridit a ulozit do vystupniho souboru

tohle vymyslel snad kazdy uloha tedy vlastne byla jak najit nejlepsi kurz.

da se pouzit jakasi prihradkova metoda, kde se vzdy zaobiram intervalem kurzu a pro dalsi fazi vemu tu lepsi polovinu (to poznam podle poctu obchodovanych cennych papiru pri kurzu stredu toho intervalu) no a timhle delenim dojdu k jednobodovymu intervalu a mam to.
druha varianta (jak Töpfer rekl beznejsi) pouzivala vnejsi trideni, tedy rozdelit vstup na nakup a prodej, setridit je samostatne podle ceny a vybrat optimum... (treba metodou slevanim a hledanim maxima)

KF (dopiste nekdo prosim zadani na to uz nemam cas)

doplněno, snad to není úplně zmateně tk

4. 6. scrabble

Velký příklad: Nalézt nejlépe obodovaný tah ve scrabble. Vstup:

n≤20: rozměr desky
poloha bonusů ( 2x, 4x slovo, 2x, 4x písmeno)
písmena na desce
7 písmen v přihrádce
obodování písmen (pracuje se s celou českou abecedou, 41 písmen)
slovník přípustných slov ≤100000

Smí se použít paměť až několikanásobku velikosti slovníku. Je vhodné zvlášť uvést nějakou inicializaci nezávislou na konkrétním tahu (zřejmě tedy předžvýkání slovníku). Platí běžná scrabblová pravidla.

Stejně jako «čokoláda» je tento příklad prý z minulého roku. — Adam

Řešení: By mělo obsahovat následující elementy: Vybudování stromů (já měl větvící se dle písmen, což je asi nejlepší) ze slovníku, ideálně ve směru čtení slov i po zpátku (tzn. první větvení dle posledního písmene, což mě nenapadlo, přitom, je to podle mě ten hlavní fígl), vybudování hashovací tabulky ze slovníku pro ověřování “bokem” vytvořených slov. A z toho vychází zbytek, tzn. že se vždycky vezme něco, co už na desce je podle toho se projde pár větvení jednoho ze stromů a dále se prochází podle podle slov, která mohu klást na desku, přičemž se průběžně počítají body a ověřují “bokem” vytvořená slova.

Mně chyběl ten zpětný slovník, přitom se nás k tomu při zadávání vyloženě snažili dovést tím, jak rozebírali možnosti navazování slov. I tak jsem dostal jedničku. Zkouška probíhala příjemně, malý příklad i teorii jsem měl Ok. A podobně mírný byl Holan, co jsem slyšel, i k ostatním. Jak to probíhalo u Töpfera, nevím, ale divil bych se, kdyby to bylo výrazně jiné. — Adam
Töpfer byl super. Příjemnej, toleroval mi i drobné neznalosti, když jsem předtím měl písemku skoro bezvadně. Mě naopak přišlo, že víc vyhazoval Holan. Ale těžko říct. Nejvíc samozřejmě vždycky zleží na znalostech :) Čestmír

28. 5. čokoláda

Zadani velkeho prikladu: Mate ctvercovou cokoladu 10 * 10 s policky o stranach 1. V cokolade je nekolik (<= 1000) orisku a hrozinek kruhoveho tvaru. U kazdeho orisku a hrozinky znate jejich souradnice(realne) a polomer(realny). PROBLEM: rozdelte cokoladu na libovolne velke tri dily, s co nejmensi namahou (na rezani) a to tak, ze rezat muzete jen po hranach jednotlivych dilku a v cokolade nesmi byt vyriznuty otvor. Rezani cokolady stoji 1, rezani pres cast s oriskem 5 a rezani pres hrozinku 1/2 energie na jednu hranu (tzn kdyz pulku hrany zabira orisek a zbytek je cokolada, tak hrana stoji 3 j. energie)... Mate k dispozici 1MB pameti. (Napsal Pepa Moudřík, já to sem jen přesunul.)

Reseni: (aneb ja jsem to delal takhle) Napraed se vhodne ohodnoti hrany podle toho kolik je na nich orisku/hrozinek. ( treba pomoci delky tetivy ) Tim se problem prevede na grafovou ulohu, kterou lze resit ruznymy zpusoby. Delal jsem to pomoci F-W a vhodnym prozkoumanim minimalnich cest z okraje na okraj ( namalujte si to na papir a nemel by to byt velky problem ) – 1 rez – a pak vsech cest z (okraje + uzly prvni cesty) na (okraje + uzly prvni cesty) – minimum ze souctu delek je reseni. Bohuzel vsak tenhle algotritmus muze minout optimalni reseni pri zakerne zvolenem rozlozeni orisku a hrozinek. Holan to ale stejne celkem uznal ( prodiskutovali jsme taky nejake chyby a jejich napravu, ... ) a celkove se mi zdal na zkousce velmi prijemny...

Hlavní problém je, že nejkratší řez na tři díly nemusí IMO obsahovat nejkratší řez na dva díly, navíc to má docela slušnou složitost, takže takovej nápad: pro každý vnitřní vrchol: { Dijkstra, následně vybrat z krajních vrcholů tři s nejkratší vzdáleností od daného vnitřního vrcholu, zapamatovat vrcholy, cesty a součet délek} a z těchto součtů minimum. To by mohlo fungovat a nemá to špatnou složitost, vzhledem k tomu, že graf je řídký (m = Θ(n)). — Adam

30. 4. studentské ankety (ukázková úloha na přednášce)

Zadání

Vstup

soubor Lístky (data po řádcích oddělena tabem)
- Učitel (jméno, příjmení; jednoznačně) — string[50]
- Předmět — string[50]
- Hodnocení — číslo 1 až 5
soubor Katedry (data po řádcích oddělena tabem)
- Učitel (jméno, příjmení) — string[50]
- Katedra — string[50]

Výstup

soubor Učitelé, resp. soubor Katedry (setříděné podle učitelů, resp. kateder)
- Učitel
- Předmět
- Průměrné hodnocení
- Střední kvadratická odchylka

Střední kvadratická odchylka: Průměr čtverců rozdílů hodnot a střední hodnoty.

Omezení

učitelů do 10000
kateder do 100
předmětů do 5000
lístků 100000
paměť do 64 KB

Řešení

Úvaha: soubory se nám nechce číst moc často, ale asi to bude třeba

Zřejmě bude třeba třídit podle klíčů (Učitel, Předmět) (tzn. jeden průchod, dva klíče).

Postřeh: Σ (x_i – R)² / N = Σ (x_i² – 2x_iR – R²) / N = (Σ x_i² – RΣ2x_iR – NR²)/N

U – délka souboru Učitelé

L – délka souboru Lístky

UP – počet platných kombinací (Učitel, Předmět)

Návrh algoritmu:

Setřídit Lístky podle (Učitel, Předmět).
Setřídit Katedry podle (Učitel).
Čtu souběžně oba soubory (sekvenčně), dokud stejný (Učitel, Předmět) přičítám sumy x_i, x_i², jinak vypíšu. Zapisuju jeden soubor s Učiteli, druhý s Učiteli a Katedrami.
Setřídím soubor s Učiteli a Katedrami podle (Katedra), zapíšu bez pole Katedra.

Má-li soubor s lístky délku L: setřídím v L log L, vypíšu v L, projdu sumy v L atd. (vyjádřeno pomocí U, L, UP).

Tip: Neměl jsem foťák, ale bylo nám doporučeno, abychom si kreslili obrázky (aka data-flow diagramy) jako Holan na tabuli – data a akce pospojované šipečkami.

Části vypracování řešení úlohy

Do Upřesnění nebo postřehů:

průběžné počítání odchylky viz výše
předpoklady platného vstupu (všichni učitelé z lístků jsou z nějaké katedry)
promyslet co se kolikrát bude muset dělat (načítat, vypisovat, slévat), kolik čeho bude (moct být) v paměti

Do Diskuse:

v tomhle případě nic moc
ještě by leda šly jména kateder v určité fázi nahradit čísly/zkratkami, protože je potřebujeme jen na třídění
obecně napsat alternativní algoritmus, byť nerozmyšlený

Do Shrnutí:

přehled na A4, aby se v tom někdo vyznal

26. 1. (info o zkoušce na přednášce)

Malý příklad (na praktickou znalost)
- dynamické proměnné, spojové seznamy
Velký příklad
- Program
  - Součástí zadání může být omezení paměti. Je možné, že přesné řešení by mělo nepřijatelnou složitost, pak je třeba volit vhodné přibližné řešení (heuristika, třeba i více heuristik).
  - Výsledek má být buď (dostatečně) popsaný algoritmus slovy, v pseudokódu, případně i skutečném jazyce.
  1. upřesnění zadání
  2. postřehy k zadání úlohy (zbytečná data apod.)
  3. zdůvodnění volby algoritmu (složitost, případně náročnost na psaní, ladění)
  4. reprezentace dat
  5. dekompozice programu (rozdělení na nezávislé části)
  6. diskuse problému
  7. na A4 shrnutí 1.-5.
- Ústní část (asi půl hodiny)

Jako příklad úlohy uváděl problém s letištěmi, který snad je/bude na jeho stránkách, ovšem s tím, že na zkoušku je tenhle příklad naddimenzovaný.

Matfiz: Programování/ZkouškaLS2007