PRM044 - cvičení 1. ročník matematika
skupina X51 ZS 2007/8 - středa 14:00 K3

• Docházka
• Příklady témat k zápočtovým programům.
  
  Je třeba dohdnout se do Vánoc na tématu a nejpozději do 10. ledna poslat specifikaci.
• Obsah cvičení a úkoly
  1. cvičení 3.října
  2. cvičení 10.října
  3. cvičení 17.října
  4. cvičení 31.října
  5. cvičení 7.listopadu
  6. cvičení 14.listopadu
  7. cvičení 21.listopadu
  8. cvičení 28.listopadu
  9. cvičení 5.prosince
  10. cvičení 12.prosince
  11. cvičení 19.prosince
  12. cvičení 9.ledna

Obsah cvičení

1. cvičení 3.ří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 z N prvků
   • 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.
     Jednoduchá neprohrávající strategie pro hráče na tahu.
   • Lámání čokolády
   • Cesty věže po šachovnici 8 x 8.
   • Na rozmyšlenou:
     1. 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ě.
     2. 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řeporavit 1000 banánů.
     3. Řešte předchozí úlohu obecně. Velbloud má nosnost K a spotřebu s banánů na 1 km, na startu je hromada V banánů.
        • Najděte největší vzdálenost D, do které lze přepravit zadané množství banánů.
        • Najděte způsob, který do zadané vzdálenosti D přepraví co nejvíce baná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í 10.října
   • Základní úloha o velbloudovi
   • Mladík a princezna
   • Hra s kameny
     Hraje hraje na pásce jejíž políčka jsou očíslována zleva od 1 do počtu polí pásky. Na pásce je N kamenů. Hru hrají střídavě dva hráči. V každém tahu si hráč na tahu vybere jeden z kamenů a posune ho nenulový počet políček doleva, při tom však tento kamen nesmí opusit pásku a zůstat vpravo od kamene, který ležící vlevo od něj. Hru prohraje ten, kdo již nemůže provést žádný tah.
     Hra s dvěma kameny
     • Podle pravidel hra končí prohrou hráče na tahu v pozici kamenů (1,2)
     • Nalezli jsme vyhrané a prohrané pozice
   • "Definice" prohrané a vyhrané pozice z hlediska hráče na tahu
   • Tahání koulí z urny
   • 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). Kromě podezřelých koulí máme k dispozici i libolný počet zaručeně správných koulí.
     Našli jsme způsob jak na dvě vážení jde úlohu vyřešit pro N=4.
   • Na rozmyšlenou zůstává:
     1. Úloha 1. z minulého cvičení
     2. Úloha 3. z minulého cvičení
     3. Úloha 4. z minulého cvičení
   • Nové úlohy na rozmyšlenou:
     1. Zjistěte pro kolik koulí dovedete úlohu vyřešit na tři vážení
     2. Zkuste tutéž úlohu řešit obecně:
        
        1. pro kolik koulí dovedete úlohu vyřešit máte-li možnost vážit k krát
        2. kolik potřebujete vážení pro vyřešení úlohy s N podezřelými koulemi
     3. Vězni
        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, 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ňů"
     4. Nalezněte vyhrané a prohrané pozice (pro hráče na tahu) pro hry se třemi a čtyřmi kameny
   • Domácí cvičení:
     Algoritmus pro nalezení třetího z pěti na co nejmenší počet porovnání
     Snažte se o co nejjednodušší formulaci algoritmu + případně důkaz toho, že je optimální
     Pošlete na můj mail do úterý 9:00 ráno se subjectem PRM044dcv1
3. cvičení 16.října
   • O systému CodEx - výzva k registraci do něj
   • Komentář k domácímu úkolu
   • Úloha o vězních
   • Rodina jde tunelem
   • Pokládání mincí na stůl
   • 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). Kromě podezřelých koulí máme k dispozici i libolný počet zaručeně správných koulí.
     Našli jsme způsob, jak na dvě vážení jde úlohu vyřešit pro N=4 a pro N=13 na tři,
     umíme úlohu vyřešit pro N=3 bez správné koule na dvě vážení, dokažte, že pro 4 to bez ní nejde
     spočítali jsme, že máme-li k dispozici k vážení nelze úlohu vyřešit pro více než N_k koulí - N_k = (3^k-1)/2 .
     
   • Na rozmyšlenou zůstává: vše z minula kromě vězňů - zamyslete se nad sebou
   • Nové úlohy na rozmyšlenou:
     1. Hra se třemi a čtyřmi kameny - zadání na minulém cvičení
     2. Jak daleko od hrany stolu se může dostat věž, v jejíž každé vrstvě je jedna cihla
     3. Zkuste úlohu řešit úlohu o vážení obecně:
        
        1. pro kolik koulí dovedete úlohu vyřešit máte-li možnost vážit k krát
        2. kolik potřebujete vážení pro vyřešení úlohy s N podezřelými koulemi
     4. Položte si otázku, jak se tyto výsledky změní když nemáte k dispozici správné koule resp. jich máme jen omezený počet.
     5. Zamyslete se nad úlohou, třeba přijdete na další zajímavá trvzení o vážení
4. cvičení 31.října
   Dohodli jsme hromadnou konzultaci o prostředí překladače Borland Pascal a systému CodEx
   v úterý v 19:00 v laboratoř SW1 v přízemí rotundy budovy na MS
   Ukázali jsme si základy práce v prostředí Borland Pascalu (editor, překlad programu,
   ladící prostředky - breakpointy, krokování výpočtu, sledování hodnot proměnných v okně Watch
   chyby při překladu a běhu programu, práce s nápovědou), odevzdání úloh do systému CodEx
   • Mladík a princezna
   • Elektrikář
   • 13 koulí na 3 vážení
   • Důkaz, že k vyřešení úlohy pro 13 koulí na tři vážení potřebujeme správné koule
     de facto jsme dokázali, že nejde úlohu s N_k koulemi vyřešit na k vážení bez správných koulí
   • Opakování definic o asymptotické složitosti
   • Na rozmyšlenou zůstává: mnoho úloh z dřívějška
   • Nové úlohy na rozmyšlenou:
     1. Na zahradě je N záhonů, na každý z nich je možno vysít buď mrkev nebo petržel. Nikdy však nesmí být dva záhony petržele na sousedních záhonech. Najděte efektivní způsob jak spočítat pro N počet možností, jak lze N záhonů osít - předpokládejte, že N může být hodně velké a tedy probrání všech možností není únosné. Určete asymptoticklou složitost Vašeho výpočtu.
     2. Do dražby jde byt o hodnotě více než 1 milion. Každý, kdo se dražby chce přihlásit musí zaplatiti dražební jistinu, kterou v případě, že byt nevydraží nedostane zpátky. Vítězi dražby se dražební jistina započte do splácení vydrařené částky.
        Když zájemci přišli na dražbu zjistili, že jsou jen dva. Mohou se nějak dohodnout na postupu, aby to bylo pro oba optimální?
5. cvičení 7.listopadu
   • Dražba
   • Jednoduché programy:
     • Rozklad čísla na prvočíselné dělitele
     • Hledání minima a maxima včetně jejich počtu výskytů
     • Součty prvků na lichých a sudých místech posloupnosti
     • Součty lichých a sudých čísel v posloupnosti
6. cvičení 14.listopadu
   • Jednoduché programy:
     • Index prostředního výskytu prvku v poli
     • Hledání maximální rostoucí řásti posloupnosti
     • Hledání prvního výskytu posloupnosti v jiné posloupnosti
     • Kolikrá se vyskytuje jedna posloupnost v druhé
   • Domácí úlohy v CodExu - na 21.11.:
     obě úlohy jsme rozebírali na cvičení, jde tedy o především o procvičení práce s překladačem a systémem CodEx
     • Frekvence minima a maxima
     • index prostředního výskytu
   • Domácí úloha v CodExu - na 28.11.: Mrkev a petržel
7. cvičení 21.listopadu
   • mrkev a petržel
   • Algoritmy pro práci s permutacemi
     1. hledání následující (v lexikografickém uspořádání) permutace k zadané permutaci
     2. kolikátá je zadaná permutace v lexikografickém uspořádání?
     3. Najděte K-tou permutaci z čísel 1 .. N
   • Správně uzávorkované výrazy s jedním typem závorek
   • Správně uzávorkované výrazy s více typy závorek
   • Domácí úkol: programy pro práci s permutacemi, realizující první dva probírané algoritmy (text odladěných programů pošle mailem s předmětem "PRG044dcv2" nejpozdějido úterý 27.11. 16:00 jako přílohu se jměnem jaké je Vaše příjmení - např. Novak1.pas. Ve zdrojovém textu napište na prvnířádek komentář se svým jménem a stručným zadáním úlohy)
     
     1. Na vstupu je na první řádce číslo N udávající délku permutace a na druhém řádku N čísel permutace 1 .. N.
        Na výstup opíšeme na první řádek vstupující permutaci a na druhý řádek následující permutaci,
        (pokud je vstupní posloupnost maximální - t.j. klesající, vytiskněte první permutaci t.j. rostoucí
     2. Vstup druhé úlohy je stejný, výstupem je pořadové číslo zadané permutace v lexikografickém uspořádání
   • Tři zadané dříve zadané úlohy v CodExu
8. cvičení 28.listopadu
   • Úlohy na matice
   • Jednoduchá písemka
9. cvičení 5.prosince
   • Komentář k písemkám
   • rozbor úlohy na zpracování textu:
     Na vstupu je textový soubor F (žádná z jeho řádek není delší než 35 znaků) a string S (délky kratší než 10).
     Na výstupu je každý řádek na výstupu tolikrát, kolikrát je v něm obsažen string S, ale posunut tak, aby tyto výskyty byly pod sebou.
     Například je-li string S= "ABA",
     pak řádek "ABABABAB" vystoupí třikrát a
     řádek "ABBABBA" nevystoupí ani jednou
     Domácí úkol: (text odladěného programu pošlete mailem s předmětem "PRM044dcv3" nejpozději do úterý 4.12. 16:00 jako přílohu se jménem jaké je Vaše příjmení - např. Novak1.pas. Ve zdrojovém textu napište na prvnířádek komentář se svým jménem a stručným zadáním úlohy)
   • Úlohy o práci s kalendářem
     • počet dní mezi dvěma daty - úloha je v Codexu
     • kolikrát bylo mezi dvěma daty "pátek třináctého"
     • přičtení časového intervalu- např. 45 let, 87 měsíců a 9856 dní - k danému datu
     • časový interval jako "rozdíl dvou dat"
   • Povinně alespoň dvě úlohy v Codexu z těchto:
     • Počet dní
     • Goldbachova kratochvíle
     • Byrokratický aparát
     • Cesta králem - délka
10. cvičení 12.prosince
    • Kritika těch (mnoha), kteří neposílají domácí úkoly (písemné resp. v CodExu)
      Vyhlašuji předvánoční amnestii - můžete mi poslat úkoly, které jste neposlali, i dodatečně - nejpozději do 22. prosince. Totéž se týká i úloh v systému CodEx - je u nich prodloužena lhůta dodání do 5.1.2008 je u nich
    • rekursivní řešení generování všech uspokojitelných front
    • generování všech rostoucích posloupností K prvků z prvků 1..N
    • generování všech posloupností K prvků z prvků 1..N
    • Domácí úkol: (text odladěného programu pošlete mailem s předmětem "PRM044dcv4" nejpozději do úterý 18.12. 16:00 jako přílohu se jménem jaké je Vaše příjmení - např. Novak1.pas. Ve zdrojovém textu napište na prvnířádek komentář se svým jménem a stručným zadáním úlohy), případně můžete jako přílohy poslat i výstupy testů programu
      

      Zarovnávání textu "do bloku"
      Vstupem programu je textový soubor a číslo SIR (SIR je větší než 21, kratší než 80). Slovem nazveme takový úsek textu, který je z obou stran oddělen jednou či více mezerami nebo konci řádků. Všechna slova ve vstupním souboru jsou kratší než 10 znaků. Napište program, který obsah vstupního souboru vytiskne se zarovnanými okraji na levé i pravé straně (jako v knize) se řádky širokými SIR (uvažujte neproporcionální font). Dosáhnete toho tím, že mezi slova vložíte vhodný počet mezer (rovnoměrně rozdělený) a změníte rozdělení slov textu do řádků. Na každý řádek výstupního souboru musí vystoupit maximální možný počet slov.

    • Alespoň dvě úlohy ze čtyřech nových v CodExu - jsou otevřeny do 19.12.2007 8:00 hod:
      • Kombinace
      • Počet inversí
      • Přelévání vody
      • Cenzura - ignorujte návod,
        že máte pracovat se souborem file of char a pracujte se standardními textovými soubory typu text
11. cvičení 19.prosince
    písemná práce
    • klouzavé průměry
    • N nejčastěji se vyskytujících slov ve vstupním textovém souboru
12. cvičení 9.ledna