PRM044 - cvičení 1. ročník matematika
skupina 58 ZS 2011/12 - úterý 9:00 K11

1. cvičení 4.října
2. cvičení 11.října
3. cvičení 18.října
4. cvičení 25.října
5. cvičení 1.listopadu
6. cvičení 8.listopadu
7. cvičení 15.listopadu
8. cvičení 22.listopadu
9. cvičení 29.listopadu
10. cvičení 6.prosince
11. cvičení 13.prosince
12. cvičení 20.prosince
13. cvičení 3.ledna

Obsah cvičení

1. cvičení 4.října
   • Kdo jsme a odkud jsme přišli, co zde očekáváme
   • 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ů - vzoreček
     můžete zkusit dokázat, že nejde rychleji (je to těžší)
   • 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
   • Písemný úkol:(přineste na cvičení)
     Najděte prostřední z pěti čísel.
     Snažte se:
     1. o co nejjednodušší zápis algoritmu
     2. o co nejmenší počet porovnání
   • Rozmyslet:
     1. Najděte pro tabulku čokolády o K řádcích a L sloupcích způsob, který ji na co nejmenší počet lámání nakouskuje na K*L kousků o jednom dílku.
     2. 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).
        • na šachovnici bez rohového pole a1
        • na šachovnici bez dvou protilelehlých rohových polí (např. a1 a h8)
     3. 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).
     4. Najděte způsob, jak na co nejmenší počet násobení spočítat N-tou mocninu
     5. Spočítejte počet osevních plánů N záhonů, pro něž platí:
        • na každém záhonu je buď mrkev nebo petržel
        • Na žádných dvou sousedních záhonech nesní být petržel
        Snažte se o efektivní výpočet.
2. cvičení 11.října
   • Ti, kdo nepřinesli úkol, mi ho pošlou nejpozději do čtvrtka 13.října e-mailem. Text úkolu pošlete jako přílohu mailu s předmětem "PRMDCV1" podepište se i v tomto souboru.
   • Cesty po šachovnici. Zbývá nám jen ukázat, že z libovolného bílého políčka šachovnice jíž chybí jeden černý roh vede prostá cesta procházející každým polem právě jednou. Zkuste rozmyslet, je asi technicky náročné, neztrácejte nad tím mnoho času.
   • Lámání čokolády.
   • Mrkev a petržel -rozmyslete si způsob, kterým jsme úlohu vyřešili.
   • 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.
   • Návod pro úlohu s princem
   • Rozmyslet: ¨
     1. Č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.
     2. Obdobně tři kameny
     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. Velbloud má nosnost 1000 banánů a spotřebu 1 banán na 1 km. Na hromadě je 3000 banánů, najděte způsob, jak do co největší vzdálenosti přepravit 1000 banánů.
        Zkuste úlohu řešit obecně.
     5. 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ě krá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ňů"
3. cvičení 18.října
   • pořiďte si účet do laboratoře v Karlíně a přihlaste se do Codexu
   • Velbloud a banány. Pro konkrétní zadání vyřešeno, zkuste řešit obecně (jak daleko lze donést dané množství banánů a jaké množství banánů jde donést do zadané vzdálenost, oboje pro zadanou nosnost a spotřebu velblouda a velikost hromady na startu)
   • Úloha s princeznou
   • Rozmyslet:
     1. vše, co jsme nedodělali
     2. Synchronizace automatů:
        Navrhnout konečné automaty G(enerál), Z(adák) a V(oják) tak, aby libolně dlouhá posloupnost vojáků začínající generálem a končící zadákem dokázala vydat salvu za nějakou dobu po generálově rozkazu.
        Nejde o přesný popis automatů, ale o myšlenku jejich komunikace
     3. 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).
        Uvažujte dvě varianty zadání: bu´d máme na počátku kromě podezřelých koulí i nějaké správné nebo nemáme
     4. 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ě.
     5. 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).
4. cvičení 25.října
   • kulový blesk
   • páska sudé délky
   • Úloha s vězni
   • Návod pro synchronizaci automatů
   • Nová fakta o úloze s koulemi:
     1. Bez správné koule jde vyřešit s 12 koulemi na 3 vážení.
     2. Důkaz toho, že na k vážení můžeme úlohu (i s případně správnými koulemi) nejde vyřešit pro více než N_k = (3^k-1)/2
   • Rozmyslet:
     1. Vše, co jsme neudělali
     2. Důkaz, že pro N_k koulí nelze úlohu vyřešit na k vážení bez správné koule
     3. Najděte algoritmus, který pro N_k koulí vyřeší úlohu na K vážení pokud má k dispozici správné koule, (kolik správných koulí stačí?),
        pokud nepůjde obecně, zkuste alespoň z 13 podezřelých s jednou správnou na 3 vážení.
5. cvičení 1.listopadu
   • Synchromizace automatů pomocí nalezení poloviny řady jako místa, kde se setkají signály vyslané rychlostmi 1 a 1/3
   • Elektrikář
   • Hra se čtyřmi kameny - neuděli jsme
   • Základy práce s prostředím Borland Pascalu,
     pohrajte si s ním (můžete si nainstalovat Free Pascal)
   • Komentář k úlohám v CodExu
   • Zkuste si vyřešit úlohy, které jsou ve Vaší skupině v systému CodEx
     budou-li problémy, nevadí, odevzdejte, co dolážete, zapamatujte si problémy, které jste měli, abyste se mohli zeptat
   • Na rozmyšlenou zůstávají všechny úkoly, které jsme nedodělali
6. cvičení 8.listopadu
7. cvičení 15.listopadu
   • čtyři kameny
   • pokus o obecné řešení úlohy s velbloudem
   • "písemka" v Codexu - inverzní permutace
   • Algoritmická písemka:
     Na stůl tvaru odélníka pokládají dva hráči střídavě mince (všechny jsou stejné). Mince musí ležet celá na stole, nesmí ležet na druhé. Prohraje ten, který už další minci nemůže položit. Je hra pro začínajícího hráče vyhraná nebo prohraná?
   • Domácí úkol: hra NIM Na hromádce je na počátku N sirek. Hráči střídavě odebírají přípustný počet sirek. Hráč, který vezme poslední prohrál.
     Najděte, které počáteční konfigurace jsou vyhrané resp. prohrané pro hráče, který začíná:
     když hráč na tahu smí vzít K sirek
     1. K je jedno z čísel {1,2,3}
     2. K je jedno z čísel {1,3,4}
     3. K je jedno z čísel {1,3,5}
     4. K je libovolné sudé číslo
     5. K je libovolné liché číslo
     Pošlete nejpozději v pondělí 21.11. do 14:00 mailem se subjektem "DCvM1", řešení napište do souboru, který pošlete v příloze, v tomto dokumentu se podepište
8. cvičení 22.listopadu
   • Komentář k úlohám v CodExu
   • Lexikografické uspořádání permutací
   • předávání parametrů
   • Rozmyslete všechny úlohy. které zůstávají nedodělané
9. cvičení 29.listopadu
   • správně uzávorkované výrazy s jedním či více typy závorek - různé algoritmy
   • pojem zásobníku
   • komentář k úlohím v Codexu
   • řešení úlohy s 13 podezřelými koulemi a jednu správnou na tři vážení - zobecněte
   • Rozmyslete všechny úlohy. které zůstávají nedodělané
10. cvičení 6.prosince
    • rozbor několika odevzdaných úloh v Codexu
    • implementace backtrackingu pomocí rekursivnbí procedury - generování správně uzávorkovaných výrazů
11. cvičení 13.prosince
    • témata na zápočtové úlohy
      do Vánoc by se každý měkl domluvit na tématu zápočtové úlohy a nejpozději do 10. ledna odevzdat specifikaci
    • rozbor několika odevzdaných úloh v Codexu
    • písemka v Codexu
12. cvičení 20.prosince
    • témata zápočtových úloh
      s většinou jsme domluveni, abychom předešli nedorozuměním, pošlete mi (pokud možno ještě do Vánoc) mail se subjectem ZAPOCET, který bude obsahovat téma
      pokud bych vám do 30.12. neodpověděl, pošlete znovu se subjectem URGENCE
    • po odsouhlasení tématu mi pošlete specifikaci (subject SPECIFIKACE) nejlépe v prvním týdnu výuky po Vánocích, nejpozději do 10. ledna. Budete-li s tím mít potíže, domluvte si konzultaci.
    • o praktických testech - bude na přednášce, je podrobně na webové straně předmětu
    • příště si napíšeme písemku (na algoritmizaci a jednoduché programování)
    • na zápočet byste měli získat 150 bodů v Codexu - je možné domluvit individuální postup u těch, kteří zaostávají
      má smysl řešit i netriviální úlohy, jejichž termín odevzdání jste nestihli
    • zápočtové úlohy s dokumentací byste měli odevzdat nejpozději do 25.února (nejprve mailem a pak domluvit si individuální předání)
      pokud nebudu spokojen s programem nebo dokumentací, dostanete 2-3 týdny na dodělání
      v žádném případě by se však definitivní odevzdání zápočtového programu nemělo posunout za konec března
    • komenář k úloze nalezení nejkratší cesty šachové figurky na šachovnici
    • komentář k úloze kontrola uzávorkování
    • komentář k úloze
    • algoritmus hledání vyhraných a prohraných pozic pro konkrétní hru
    • rozbor nových úloh v Codexu
13. cvičení 2.ledna
    Minulý zápis jsem neuveřejnil včas. proto se termíny pousouvají

    • témata zápočtových úloh
      s většinou jsme domluveni, abychom předešli nedorozuměním, pošlete mi do í.ledna mail se subjectem ZAPOCET, který bude obsahovat téma
      pokud bych vám do konce 12.1. neodpověděl, pošlete znovu se subjectem URGENCE
    • zápočtové úlohy s dokumentací byste měli odevzdat nejpozději do 25.února (nejprve mailem a pak domluvit si individuální předání)
      pokud nebudu spokojen s programem nebo dokumentací, dostanete 2-3 týdny na dodělání
      v žádném případě by se však definitivní odevzdání zápočtového programu nemělo posunout za konec března
    • rozbor úloh