PRG030 ZS 2007/8 cviceni X32

PRG030 - cvičení 1. ročník informatika
skupina X32 ZS 2007/8 - úterý 12:20 S7/SW2

důležité : zaregistrujte se v systému Codex

Docházka

Obsah cvičení a úkoly

cvičení 2.října - S7
cvičení 9.října - SW2
cvičení 16.října - S7
cvičení 23.října - SW2
cvičení 30.října - S7
cvičení 6.listopadu - SW2
cvičení 13.listopadu - S7
cvičení 20.listopadu - SW2
cvičení 27.listopadu - S7
cvičení 4.prosince - SW2
cvičení 11.prosince - S7
cvičení 18.prosince - SW2
cvičení 8.ledna - S7

Obsah cvičení

cvičení S7 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ů
  z N prvků - viz úloha na rozmyšlenou
- Pět největších z davu.
- Lámání čokolády
- Cesty věže po šachovnici 8 x 8. Viz úlohy na rozmyšlenou
- Na rozmyšlenou:
  1. Napište vzorec, který udává počet porovnání nutných k nalezení 2. největšího z n prvků
    těžší: případně dokažte, že na méně vážení již to nejde.
  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. 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)
  4. 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. Najděte jednoduchou neprohrávající strateii pro hráče na tahu.
  5. Najděte algoritmus, který pro libovolné vstupní preference N mužů a N žen nalezne stabilní párování (párování je stabilní jestliže v něm neexistuje nesezdaná dvojice, která kdyby se sezdala oba její členové by na tom - podle svých preferencí vydělali).
  6. 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ů.
  7. Ř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ů

cvičení SW2 9.října
- Vzorec, který udává počet porovnání nutných k nalezení 2. největšího z n prvků
- Minimalizace cest elektrikáře
- Jednoduchá neprohrávající strategie pro hráče na tahu pro stříhání pásky sudé délky.
- Problém stabilního párování a jeho řešení algoritmem pánské volenky.
  Důkaz toho, že pánská volenka vytvoří stabilní párování, které je mezi všemi stabilními párováními "optimální pro muže".
- Řešení základní úlohy o velbloudovi
- Na rozmyšlenou:
  1. 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).
  2. 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, 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. zůstává úloha 3 z minula
  4. zůstává obecné řešení úlohy o velbloudovi
  5. 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
- 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 pondělí 10:00 ráno se subjectem PRG030dcv1

cvičení S7 16.října

Informace o systému CodEx a výzva, aby se všichni zaregistrovali
Třetí z pěti, komentář k domácímu úkolu
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.
- 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,
spočítalijsme, ž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:
1. Zůstávají úlohy 1-5 (tj. všechny - zamyslete se nad sebou) z minula
2. Hra se třemi kameny
3. Hra se čtyřmi kameny
4. Dva hráči pokládají na stůl střídavě mince stejného typu. Minci lze položit jen je-li na ni na stole volné místo (každá mince musí ležet na stole, na na jiné minci). Prohrává ten, kdo již není schopen další minci položit. Zjištete pro koho je hra, která začíná s prázdným stolem, vyhraná (jak to závisí na rozměrech stlu a mincí?).
5. Zjistěte pro kolik koulí dovedete úlohu vyřešit na tři vážení
6. 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
7. 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.
8. Zamyslete se nad úlohou, třeba přijdete na další zajímavá trvzení o vážení

cvičení SW2 23.října
Dohodli jsme konzulaci o práci v prostředí Borland Pascalu - tento čtvrtek (25.10.) od 16:30 v mé pracovně (MS II.patro vlevo od schodiště)
- Synchronizace automatů - Generál, Vojáci a Zadák
- Pokládání mincí na stůl
- Hry se třemi a čyřmi kameny
- Vězni a žárovka
- 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)
- Na rozmyšlenou zůstávají:
  1. Všechny problémy o vážení - podívejte se všichni
  2. Obecné řešení úlohy o velbloudovi
  3. Chlapec, princezna a otočný stůl
  4. Cesty věží po šachovnicích s ukradenými políčky
- Nové úlohy na rozmyšlenou:
  1. Nalezení maximálního jedničkového obdélníka v zadaném obdélníku o rozměrech m krát n
    nalezněte řešení, které je asymptoticky lepší než m³ * n³
  2. Jak daleko od hrany stolu se může dostat věž, v jejíž každé vrstvě je jedna cihla
- Domácí úlohy v CodExu - budou zveřejněny do 24.10. večer, odeslat nutno do 29.10. 16:00 hod.
  1. Rozklad na prvočinitele
  2. Druhou se mi nepodařilo do systému dostat - pokud se tam objeví, bude nepovinná

cvičení 30.října - S7
- Opakování definic o asymptotické složitosti
- Chlapec, princezna a otočný stůl
- Cesty věží po šachovnicích s ukradenými políčky
- Koncepce programu, který k zadanému poli A číslu X nalezne index prostředního výskytu prvku X v poli A
- 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í
- Na rozmyšlenou zůstávají:
  1. Další tvrzení o problému vážení - podívejte se všichni
    např.
    1. Jde úlohu pro N_k koulí vyřešit na k vážení?
    2. Pro kolik koulí umím úlohu vyřešit na k vážení bez správných koulí( nebo alespoň pro k=3)?
    3. Kolik správných koulí potřebuji pro optimální výsledek na k vážení?
    4. další otázky
  2. Obecné řešení úlohy o velbloudovi
  3. Nalezení maximálního jedničkového obdélníka v zadaném obdélníku o rozměrech m krát n
    nalezněte řešení, které je asymptoticky lepší než m³ * n³ - podívejte se na to všichni
  4. Jak daleko od hrany stolu se může dostat věž, v jejíž každé vrstvě je jedna cihla
- Nové úlohy na rozmyšlenou:
  1. Na zahadě 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é.
    Odhadněte asymptotickou složitost Vašeho algoritmu pošlete mi buď mailem
    (s předmětem PRG030dcv2 a řešením v přiloženem souboru, který bude mít jako jméno Vaše příjmení, např. Novak.doc nebo Novak.txt)
    nebo jako komentář v programu, který pošlete do systému CodEx
  2. Najděte co nejefektivnější algoritmus pro nalezení nejdelší vybrané rostoucí posloupnosti ze zadané posloupnosti
- Domácí úlohy v CodExu - budou zveřejněny do 31.10. večer, odeslat nutno do 3.11. 16:00 hod.
  1. Počet různých možností osevu N záhonů
  2. Nalezení prostředního výskytu prvku X v poli A

cvičení 6.listopadu - SW2
- Komentář k domácím úkolům
- Mrkev a petržel
- Prostřední výskyt
- Jak daleko od hrany stolu se může dostat věž, v jejíž každé vrstvě je jedna cihla
- Maximální jedničkový obdélník v čase m*n²
- 12 koulí na 3 vážení bez správné koule
- On line práce s překladačem Borland Pascalu a systémem CodEx - úloha Frekvence minima a maxima
- Písemný domácí úkol: "obecné řešení problému s velbloudem
  pošlete nejpozději do pondělí 12.11. v 16:00 mailem s předmětem PRG030dcv3 a řešením v přiloženem souboru,
  který bude mít jako jméno Vaše příjmení, např. Novak.doc nebo Novak.txt)
- Domácí úlohy v CodExu - na cvičení 20. listopadu, odeslat nutno do 18.11. 16:00 hod.
  1. Hledání max jedničkového obdélníka bude zadanána do 13.listopadu
  2. Palety - zadáni je v CodExu
- Na rozmyšlenou zůstávají:
  1. Další tvrzení o problému vážení - podívejte se všichni
    např.
    1. Jde úlohu pro N_k koulí vyřešit na k vážení?
    2. Pro kolik koulí umím úlohu vyřešit na k vážení bez správných koulí?
    3. Kolik správných koulí potřebuji pro optimální výsledek na k vážení?
    4. další otázky
  2. Najděte co nejefektivnější algoritmus pro nalezení nejdelší vybrané rostoucí posloupnosti ze zadané posloupnosti
- Nové úlohy na rozmyšlenou:
  1. 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í?
  2. Piráti
    Pět pirátů si dělí poklad 100 zlaťáků. A to tak, ze vždy nejstarší navrhne rozdělení mezi ně a ostatní o něm hlasují.
    Když je většina pro, tak se zlaťáky tak rozdělí a je konec. Jestliže je alespoň polovina proti,
    tak nejstaršího popraví a obdobným způsobem pokračují v dělení. Každý z pirátů se snaží s klesající prioritou
    1) přežít 2) získat co nejvíc zlaťáků 3) zabít co nejvíc kolegů. Jak bys zlaťáky rozdělil, kdybys byl nejstarší ?

cvičení 13.listopadu - S7
- Příklad jednoduché rekursivní procedury, která si alokuje vlastní paměť
- Výpočet kombinačního čísla s prevencí přetečení - proč není dobré volat funkci faktoriál.
- Vyhodnocení částečného součtu konrétní řady - jak počítat vzorečky
- Jednoduchá písemka
  předběžné výsledky ukazují, že všichni si potřebují zopakovat vše, co z jazyka bylo na přednášce, tak, aby jim to buď bylo jasné nebo věděli, na co se potřebují zeptat.
- Na rozmyšlenou zůstává vše z minulých cvičení
  zvláště důležité je hledání max. rostoucí vybrané posloupnosti
- Přibývá další úkol v CodExu: Hledání všech různých rozkladů zadaného čísla na součty menších sčítanců

cvičení 20.listopadu - SW2
- Komentáře k písemkám
- Opakování predávání parametrů hodnotou a referencí
- Testování správně uzávorkovaných řetězců z jednoho typu závorek a plevelných znaků
- Testování správně uzávorkovaných řetězců ze závorek více typů a plevelných znaků
- Nalezení následující (v lexikografickém uspořádání) permutace k zadané permutaci
- Kolikátá je zadaná permutace v lexikografickém uspořádání permutací?
- Která permutace je na k-tém místě v lexikografickém uspořádání permutací?
- Písemný domácí úkol:(pošlete mi nejpozději do pondělí 26.11. v 16:00 mailem s předmětem PRG030dcv4 a řešením v přiloženém souboru, který bude mít jako jméno Vaše příjmení, např. Novak.doc nebo Novak.txt)
  Program pracující s permutacemi obsahující alespoň jeden podprogram řešící některou z třech úloh o permutacích, které jsme na cvičení probírali. Posílejte jen programy, které jste odladili. Na první řádku napište komentář s vaším jménem.
- Codex: Palety
- zústavají ostatní věci na rozmyšlenou
- Podívejte se na to, co bylo/bude na přednášce o práci s ukazateli (pointry)

cvičení 27.listopadu - S7
- O zápočtech, domácích úkolech, a jiných otázkách
- Několik poznámek k práci s ukazateli
- vkládání prvku do neklesajícího jednosměrného seznamu ukončeného nilem
- Písemný domácí úkol: (pošlete mi nejpozději do pondělí 26.11. v 9:00 mailem s předmětem PRG030dcv5 a řešením v přiloženém souboru, který bude mít jako jméno Vaše příjmení, např. Novak.doc nebo Novak.txt), na první řádku napište komentář s vaším jménem.
  Sestavte poprogramy realizující destruktivní a nedestruktivní slévání dvou rostoucích seznamů.
  Destruktivní varianta sestaví slitý seznam (přímo) z prvků slévaných seznamů, nedestruktivní ponechá původní seznamy beze změny a vytoří zcela nový seznam sestávající se z prvků jejich sjednocení
- Na rozmyšlenou:
  1. pánská volenka - nejsilnější muž si vezme nejbohatší mladší nezadanou ženu,
    zvažte jaká uspořádání "vstupujících" seznamů mužů a žen by byla výhodná
  2. Řídká matice je reprezentována jako seznam čtveřic (č.řádku, č.sloupce, nenulový_prvek, další_čtveřice)
    uspořádaný podle čísel řádek (a uvniř jedné řádky podle čísla sloupce). Seznam může případně mít hlavu.
    Rozmyslete dva algoritmy nad touto reprezentací řídkých matic:
    - transpozice matice
    - násobení matic
- Programolam - až budete myslet, že s ukazateli umíte pracovat:
  vyřazení zkažené konzervy (konzerva má čtyři pointry na své sousedy), jde o elegantní řešení.

cvičení 4.prosince - SW2
- programátorský duathlon
  1. písemka na práci se seznamy - pánská volenka
  2. Codex: Počet dní
- Pokud víte, že jste písemku neměli dobře, pošlete mi správné řešení mailem (pošlete mi nejpozději do pondělí 10.12. v 9:00 mailem s předmětem PRG030dcv6 a řešením v přiloženém souboru, který bude mít jako jméno Vaše příjmení, např. Novak.doc nebo Novak.txt), na první řádku napište komentář s vaším jménem.
- Pokud se Vám nepodařilo na cvičení dokončit řešení úlohy Počet dní, vyřešte ji do úterý 11.12. do 9:00.
- Codex na 11. prosince úloha Římská kalkulačka, vyřešte ji do úterý 11.12. do 9:00.

cvičení 11.prosince - S7
- První nabídka témat zápočtových úloh
- rozklad čísla na součty menších sčítanců
  rekursivní a nerekursivní řešení
- fronta před kinem
- Vyřešte nejpozději do 18.12. v 9:00 hod alespoň dvě ze tří nových úloh v CodExu:
  - cenzura
  - Golombovo pravítko
  - Hra s kameny
- Na rozmyšlenou (přibližte se co nejvíc programu)
  1. Vstupem je počet nádob, velikost (v) každé z nich a počáteční počet litrů (r) rumu v ní.
    Tahem z i do j rozumíme přelití min( v_j - r_j , r_i) litrů rumu z nádoby i do nádoby j.
    Vytvořte podprogram, který k zadanému číslu X zjistí, zda jde naměřit X litrů nebo ne
    a pokud ano určí jednu z možností, jak to jde udělat na co nejmenší počet tahů.
    Naměřením X litrů rozumíme situaci, kdy v nějaké podmnožině nádob je dohromady přesně X litrů rumu.
  2. Je dána pevně posloupnost čísel x₁, x₂, ..., x_n. Napište podprogram, který pro zadané číslo Y vypíše všechny výrazy, které vzniknou tím, že mezi čísla zadané posloupnosti vložíme jedno ze znamének ( +, -, *, /, % ) tak, že hodnota výrazu je rovna Y.
    Zanedbáváme priority operací a vyčíslujeme zleva doprava. Oprace % znamená slití, např. 571 % 80 je 57180.
- Nejpozději do konce výuky si každý vybere téma pro zápočtovou úlohu (do 15.12. bude zde seznam témat - vlastní nápady však jsou vítány), nejpozději do 5. ledna mi pošlete mailem specifikaci.

cvičení 18.prosince - SW2

samoseorganizující seznamy
otáčení seznamu
...

domluvili jsme si konzultace na pátek 4.ledna od 14:00 do 18:00,
budu ve své pracovně - pokud by to bylo potřeba přestěhujeme se někam - zanecháme vzkaz na dveřích

Smysl má příjít buď s konkrétními dotazy nebo (a to především) s nějakými úlohami, které jste řešili doma.
Můžete použít např. tyto příklady:

Množina přirozených čísel je repezentována jako cyklický rostoucí seznam s hlavou
(ve které je -1).
1. realizujte destruktivní sjednocení
2. realizujte nedestruktivní sjednocení
Řídká matice je reprezentována jako seznam čtveřic (č.řádku, č.sloupce, nenulový_prvek, další_čtveřice)
uspořádaný podle čísel řádek (a uvniř jedné řádky podle čísla sloupce). Seznam může případně mít hlavu.
- realizujte transpozici matice
- realizujte násobení matic

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

PRG030 - cvičení 1. ročník informatika skupina X32 ZS 2007/8 - úterý 12:20 S7/SW2

Obsah cvičení

PRG030 - cvičení 1. ročník informatika
skupina X32 ZS 2007/8 - úterý 12:20 S7/SW2