NMIN101 - cvičení 1. ročník matematika
skupina 50 ZS 2014/15 - středa 12:20 K11

Pokyny jak posílat domácí úlohy

Text řešení pošlete jako přílohu/y mailu se subjectem, který je uveden u zadání úlohy.
Soubory, které posíláte jako přílohu pojmenujete svým příjmením plus případně další informací. V každém z těchto souborů uveďte na první řádek svoje jméno a pojmenování úlohy

  1. cvičení 1.října
  2. cvičení 8.října
  3. cvičení 15.října
  4. cvičení 22.října
  5. cvičení 29.října

Obsah cvičení

  1. cvičení 1.října
    • Kdo jsme a odkud jsme přišli
    • 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ů
      rozmyslet:
      obecně z N prvků - vzoreček
      můžete zkusit dokázat, že nejde rychleji (je to těžší)
    • Nalézt cestu věže, která
      • projde přes každé políčko šachovnice právě jednou
      • projde přes každé políčko šachovnice právě jednou a navíc končí na políčku sousedním se startovním políčkem
      obě úlohy pro následující šachovnice
        udělali jsme
      1. obyčejná šachovnice 8x8
      2. šachovnice 8x8 v níž chybí jedno rohové pole
      3. šachovnice 8x8 v níž chybí dvě rohová pole ležící na jedné diagonále
      zbývá k rozmyšlení:
      najít algoritmus pro nalezení cesty na šachovnici 2.
    • Rozmyslet:
      1. 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ňů"
      2. Nalezněte na co nejmenší počet porovnání třetího z pěti.
      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. 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í 8.října
    • Druhého největšího z N jde najít na N-2+ up(log2(N)),
      de up(x) je horní celá část z x tj. nejmenší celé číslo větší nebo rovno x
    • Diskuse některých úloh na rozmyšlení z minula - ty, které jsme nevyřešili, zůstávají na příště
    • Prostřední z 5
    • (Griesova) úloha o tahání koulí z urny - pojem invariantu
    • Lámání čokolády
    • Nové úlohy na rozmyšlenou:
      1. Minimalizujte počet cest nahoru a dolů elektrikář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ě. Elektrikář má k dispozici baterii (zdroj proudu) a žárovku, může spojovat, rozpojovat a popisovat konce žil
      2. Mrkev a petržel
        Na záhony se seje buď mrkev nebo petržel. Jediným omezením je, že nesmějí být dva záhony petržele vedle sebe. Nalezněte kolik je osevních různých plánů pro N záhonů.
        Zamyslete se i nad tím, jak tento výpočet provést co nejrychleji.
      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ď máme na počátku jen podezřelé koule nebo máme na počátku i nějaké správné koule
        Udělali jsme několik speciálních případů,
        zkuste zjistit co nejvíce faktů o tomto problému - buď další speciální případy nebo obecný algoritmus, případně i s důkazem, že lépe to nejde
    • Písemný úkol:(přineste na cvičení, nebo pošlete emailem s subjectem "Dcv1" - viz pokyny, jak posílat domácí úkoly) 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í
  3. cvičení 15.října
    Zřiďte si účet v Karlínských laboratořích a zaregistrujte se do Codexu - příště to již budeme potřebovat!!
    • Diskuse některých úloh na rozmyšlení z minula - ty, které jsme nevyřešili, zůstávají na příště
    • Úloha s vězni
    • 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.
    • Při formulacích tvrzení o hrách dvou hráčů, je výrazně jednodušší je formulovat "pro hráče na tahu" než pro "bílého"
    • "obecná" definice vyhraných a prohraných pozic - rozmyslete důkladně!
    • stříhání z pásky sudé délky
    • úloha o princezně
    • Nové úlohy na rozmyšlení:
      1. Hráči pokládají střídavě stejné mince na obdélníkový stůl. Ten, který už nemůže minci položit, prohrál.
        Najděte vyhrávající strategii pro hráče, který začíná
      2. Č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.
      3. Obdobně tři kameny
        Uvažujete-li o úlohách se 3 resp. 4 kameny, je některé z nich speciálním případem druhé?
      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 i obecně.

      • Písemný úkol:(přineste na cvičení, nebo pošlete emailem s subjectem "Dcv2" - viz pokyny, jak posílat domácí úkoly) Napište jakékoli nové tvrzení o úloze s koulemi
      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ď máme na počátku jen podezřelé koule nebo máme na počátku i nějaké správné koule
      Udělali jsme několik speciálních případů,
      zkuste zjistit co nejvíce faktů o tomto problému - buď další speciální případy nebo obecný algoritmus, případně i s důkazem, že lépe to nejde
  4. cvičení 22.října
    • prostřední z pěti - jeden způsob zápisu řešení
    • mince na stole
    • tři a čtyři kameny - nedořešili jsme zůstává
    • elektrikář - dílší řešení, návod k řešení, ve které počet cest neávisí na počtu žil kabelu - dodělejte!
    • velbloud, pokud máte resp. vymyslíte obecné řešení, pošlete ho mailem
    • prostředí Borland Pascalu, systém Codex
      vyzkoušejte si práci s nimi, odvzdejte nějaké úlohy do Codexu, připravte si dotazy
    • Úlohy, které jsme nedodělali, zůstávají;
      do domácího úkolu připusijte další tvrzení o koulích, na které přijdete - příště vybereme
  5. cvičení 29.října
    • komentáře k odevzdaným úlohám v Codexu
    • úloha Sudá a lichá - všichni povinně odevzdají do Codexu řešení, které neplýtvá zbytečně pamětí
    • vstup čísel
    • formátování výstupu
    • Komentář resp. návod k nově zadaným úlohám v Codexu
    • připravte si dotazy k jazyku, prostředí překladače, systému Codex
    • zůstávají na rozmyšlenou všechny problémy, které jsme dosud nevyřešili
      • Nová úloha k rozmyšlení:
    • 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