Ve skolnim roce 2011/2012 vedu cviceni z predmetu Algoritmy a jejich implementace (NDMI074). Tady najdete podminky pro zapocet, seznam domacich ukolu, i vice ci mene detailni zpravodajstvi ze cviceni a odkazy souvisejici s tim, o cem budeme zrovna mluvit. Budete-li mit jakekoliv dotazy ci pripominky, nevahejte nam poslat mail nebo s nami promluvit osobne.
Kdy cviceni bude? Cviceni ma dve paralelky - kazde pondeli od 17:20 v SU1 a kazde utery od 15:40 take v SU1. Na cviceni se zapisujte v SISu.
Co od Vas ocekavame? Predpokladame, ze mate ucet v u-labu, umite alespon zaklady C, jiz jste nekdy videli UNIXovou prikazovou radku a snad si i nejaky Cckogram v UNIXu prelozili a spustili.
O cem cviceni bude? Podivejte se na plan nize. Budeme se soustredit na prakticke vyzkouseni si a zvladnuti zakladnich technik souvisejicich s implementaci vypocetne narocnych programu - bezne neefektivni a efektivni programatorske obraty ve vnitrnich smyckach, zkoumani moznosti optimalizace prekladacem, zpusoby a moznosti profilovani, ruzne moznosti paralelizace a zaklady programovani na GPU. Snad se dozvite i par programatorskych zajimavosti.
A co zapocet? Dostanete jej za hrstku domacich ukolu a hlavne zapoctovy program. Na zapocet nebude mit vliv dochazka na cviceni (prestoze vrele doporucena).
Za domaci ukoly byste meli nasbirat behem semestru alespon 20 bodu. Ulohy budou spocivat v co nejefektivnejsi implementaci ruznych drobnejsich algoritmu. Presny zpusob bodovani ukolu viz nize. Preteceni ci nedosazeni celkove bodove hranice bude mit vliv na pozadovany rozsah zapoctaku.
Hlavni podminkou zapoctu je zapoctovy program. Ten by mel spocivat v ukazce efektivni zoptimalizovane implementace nejakeho konkretniho algoritmu; inspiraci muzete hledat napriklad na prastrance prednasky. Nestaci jen ukazat zdrojak, budeme chtit i komentar o tom, na kterych mistech program travi nejvice casu (a proc), jak jste se pokusili uzka hrdla odstranit a proc si myslite, ze rychleji to jiz nepujde; mala diskuse nad zapoctakem bude (krome dotazu na probranou latku) i soucasti zkousky.
Tema zapoctoveho programu byste si meli vybrat do pulky semestru, ocekavam, ze postupne zacnete jeste behem semestru pracovat i na implementaci. Tvrda deadline na odevzdani prvni verze zapoctaku bude zacatek zari, odevzdat finalni verzi zapoctaku byste meli nejpozdeji tyden pred zkouskou, abychom meli dostatecne casove buffery (vetsinou se ruzne zvedave vyptavam).
Za ukol mate (zhruba) do 14 dnu od zadani co nejefektivneji naimplementovat v jazyce C reseni daneho problemu. Vase reseni musi jednak spravne odpovedet na nekolik testovacich vstupu, druhak bezet dostatecne rychle. Pro kazdy ukol je v systemu schovana rozumne implementovana (ale neprilis zoptimalizovana) referencni implementace; pobezite-li stejne rychle, dostanete 5b, pobezite-li pomaleji/rychleji, dostanete od 1b do 15b:
score = min(floor(5 * reftime/yourtime), 15)
Reseni posilejte na e-mailovou adresu aim@kam.mff.cuni.cz;
v subjectu uvedte pouze identifikator ukolu a v tele mailu pouze kod reseni.
Napriklad v UNIXu prikazem cat zdrojak.c | mail -s kod aim@kam.mff.cuni.cz
(s ruznymi privesky, ktere muze generovat treba Vas webmail, se zatim nevyrovname,
klidne to z nej vsak alespon zkuste).
Do nekolika minut byste meli dostat zpet informaci o vysledcich.
Zatim je nas vyhodnocovaci robot spise v testovacim provozu, takze kdyz
se Vam nebude neco zdat, nevahejte se ozvat na aim@ucw.cz
(to ctou skutecni lide).
Vase reseni budeme merit prelozene gcc-4.6.2 -lm -Wall -O3 -march=native -std=gnu99
na 8x AMD FX-8150 Bulldozer.
Reseni uzavrenych ukolu. (Pokud zatim v adresari reseni daneho ukolu zadne neni, muzete stale ziskavat body!)
Aktualni vysledky:
| Student | Priklady | Bodu |
|---|---|---|
| "Adam Juraszek" <juraszea@...> | eras(15:6.50) lone(15:0.39975) | 30 |
| "Dominik Taborsky" <taborskd@...> | eras(9) wave(12) | 21 |
| "Jakub Hajic" <j.hajic@...> | eras(15:5.53) wave(11) | 26 |
| "Jan Benes" <benej5am@...> | lone(10) wave(15:0.2295) | 25 |
| "Jan Tomasek" <tomasek.jan@...> | eras(15:6.31) lone(2) wave(15:0.20075) | 32 |
| "Petr Fejfar" <fejfarp@...> | eras(11) | 11 |
| "Roman Kucera" <kucer6am@...> | eras(15:5.45) lone(15:0.362) pixr(14) wave(4) | 48 |
| "Stepan Havranek" <havranek.stepan@...> | eras(15:6.58) | 15 |
| "Vaclav Obrazek" <obrazev@...> | eras(14) lone(6) wave(2) | 22 |
| =?ISO-8859-1?Q?KarelKr=E1l?= <kralkareliv@...> | eras(15:5.13) pixr(3) wave(4) | 22 |
| =?UTF-8?Q?Ond=C5=99ejMajerech?= <oxyd.oxyd@...> | eras(13) | 13 |
| Martin Pelikan <pelikan@...> | pixr(12) | 12 |
| Ondrej Majerech <oxyd.oxyd@...> | pixr(7) | 7 |
| Petr Baudis <pasky@...> | eras(6) ir90(5) lone(8) pixr(7) wave(8) | 34 |
| pasky@... | wave(4) | 4 |
| tauferp@... | eras(15:5.04) lone(15:0.31525) wave(15:0.1945) | 45 |
Plan je pouze predbezny! Temata kursivou nemuseji 1:1 odpovidat jednotlivym tydnum.