Cvičení NPRG030 v pondělí

Cvičení se odehrává v lichých týdnech (počínaje prvním) v učebně S7, v sudých v počítačové laboratoři SW2. Tam je pro práci nutné zřídit si účet, bližší informace naleznete zde. Na cvičení se budeme zabývat algoritmy a jejich implementaci budeme provádět v jazyku Pascal.

Pro získání zápočtu je nutné splnit všechny tři následující podmínky:

1. Získat alespoň 100 bodů z domácích úkolů. Na cvičení si vedu prezenci, a pokud budete chybět nejvýše na čtyřech cvičeních, obdržíte bonus 20 bodů k domácím úkolům. Dále je možné body získat za aktivitu na cvičení či dle uvážení cvičícího. Naopak za opisování domácích úkolů mohu dle svého uvážení body strhnout nebo libovolně rozdělit.
2. Úspěšné absolvování zápočtové písemky na ukazatele alespoň na 15 bodů z 25.
3. Vypracování zápočtového programu v dostatečném rozsahu.

Domácí úkoly budou dvojího typu, praktické a teoretické. Praktické se odevzdávají pomocí rozhraní CodEx a jsou automaticky vyhodnocovány na několika vstupních souborech. Jejich odevzdání je však časově omezeno. Pro možnost odevzdávání úloh je potřeba si nejprve zřídit účet a poté mi zaslat jeho login na mail, abych vás mohl zařadit do skupiny. Pokud se objeví jakékoliv problémy, pište nejprve mě, až poté administrátorovi. Teoretické úkoly jsou malinko těžší, vyžadují vyřešení daného problémů (mnohdy alespoň tak rychle jako je nějaký předepsaný čas) a také by jejich řešení mělo obsahovat zdůvodnění správnosti. Řešení mi posílejte mailem a to buď přímo v textu mailu nebo jako přílohu v libovolném rozumném formátu (tím myslím čistý text, HTML, PDF, PS, nikoliv obskurnosti jako DOC, RTF a podobné, pokud podobné formáty, převeďte výsledek do PDF).

Inspiraci na téma a rozsah zápočtového programu naleznete například na stránkách Martina Mareše. Do konce listopadu je nutné mi mailem zaslat specifikaci, ve které popíšete jaký zápočták hodláte programovat. Tím minimalizujete riziko, že by Váš zápočták byl odmítnut jako moc jednoduchý nebo příliš podobný některému z vašich kolegů. Součástí specifikace by měl být stručný popis toho, co by měl program umět a v jakém programovacím jazyku (případně s použitím jakých knihoven) ho budete implementovat. Doporučené jazyky jsou Pascal, C nebo C++. Pokud máte však dobrý důvod použít něco jiného, zkuste mi napsat. Nutnou součástí zápočťáku je jeho dokumentace, to jak programátorská (jaké techniky a algoritmy jste použili a podobně), tak uživatelská (jak se program ovládá), podobně jako u domácích úkolů v rozumném formátu. Ošetřeny by také měli být věci jako neplatné vstupy.

Na některém z posledních cvičení budeme psát zápočtovou písemku na ukazatele. V té si ověřím vaše znalosti získané během semestru. Bližší informace upřesním později.

Pokud všechny podmínky splníte, dostanete zápočet, ten Vám však do indexu a do SISu zapíše přednášející.

Konzultační hodiny nevypisuji, ale lze si je domluvit po mailu. Ideální doba je například na konci cvičení.

Opravná písemka je opravena, omlouvám se za zpoždění. Případná náhradní písemka bude v prvním týdnu letního semestru.

Seznam teoretických úkolů

Byly zadány tyto teoretické úlohy, v závorce je uveden počet bodů za vyřešení:

• Ňam(10) je hra podobná nimu (odebírání zápalek), ale hraje se s kousky čokolády. Na cvičení jsme rozebírali několik variant, zkuste vyřešit následující. Hráči se střídají a v každém kole mohou sníst 2 nebo 3 kousky čokolády. Prohrává ten, kdo již nemůže táhnout/jíst. Navrhněte vyhrávající strategii, při které navíc sníte maximum kousků čokolády (tzv. hladový algoritmus :)). Vězte však, že váš soupeř se vám bude v mlsání snažit bránit.
• Div3(10) popište, jak lze u čísla zapsaného ve dvojkové soustavě zjistit jeho zbytek po dělení třemi (pochopitelně bez toho, abyste ho převáděli do desítkového zápisu).
• Kač(15) - Byla jednou jedna kačenka, která plavala uprostřed kruhového jezírka. Ale poranila si nožku a tak nemůže vzlétnout z hladiny jezera. Jediná její šance je se tedy dostat na břeh. Bohužel tam na ni číhá hladová kočka, která, jak už to bývá, moc ráda žere kačenky. Taková kočka se pohybuje 4x tak rychle než kačenka plave po hladině. Nalezněte způsob, jakým může kačenka vyváznout. O strategii kočky však nemůžete činit žádné předpoklady.
• Min(10) - Mějte pole A[1..N], které již máte načtené do paměti. Vymyslete algoritmus, který vám pro pole vrátí pozici jeho lokálního minima. Lokální minimum je prvek k, který splňuje A[k-1]>=A[k]<=A[k+1]. Pro jednoduchost předpokládejte, že A[0]=A[N+1]=nekonečno. Problém však je, že vás algoritmus musí být rychlejší než O(N), tedy nemůžete procházet jednu položku pole po druhé.
• Divs(20) - Na cvičení jsme si ukazovali algoritmus Erathostenovo síto, který pro každé číslo zjistí, zda je prvočíslo, či nikoliv. Upravte tento algoritmus se zachováním původní časové složitosti O(N log log N) tak, aby spočítal, kolik má číslo různých dělitelů. Například číslo 8 má 4 různé dělitele: 1,2,4 a 8, číslo 12 má 6 různých dělitelů: 1,2,3,4,6 a 12.
• COCI - Chorvatská online soutěž (Crotian Open Competition in Informatics), pokud se zúčastníte, máte možnost získat body na zápočet, konkrétně získáte třetinu bodů ze soutěže. Každé kolo se koná přibližně jednou za měsíc, časový limit na vyřešení úloh jsou tři hodiny. Správnost a počet získaných bodů se dozvíte po ukončení soutěže. Bližší informace naleznete na adrese: http://hsin.hr/coci.
• Drak(5+10) - Rytíř při své výpravě zabloudil do dračí jeskyně, ve které, jak už to v pohádkách bývá, žil drak, který nikdy nespí. Kdo zkoušel hodně dlouho nespat, ten určitě ví, že při tom pořádně vyhládne. A navíc rytíři jsou drakova oblíbená pochoutka. Rozhodl se mu však dát šanci a nechat ho vyváznout. Vybral si jednou číslo od 0 do N-1 a rytíř ho má uhodnout, pokud se mu to však nepodaří dost rychle, tak drak ho sní. Rytíř může klást drakovi otázky, zda číslo leží v nějaké množině (třeba jestli je sudé nebo jestli je větší než pět). Na základě minimálního počtu položených otázek se má dobrat ke správné odpovědi. Všechno má jeden veliký háček: drak považuje za férové nejvýše jednou během odpovídání zalhat. Pokud bude vaše řešení fungovat i pro lhací variantu, dostanete celých 15 bodů. Například pro N=1000000 vystačí rytíři pouze 26 otázek.
• Cykly(10) - Dostanete na vstupu ukazatel na první prvek spojáku. Máte v lineárním čase vůči jeho délce (kterou však neznáte) rozhodnout, zda je či není zacyklený. Navíc můžete využít pouze konstantně mnoho paměti a spoják nemůžete jakkoliv modifikovat.

Co jsme dělali na cvičeních

• 06.10.2008 - řešili jsme všemožné logické úlohy. Různé varianty nim (ňamu), lámání čokolády, zkoumali mosty v Královci a zabývali se piškvorkami.