Homepage » Cvičení

Cvičení programování

• K přednášce Programování II Martina Pergela
• Středa 19:00 - 20:30 v K11
• Podmínky zápočtu:
  • Alespoň 50% bodů za úlohy v CodExu
  • Aktivní účast na cvičeních, dobré výsledky písemek
  • Zápočtový program
• Příklady na trénování základů
• Zimní semestr

0. cvičení, 24. 2. 2011

• Nejdůležitějším bodem cvičení byla snaha najít vhodný termín cvičení.
• Dozvěděli jste se (výše uvedené) podmínky zápočtu.
• Dělali jsme jeden příklad simulující práci jednoduchého serveru v síťové aplikaci pomocí fronty a textových souborů. Bohužel se to moc nepovedlo, mimo jiné proto, že mnou připravený program nešel na školních počítačích spustit (třebaže přeložit ano). Program generující pakety najdete tady a server, který jste měli vytvořit, tady.
• Sejdeme se ve středu 2. 3. v 19:00 v K11.

1. cvičení, 2. 3. 2011

• Důkaz dolního odhadu složitosti třídění
• Quicksort
• Mergesort
• Heapsort
• Countsort
• Bucketsort
• Dobrovolný domácí úkol: Dostanete pole 100 čísel z intervalu {0,…,9999}. Seřaďte je v lineárním čase, smíte alokovat maximálně 500 paměťových míst (integerů) + pár (max. 10) pomocných proměnných. ("Lineární čas" pro pevný počet prvků ve skutečnosti nedává smysl; myslím tím, že n=100 a smíte alokovat nejvýše 5*n prvků. Váš algoritmus by měl fungovat pro každé n, ten interval hodnot je vždy stejný.)

2. cvičení, 9. 3. 2011

• Správná odpověď na domácí úkol je Radixsort.
• Začali jsme pointery.
• Měli byste chápat: @, ^, new(p), dispose(p), co je garbage
• Motivace k pointerům: třídění velkých struktur podle různých kritérií
• Spojový seznam — definice a použití
• Vypsání čísel pozpátku
• Přidání prvku za prvek
• Odebrání prvku za prvkem
• Odebrání prvku přímo (workaround s nahrazováním datové složky)
• Příští týden bude písemka na třídění, pointery a základní věci se spojovými seznamy.
• 14. 3. nezapomeňte oslavit Π-Day!

3. cvičení, 16. 3. 2011

• Psala se písemka, body za ni máte v CodExu.
• Příště se bude psát náhradní pro ty, kdo tam nebyli.
• Zamyšlení: jak měnit funkcí hodnotu proměnné bez var? Odpověď: předat funkci @prom. (Takto se předávají proměnné odkazem například v C.)
• Vysvětlili jsme si význam hlavy spojového seznamu a nadále jsme pracovali jen se spojákem s hlavou. Doporučuji vám totéž při řešení příkladů a domácích úkolů, pár řádků navíc v inicializaci se vám odvděčí snazší implementací ostatních procedur.
• Dělali jsme běžné funkce a procedury se spojovými seznamy. Najdete je v příkladech na procvičování, je tam i pár rad pro implementaci. Jejich vyřešení vám velmi pomůže s aktuálními úlohami v CodExu.

4. cvičení, 23. 3. 2011

• Psala se náhradní písemka, body budou v CodExu.
• Probíraly se všelijaké vyhledávací stromy: AVL, červenočerné, B-stromy.
• Potom jste si zkoušeli napsat některé procedury a funkce vyhledávacích stromů: insert, delete, member (zda tam prvek je), print (výpis prvků vzestupně). Velmi vám doporučuji naučit se je psát.
• Nezapomínejte plnit úlohy v CodExu. To, že na ně máte hodně času, vám má dát příležitost je zvládnout, ikdyž třeba celý jeden týden nemáte čas, ale lehkomyslně odkládat plnění nepovažuji za rozumné.

5. cvičení, 30. 3. 2011

• Tentokrát jsme se věnovali binárním souborům a hodně se programovalo.
• Dostali jste seznam programovacích jazyků a z něj jste vytvořili binární soubor.
• Nad ním jste pak měli postavit binární vyhledávací strom, jehož základní implementaci jste dostali.
• Potom jste se měli uživatele dotazovat na názvy jazyků a vracet jejich popis tak, abyste O(1)-krát přistupovali k souboru a průměrně O(log(n))-krát k vnitřní paměti.
• Již komplikovanější rozšíření by pak bylo zvládnout z databáze i mazat se stejnou složitostí.
• Příště budeme psát písemku na spojáky, stromy a binární soubory.

6. cvičení, 6. 4. 2011

• Psala se písemka, body budou v CodExu, náhradní písemka za týden.
• Stručně jste se dozvěděli, jak se mají řešit domácí úkoly.
• Dynamické programování: připomněli jste si už známé úlohy (cacheovaná rekurze, mrkev a petržel, batoh).
• Dělali jsme pomocí dynamického programování úlohu na hledání nejdelší společné podposloupnosti.
• Dobrovolný domácí úkol, kterým příště začneme: pronajímáte na prázdniny (den 1 až den 62) loď a dostanete mnoho nabídek ve formě “chci si půjčit loďku od dne X do dne Y za Z korun”. Vyberte z nich ty, aby váš zisk byl největší. Nabídky se nesmí překrývat, půjčujete vždy od rána dne X do večera dne Y. Kdo si na příště připraví hezké funkční řešení pomocí dynamického programování, dostane body (v řádu jednotek).
• Během víkendu snad všem rozešlu komentáře k zápočťákům ze zimního semestru.
• A už je čas vymýšlet témata zápočťáků na léto. Zkuste nějaké vymyslet, do konce měsíce od vás chci alespoň téma. Tento termín je striktní, nebudu tak benevolentní k jeho nedodržení, jako v zimním semestru.

7. cvičení, 13. 4. 2011

• Bylo předvedeno řešení příkladu s loďkou.
• Společně jsme dali dohromady Dijkstrův algoritmus hledání nejkratší cesty v grafu s kladně ohodnocenými hranami.
• Na závěr jsem zopakoval postup hledání nejlepšího uzávorkování matic pro násobení.

8. cvičení, 20. 4. 2011

• Loďky můžou být klidně dvě. Vymýšlením algoritmu jsme strávili v podstatě celé cvičení.
• Příště bude písemka na dynamické programování.

9. cvičení, 27. 4. 2011

• V písemce byl úkol vymyslet algoritmus na hledání nejdelší rostoucí podposloupnosti, nikdo ho nevyřešil.
• Společně jsme ho potom zvládli.
• Potom jsem vám navrhnul témata zápočtových programů. Většina z nich je popsána zde.
  • Least Common Ancestor — s předpracováním v lineárním čase a dotazem v konstantním čase (Kapitola 9) [zabráno]
  • Suffixový strom ­— stavba v lineárním čase rekurzivním algoritmem (Kapitola 10)
  • Kreslení rovinných grafů v lineárním čase (Kapitola 11) [zabráno]
  • Minimální kostra v čase O(m·loglog(n)) (Kapitola 6, algoritmus #3) [zabráno]
  • Union-Find s předem známou posloupností Unionů (Kapitola 9)
  • Nejkratší cesta v grafu s nezáporně, cele a omezeně (L) ohodnocenými hranami v čase O(m+nlogL/loglogL) (Kapitola 13, Víceúrovňové přihrádky)
  • Fast Fourier Transform — násobení polynomů [zabráno]
  • RSA (s dlouhými čísly) [zabráno]

10. cvičení, 4. 5. 2011

• Zadefinováno: kombinatorická hra, vyhraná a prohraná pozice.
• Analyzovali jsme hry:
  • Nim s odebíráním 1-3
  • Nim s více hromádkami
  • Nim s více hromádkami, odebíráním 1-3
  • Taháme figurkou na šachovnici doleva a nahoru
  • Taháme figurkou na šachovnici doleva, nahoru, dolevanahoru
  • Taháme figurkou na šachovnici doleva, nahoru, dolevanahoru, dolevadolu, dopravanahoru — zacyklení (nemůžeme pozicím přiřadit nimbers)
  • Taháme figurkou na šachovnici doleva o 1, 2 nebo 3 nebo nahoru o 1, 2 nebo 3 — ekvivalentní Nimu se dvěma hromádkami a odebíráním 1-3
  • Hraní několika her současně, hráč si vždy vybírá, kde chce hrát
  • Hra se 4 kameny: 4 kameny na stole, posouváte kámen ke kraji stolu, nesmíte přeskakovat kameny
  • Hra se 3 kameny: dá se převést na předchozí případ
• Zavedli jsme si nimbers
• Nimber součtu her je xor nimberů her
• Za dobrovolný domácí úkol to dokažte. (Z definice — stačí ukázat, že: xor triviálně prohrané pozice je *0; je-li xor her roven *0, nedá se táhnout do *0; není-li roven *0, dá se táhnout do *0)

11. cvičení, 11. 5. 2011

• Dokázal jsem vám, že xor se na sčítání her skutečně hodí.
• Mohlo by se vám hodit, že Pascal má xor nativně — operand xor; normálně mu předhodíte dva integery a dostanete integer — binární xor, tak jak byste ho sami počítali.
• Programovali jsme objektový model, na něm jste si mohli vyzkoušet zapouzdření (public, protected), dědičnost a polymorfismus (virtuální metody).
• Další a poslední cvičení bude až za dva týdny kvůli rektorsko-děkanskému dnu a na něm si zkusíte nějaký příklad podobný zkouškovému. Aby vám to k něčemu bylo, zopakujte si celý semestr přednášek i cvičení.
• Jedna úloha v CodExu má první termín právě na volný den, kdo bude chtít nápovědu, nechť se ozve e-mailem, vynasnažím se ji poslat hned večer.

12. cvičení, 25. 5. 2011

• Poslední cvičení. Dělal se zkouškový příklad “Vyhodnocení anonymní ankety”. Po půlhodině přemýšlení jste ho pak společně docela dali dohromady.
• V CodExu už máte i body za docházku. 1. června končí zbylé CodExové úlohy, pak už žádné body nezískáte, bude pak tedy jasno, kdo se ještě má snažit mi nabízet zápočťák.
• Kdo mi ještě neposlal specifikaci, nechť tak učiní co nejdříve. Nemusí to být žádný velký sloh, hlavně ať je jasné, na čem jsme se dohodli.
• Pilotní verzi zápočťáku i s dokumentací mi pošlete do konce srpna. Zase se pak někdy sejdeme a můžete dostat zápočet.
• Jinak přeji mnoho zdaru při studiu a jiných věcech.

---