Cvičení z programování
Ve školním roce 2002/2003 vedu cvičení z předmětu Programování I [NPRG004]. K tomu také patří zadávání a hodnocení Ročníkového projektu I [NPRG018].
Zimní semestr
V zimním semestru se cvičení koná každé pondělí od 14.00 v posluchárně E4.
Podmínky k získání zápočtu jsou:
- Vypracování alespoň tří domácích úkolů, které budou zadávány v průběhu semestru na cvičeních a rovněž se budou objevovat na těchto stránkách.
- Vypracování zápočtového programu v Pascalu
Požadavky:
- Téma: libovolné, jaké si vymyslíte, má-li odpovídající obtížnost. Nabízím poměrně rozsáhlý 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šší, ostatní berte jako návnadu pro vaši fantazii; vlastní nápady jsou ovšem vřele vítány. Jinými zajímavými zdroji inspirace mohou být: archiv programátorského korespondenčního semináře, archiv Matematické Olympiády kategorie P, stránka Roberta Špalka, stránka Dana Kráľe.
- Do konce listopadu mne kontaktujte a sdělte mi, jaké téma jste si vybrali. Předejdete tak tomu, že váš zápočtový program bude hodnocen jako příliš jednoduchý či že vám bude vytýkáno, že programujete totéž co kolega. Toto "přihlášení" zápočtového programu je povinné!
- 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).
- 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 mi mužete předat buďto na cvičení nahraný na disketě, CD
či ZIP disku 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 mi 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í.
Letní semestr
V letním semestru cvičení pokračuje, koná se každý čtvrtek od 12:20 v posluchárně M4.
Zápočet je opět za alespoň tři domácí úkoly a zápočtový program, tentokráte o něco složitější (odpovídá obtížnosti alespoň 5 podle výše zmíněného seznamu). Do konce dubna se ozvěte, jaký zápočťák byste chtěli programovat.
Zápočtové programy je možno tvořit i v jiných procedurálních jazycích nežli v Pascalu, ale je nutné se na tom předem domluvit.
Ročníkový projekt I
V rámci cvičení rovněž zadávám (tedy vlastně schvaluji zadání, stejně jako u zápočtových programů) a hodnotím Ročníkový projekt I, za který je ovšem samostatný klasifikovaný zápočet, jehož získání není ke zkoušce nutné.
Vaším projektem by měl být nějaký větší a složitější program včetně odpovídajícího uživatelského rozhraní. Může to také být patřičně rozšířená verze zápočtového programu (např. zápočťák: šachová strategie, projekt: šachový program s grafickou šachovnicí používající tuto strategii).
Ročníkové projekty se obvykle píší v Delphi, pokud byste si rádi vybrali jiné prostředí, ozvěte se mi.
Úkoly ze zimních cvičení
| Datum | Úkoly |
|---|---|
| 14. 10. | Je dáno 12 kuliček stejných hmotností až na jednu, která je lehčí nebo těřší než ostatní. Popište postup, jak pomocí 3 vážení na rovnoramenných vahách zjistit, která to je a zda je lehčí či těžší. |
| Dokažte, že pro 13 kuliček jsou již potřeba 4 vážení. | |
| Nalezněte sadu co nejméně závaží, se kterou lze navážit libovolný celý
počet gramů od 0 do 999. a) závaží se kladou vždy na jednu misku, vážený předmět na druhou, b) závaží lze pokládat na obě misky. Zkuste dokázat, že vaše řešení je optimální. | |
| 21. 10. | Popište strategii pro hru odebírání zápalek se dvěma hráči a jednou hromádkou, přičemž v každém tahu se odebírá počet zápalek tvořící mocninu dvojky. |
| 28. 10. | Cvičení se nekonalo (státní svátek). |
| 4. 11. | Napište program, který zadané přirozené číslo převede do soustavy o základu -2. (0->0, 1->1, 2->110, 3->111, -1->11, -2->10, ...) |
| (*) Sestrojte algoritmus, který nalezne k zadanému číslu číslo zrcadlové (tj. takové, jehož dvojkový zápis obsahuje přesně tytéž číslice, jenže pozpátku) v čase O(log n), kde n je počet číslic původního čísla. Obě čísla se vejdou do integeru a operace s integery (včetně načtení a vypsání) trvají konstantně dlouho. Pro jednoduchost předpokládejte, že n je mocnina dvojky a že dokážete počítat mocniny v konstantním čase, pak si rozmyslete, jak se bez těchto předpokladů obejít. | |
| 11. 11. | Goldbachova hypotéza (dosud není známo, zda platí) říká, že každé sudé číslo mimo dvojky je součtem nějakých dvou prvočísel. Napište program, který toto ověří pro všechna sudá čísla menší než zadané N tak, že rozklady najde. |
| Napište program, který pro zadaná čísla a, b, c co nejefektivněji spočte ab mod c. | |
| Pro každé prvočíslo p a každé číslo a (0<a<p) podle Malé Fermatovy věty platí, že ap mod p=a. Ovšem existují i složená čísla p, pro která tato rovnost platí pro každé a, těm se říká Carmichaelova čísla. Napište program, který najde nejmenší takové číslo (je menší než 1000). | |
| Objevte princip, na němž je založena "závorková soustava" a (*) napište program pro převod mezi závorkovou a desítkovou soustavou. | |
| 18. 11. | Naprogramujte binární vyhledávání tak, aby v případě, že se hledané číslo v poli nevyskytuje, nalezlo nejbližší větší číslo. K programu, prosím, dodejte i důkaz jeho správnosti. |
| (*) Racionální verze hry "mysli si číslo": hádané číslo je zlomek, jehož čitatel i jmenovatel jsou menší jak zadané N. Jednodušší verze: minimalizujte počet dotazů; verze složitější: snažte se i o to, aby bylo dotazy možné rychle generovat. | |
| 25. 11. | Cvičení se nekonalo. |
| 9. 12. | Napište program, který pro zadané x (real) a N (integer) nalezne co nejlepší aproximaci čísla x zlomkem, jehož jmenovatel je menší jak N. |
| 16. 12. | Napište program, který vypíše všechny n-prvkové posloupnosti nul a jedniček v takovém pořadí, aby se každé dvě sousední lišily v právě jednom prvku. |
| Napište program, který vypíše všechny permutace množiny 1...n. | |
| ... tak, aby se každé dvě sousední lišily právě prohozením dvou prvků. | |
| (*) Vymyslete algoritmus pro výpočet n-tého Fibonacciho čísla Fn v čase lepším než lineárním za předpokladu, že aritmetické operace s čísly velkými řádově Fn lze provádět v konstantním čase. Hint: použijte explicitní vzorec a nalezněte jeho vhodnou aproximaci. | |
| 6. 1. | Problém Bílé paní: je dáno obdélníkové bludiště m krát n políček, jehož každé políčko je buďto volný prostor nebo zeď. Nalezněte mezi dvěma zadanými body cestu, která prochází co nejméně zdmi. |
| Problém Santa Clause: Santa Claus rozváží dárky po světě, který budeme aproximovat bludištěm z předchozí úlohy. Jelikož se jeho sobí spřežení pohybuje zběsilou rychlostí, působí na něj Coriolisova síla, takže dokáže buďto jezdit rovně nebo zahýbat doprava (doleva nikoliv, to už by pro soby bylo moc namáhavé). Nalezněte nejkratší cestu mezi dvěma body za těchto podmínek. | |
| Problém Kulhavého koně: Kulhavý kůň je šachová figurka, která v sudých tazích skáče jako kůň a v lichých chodí jako pěšec (tedy o jedno políčko dopředu). Nalezněte pro zadanou šachovnici m krát n nejkratší cestu (měřeno počtem tahů) kulhavým koněm mezi dvěma zadanými políčky. |
Úkoly z letních cvičení
| Datum | Úkoly |
|---|---|
| 27. 2. | Naprogramujte MergeSort |
| Naprogramujte QuickSort | |
| (**) Vymyslete algoritmus pro slévání dvou setříděných posloupností v konstantním pomocném prostoru. | |
| 6. 3. | Naprogramujte třídění pomocí haldy (HeapSort) s vytvářením haldy v lineárním čase. |
| Naprogramujte operace s k-regulárními haldami: Create, Insert, DeleteMin. | |
| 13. 3. | Je dáno N čísel v rozsahu 0..N3-1. Sestrojte algoritmus, který je v lineárním čase setřídí. (Hint: Použijte příhrádkové třídění.) |
| "Jak vypadá inverzní funkce k třídění?" aneb míchání karet: Napište program, který k zadané posloupnosti vygeneruje její náhodnou permutaci tak, aby všechny permutace byly stejně pravděpodobné. To dokažte. (Lze to v lineárním čase.) | |
| (*) Vymyslete algoritmus pro lexikografické třídění řetězců v čase přímo úměrném jejich celkové délce. (**) ... takový, jehož složitost je O(n+a), kde n je celková délka a a velikost abecedy. | |
| 20. 3. | Napište program, který o dané posloupnosti levých a pravých kulatých a hranatých závorek rozhodne, zda je dobře uzávorkovaná (přesná definice: 1. prázdná posloupnost je d.u., 2. jsou-li A, B d.u., pak také AB, (A) a [A] jsou d.u., 3. každá d.u. posloupnost se dá vytvořit konečným počtem aplikací pravidel 1 a 2.). Snažte se o co nejmenší časové i paměťové nároky, případně zkuste dokázat, že to lépe nejde. |
| Napište funkci, která z jednosměrného seznamu vypustí všechny prvky splňující danou podmínku (tu můžete předat např. prostřednictvím pointeru na funkci) a vrátí pointer na výsledný seznam. | |
| Napište funkci, která jednosměrný seznam otočí na místě, tj. vrátí jiný seznam složený z těchže prvků (prvky tedy nekopíruje) v opačném pořadí. | |
| Napište funkci, která o jednosměrném seznamu rozhodne, zda je zacyklený či nikoliv. Funkce nesmí seznam nijak modifikovat a může používat pouze konstantní množství pomocné paměti. | |
| 27. 3. | Napište funkci pro setřídění jednosměrného seznamu (např. mergesortem). |
| 3. 4. | Naprogramujte operace s obousměrnými cyklickými
seznamy: založení seznamu, vložení prvku, odebrání prvku, spojení dvou seznamů do jednoho.
Všechny operace by měly mít konstantní časovou složitost a s výjimkou spojování seznamů
se obejít bez příkazu if. |
| Napište funkce pro hledání, vkládání a odebírání prvků v binárním vyhledávacím stromu (BVS) bez vyvažování a pro vypsání všech prvků takového stromu. | |
| Napište funkci, která pro zadanou množinu hodnot zkonstruuje vyvážený BVS obsahující právě tyto hodnoty. | |
| 10. 4. | Napište funkci pro nalezení následníka daného prvku v BVS (tj. nejmenšího z prvků větších než daný), naprogramujte vypisování všech prvků pomocí této funkce a dokažte, že má lineární časovou složitost. |
| Naprogramujte jednoduché a dvojité rotace v BVS. | |
| Sestrojte funkci, která co nejefektivněji spojí dva vyvážené BVS do jednoho (ne nutně
vyváženého), tj. sestrojí strom obsahující právě prvky, které se vyskytnou v některém
ze zadaných stromů (předpokládejme, že každý prvek se může vyskytnout maximálně jednou).
a) víme-li, že maximální prvek prvního stromu je menší než minimální prvek druhého b) pokud to neplatí Zkuste dokázat, že vaše řešení je nejrychlejší móžné. | |
| (*) Vymyslete (nemusíte programovat) algoritmus na vyvažování AVL stromů po insertu a deletu. Velmi se k tomu hodí jednoduché a dvojité rotace. | |
| 17. 4. | Naprogramujte hashovací tabulku s automatickým přehashováváním podporující vyhledávání, vkládání a odebírání hodnot. |
| Naprogramujte operace s (2,3)-stromy: vyhledávání, přidávání a odebírání hodnot. | |
| 24. 4. | Je dána posloupnost N celých čísel a číslo X. Zjistěte, zda existuje dvojice prvků posloupnosti, jejichž součet je X. Jde to v průměrně lineárním čase. |
| Je dána posloupnost N celých čísel a číslo X. Zjistěte, zda existuje souvislý úsek posloupnosti, jehož součet je právě X. Jde to v průměrně lineárním čase. | |
| Napište program, který pro zadanou permutaci p(1)...p(N) spočte její k-té složení: pk(i)=p(p(p(...(i)...))) [k-krát vnořeno]. Jde to v lineárním čase. | |
| 28. 4. | Hříčka: Napište program, který vypíše, zda kompilátor, kterým byl přeložen, podporuje vnořování komentářů. |
| (*) Hříčka #2: ... zda kompilátor byl kompilátorem Pascalu nebo Céčka. | |
| Mějme knihy očíslované 1..N, tloušťka i-té knihy buď ti, výška hi. Buď dále dáno číslo W. Napište program, který spočte nejmenší možnou výšku knihovny s policemi širokými W takovou, aby do ní bylo možno naskládat všechny zadané knihy v původním pořadí. | |
| 1. 5. | Cviceni se nekonalo (statni svatek), presunuto na 28. 4. |
| 5. 5. | Editacni vzdalenost retezcu P a Q je definovana jako minimalni pocet editacnich operaci (vsunuti jednoho znaku, vypusteni jednoho znaku, nahrada jednoho znaku jinym), kterymi je mozne z P vyrobit Q. Naprogramujte co nejefektivnejsi funkci, ktera pro zadane 2 retezce spocte jejich editacni vzdalenost. |
| Je dan retezec bez mezer a velky slovnik. Napiste program, ktery vypise, jak lze zadany retezec rozlozit na slova vyskytujici se ve slovniku; pokud existuje vice reseni, vyberte to, ktere pouziva co nejmene slov. Pokud i vice takovych, vyberte libovolne z nich. | |
| Napiste program, ktery pro zadane frekvence pismen spocita jejich optimalni
rozmisteni na klavesnici telefonu, tj. takove, aby:
1. kazde cislici byl prirazen souvisly usek abecedy, 2. pokud je cislice i<j, byla vsechna pismena prirazena cislici i v abecede pred vsemi pismeny prirazenymi cislici j. 3. na napsani nahodneho textu se zadanymi frekvencemi bylo potreba co nejmene stisku klaves (na prvni pismeno prirazene cislici je potreba jeden stisk, na druhe dva atd.). | |
| 8. 5. | Cviceni se nekonalo (statni svatek), presunuto na 5. 5. |
| 15. 5. | Cviceni se nekonalo (byl jsem na Jarni Skole Kombinatoriky) |
| 22. 5. | Cvicil za mne Pavel Machek, zadne domaci ukoly nezadal. |