PRG030 - cvičení 1. ročník informatika
skupina 42 ZS 2008/9 - středa 12:20 S7/SW2

důležité : zaregistrujte se v systému Codex
Udělování zápočtů
Obsah cvičení a úkoly
1. cvičení 1.října - S7
2. cvičení 8.října - SW2
3. cvičení 22.října - SW2
4. cvičení 29.října - S7
5. cvičení 5.listopadu - SW2
6. cvičení 12.listopadu - S7
7. cvičení 19.listopadu - SW2
8. cvičení 26.listopadu - S7
9. cvičení 3.prosince - SW2
10. cvičení 10.prosince - S7
11. cvičení 17.prosince - SW2
12. cvičení 7.ledna - S7

Obsah cvičení

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í
- Cesty věže po šachovnici 8 x 8. Viz úlohy na rozmyšlenou
- Lámání čokolády
- 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.
- Na rozmyšlenou:
  1. 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)
  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. 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ňů"

cvičení SW2 8.října
- registrujte se v CodExu
- Řešení úlohy o velbloudech, zůstává: napište "vzorečky" pro maximální vzdálenost resp. pro maximální dopravené množství
- 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í strategii pro hráče na tahu.
- Hra se čtyřmi kameny,zůstává: hra se třemi kameny
- Vězni a žárovka
- 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í.
- Na rozmyšlenou:
  1. Zůstává úloha o cestách věže po šachovnici.
  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. Úloha o synchronizaci konečných automatů.
    Synchronizace automatů: Navrhnout konečné automaty G(enerál), Z(adák) a V(oják) tak, 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

cvičení 22.října SW2
- Minimalizace cest elektrikáře - najděte srozumitelnější popis řešení
- Tahání koulí z urny
- Řešení úlohy pro N=12 bez správných koulí na tři vážení
- 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 dvě vážení jde úlohu vyřešit pro N=4.
- Řešení základní úlohy o velbloudovi
- Na rozmyšlenou:
  1. Všechny úlohy, co jsme nedodělali
  2. Chlapec, princezna a otočný stůl
    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).
  3. Jakékoli zatím neznámé tvrzení o úloze s vážením
- zaregistrujte se do Codexu, zřiďte si účet v laboratořích na MS
- Tři domácí úkoly v Codexu
  - Suma - triviální na vyzkoušení práce se systémem
    udělají všichni, o další dvě se všichni pokusí
  - Frekvence minima a maxima
  - Mrkev a petržel

cvičení S7 29.října
- Komentář k odevzdaným úlohám v systému Codex
- Abstraktní model textového souboru v Pascalu,
  pro ukončování řádků používajte výhradně proceduru writeln, pro přechod na další řádek readln
- Práce s textovými soubory:
  Musíme
  1. deklarovat proměnné pro textové soubory např. F,G : text
  2. přiřadit těmto proměnným konkrétní soubory operačního systému pomocí volání procedury assign, např. assign(F,'A.txt');
  3. otevřít vstupní soubor pro čtení reset(F)
  4. otevřit výstupní soubor pro výstup rewrite(G)
  5. příkazy read, readln, eof a.t.d. mají první parametr typu soubor, tedy např. read(F,X)
    není-li uveden, doplní se input - standardní vstup
  6. příkazy write, writeln a.t.d. mají první parametr typu soubor, tedy např. writeln(G,X,Y)
    není-li uveden, doplní se output - standardní výstup
  7. pro jistotu je dobré na konci programu uzavřít výstupní soubor close(G)
- Mrkev a petržel
- Synchronizace automatů
- Princ, princezna a stůl
- 13 koulí s jednou správnou na 3 vážení, důkaz, že bez správné to nejde
- Návod k obecnému tvrzení
- Na rozmyšlenou:
  1. Cokoliv nového o vážení koulí
  2. kulový blesk - stěhování
  3. Cesta věže po šachovnici s jedním ukouslým rohem
  4. elektrikář
- Písemný domácí úkol (buď pošlete mailem nejpozději do úterý 4.11. 9:00 nebo přineste na cvičení):
  Řešte úlohu o velbloudovi 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ů
  Budete-li posílat mailem, pošlete jako textový soubor v příloze mailu s předmětem "INFDCV2" na adresu kryl@ksvi.mff.cuni.cz
- Úlohy v Codexu do úterý 4.11. 20:00 hodin
  1. pokud jste nebyli zatím úspěšní Frekvence minima a maxima
  2. Permutace sloupců matice
  3. Goldbachova kratochvíle

cvičení SW2 5.listopadu
- 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
- Kulový blesk
- Elektrikář
- Písemný domácí úkol:
  Řešení obecné úlohy o vážení (návod na cvičení byl)
- Na příště:
  1. další úlohy v Codexu, pokud jste neudělali některé předchozí, dodělejte je
  2. úloha o nalezení maximálního jedničkového obdélníka v 0/1 obdélníku
  3. zopakujte si a rozmyslete podprogramy a předávání parametrů

cvičení S7 12.listopadu
- Podprogramy a předávání parametrů
- Reálná (zaokrouhlená) čísla a celá (zobrazená přesně) čísla
- Nalezení následující permutace v lexikografickém uspořádání
- Umocńování s minimálním počtem násobení.
- Rozmyslet a napsat:
  - Pořadové číslo zadané permutace
  - k-tá permutace
- Napsat podprogramy pro násobení matic a hledání N-té mocniny matice (s minimálním počtem násobení),
- Nové úlohy v Codexu

cvičení SW2 19.listopadu
- Podprogramy a předávání parametrů
- Reálná (zaokrouhlená) čísla a celá (zobrazená přesně) čísla
- Nalezení následující permutace v lexikografickém uspořádání
- Umocńování s minimálním počtem násobení.
- Rozmyslet a napsat:
  - Pořadové číslo zadané permutace
  - k-tá permutace

cvičení S7 26.listopadu
- Rekurse
- Rozklad čísla na menší sčítance
- dynamicky alokované proměnné a ukazatele
- jednoduché příklady
- Domácí úkol: - pošlete mi jako přílohu mailu s předmětem DcvInf"
  procedura pro otáčení cyklické lineárního seznamu
- Nové úlohy v CodExu - pište i komentáře!!!
- rozmyslet (napsat)
  podpogramy pro destruktivní a nedestruktivní sjednocení dvou množin reprezentovaných jako rostoucí lineární seznamy jejich prvků

cvičení SW2 3. prosince.
- Písemka na rekurzi v CodExu
- Destruktivní a nedestruktivné sjednocení množin reprezentovaných jako rostoucí seznam jejich prvků
  napište na příšte tak, abyste je buď uměli rychle napsat nebo abyste měli na co zeptat"
- Trvá domácí úkol z minula
- Úlohy v CodExu včetně té, která byla v písemce.
- Rozmyslet úlohu o nezávislosti N dam na šachovnici N x N.

cvičení S7 10. prosince.
- Komentář k výsledkům v Codexu
- Nabídka témat zápočtových úloh
  Termíny - rozumí se vždy nejpozději:
  - do Vánoc se domluvit na tématu
  - do 7.1. napsat aposlat e-mailem se subjectem "specInf" specifikaci
  - do 28.února odevzdat první verzi (musí už chodit) programu i dokumentace
  - do 21.3. odevzdat konečnou verzi
- Obraz a vzor množny - domácí úkol poslat mailem se subjectem "Dcv3Inf"
- Dominance dam na šachovnici - poslat hlavní myšlenku řešení
- Vyřazení konzervy - napsat a přinést na příští cvičení

cvičení SW2 17. prosince.
- Písemka v CodExu
- Komentář k úkolům
- nové úlohy v codexu
- Datové struktury k úloze o dominanci
- Stručné opakování pojmů
- Vyřazování konzery
- Zápočtové úlohy

cvičení SW2 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

cvičení 15.ledna - S7
"Zápočtová" písemka na ukazatele

Udělování zápočtů

Připomínám termíny k odevzdávání zápočtových programů - rozumí se vždy nejpozději:
1. do Vánoc se domluvit na tématu
2. do 7.1. napsat aposlat e-mailem se subjectem "specInf" specifikaci
3. do 28.února odevzdat první verzi (musí už chodit) programu i dokumentace
4. do 21.3. odevzdat konečnou verzi
Pokud jste některý z termínů prošvihli, snažte se to co nejrychleji napravit,
Termíny 3) a 4) nelze prodloužit.
Dodatečné úlohy v CodExu musí vyřešit následující tři studenti: Lokaj Alexandr, Sabo Roman, Šípoš Peter.
Do zadaných úloh jsem přidal 6 nových, které mají termín odevzdání 22.2.2009. Do této doby musí každý ze studentů vyřešit libovolné 4 z nich. Vyřešením se rozumí získání všech bodů v CodExu. Je nutné zdrojové texty patřičně okomentovat a nejpozději do konce prvního týdne přednášek přijít na konzultaci (a na ní rozumět daným řešením).
Podmínky z písemných prací nakonec splnili následují studenti. Výsledky obou písemek na pointry shruje následující tabulka
(1=dobře, 1- = skoro dobře, 0 = špatně)

	P1	P2
Drobný Michal	1	1
Dzurenko Martin	1	0
Haas František	1	1
Harasim Jiří	1	1
Hřebejk Tomáš	1	1
Lokaj Alexander	0	1
Novotný Jiří	0	1-
Pecka Martin	1	1-
Petruňa Martin	1	1
Sabo Roman	0	1-
Skalický Jakub	0	1
Šípoš Peter	0	1

PRG030 - cvičení 1. ročník informatika skupina 42 ZS 2008/9 - středa 12:20 S7/SW2

Obsah cvičení

Udělování zápočtů

PRG030 - cvičení 1. ročník informatika
skupina 42 ZS 2008/9 - středa 12:20 S7/SW2