Cvičení z programování I pro pokročilé
Ve školním roce 2009/2010 vedeme s Milanem Strakou speciální cvičení z předmětu Programování I [NPRG030] pro pokročilé studenty, kteří již nasbírali nějaké zkušenosti z programování (třeba v olympiádách a korespondenčních seminářích) a chtěli by se naučit víc.
Viz též letáček :-)
Cvičení se koná každé pondělí od 12:20 v S6, kdo chcete chodit, přihlašte se, prosíme, v SISu.
Podmínky k získání zápočtu jsou (AND):
- vypracování domácích úkolů za alespoň 100 bodů
- vypracování zápočtového programu
Kontakt
Svým cvičícím pište na adresu mami@ucw.cz (Martin+Milan).
Zápočtový program
- Téma: libovolné, jaké si vymyslíte, má-li odpovídající obtížnost. Pokud vás ještě múza nepolíbila, podívejte se na náš seznam témat (na skladě též zdrojový text v TeXu a pěkně vysázená verze v PDF); přiměřené pro zimní semestr jsou úlohy obtížnosti 3 a vyšší. Jinými zajímavými zdroji inspirace mohou být: archiv programátorského korespondenčního semináře a archiv Matematické Olympiády kategorie P.
- Jazyk: nejlépe Pascal nebo C; pokud máte dobrý důvod použít něco jiného, ozvěte se, lze se domluvit.
- Odevzdání specifikace programu do konce listopadu. Tím máme na mysli krátký popis toho, co všechno by program měl umět. Vyhnete se tak tomu, že by váš zápočtový program odevzdaný den před koncem zkouškového období byl odmítnut jako příliš triviální nebo příliš podobný programu někoho z vašich kolegů.
- Nedílnou součástí zápočtového programu je dokumentace, a to jak uživatelská (vysvětující, jak se program ovládá), tak programátorská (ta popisuje, jak program uvnitř funguje; postrádá smysl popisovat každou funkci či proměnnou, zaměřte se spíš na celkový návrh programu a použité algoritmy, pokud jste je sami nevymysleli, je moudré uvést odkazy na zdroje, z nichž jste čerpali).
- Specifikaci i dokumentaci odevzdávejte buďto v papírové podobě nebo chcete-li šetřit naše lesy, elektronicky v libovolném otevřeném formátu (tím se myslí formát, jehož struktura je všeobecně známa a na jehož prohlížení není potřeba žádný komerční software; speciálně tedy ne MS Word!), nejlépe jako čistý text, HTML, PostScript či PDF.
- Hotový program nám mužete předat buďto na cvičení nahraný na CD či v lahvi (totiž USB flašce)
nebo jej poslat po Internetu, buďto e-mailem nebo (pokud je poněkud
větších rozměrů, řekněme nad 0.5MB) uploadem do
ftp://atrey.karlin.mff.cuni.cz/pub/priv/(ale pak pošlete mail se jménem souboru). Pokud se zápočťák skládá z většího množství souborů, raději jej předtím zabalte ZIPem nebo TARem (RAR, prosím, ne). - Zápočtový program musí mít přiměřeně ošetřené vstupy. Tím se myslí, že komunikuje-li s uživatelem, měl by počítat s tím, že uživatel je nešika a občas zadá špatný vstup a nenechat se tím zmást a bez zaváhání je odmítnout. Naopak, pokud programujete knihovnu funkcí, můžete předpokládat, že všechny vstupy jsou korektní.
Domácí úkoly
Domácí úkoly jsou dvou druhů:
- Praktické – odladěné programy řešící jednoduché problémy. Odevzdávají se do CodExu, který je automaticky testuje. Jakmile si v CodExu založíte účet (pokud možno si jako kroužek nastavte 99), napište nám a my vás přidáme do naší skupiny I99 a uvidíte všechny již zadané úlohy. Pozor, některé úlohy bude možné řešit pouze nějakou dobu (např. měsíc) po zadání.
- Teoretické – těžší problémy, kde jde daleko víc o efektivní algoritmus než implementační detaily. Řešení nám posílejte mailem, a to buď v těle zprávy nebo jako textovou přílohu. U některých úkolů je v hranatých závorkách zmíněna časová složitost, které (případně lepší) byste měli dosáhnout.
Na získání kýžené stovky bodů bohatě stačí praktické úlohy, pokud je řešíte včas.
Teoretické úkoly
| Datum | ID | Body | Příklady |
|---|---|---|---|
| 5. 10. | funb | 5 | Co dělá funkce bc() z letáčku? |
| funf | 10 | Co dělá funkce flr() z letáčku? Jakou má časovou složitost? | |
| liar | 15 | Dokažte, že ve hře "mysli si číslo" s nejvýše jednou lží potřebujeme aspoň log2 n + log2 log2 n + konst. tahů. | |
| 12. 10. | knih | 10 | Na cvičení jsme dotříďovali posloupnost, ve které je každý z n prvků na pozici
vzdálené nejvýše k od spravné. Jak to udělat, když neznáme k? [lépe než Θ(n log n)]
[+5 bodů] ... se složitostí O(n log k). |
| real | 10 | Představte si, že máte počítač, který umí počítat v konstantním čase s neomezeně velkými a neomezeně přesnými reálnými čísly: sčítat, odčítat, násobit, dělit, umocňovat, počítat celé části apod. Jak na tomto počítači hledat N-té prvočíslo v konstantním čase? | |
| 2. 11. | elec | 10 | Dokažte, že řešení úlohy o volbách, které jsme dělali na cvičení, funguje
i s neostrou nerovností.
[+5 bodů] místo důkazu protipříklad :) |
| elek | 15 | Obecnější volby: chceme najít kandidáty, pro které hlasuje více než n/k voličů. Tentokrát si můžeme dovolit paměť závislou na k, nikoliv však na n. | |
| 9. 11. | knxt | 10 | Jak vypsat posloupnosti n nul a jedniček s právě k jedničkami nerekurzivně? |
| kgry | 10 | Jak vypsat posloupnosti n nul a jedniček s právě k jedničkami v takovém pořadí, aby se každé dvě sousední lišily jen na dvou pozicích? | |
| pgry | 10 | Jak vypsat permutace na n-prvkové množině tak, aby se sousední dvě lišily právě jednou transpozicí? | |
| 23. 11. | bfsq | 15 | Budeme-li hledat do šířky v rovinném bludišti NxN, jak velká fronta je potřeba? Stačí O(N)? |
| 30. 11. | kdim | 10 | Zobecnění prefixových součtů: Vymyslete pro pevné d datovou strukturu, která dostane na vstupu d-rozměrnou matici, v čase lineárním s její velikostí provede předvýpočet a pak bude umět zjistit v konstantním čase součet prvků v libovolné d-rozměrné souvislé podmatici (tedy d-rozměrném kvádru). |
| 7. 12. | diam | 10 | Dokažte, že následující algoritmus správně spočíta průměr stromu (maximum vzdáleností mezi vrcholy): zvolíme libovolný vrchol v, najdeme vrchol x nejvzdálenější od v, najdeme vrchol y nejvzdálenější od x a prohlásíme za průměr vzdálenost xy. |
| 11. 1. | tcol | 15 | Navrhněte datovou strukturu, která při inicializaci dostane zadaný strom, něco si pro něj předpočítá a pak umí operace "obarvi daný vrchol černě/bíle" a "spočítej, kolik je pod daným vrcholem černých a bílých vrcholů". |
| 10. 5. | zapo | ε | Body navíc na výborný zápočťák. |
Výsledky
| Jméno | Teoretické příklady | CodEx | Bodů | Zápočťák | Z |
|---|---|---|---|---|---|
| David Brázdil | funb(5) | 85 | 90 | BSP stromy | |
| Radim Bufka | 0 | 0 | |||
| Leonid Buneev | 40 | 40 | |||
| Pavel Dvořák | – | 0 | |||
| Richard Ejem | funf(5) funb(5) knxt(10) elec(10) pgry(10) | 60 | 100 | Hledání duplikátů OK | Z |
| Petr Fanta | – | 0 | |||
| Marek Fišer | real(10) funf(10) funb(5) zapo(15) | 60 | 100 | L-systémy OK | Z |
| Thomas Jandečka | – | 0 | |||
| Peter Júnoš | funb(5) | – | 5 | ||
| Vojtěch Král | 20 | 20 | Crashtest | ||
| Jan Matějka | 100 | 100 | |||
| Lucie Mohelníková | 0 | 0 | |||
| Marek Nečada | funb(5) diam(10) knxt(10) kdim(5) | 70 | 100 | Rozvrhovátko OK | Z |
| Jitka Novotná | funb(5) knih(5) real(10+...) diam(10) | 90 | 120 | Kaktusy OK | Z |
| Václav Pernička | – | 0 | |||
| Milan Rybář | 50 | 50 | |||
| Veronika Steffanová | – | 0 | |||
| Jan Tichý | bfsq(15) funb(5) pgry(10) | 70 | 100 | DeCAPTCHAtor OK | Z |
| Mikhail Tikhonov | 0 | 0 | |||
| Pavel Veselý | funb(5) funf(10) | 90 | 105 | Žluťoučký kůň OK | Z |
| Jakub Vlček | – | 0 | |||
| Martin Zikmund | 10 | 10 |
(body z CodExu se přepočítávají jednou nočně)
Co jsme dělali
| datum | co se cvičilo |
|---|---|
| 5. 10. | Jak rotovat pole? Jak najít chybějící perlu? Nebo dvě? Hádání čísla s lhářem. |
| 12. 10. | Jak dotřídit knihovnu, když je k knížek špatně? Když je každá vzdálena o nejvýše k od správné polohy? (Jak pomocí haldy, tak tříděním bloků a sléváním.) Šifrujeme mřížkou (opakovaně). |
| 19. 10. | Euklidův algoritmus a jeho složitost. Úsek s maximálním součtem (a případně zadanou délkou) – mnoho různých algoritmů. Úsek se zadaným součtem. |
| 26. 10. | Jak čísla 1...N opatřit znaménky, aby byl jejich součet roven K? Nejdelší vyvážený úsek. Počítání minim všech úseků dané délky. Počítání součinů bez i-tého prvku (šetříme prostorem). Budou volby. |
| 2. 11. | Ještě jednou volby. Generování posloupností nul a jedniček rekurzivně i nerekurzivně. Jak to dělat, když chceme, aby se dvě sousední lišily jen na jedné pozici? |
| 9. 11. | Generování posloupností s právě k jedničkami, generování permutací (rekurzivně i nerekurzivně). |
| 16. 11. | Míchání karet aneb překvapivě mnoho způsobů, jak si pořídit náhodnou permutaci. Prohledávání do šířky: Problém kulhavého koně. Problém s maticí: máme matici A celých čísel, ostře rostoucí v řádcích i sloupcích, a chceme najít všechny dvojice (i,j) takové, že A[i,j] = i+j. |
| 23. 11. | Různé triky na dolní odhady složitosti (maticová úloha z minula, vážení kuliček, třídění, konvexní obaly). Prohledávání do šířky: kulhavé autíčko, Théseus a Minotauros (s mečem), stručně o Patnáctce a nejmenších násobcích daného čísla složených z 0 a 1. |
| 30. 11. | Nuly a jedničky. |
| 7. 12. | Lezení po stromech: nejdelší cesta, největší nezávislá množina, mafiáni. Asfaltujeme město. |
| 14. 12. | Grafoviny: kreslení jedním tahem či nejmenším možným počtem tahů, vyvážená a skoro vyvážená orientace grafu, podgraf s polovičními stupni a párování v 2k-regulárním bipartitním grafu. Mocnění matice sousednosti. Wanted: šéf agentů. |
| 4. 1. | Jeřábníkovy starosti. Vyhledávací stromy. |
| 11. 1. | Napadl sníh aneb Steinerovy stromy pro body v rovině (jen zmínka). Vyvažovaní stromů pomocí rebuildů, střádáme do prasátek. Počítání inverzí v posloupnosti. Převod permutace na její pořadí a zpět. Jak pro strom předpočítat vhodné údaje, abychom uměli v čase O(1) odpovídat, v jakém příbuzenském vztahu jsou dané 2 vrcholy? |