Homepage » Cvičení

Cvičení programování

• K přednášce Programování I Martina Pergela
• Pátek 11:30 - 13:00 v K11
• Podmínky zápočtu:
  • Úspěšné složení praktického testu (viz stránku přednášky)
  • Alespoň 50% bodů za úlohy v CodExu
  • Zápočtový program
  • Aktivní účast na cvičeních, domácí úkoly a písemky
• Příklady na trénování

1. cvičení, 1. 10. 2010

• Založte si účty v Karlínském labu a v CodExu; může se hodit i účet do Malostranského labu.
• Dozvěděli jste se (výše uvedené) podmínky zápočtu.
• Opakovali jsme Erastothenovo síto a Euklidův algoritmus, které znáte z přednášky.
• Dělali jsme několik logických úloh:
  • Spojte devět puntíků (3x3) čtyřmi navazujícími úsečkami.
  • Odměřte 6 litrů pomocí 9-ti a 4-litrové nádoby.
  • Pokračujte v řadě: 1, 11, 21, 1211, 111221, 312211, 13112221, ?
  • Převezte přes řeku tři kanibaly a tři misionáře, přičemž nikdy nesmí být nenulový počet misionářů v menšině, do loďky se vejdou nejvýše dva lidé, jet může i jeden sám.
  • Je dáno devět koulí, jedna je maličko těžší. Určete která, máte-li k dispozici rovnoramenné váhy a můžete vážit dvakrát.
  • Z kolika nejvíce koulí dokážu určit jednu těžší na tři vážení?
  • Je dáno dvanáct koulí, všechny krom jedné váží stejně, o vadné nevíme, zda je těžší, nebo lehčí. Smíme vážit třikrát a úkolem je určit vadnou.
• Domácí úkol: Uzavřený tah věží po šachovnici je taková posloupnost všech políček, že každé z nich navštíví věž pomocí regulérních tahů – přesunů na vedlejší pole – právě jednou, kromě políčka, na kterém začne i skončí (to navštíví právě dvakrát). Otevřený tah je takový, že neskončí na políčku, kde začínala a navštíví každé pole právě jednou.
  Uvažujme tři šachovnice: šachovnice 8×8, šachovnice 8×8 bez jednoho rohu, šachovnice 8×8 bez protilehlých rohů. Pro každou z těchto šachovnic zjistěte, zda 1) existuje uzavřený tah věží; pokud ano, popište ho, pokud ne, dokažte to, 2) existuje otevřený tah věží; pokud ano, popište ho, pokud ne, dokažte to. Počáteční pozici věže si zvolte, jak se vám hodí. Řešení mi posílejte e-mailem.

2. cvičení, 8. 10. 2010

• Viděli jste řešení domácího úkolu.
• Ukázali jsme si, že funguje volenkový algoritmus na hledání stabilního párování. Píše se o něm například zde.
• Popovídali jsme si o Ariadnině algoritmu hledání s návratem (backtracking) a jak se dá vylepšit, aby se vracel bez smyček. Opět jsme ukazovali, že je to korektní algoritmus. Můžete si ho prohlédnout tady.
• Na bludišti a na šachovnici s koněm jsme si ukázali, jak vypadá prohledávání do šířky a k čemu se hodí.
• Domácí úkol nebude, zato si příště napíšem písemku.

3. cvičení, 15. 10. 2010

• Psala se slíbená písemka:
  • Máte pět koulí, z nichž jedna je označená a ta váží přesně 1 kg. Z ostatních čtyř tři váží také 1 kg a jedna jinak. Na dvě vážení na rovnoramenných vahách ji určete.
  • Dokažte konečnost Ariadnina algoritmu.
  • Dokažte parciální správnost volenkového algoritmu.
• Povídali jsme si o složitosti algoritmu.
  • Zkoumáme složitost časovou a paměťovou (prostorovou).
  • Zajímá nás v nejhorším a v průměrném případě.
  • Jedná se o funkci závislou na vstupu.
  • Téměř nikdy nejsme schopni ji vypočítat přesně – záleží na implementačních detailech. Proto se zavádí asymptotická složitost, která zanedbává koeficienty a méně významné členy.
  • Známe následující notace: o(), O(), Θ(), Ω(), ω().
  • Z nich je pro nás z hlediska složitosti nejzajímavější O(), protože pokud pro nějakou funkci c(n) a složitosti f(n) a g(n) platí f(n)=O(c(n)) & f(n)≠O(c(n)), je f(n) lepší, než g(n).
• Časovou složitost volenkového algoritmu jsme vypočetli jako O(n²), kde n je počet mužů a žen, za předpokladu, že jedna návštěva trvá konstantní čas.
• Zkuste vymyslet, jakou časovou složitost má Ariadnin algoritmus v závislosti na počtu místností (= křižovatek) a chodeb. Předpokládejte, že každý prováděný test v algoritmu trvá konstantní čas.
• Na další cvičení budete potřebovat účty v CodExu a v Karlíně!

4. cvičení, 22. 10. 2010

• Zkoušeli jsme si jednoduché programy v Pascalu:
  • Vypsat součet dvou čísel.
  • Vypsat větší ze dvou čísel.
  • Vypsat součet seznamu čísel ukončeného nulou.
  • Vypsat faktoriál čísla.
• Do CodExu jsem vám zadal další jednoduché úlohy za body. Pokud nevidíte svoji skupinu nebo pokud jste přesvědčeni, že váš kód je v pořádku a přesto nefunguje, napište mi. Počítejte s tím, že do proměnné typu integer se vejdou jen čísla menší, než 32768. Potřebujete-li větší, použijte longint.
• Připravil jsem vám stránku s příklady na procvičení, jednoduchými i trošku záludnějšími. Jsou naprosto nepovinné, nicméně můžete se zeptat, kdyby vás zajímalo, jak se nějaký řeší.

5. cvičení, 29. 10. 2010

• Jako záskok cvičil Radek Fürbach.
• Dělaly se následující úlohy na pole:
  • Minimum čísel v poli
  • Průměr prvků
  • Četnost prvku
  • Modus prvků
  • Něco o třídění

6. cvičení, 5. 11. 2010

• Ukázali jsme si řešení CodExových domácích úkolů.
• Porovnávali jsme funkce (asymptoticky).
• Dělali jsme příklady na funkce (a stihli jsme jich smutně málo):
  • Funkce na spočítání součtu čísel
  • Procedura na vypsání součtu čísel, která využívá předchozí funkce
  • Procedura na výměnu prvků (nutno předat odkazem)
• Prosím ty, kterým se dnes příliš nedařilo (potřebovali moji pomoc), aby si doma zkoušeli procedury a funkce napsat a ujistili se, že dobře chápou, jak se s nimi pracuje. Nemůžeme si dovolit ztrácet tolik času na syntaktických záležitostech.
• V CodExu přibyly nějaké úlohy na pole.
• Úlohy konkrétně na funkce a procedury v CodExu nejsou (principielně se můžete téměř v jakémkoli programu bez procedur a funkcí obejít), proto jsem tam přidal ještě několik obecných úloh na to, co už byste měli umět.
• Obecně platí, že na cvičení, kterým končí první termín CodExové úlohy, se popíše, jak se dá úloha řešit. Potom budete mít ještě dva týdny na implementaci prozrazeného řešení za polovinu bodů.
• Máte-li dotazy, pište mi e-maily, snažím se na ně reagovat rychle. Přímo na cvičení na to nebývá čas, to pak leda jste-li ochotni zdržet se po něm.

7. cvičení, 12. 11. 2010

• Nastínil jsem řešení CodExových domácích úkolů a možné potíže při jejich implementaci.
• Navrhli jsme a implementovali algoritmus na setřídění pole:
  • Umím setřídit pole, pokud umím postupně v každé části i…n přesunout minimum na začátek.
  • Umím přesunout minimum dané části na začátek, pokud umím najít minimum a vyměnit prvky.
  • Najít minimum vybrané části zvládnu.
  • Vyměnit prvky také.
  Výsledkem byly čtyři procedury/funkce sort, swapmin, findmin a swap. Musí se napsat v takovém pořadí, aby všechny funkce, které nějaká funkce používá, byly v kódu definované nad ní. Nebo si pomůžete použitím prototypů – napíšete před definice svých funkcí hlavičky funkcí, stejný řádek, jako u definice, a na jeho konec připíšete forward; více zde.
• Začali jsme rekurzi:
• Připoměli jsme si počítání faktoriálu rekurzí i for-cyklem.
• Ukázali jsme si, že může mít horší paměťovou složitost, než jiná řešení (o časové to platí také, ale k tomu příště).
• Faktoriálovou funkci jsme modifikovali na funkci, která počítá posloupnost a₁ = 1, a_n = a_n-1 + 2n - 1.

8. cvičení, 19. 11. 2010

• Ukázali jsme řešení CodExových domácích úkolů.
• Povídali jsme si o následujícím mixu užitečných informací:
  • Je možné formátovat výstup tak, že při výpisu za proměnnou dopíšete :x, kde x je přirozené číslo a znamená minimální počet znaků, který bude využit na vypsání čísla, zleva bude prostor doplněn nulami. Je-li navíc vaše proměnná typu real nebo double, můžete za ni dopsat :x:y, kde x má stejnou funkci a y je počet desetinných míst.
  • Existují proměnné MAXINT a MAXLONGINT, které obsahují maximální hodnoty příslušných datových typů.
  • Typ proměnné real a double není (z principu jeho uložení v paměti) zcela přesný. Důsledkem je, že při porovnávání těchto čísel na rovnost může docházet k chybám. Řešení – nedělejte to.
  • Řídící proměnná for-cyklu se nesmí uvnitř cyklu měnit. Mimo cyklus se pak nesmí zjišťovat její hodnota. ("Nesmí" zde znamená, že výsledek takovéhoto konání je nedefinovaný.)
  • Vícerozměrná pole se v pascalu deklarují jako p: array[a..b,c..d] of integer a přistupuje se k nim jako p[k,l].
  • Program nechápe vstup z klávesnice a výstup na obrazovku jako řádky textu, co se prokládaně objevují na obrazovce, ale prostě jen jako frontu, odkud mu chodí textová data a frontu, kam posílá textová data. To hlavně znamená, že pokud zadání programu je, že s každým přijatým číslem něco uděláte a výsledek vypíšete, nemusíte si všechny jednotlivé výsledky ukládat a vypsat je až po přečtení posledního vstupu, můžete je vypisovat hned.
• Pak jsem ještě ukázal na příkladu, jak špatně (exponenciálně) může dopadnout paměťová složitost algoritmů s rekurzí a jak to můžeme někdy zachránit pomoci cacheování výsledků.
• Pokud máte nějakou představu, můžete mi posílat nápady na své zápočtové programy.

9. cvičení, 26. 11. 2010

• K zápočtovým programům:
  • Můžete se inspirovat zde.
  • Do 17.12. bychom měli být dohodnuti na tématu vašeho zápočtového programu. Když by někdo byl naprosto neschopen rozhodnutí, zkusím mu nějaké téma vnutit 10.12. po cvičení.
  • Do 24.12. mi sepíšete specifikaci. Specifikace by měla obsahovat informace o tom, co program umí, co neumí (jaká má omezení), jak přijímá vstup a jak vrací výstup, pokud možno jakou má složitost časovou i paměťovou.
  • Potom můžete vesele programovat. Deadline pro odevzdání hotového programu bude nejdříve konec zkouškového a nejpozději konec akademického roku.
• Naučili jste se vyhodnocovat rekurzí výrazy zadané v prefixové notaci, po malém přepsání program můžete odevzdat v CodExu. Vzhledem k tomu, že jste ještě řetězce moc nepotkali, tady je funkce, pomocí které můžete získávat jednotlivé prvky toho výrazu.

10. cvičení, 3. 12. 2010

• Popsal jsem vhodná řešení Goldbachovy kratochvíle a Hanoiských věží.
• Dělali jsme program 'cenzura', na němž jsme si procvičili práci s textovými soubory, řetězci, znaky a záznamy:
  • Externí soubor pravidel rules.txt obsahuje několik řádků, na kterých jsou vždy dvě slova oddělená mezerou.
  • Další externí soubor – dopis letter.txt obsahuje libovolný text.
  • Program načte soubor pravidel, přečte dopis a přepíše ho do souboru out.txt tak, že vždy, když v něm najde první slovo pravidla, nahradí ho druhým slovem, zbytek opíše beze změny.

11. cvičení, 10. 12. 2010

• Popsal jsem řešení přesného batohu a mrkve a petržele.
• Rozluštili jste hezkou hádanku.
• Popsal jsem vám floating-hash algoritmus na hledání v textu, na naprogramování už nezbyl čas.
• Nabídnul jsem vám několik poměrně snadných témat zápočtových programů.
• Posílejte mi témata zápočťáků. Termíny jsem o týden posunul – témata mi pošlete do příštího cvičení 17.12., specifikace do Vánoc.

12. cvičení, 17. 12. 2010

• Vyhlášen termín odevzdání zápočtových programů: 1. dubna.
• Strávili jsme celé cvičení programováním hledání mediánu v lineárním čase a dokonce jsme to stihli.
• Když mi pošlete vlastní naprogramovaný funkční algoritmus, dostanete 10 bonusových bodů. Pokud si myslíte, že má fungovat a nefunguje, taky mi to taky můžete poslat k prozkoumání.
• Přidal jsem posledních pět úloh do CodExu a zaokrouhlil jsem tak maximální počet bodů, které za ně můžete získat, na 192. Na zápočet tedy potřebujete 96. Mnozí z vás už tuto hranici téměř překonali, nicméně zkusit si vymyslet řešení nových úloh může být velmi poučné.
• Ti, kdo se mnou ještě nedomluvili téma zápočťáku, by si se mnou měli horlivě dopisovat. Kdo se se mnou nedomluví do Vánoc, tomu asi budu strhávat body v CodExu. A od vás všech chci pod stromeček specifikaci.

13. cvičení, 7. 12. 2010

• Popsali jsme řešení domácích úkolů: slévání souborů, součin matic, počet správných uzávorkování, inverzní permutace, Césarova šifra.
• Zbytek hodiny jsme společně vymýšleli, jak se dá hledat cesta obecnou figurkou na šachovnici.
• Kdo mi nepošle do příštího cvičení specifikaci, nedostane zápočet.

14. cvičení, 14. 12. 2010

• Ať se vám daří při zkouškách. Nejdřív udělejte zkoušky a praktický test a až pak se pusťte do zápočtového programu.
• Dokumentaci k programům napište pořádně. Hezký návod najdete na stránkách R. Kryla.
• Promýšleli jsme typické úlohy, které se mohou objevit u zápočtového testu.
• Počty bodů v CodExu jsou uzavřené, věřím, že dostatek bodů na zápočet mají právě ti, kdo si ho zaslouží.
• Vypadá to, že budu cvičit i v příštím semestru, tak doufám, že většinu z vás potkám. =:)

---