Algoritmy a jejich implementace - cvičení

V akademickém roce 2016/2017 vedl cvičení z předmětu Martina Mareše Algoritmy a jejich implementace (NDMI074) Ondra Hlavatý. Tady najdete podmínky pro zápočet, seznam domácích úkolů, i více či méně detailní zpravodajství ze cvičení a odkazy související s tím, o čem budeme zrovna mluvit. Budete-li mít jakékoliv dotazy či připomínky, neváhejte nám poslat mail, nebo si s námi promluvit osobně.

Aktuální domácí úkol: life

Naprogramujte simulátor Conway's game of life. Použijte k tomu drobnou modifikaci aim-kitu, aim-life. Ten naleznete již tradičně v camellia:/usr/share/aim/aim-life, případně lze stáhnout. Paralelizace je povolena.

Na vstupu máte černobílý obrázek v pbm, kde černá (1) značí živou buňku, bílá (0) značí mrtvou. Můžete předpokládat, že rozměry obrázku jsou dělitelné 16. Nečekejte však, že jsou čtvercové. Dalším vstupem je pak počet iterací (kroků hry života), které máte odsimulovat.

Vraťte počet buňek, které jsou živé v původním výřezu daném vstupním souborem. Celou hru ovšem simulujte na nekonečné rovině.

Deadline tohoto úkolu je konec září. Není povinný.

Zápočtové programy

Pamatujte, že pro získání zápočtu je potřeba vypracovat samostatný zápočtový program. Jeho téma si vyberte, nechte schválit a vypracujte.

Přibližný algoritmus pro určení očekávané obtížnosti zápočtového programu:

Data na camellii

Přeneste si užitečná data z camellie, vaše účty a data budou v dále neohlášené době v průběhu ZS 2017/18 smazána.

Kdy a kde je cvičení?

Letos cvičení probíhá každé úterý v 9:00 v učebně SU1.

Co od Vás očekáváme?

Předpokládáme, že máte účet v labu a již jste někdy viděli UNIXovou příkazovou řádku. Zbytek vás zkusíme naučit.

O čem cvičení bude?

Budeme se soustředit na praktické vyzkoušení si a zvládnutí základních technik souvisejících s implementací výpočetně náročných programů - běžné neefektivní a efektivní programátorské obraty ve vnitřních smyčkách, zkoumání možnosti optimalizace překladačem, způsoby a možnosti profilování, různé možnosti paralelizace a možná něco navíc. Snad se dozvíte i pár programátorských zajímavostí.

A co zápočet?

K získání zápočtu bude potřeba odevzdat zápočtový program. Jeho obtížnost se bude řídit podle množství získaných bodů z domácích úkolů ‒ čím více bodů, tím lehčí bude zápočťák. Pokud budete mít opravdu hodně bodů, může vám být i odpuštěn. Naopak, 0 bodů z domácích úkolů může zapříčinit zadání téměř neřešitelného programu. Docházka na cvičení není povinná, ale informace ze cvičení mohou být důležité k pochopení domácích úkolů.

Domácí úkoly

Za úkol máte (zhruba) do 14 dnů od zadání co nejefektivněji naimplementovat v jazyce C řešení daného problému.

K měření a testování vašich strojů máte k dispozici stroj camellia.kam.mff.cuni.cz. Uživatelské jméno je stejné jako do SISu, heslo jste dostali na cvičení na papírku. V opačném případě se ozvěte na mail cvičení.

Pokud jste to již neudělali, změňte si své heslo pomocí příkazu passwd.

K odevzdávání slouží skript aim-submit. Bez parametrů vypíše nápovědu a úlohy, které lze odevzdat. Také je k dispozici skript aim-test, který spustí pár testů a odhadne počet obdržených bodů. Slouží jen pro orientaci. Kdyby dával řádově špatné výsledky, dejte vědět.

Úlohy se vyhodnocují v 5:00 ráno automaticky. Všechny uživatelské procesy jsou zabity, takže si na serveru nenechávejte nic důležitého běžet. Vaše řešení bude zkompilováno dle zadání úlohy a spuštěno samostatně.

Vaše řešení musí jednak správně odpovědět na několik testovacích vstupů, druhak běžet dostatečně rychle. Pro každý úkol je v systému schovaná rozumně implementovaná (ale nepříliš zoptimalizovaná) referenční implementace; poběžíte-li stejně rychle, dostanete 5b, poběžíte-li pomaleji/rychleji, dostanete od 1b do 15b:

score = min(floor(5 * reftime/yourtime), 15)

Výsledky obdržíte mailem, veřejná tabulka s body bude k dispozici na této stránce.

E-maily obdržíte na username@camellia. Funguje zde obvyklé doručování e-mailů, takže lze do souboru ~/.forward umístit alternativní adresu, na kterou se maily budou přeposílat. Na začátku máte v tomto souboru svůj e-mail ze SISu.

V tabulce budete uvedeni pod uživatelským jménem, nebo pod obsahem souboru ~/.nickname. Pro začátek je tam vaše jméno. Ano, rozbijete to, pokud budete chtít :)

Odevzdávací systém není ani tak stabilní a odladěný jako CodEx, je spíchnutý na koleni. Tento ročník je první, testovací. Pokud najdete způsob, jak jej rozbít, oceníme, pokud nám o něm řeknete dříve, než to uděláte :)

aim-kit

Pro několik příštích úkolů použijeme framework pro práci s obrázky. Lze si ho stáhnout, nebo najít na camellii v /usr/share/aim/aim-kit. Obsahuje malé README. Přečtěte si jej.

K jeho zprovoznění na svých strojích budete potřebovat knihovnu netpbm.

K testování úloh v aim-kitu můžete použít aim-test <task>, ale pozor, tentokrát netestuje korektnost. Tu totiž můžete snadno zkontrolovat vizuálně.

Aim-kit načítá obrázky ve formátu PBM. Vaším úkolem je naprogramovat funkci exercise, která dostane vstupní a výstupní obrázek jako struct image. Ta obsahuje načtený obrázek jako bitovou mapu. Výstupní obrázek se uloží do souboru. Formát PBM umí rozumná zobrazovátka obrázků, mj. třeba obyčejný display. Ten funguje dobře i na camellii s forwardováním X-ek.