PRM044 - cvičení 1. ročník matematika
skupina 53 ZS 2008/9 - čtvrtek 12:20 K11

• důležité : zaregistrujte se v systému Codex
• Obsah cvičení a úkoly
  1. cvičení 2.října
  2. cvičení 9.října
  3. cvičení 16.října
  4. cvičení 23.října
  5. cvičení 30.října
  6. cvičení 6.listopadu
  7. cvičení 13.listopadu
  8. cvičení 20.listopadu
  9. cvičení 27.listopadu
  10. cvičení 4.prosince
  11. cvičení 11.prosince
  12. cvičení 18.prosince
  13. cvičení 8.ledna

Obsah cvičení

1. cvičení 2.ří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ů - vzoreček
   • 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
   • Lámání čokolády
   • Cesty věže po šachovnici 8 x 8.
   • Písemný domácí úkol:
     Popište algoritmus pro hledání prostředního prvku z pěti prvků, který potřebuje pro jeho nalezení co nejmenší počet porovnání.
   • 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. Hra se čtyřmi kameny
     3. Hra se třemi kameny
     4. Najděte pro zadané startovní pole cestu věže, která projde přes každé pole právě jednou resp. takovou "uzavřenou" (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)
     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ě 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ňů"
 
2. cvičení 9.října
   • 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.
     Nalezení jednoduché neprohrávající strategie pro hráče, který začíná.
   • 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).
     Našli jsme způsob jak na dvě vážení jde úlohu vyřešit pro N=3,
     a pro N=9 na tři vážení. Našli jsme způsob jak na dvě vážení jde úlohu vyřešit pro N=4.
   • 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 .
   • Stejná úloha, Kromě podezřelých koulí máme k dispozici i libolný počet zaručeně správných koulí.
   • Nové úlohy na rozmyšlenou:
     1. Zjistěte pro kolik koulí dovedete úlohu vyřešit na tři vážení, zjistěte jakákoli další fakta o dané úloze
     2. Stejná úloha, Kromě podezřelých koulí máme k dispozici i libolný počet zaručeně správných koulí.
     3. Zkuste obě tyto úlohy ř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
     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).
     5. Nalezněte vyhrané a prohrané pozice (pro hráče na tahu) pro hry se třemi a čtyřmi kameny
     6. Synchronizace konečných automatů generál, vojáci, zadák.
     7. Jak daleko od hrany stolu se může dostat věž, v jejíž každé vrstvě je jedna cihla
 
3. cvičení 16.října
   • O systému CodEx - opakovaná výzva k registraci do něj, je třeba si zřídit účet v laboratoři v Karlíně
   • Úloha o vězních
   • elektrikář
   • Na rozmyšlenou zůstává:
     • najít cestu věže ze zadaného startovního políčka na šachovnici s jedním ustřiženým rohem
     • princ a princezna
     • synchronizace konečných automatů- generál, voják, zadák
     • Hra se třemi a čtyřmi kameny - zadání na minulém cvičení
   • Nové úlohy na rozmyšlenou:
     1. 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
     2. 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.
     3. Zamyslete se nad úlohou, třeba přijdete na další zajímavá trvzení o vážení
 
4. cvičení 23.října
   • Komentář k domácímu úkolu
   • Připomenutí, že se máte zaregistrovat do Codexu a zřídit si účet v laboratoři v Karlíně
   • částečné řešení hry se 4 koulemi
   • Tahání koulí z urny
   • Pokládání mincí na stůl
   • 12 koulí bez správné na 3 vážení, 13 koulí na 3 vážení, máme-li jednu správnou
   • Návod pro řešení úlohy o synchronizaci konečných automatů
   • 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ů.
   • Na rozmyšlenou zůstávají všechny nevyřešené úlohy z dřívějška
   • Nové úlohy na rozmyšlenou:
     1. Optimální řešení úlohy o velbloudovi a banánech
     2. Ř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ů
   • Písemný úkol:
     pošlete na můj mail nejpozději v úterý večer s předmětem "Dcv1"
     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.
   • Zkuste vyřešit a odevzdat úlohu Suma v Codexu, abyste alespońe věděli v čem byl problém, pokud to nepůjde, nevadí, vše si ukážeme
5. cvičení 30.října
   • Mrkev a petržel
   • Princezn
   a
   • .....
   • Předvedení prostředí Borland Pascalu,
     nastavení pracovního adresáře (Change Dir), práce s editorem, kontextový help (Ctrl+F1), překlad a spouštění programu, krokování, breakpointy, sledování hodnot proměnných v okně watch, napsání jednoduchého programu
   • Zůstávají všechny úlohy, které jsme nevyřešili
   • Písemný úkol:
     Řešení úlohy s princeznou
     Pošlete na můj mail nejpozději v úterý večer s předmětem "Dcv2"
     rešení pošlete v příloze v souboru (použijte některý z běžných typů (doc, rtf, pdf, txt), který bude mít za jméno Vaše příjmení.
     pokud je to pro vás jednodušší, můžete úkol přinést na papíře na cvičení
   • Úlohy v Codexu
6. cvičení 6.listopadu
   • Velbloud a banány
     písemný domácí úkol (pošlete emailem se subjektem "Dcv3" nebo přineste na cvičení): obecné řešení úlohy
   • Druhý největší z třetího nejdelšího úseku
     kolik proměnných potřebujeme, vytvořit příslušný program - poslat v Codexu (úloha bude k dispozici až v úterý večer)
     kolik proměnných potřebujeme pro nalezení K-tého největšího z m-tého nejdelšího úseku
   • Rozmyslet úlohu "kulový blesk"
   • Udělat co nejvíc programů v CodExu, povinně rozklad čísla na prvočíselné dělitele, který jsme započali na cvičení
7. cvičení 13.listopadu
   • Kulový blesk, řešení za dva dny a jeho geometrická interpretace
   • Permutace, lexikografické uspořádání
   • Nalezení následující permutace v lexikografickém uspořádání
   • Pořadí permutací
     rozmyslete si a napište tak, abyste tomu ještě za měsíc rozuměli - podobná návod byl
     1. Zjistit kolikátá je zadaná permutace
     2. Zjistit permutaci (čísel 1..N), která je v lexikografickém uspořádání na K-tém místě
   • Příklad na počítání součtu prvních N členů mocninné řady
     Domácí úkol (odevzdejte v Codexu jak řešení úlohy fiktřada - bude tam až v pondělí)
   • Jednoduché prográmky pro zacházení s maticemi
   • Nové úlohy v CodExu - jsou již bodovány, pokud možno dodělejte ty, které jste ještě nevyřešili
8. cvičení 20.listopadu
   • ukázkový jednodychý prográmek pro práci s textovými soubory a maticí
     v neděli večer bude příslušná úloha v Codexu i s testovacími daty
   • nové úlohy v Codexu
   • zůstavají všechny věci na rozmyšlení
9. cvičení 27.listopadu
   • jednoduchá "písemka v CodExu
   • Návod k řešení úlohy nejkratší cesta králem
     • algoritmus vlny
     • zpětný chod
     • diskuse (ne)vhodnosti tohoto způsobu vstupu dat
   • Opakování typu recrord
   • Jednoduchá funkce pro zjišťování počtu rostoucích úseků ve vektoru
   • Zůstává vše z dřívějška
   • CodeEx: prodlouženy lhůty k odevzdávání dvou úloh, přidány nové úlohy
     dodatečně jsem obodoval úspěšná řešení z počátku semestru, které neměly přiděleny body
10. cvičení 4.prosince
    • Algoritmy pro kontrolu správného uzávorkování (s jedním nebo více páry závorek)
    • Ukázka práce se složitějšími datovými strukturami
    • Opakování pojmy vyhrávající a prohrávající pozice
    • Komentář zadání některých příkladu z CodExu
    • Šifra Monte Christo
      
      • úloha kontrola mřížek v Codexu
      • rozmyslete si: algoritmus (a jeho implemenaci) šifrování a dešiforvání
    • Dožeňte své dluhy v CodExu - prodloužil jsem termíny
11. cvičení 11.prosince
    • Nabídka témat zápočtových programů.
      
      Termíny:
      • Do Vánoc domluvit si téma
      • Do konce semestru mít schválenu specifikaci, (abyste to stihli, musíte mi ji poslat počátkem prvního týdne výuky v lednu).
      • Do 7.3.2009 odevzdat první verzi zápočtového programu a jeho dokumentace (už musí být v podstatě dobře)
      • Do konce března odstranit závady v programu, případně dovést dokumentaci do přijatelného stavu (to se Vám nemusí podařit na první nebo druhý pokus)
    • Rekursivní procedura pro výpis všech permutací čísel 1..N
    • Komentář k novým úlohám v Codexu
    • Dožeňte své dluhy v CodExu - prodloužil jsem termíny některých úloh
12. cvičení 18.prosince
    • Komentář k úlohám v Codexu, odstavcovač, vyhrané a prohrané pozice
    • Analýza a návrh podprogramů řešících úlohu o testování všech kombinací znamének zda ze zadaných cifer vytvářejí zadané číslo
      do slivestra bude úloha v Codexu - je poviným domácím úkolem
    • Zápočtové úlohy
    • Dožeňte své dluhy v CodExu - prodloužil jsem termíny některých úloh
13. cvičení 8.ledna
    • Písemná práce
    • Pokud jste nesplnili svoje povinnosti ohledně zápočtového programu, rychle to dožeňte
    • Prodloužil jsem termíny úloh v CodExu
14. cvičení 15.ledna
    • Rozbor příkladů z písemné práce
    • Pokud jste nesplnili svoje povinnosti ohledně zápočtového programu, rychle to dožeňte
    • Rekapitulace splnění povinností k zápočtu ze cvičení
    • Dohodnuta mimořádná konzultace v úterý 20.ledna od 15:00 v laboratoři SW1 v přízení budovy na MS