Cvičení NPRG031 ve čtvrtek

Cvičení se odehrává 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 a později v C#.

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

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.
Úspěšné absolvování zápočtové písemky na základní znalosti algoritmů.
Úspěšné absolvování zápočtové písemky u počítače v jazyku C#.
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 března 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ý jazyk je C#, avšak je možné psát i v 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.

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í.

POZOR! - na cvicení 7.5. budeme psát teoretickou zápočtovou písemku.

Seznam teoretických úkolů

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

Halda(10) - napište implementaci haldy v poli spolu s základními operacemi vložení nového prvku, vrácení minima a odebrání minima (nebo i jiného prvku daného indexu).
Stok(10) - mějme orientovaný graf popsaný matici sousednosti, kterou již máte načtenou v paměti. Stok je vrchol, do kterého vede hrana ze všech ostatních vrcholů grafu, ale z něj žádná hrana nevede. Dokážete ho nalézt rychleji než v čase O(N²).
Rekon(5+5) - mějme prefixový a infixový zápis binárního stromu, dokážete z něj zrekonstruovat postfixový zápis? Plný počet bodů dostanete za optimální řešení v čase O(N).
Řeka1(5) - na břehu řeky stál muž spolu s celým svým majetkem: psem, kozou a hlávkou zelím. Rád by všechen majetek přepravil na druhou stranu, avšak do loďky s sebou vždy může vzít jenom jednu jedinou věc. Navíc pokud nechá kozu bez dozoru se zelím, tak mu ho sní. A podobně pokud nechá psa bez dozoru u kozy, tak už kozu mít nebude. Existuje způsob, jak může vše v pořádku přepravit?
Řeka2(5) - podobně jako v předchozí úloze, na břehu jezera byli tři žárlivý manželé spolu se svými manželkami. Do loďky se opět vejdou nejvíce dvě osoby, navíc žádný muž nepřipustí, aby ho jeho manželka opustila, pokud by s ní byl ještě nějaký jiný muž. Můžou se všichni přepravit na druhou stranu.
Důl(10) - máme tři doly, které je potřeba zásobovat jídlem. Jídla jsou tři druhy: chléb, maso a ryby. Jednou za časovou jednotku obdržíme nějaký druh jídla a musíme ho poslat do některého z dolů. Horníci v dolech si pamatují, jaké dva druhy potravin jedli naposledy. Pokud jsou různé, potom vyprodukují 2 jednotky, pokud naopak jsou stejné, vyprodukují jen jednu jednotku. Nalezněte, kolik maximálně můžeme vyprodukovat jídla, když budeme potraviny vhodně rozdělovat.
Jezero(20) - jezero si můžeme představit jako kruh, na jehož kraji jsou vybudována města. Města spolu obchodují a mezi určitými dvojicemi měst jsou vybudovány povolené trasy (úsečky mezi městy). Rádi bychom nalezli cestu, která začíná v jednom městě a postupně projde všechna ostatní, používá pouze povolené trasy a navíc sama sebe nikde nekříží.
BST(10) - napište implementaci binárního vyhledávacího stromu se základními operaci vkládání, hledání, mazaní a výpisu setříděné posloupnosti. Nevyžaduje se vyvážování.
Jeřáb(15) - matematický jeřáb si můžeme představit jako sadu kloubů, které jsou postupně propojeny rameny jeřábů (prostě jako skládací metr). S jeřábem postupně provádíme operace otočení některého kloubu o určitý úhel. Rádi bychom po každé operaci popsali polohu konce jeřábu a to pokud možno bez toho, abychom pořád přepočítávali pozici všech kloubů.

Co jsme dělali na cvičeních

26.02.2009 - Procházení do šířky a do hloubky, aplikace na úlohách s šachovnicemi a grafy. Rozšiřování stavového prostoru: Theseus a Minotaurus.
05.03.2009 - Aplikace rozděl a panuj, hledání nejdalší cesty v stromě, centrum grafu, pokrývání stromů a komprimace obrázku rekurzivním algoritmem.
12.03.2009 - Řešení dalších úloh se stromy.
19.03.2009 - Dijkstrův a Floyd-Warshallův algoritmus na hledání nejkratší cesty a jejich aplikace na řešení úloh: nejpravděpodobnější cesta, nejdalší cyklus, nejkratší sled mezi dvěma vrcholy.
26.03.2009 - Praktická hodina s programováním v C#.
02.04.2009 - Procvičování diskrétní simulace.
09.04.2009 - Převody výrazů na stromy, prefixové a postfixové tvary, vyhodnocování výrazů, rekonstrukce postfixového zápisu z prefixového a infixového.
23.04.2009 - Řešení úloh pomocí dynamického programování, úloha s demonstracemi v New Yorku, se sjižděním svahu a se získávání autogramů.
30.04.2009 - Binární vyhledávací stromy a jejich aplikace: úlohy s posloupnostmi a úloha s jeřábem. Navíc jsme se zabývali vyvažováním vyhledávacích stromů a rozebrali optimálnost AVL stromů a červeno-černých stromů.