PRG030 - cvičení 1. ročník informatika
skupina 42 ZS 2009/10 - čtvrtek 14:00 S7/SW2

důležité : zaregistrujte se co nejdříve v systému Codex

1. cvičení 1.října - S7
2. cvičení 8.října - SW2
3. cvičení 15.října - S7
4. cvičení 22.října - SW2
5. cvičení 29.října - S7
6. cvičení 5.listopadu - SW2
7. cvičení 12.listopadu - S7
8. cvičení 19.listopadu - SW2
9. cvičení 26.listopadu - S7
10. cvičení 3.prosince - SW2

Obsah cvičení

1. cvičení S7 1.října
   • Kdo jsme a odkud jsme přišli, co jsme tam zažili
   • Hledání největšího prvku z N prvků, včetně důkazu, že nejde rychleji
   • Hledání druhého největšího prvku z 8 prvků
     obecně z N prvků - vzorec pro počet porovnání
   • Najděte pro zadané startovní pole cestu věže, která projde přes každé pole právě jednou resp. takovou, která je "uzavřená" (skončí na sousedním políčku stratovního pole).
     • pro šachovnici 8 x 8
     • na šachovnici bez rohového pole a1
   • Písemný domácí úkol (přineste tak, abyste to mohli odevzdat):
     Najděte prostředního z pěti na co nejmenší počet porovnání.
     Stejně důležitá jako snaha o minimalizaci počtu porovnání je snaha najít stručný a výstižný popis algoritmu.
   • Rozmyslete si ( a řešení si napište tak, abyste ho byli schopni jednoduše a srozumitelně vysvětlit ostatním)
     1. Řešte obě úlohy cesty věže na šachovnici bez dvou protilelehlých rohových polí (např. a1 a h8)
     2. Minimalizujte počet cest nahoru a dolů elektřikáře, který má za úkol spárovat dolní a horní konce žil kabelu s n žílami (popište algoritmus elektřikáře a vyjádřete nutný počet cest jako funkci počtu žil). Řešte např. pro n=27, ale raději obecně.
     3. Na políčcích pásky sudé délky jsou napsána nějaká kladná čísla. Dva hráči se střídají ve hře. Hráč na tahu si může vybrat, které z krajních políček pásky si ustřihne. Po skončení hry vyhrál ten z hráčů, kterému se podařilo ustříhat políčka s větším součtem.
        Nalezněte jednoduchou neprohrávající strategii pro hráče, který začíná.
     4. Vězni, žalářníci a lampa
        Ve vězení je N vězňů odsouzených na doživotí a každý z nich má svou vlastní celu bez oken. Každý den je jeden z vězňů odveden do speciální místnosti, kde je vyslýchán. V této místnosti je na stropě žárovka a na zdi vypínač. Před prvním výslechem je žárovka zhasnutá. Během výslechu může vězeň žárovku pomocí vypínače libovolně rozsvěcet a zhasínat. Když další den přivedou do místnosti dalšího vězně na výslech, tak je žárovka v takovém stavu (rozsvícená nebo zhasnutá), v jakém ji nechal předchozí vězeň. Vězni jsou vyslýcháni v libovolném pořadí a každý z vězňů může být vyslechnut i vícekrát – pokud by výslechy probíhaly po nekonečně mnoho dní, tak by byl každý z vězňů vyslechnut nekonečně mnohokrát. Od určitého okamžiku tedy určitě nastane stav, že každý z vězňů byl vyslechnut alespoň jednou. Pokud pak kdykoliv potom kterýkoliv z vězňů během výslechu řekne: „nyní jsme byli všichni vyslechnuti alespoň jednou“, tak budou všichni vězni propuštěni. Pokud někdo tuto větu řekne dříve než je to pravda, tak budou všichni vězni popraveni. Před začátkem výslechů se vězni mohou půl hodiny společně procházet po vězeňském dvoře a domluvit si strategii, jak rozsvěcet a zhasínat žárovku a kdy má někdo pronést propouštěcí formuli. Vaším úkolem je pro vězně tuto strategii vymyslet. K výslechům mohou vězně vodit zcela libovolně, jediným pravidlem, které vyšetřovatelé musí dodržet je, že v libovolném okamžiku musí platit:
        " Každý vězeň bude ještě v budoucnu vyslechnut, pokud celý proces neskončí popravou či propuštěním vězňů"
     5. Mladík se uchází o princeznu. Získá ji, pokud uspěje v následující zkoušce.
        Mladíka postaví se zavázanýma očima před otáčecí čtvercový stůl, v jehož rozích stojí 4 sklenice. Každá sklenice může být v jedné ze dvou poloh - dnem vzhůru a dnem dolů. Mladík může v každém kole šáhnout na kterékoli dvě sklenice a podle své vůle případně změnit polohu některých z nich. Účelem je, aby všechny 4 sklenice byly ve stejné poloze. Pokud se to stane - princezna mu to oznámí, on v zkoušce obstál a mohou se chystat zásnuby. Pokud princezna neoznámí úspěch, hra pokračuje dalším kolem. Před tím však sluha stolkem otočí (mladík neví jak).
2. cvičení SW2 8.října
   • řešení úlohy 1 - cesty na šachovnici
   • řešení úlohy 3 - páska sudé délky
   • řešení úlohy 4 - vězňové
   • diskuse úlohy 2 o elektrikáři - zůstává na rozmyšlenou
   • diskuse úlohy 5 o princezně
     klíčem k řešení je uvědomit si, že princ má v každém tahu na výběr jen ze dvou možností:
     může šáhnout buď na diagonálu nebo stranu stolku
     řešení úlohy je písemný domácí úkol na příští cvičení
   • Pojem vyhrané a prohrané pozice, jaké vlastnosti mají množiny vyhraných a prohraných pozic. - Rozmyslete si důkladně!
   • Dva kameny
     Dva hráči hrají následující deskovou hru. Hracím plánem je jedna řada tvořená 1000 políčky, pole jsou očíslována zleva doprava přirozenými čísly od 1 do 1000. Na začátku hry na náhodně zvolených dvou různých polích leží hrací kameny. Výchozí situaci hry lze tedy popsat dvojicí různých celých čísel od 1 do 1000. Oba hráči se ve hře pravidelně střídají. Hráč, který je na tahu, zvolí jeden z kamenů a přemístí ho o libovolný počet polí směrem doleva. Musí přitom kámen posunout alespoň o jedno políčko a zároveň svým tahem nesmí přeskočit jiný hrací kámen ani nesmí umístit přesouvaný kámen na již obsazené políčko. (Tah tedy nelze provést s kamenem stojícím na políčku číslo 1 ani s kamenem stojícím na políčku i, je-li políčko číslo i-1 právě obsazené.) Hra končí ve chvíli, kdy už nelze provést žádný tah, tzn. až se dostanou oba hrací kameny na políčka s čísly 1 a 2. Zvítězil ten z hráčů, který svým tahem dosáhl této koncové situace. Určete, jaké pozice jsou vyhrané a jaké prohrané. Úlohu jsme vyřešili.
   • Máme N podezřelých koulí, mezi nimi je nejvýše jedna špatná (tj. lehčí nebo těžší). Pomocí rovnoramenných vah máme na co nejmenší počet vážení zjistit která ze 2*N+1 možností nastala (buď jsou všechny koule správné nebo je jedna z nich špatná a musíme zjistit nejen, která to je, ale i zda je lehčí či těžší než správné koule).
     Ukázali jsme, že úlohu pro N=3 jde řešit na dvě vážení, a dokázali, že pro N=4 nejde vyřešit na dvě vážení.
     Zkuste zjistit s kolika koulemi jde úlohu vyřešit na K vážení (alespoň pro K=3) a naopak na kolik vážení jde vyřešit úlohu s n koulemi.
     Jak se tyto výsledky změní, máme-li kromě podezřelých koulí k dispozici i libolný počet zaručeně správných koulí.
     
   • Úlohy na rozmyšlenou:
     1. Tahání koulí z urny. V urně je na začátku B bílých a C černých koulí. Hra probíhá tak, že vždy vytáhneme z urny dvě koule a vrátíme tam jednu podle těchto pravidel:
        • vytáhneme-li dvě černé, vrátíme bílou,
        u
        • vytáhneme-li dvě bílé, vrátíme bílou,
        • vytáhneme-li dvě koule různé barvy, vrátíme černou.
        Abychom hru mohli hrát, musíme tedy mít k dispozici i dostatečně mnoho bílých koulí mimo urnu. V každém kroku se zmenší počet koulí v urně o jednu. Nakonec tam tedy zbyde jen jedna. Ten, kdo hru hraje, do urny nevidí a neví, kolik jakých koulí v ní je. Dovedli byste předpovědět, koule jaké barvy v urně zbyde jen na základě počtů bílých a černých koulí na začátku?
     2. Kulový blesk
        Jistých N rodin bydlí v bytech, které označíme celými čísly od 1 do N. Rodiny se dohodly provést cyklickou N-směnu bytů (viz též film Kulový blesk). Rodina z bytu číslo 1 chce do bytu číslo 2, rodina z bytu číslo 2 do bytu číslo 3, atd., až rodina z bytu číslo N se bude stěhovat do bytu číslo 1. Výsledné záměny bytů je třeba dosáhnout postupným prováděním dvojsměn. Některé rodiny se tudíž budou během celé akce stěhovat vícekrát. Každá rodina se ale může přestěhovat nejvýše jednou za den. V jednom dni může samozřejmě probíhat souběžně více dvojsměn bytů. Určete, jaký nejmenší počet dní postačí pro dané N k uskutečnění celé zamýšlené akce. Sestavte rozpis, podle něhož je třeba při výměnách bytů postupovat, aby se tohoto minimální počtu dní dosáhlo (tzn. rozpis určující, kdo se který den stěhuje kam).
     3. Věž z cihel
        Máme k dispozici neomezenou zásobu cihel, všechny cihly jsou stejné. Na stůl budeme pokládat cihly na sebe jednu na druhou. Každá cihla musí ležet na cihle předchozí, může ji ovšem částečně přesahovat do strany. Není však povoleno umístit více cihel do stejné výšky nad deskou stolu. Zjistěte, jak nejdále od hrany stolu se se svou stavbou z cihel dokážete dostat.
     4. Zkuste najít jakékoli nové tvrzení o úloze s koulemi
     5. Čtyři kameny
        Stejná úloha jako byla úloha se dvěmi kameny, ale se čtyřmi hracími kameny. Výchozí situace hry je tedy popsána čtveřicí různých celých čísel od 1 do 1000 (čísla políček, na nichž leží kameny). Hra končí ve chvíli, kdy se hrací kameny dostanou na pole s čísly 1, 2, 3 a 4. Úkolem je opět určit, pro které výchozí situace hry si může zajistit výhru začínající hráč, a nalézt vítěznou strategii hry.
     6. stejná hra se třemi kameny
3. cvičení 15.října S7
   • registrujte se v CodExu
   • komentář k domácímu úkolu - třetí z pěti. Jde na šest porovnání, Zkuste takové řešení najít a co nejednodušeji popsat. Na rozmyšlenou na příště
   • úloha o tahání koulí z urny - 1. úloha z minula
     pojem invariantu
   • pokládání mincí na stůl
   • kulový blesk ve dvou dnech
   • věž z cihel
   • Opakování definice vyhrávající a prohrávající pozice - rozmyslete si důkladně.
   • Hra se čtyřmi kameny resp. třemi kameny zůstává
   • Zkuste najít jakékoli nové tvrzení o úloze s koulemi
   • Vážení koulí
     
     • jde na 3 z 12 podezřelými koulemi bez správné
     • odhad pro kolik nejvýše koulí můžeme rozhodnout za k vážení
   • Písemný domácí úkol: Mrkev a petržel
     Máme pole, které má deset záhonů. Na každý záhon můžeme vysadit mrkev, nebo petržel. Kolika způsoby můžeme pole osít, když nesmí růst dva záhony petržele vedle sebe? Pozn: Záhony máme očíslovány (tj zrcadlová řešení se započítávají normálně - 2x).
     Snažte se o co nejrychlejší výpočet toho počtu pro obecný počet záhonů. Pokud umíte programovat, rozmyslete si, jak byste Váš postup naprogramovali.
   • Na rozmyšlenou:
     1. Všechny úlohy, co jsme nedodělali
     2. Provázky
        Mám naolejovaný provázek. Když ho na jednom konci zapálím, bude postupně odhořívat, až za 1 hodinu dohoří na druhý konec (a zhasne). Provázek však není všude stejně široký, a proto ani nehoří stále stejně rychle. Nelze tedy tvrdit, že např. polovina provázku shoří za půl hodiny. Lze splnit následující úkoly ?
        1. mám jeden provázek a potřebuji změřit půl hodiny
        2. mám dva provázky a potřebuji změřit čtvrt hodiny
        Pozn: okamžik, od kdy začínám měření, si mohu zvolit sám
     3. Zkuste najít jakékoli nové tvrzení o úloze s koulemi
     4. hledání stabilního párování - zadání doplním
 
4. cvičení SW2 22.října
   • zaregistrujte se do Codexu, zřiďte si účet v laboratořích na MS !!!
   • Mrkev a petržel, diskuse efektivity
   • Provázky
   • Spočítali jsme, že k vážení nelze úlohu vyřešit pro více než N_k koulí - N_k = (3^k-1)/2 .
     Našli jsme způsob jak, máme-li k dispozici jednu správnou kouli, na tři vážení jde úlohu vyřešit pro N=13.
   • Návod, jak vyřešit úlohu s N_k koulemi na k vážení - rozmyslet
   • Písemný domácí úkol: Prostřední z pěti na 6 porovnání
   • Na vstupu je posloupnost kladných celých čísel, která je ukončena -1 a nulami rozdělena na úseky.
     Hledání největšího prvku z třetího nejdelšího úseku.
     Pokuste se napsat program a zdroják mi pošlete do úterý večer jako přílohu mailu se subjectem "DCV1"
     na první řádek napište v komentáři svoje jméno a číslo kroužku.
   • Rozmyslet:
     1. Všechny úlohy, co jsme nedodělali
     2. Stabilní párování.
        Ve hře je N můžů a N žen, každá žena zadá seznam svých preferencí jednotlivých mužů (všech n), obdobně každá muž.
        Párování je nestabilní, pokud existuje žena Ž a muž M, kteří v něm nejsou spárováni, ale kdyby k sobě utekli, tak si oba (vzhledem ke svým preferekcím) polepší. párování je stabilní, když není nestabilní.
        Najděte postup, jak pro dané preference mužů a žen najít stabilní párování.
        Návod - pánská volenka
     3. Synchonizace konečných automatů
        
   • Zkuste odevzdat libovolnou úlohu v Codexu, pokud se Vám to nepovede, pamatujte si, v čem byl problém. Úlohy tam budou v sobotu.
5. cvičení S7 29.října
   • návod pro úlohu o synchronizaci automatů
   • zjednodušený tvar vstupu a výstupu v Pascalu, read, readln, write, writeln
     čtení čísel
     formátovaný výstup
   • hledání třetího největšího čísla z druhého nejdelšího úseku
   • hledání prostředního výskuty čísla v poli - různá řešení
   • funkce počítající počet inverzí v permutaci
   • Spočtěte úlohy v CodExu
6. cvičení SW2 5.listopadu
   • ukázka proostředí Delphi a jeho ladících prostředků
   • ukázka práce se systémem CodEx
   • typ record a příkaz with
   • Podprogramy a předávání parametrů
   • reprezenace matice
   • procedura, která vymění prvky symetrické podle hlavní diagonály
   • výměna řádků matice obsahujících minimum a maximum
   • řešení úlohy o synchronizaxci automatů
   • Nové úlohy v Codexu
7. cvičení S7 12.listopadu
   • Podprogramy a předávání parametrů
   • komentář k úkolům v Codexu
   • Nalezení následující permutace v lexikografickém uspořádání
   • Pořadové číslo zadané permutace
   • k-tá permutace z čísel 1..N
   • Rozmyslet a napsat:
     • Pořadové číslo zadané permutace
     • k-tá permutace
   • Nové úlohy
   • Rozmyslet:Umocńování s minimálním počtem násobení
8. cvičení SW2 19.listopadu
   • staticky a dynamicky alokované proměnné, ukazatele, new, dispose
   • vypouštění sudých čísel ze seznamu
   • Domácí úkoly:
     Odevzdejte jako ulohy Dcv1 a Dcv2 do Codexu (nebude se překládat ani vyhodnocovat), pokud se nepodaří pošlete v příloze mailu se subjectem "Dcvp"
     1. Uvažujme lineární spojové seznamy v jejichž prvcích se uchovává číslo a frekvence daného čísla (kolikrát se dané číslo na vstupu vyskytlo)
        1. Napište proceduru, která vytvoří rostoucí seznam tohoto typu, ve kterém budou všechna čísla přečtená ze vstupu
        2. Napište proceduru, která vytvoří z přečtených čísel seznam daného typu tak, že vždy naposledy přečtené číslo dá na první místo v seznamu (pokud už tam bylo, z původního místa ho přesune na začátek a zvětší mu frekvenci o 1)
     2. Napsat buď v češtině nebo v programovacím jazyce (s komentáři) algoritmus pro umocńování pomocí minimálního počtu násobení
   • Zopakujte si ukazatele, dynamicky alokované proměnné, lineární seznamy - příště si napíšeme krátkou písemku
   • Podívejte se na binární stromy
   • Nové úlohy v Codexu
9. cvičení SW2 26.listopadu
   1. jsou-li P a R ukazatele (téhož typu), je posloupnost příkazů
      new(P); P:=R
      nesmysl.
   2. procedura, která vypisuje všechny listy binárního stromu od leva do prava
   3. procedura vypisující hodnotu všech uzlů stromu "po hladinách"
   4. fronta a zásobník
   5. průchod do šířky a do hloubky
   6. průchod do šířy a do hloubky se liší jen volbou pomocné datové struktury
      je-li to zásobník, jde o průchod do hloubky,
      je-li to fronta, jde o průcod do šířky
   7. úloha 3) je vlastně průchod stromem do šířky, pošlete řešení jako úlohu Dcv3 v Codexu (stačí napsat globální definice typů a příslušnou proceduru)
   8. krátká písemka (pokud víte, že jste některý příklad nestačili resp. máte-li ji špatně, pošlete správné řešení jako přílohu mailu s předmětem "PIS", na první řádek této přílohy napište své jméno
   9. zůstává domácí úloha:
      Napsat buď v češtině nebo v programovacím jazyce (s komentáři) algoritmus pro umocńování pomocí minimálního počtu násobení
      pokud jste neposlali, pošlete mailem s předmětem "UMOC"
   10. Podívejte se na rekurzi
   11. Dožeňte úlohy v CodExu, udělám během weekendu "amnestii" - prodloužení termínů
10. cvičení S7 3. prosince.
    • umocňování na nejmenší počet násobení, rekursivní zápis algoritmu
    • Rekurse
    • Generování všech rozkladů čísla na menší sčítance
    • generování všech úspěšných front před kinem
    • Rozmyslet úlohu o nezávislosti N dam na šachovnici N x N.
    • Obecné schéma implementace algoritmu backtrackingu pomocí rekursivní procedury