PRg030 ZS 2017/18 cviceni úterý 9:00

cvičení 2.října

Hledání největšího prvku z N prvků pomocí N-1 porovnání, včetně důkazu, že nejde rychleji
můžeme použít např. metodu "hledání nejlepšího partnera" nebo "tenisový turnaj"
Hledání druhého největšího prvku z 8 prvků - jde na 9 porovnání
obecně z N prvků - vzoreček
můžete zkusit dokázat, že nejde rychleji (je to těžší)
pojem invariantu na příklad:
- Eukleidův algoritmus pro hledání největšího spol. dělitele je založen na tom, že
  "pokud je a>b , pak dvojice čísel (a,b) a (a-b,b) mají stejnou množinu společných dělitelů"
- V urně je nějaký počet černých a bílých koulí. V každém tahu vybere dvě z nich a vrátíme tam jednu podle pravidel:
  b+b -> b ; č+b -> b ; č+č -> b (abychom to mohli dělat musíme mít další bílé koule), v každé kroku se tak počet koulí v urně zmenší o jednu.
  Otázka: Na čem závisí jakou barbu bude mít poslední koule, která v urně zbyla.
  Udělali jsme - invariantem je parita počtu černých koulí, tedy bude-li na počátku černých koulí liše, bude poslední lichá, bude-li jich sudě, bude poslední bílá.
hledání invariantu můžeme použít i při řešení většiny dnešních domácí úkolů
cesty věží po šachovnici :
cesta je úplná pokud projde každým políčkem právě jednou
cesta je uzavřená pokud je úplná a končí na políčku, které sousedí s tím, kde začíná
pro danou šachovnici můžeme řešit čtyři úlohy:
1. najít nějakou úplnou cestu
2. najít pro zadané políčko úplnou cestu, která na něm začíná
3. najít nějakou uzavřenou cestu
4. najít pro zadané políčko uzavřenou cestu, která na něm začíná
Uvažujme šachovnici 8x8
- na cvičení jsme ukázali, že řešení úlohy 3. řeší i ostatní
- za domácí úkol řešte tyto čtyři úlohy pro šachovnice:
  - bez levého dolního rohu
  - bez levého dolního rohu a horního pravého rohu
  jedno nebo dvě tvrzení z toho úkolu jsou dost pracné, zkuste jen odhadnot co platí
Pokládání mincí na stůl
Dva hráči hrají hru. Střídavě pokládají na stůl po jedné minci. Minci mohou položit na stůl jak chtějí, ale ne na mince, které už tam byliy. Všechny mince jsou stejně velké.
Ten, který minci už minci nemůže položit prohrál. Pro koho je hra vyhraná a jak má postupovat?
Ukázali jsme, že vyhraje hráč, který začíná tím, že položí první minci do středu stolu a v následujících kolech pokládá minci vždy středově souměrně s tahem protovníka.
Je vidět, že stůl nemusí být obdélníkový, ale může mít jakýkoli středově souměrný tvar (na př. elepsa).
Lámání čokolády Tabulka čokolády m řad po n políčcích. Naším úkolem je tabulku přelámat tak, abychom dostali m*n dílků každý jedno políčko.
Nesmíme lámat najednou více vrstev čokolády "na sobě". Otázka: Jak máme lámat, abychom požadovaného stavu docíli po co nejmenším počtu lomů?
Na způsobu lámání vůbec nezáleží!
Každým lomem se počet kusů čokolády zvětší o 1. A na počátku je kus jeden, na konci jich má být m*n, potřebuje tedy m*n-1 lomů
Mrkev a petržel Spočtěte kolika různými způsoby jde osít K záhonů (jsou vedele sebe) mrkvi a petrželí tak, aby nikdy nebyly dva záhony petržel vedle sebe.
Našli jsme způsob jak to spočítat v lineární čase a nemuset zkoušet všechny možnosti.

Domácí úkol (pokyny k odeslání dostanete mailem)
1. najděte vzoreček pro počet porovnání při hledání druhého největšího prvku z N prvků (vyřešili jsme pro N=8
  jde dokázat, že ruchleji to nejde, ale to obtížnější
2. řešte úkoly o cestách pro šachovnici 8x8 s ustřiženým jedním rohem a s ustřiženými dvěma protilehlými rohy
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á (nemusí nutně nalést optimuální počet bodů)
4. 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é.
5. Č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.
6. Obdobně tři kameny
7. Mrkev a petržel
  Spočtěte kolika různými způsoby jde osít K záhonů (jsou vedle sebe) mrkvi a petrželí tak, aby nikdy nebyly dva záhony petržel vedle sebe.
  napište přehledně řešení, které jsme si naznačili na cvičení

cvičení 16.října

Probrali jsme časté chyby v domácích úkolech a ukázali správná řešení
Komentář k pojmu f je O(g), který byl zaveden v přednášce jako exituje konstanta C>0 a konstanta n₀ takové, že pro každé n>n₀ platí f(n)> C*g(n)
- pokud bychom se omezili na jen na data konečné velikosti žádnou užitečnou teorii složitosti bychom nemohli formulovat, teoreticky by se všechny výpočty redukovaly na hledání výsledků v databázi, kam jsme je před tím uložili
- pokud bychom definovali nějaké O₁ jako "exituje konstanta C1>0 taková, že pro každé n platí f(n)> C1*g(n)
  dostali bychom epojem ekvivalentní původní definici O, je příslušná konstanta C1 by byla větší než C
- složitost měříme až na multiplikativní konstantu, protože u velkých dat konstanta nehraje podtstatnou roli - a u reálných algoritmů nebývá přilíš vysoká
- asymptotická složitost je však dost neintuitivní např.
  v teorii algoritmů (ve všech definicích) platí tzv. věta o zrychlení (speedup therem), který říká. že výpočet každého algoritmu, který "není příliš pomalý" jde urychlit o libovolnou multiplikativní konstantu
  důkaz je více méně jednodychý, jeho "ideu" si můžeme ukázat na příkladu "z praxe": dvoupatrový výhah jezdí dvakrát rychleji než jezdí
  u výtahů to nelze takto urychlovat pořád - když je výtah vyšší než dům, už tam nemusí být vůbec. Ale u zkoumání rychlostí v blízkosti nekonečna takový "podvod" projde.
Způsob, kterým se děti učí dnes ve škole písemné násobení je poněkud nešikovný. Vyžaduje toiž sčítání (potencionálně) nekonečného množství čísel. Ješte za starého Rakouska se děti v Čechách učili násobit jinak. Výsledek násobení prvního čísla cifrou z druhého rovnou přičítali k mezivýsledku a tak žádné velké sčítání nepotřebovaly. Pokrok tedy nejde vždy "kupředu".
způsob jak najít v čase O(N*N) N největších prvků z posloupnost délky N*N
Klasifikace koulí
Máme k dispozici rovnoramenné váhy a pomocí nich máme vyřešit následující úlohu.
Z N podezřelých které buď jsou všechny správné nebo je jedna z nich buď těžší nebo lehčí určit která z 2*N+1 možností nastane. Při tom máte kromě podezřelých koulí k dispozici libovolné množství správných koulí.
Ukázali jsme, že
- z jedné podezřelé koule to umíme na 1 vážení
- ze 4 podezřelých koulí to umíme na 2 vážení
- Pomocí K vážení můžeme rozlišit nejvýše 3 ^K možností. Pokud máme vyřešit úlohu pro N podeřelých koulí, musí tedy platit
  2*N+1 <= 3 ^K
Domácí úkol
1. stabilní párování
  Uvažujme N mužů a N žen. Párováním nazveme množinu N dvojic (žena,muž).
  Vstupem pro naši úlohu jsou preference zúčastněných aktérů. T.j. každá žena zadá pořadí N mužů jak se jí líbí od nejlepšího k nejhoršímu (musí ohodnotit každého muže); obdobně každý muž zadá pořadí N žen.
  Řekneme, že párování je nestabilní když v něm existuje nějaký pár např. (Eva, Adam) takový, že alespoň jeden z nich by si mohl polepšit kdyby se rozešli,
  Přesněji:
  buď by Eva mohla odejít k Hugovi, který se jí líbí víc než Adam a který je spárován s nějakou Kunhutou, která se mu líbí méně než Eva
  nebo
  by Adam mohl odejít k Rebece, která se mu líbí víc než Eva a která je teď spárována s někým Emilem, který se jí líbí méně než Adam
  Párování je stabilní když není nestabilní, t.zn. ze žádné dvojice, se nikomu nevyplatí odejít.
  Najděte algoritmus jak k libovolným zadaným preferencím mužů a žen jde vytvořit stabilní párování
  a snažte se dokázat jeho správnost.
  Musíte tedy dokázat, že vámi navržený algoritmus pro každá vstupní data zastaví (zjistěte za jak dlouho nejpozději) a že vytvoří stabilní párování. Možná, že pro váš algoritmus bude platiti i silnější tvrzení
  Skutečně - ke každým preferencím stabilní párování existuje. Návod: vzpomeňte si na taneční nebo si o nich dejte od někoho vyprávět
2. Naprogramujte v nějakém programovacích jazyků násobení libovolně dlouhých čísel, přikterém není třeba sčítat libovolně mnoho sčítanců. Kód komentujte a odlaďte.
3. Zjistěte z kolika podezřelých koulí dovedete vyřešit úlohu o klasifikaci koulí na K vážení. Algoritmus popište a dokažte jeho správnost. Pokud to nezvládnete, určete to alespoň pro K=3. (na cičení jsme si ukázali, že na jedno vážení to jde z jedné koule a na dvě vážení ze čtyřech.
4. Zkuste zjistit o této úloze další zajímavá fakta, např.:
  - z kolika koulí to dokážeme na K vážení když nemáme k dispozici správné koule
  - kolik správných koulí nám stačí? Roste jejich potřebný počet s počtem podezřelých koulí nebo je konstatní? Jakéá je ta konstanta?
  - atd

cvičení 30.října

úloha s koulemi
S jednou správnou koulí jde na k vážení úlohu vyřešit s N_k = ( 3^k - 1 ) / 2 podezřelých koulí. Bez správné koule to jde s N_k -1 podezřelými koulemi.
Velbloud a banány
písemka na třídící algoritmy se složitostí O(n²) z přednášky
rozmyslete si algoritmy, které budou na příští přednášce a případně si připravte dotazy
domácí úkol
1. Kulový blesk Jistých N rodin bydlí v bytech, které označíme celými čísly od 1 do N. Rodiny se dohodly provést cyklickou N-směnu bytů (viz též film Kulový blesk). Rodina z bytu číslo 1 chce do bytu číslo 2, rodina z bytu číslo 2 do bytu číslo 3, atd., až rodina z bytu číslo N se bude stěhovat do bytu číslo 1. Po té, co se na směně dohodli, zjistili, že platí zákon, který nařizuje:
  1. nikdo se nesmí stěhovat víc než jednou v jednom dni
  2. jsou povoleny jen dvojsměny t.j. stěhuje-li se někdo z bytu A do bytu B, musí se jeho patrtner přestěhovat ve stejný den z bytu B do bytu A
  Zjistěte jaký nejmenší počet dní postačí pro dané N k uskutečnění celé zamýšlené akce. Sestavte rozpis, podle něhož je třeba při výměnách bytů postupovat, aby se tohoto minimální počtu dní dosáhlo (tzn. rozpis určující, kdo se který den stěhuje kam).
2. Velbloud a banány
  Velbloud má spotřebu 1 banán/km a nosnost 1000 banánů. Start je u hromady s 3000 banánů do jaké vzdálenosti dokáže dopravit 1000 banánů? Zkuste řešit i obecně: Spotřeba S, nosnost N, velikost startovaví hromady V, velikost hromady v cíli v , vzdálenost hromad D.
  1. Pro zadané S,V,N a v najděte maximální možnou vzdálenost D
  2. Pro zadané S,V,N a D najděte maximální možnou velikost v
3. 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.
  Každý automat může být v jednom z konečné množiny stavů a má v sobě funkci, která na základě jeho vlastního stavu a stavů jeho sousedů určuje nový stav (množina stavů i ona funkce jsou u všech automatů Vojáků stejné, generál a zadák se liší jen tím, že vědí, že mají souseda jen z jedné strany)..
  Nejde o přesný popis automatů, ale o myšlenku jejich komunikace
  Není to úplně snadné. Kolem roku 1965 uvedl toto cvičení jeden ze zakladatů kybernetiky s tím, že zkušený programátor by to měl vyřešit do 4 hodin. Dnes už je ale základní myšlenka součástí dobrých středoškolských kurzů programování.
  Návodná otázka: pokud úloha má řešení, za jak dlouho může k salvě dojít?
4. Dokažte, že při pánské volence dostane každý muž nejlepší ženu, kterou může v nějakém stabilním párování mít.

cvičení 13.listopadu

Domácí úkoly
- Kulový blesk jde realizovat za dva dny. Obecně libovlné otočení lze realizovat jako složení dvou osových souměrností
- Velbloud a banány
- Synchronizace automatů
  ideou synchronizace je najít střed řady tak, že vysleme dva signály jeden rychlostí 1 a druhý rychlostí 1/3. Ty se (po odražení rychlejšího) potkají uprostřed řady. Tím je tento středový voják "povýšen". Vyšle opět dva signály do leva a dva do prava. Tak budou povýšeni vojáci ve čtvrtinách. Tak se povýšení vojáci umísťují rovnoměrně po celé řadě. Vystřelí až jsou všichni povýšeni.
  Tuto ideu by ještě bylo potřeba technicky dopracovat.
Spojové seznamy
- vkládání do seznamu za daný prvek
- vkládání před zadaný prvek
- vypuštění prvku
- pole versus seznamy
- různé modely spojových seznamů
  - dvousměrný seznam
  - kruhový seznam
  - seznam s hlavou
- reprezentace řídkých polynomů jako kruhových seznamů s hlavou (má to výhodu, že nulový polynom má stejnou reprezentaci jako nenulový) obsahujícíc nenulové členy, uspořádaných podle exponentů
Algoritmus heapsortu
- definice hromady - heapu
- duální pohled na heap: binární strom a pole
- základní operace se heapem
- setřídění když už máme postavený heap
- postavení heapu
- časová složitost je N*log₂(N)
- heapsort třídí na místě (in situ)
Domácí úkol
1. napište podprogram (v nějakém jazyce resp. pseudo-jazyce), který otočí kruhový lineární seznam s hlavou
  návod zkuste si uvědomit kolik proměnných k tomu potřebujete - nejde o minimalizaci jejich počtu, ale o jejich role/význam
2. dobrovolný úkol sestavte podprogram, který realizuje sčítání řídkých polynomů reprezentovaných jako kruhové spojové seznamy s hlavou obsahující členy s nenulovým koeficentem uspořádané podle exponentů
3. Napište časově optimální algoritmus postavení heapu, která byl naznačen na přednášce
4. Označení vícežilového kabelu
  Ve vysoké budově vede kabel s N žilami z přízemí na půdu. Elektrikář může označit konce jednotlivých žil kabelu, spojovat je a následně rozpojovat, má zdroj a žárovku pomocí nichž může měřit zdali jsou ve stejné obvodu.
  Poraďte elektrikářovi postup pomocí něhož se mu podaří identifikovat konce žil, které "patří k sobě". snažte se o minimalizování cest elekrikáře mezi přízemím a půdou.

cvičení 27. listopadu

cvičení 11.prosince

komenáře k domácím úkolům
Minimax jako metoda důkazu Shanonovy věty o existenci neprohrávající strategie
Alfa beta prořezávání záleží na pořadí probírání tahů, pro se v reálných programech dávají tahy, které nejvíc mění hodnotu (např. braní a šachy v šachách) dopředu
Metoda okénka:
označíme-li F(P) výsledek minimaxové procedury a G(P,a,b) výsledek alfa-beta metody s odhady A pro minimum a b pro maximum,
pak platí, že pokud je a< G(P,a,b)<b pak platí G(P,a,b)=F(P) t.j. alfa beta spočítala rychlejí správnou hodnotu,
a pokud je G(P,a,b) < a, pak je i F(P) <b , pak i F(P)>b
Čím je okénko (a,b) uzší tím víc se procházený strom prořezává a výpočet je rychlejší.
Pokud se ne trefíme, víme na kterou stranu máme okénko posunout.
V (nejen) šachových programech se používá kaskáda spolu s metodou okénka:
Nejprve se spočítá minimax do nějaké malé hloubky, výsledky se použijí pro uspořádání tahů na nejvyšší úrovni, pak spočítáme minimax do o něco hlubší úrovně,
údaje o o tom jak se změnila spočtená hodnota a kolik to stálo času se použijí v dalším výpočtu kaskády k určení přírustku hloubky a k nastavení šířky okénka, atd.
písemka quicksort a porovnání jeho vlastností s heapsortem(složitost, ...)
domácí úkoly
z úloh 2,3 a 4 stačí dvě
1. Co nejefektivnější algoritmus pro nalezení nejdelší rostoucí podposloupnosti ze zadané posloupnosti (návod byl na cvičení)
2. Máme zadáno N nádob u každé známe její velikost v_i v litrech a kolik je v ní na začátku litrů kapaliny m_i(obě jsou přirozená čísla). Hledáme nejkratší postup jak naměřit K litrů vody t.j. nejkratší postup k nějaké konfiguraci v níž existuje podmnožina nádob taková, že součet objemů jejích prvků dává K litrů. V jednom tahu si můžem vybrat zdrojovou nádobu (s indexem z) a cílovou nádoby (s indexem c) a přelít ze zdrojové nádoby do cílové min ( m_z, v_c-m_c) - t.j. nesmíme přelít.
  Popište co nejpodrobněji algoritmus
3. Popište co nejpodrobněji výpočet hodnoty aritmetického výrazu v infixové notaci (operace *,/,+,- s proiritami); závorky
4. Popište co nejpodrobněji algoritmus hledání co největšího počtu figur zadaného typu (jedna z dáma, věž, střelec, jezdec) na nějaké šachovnici (vyberte sami: obdélník, válec, pneumatika) se zakázanými políčky.

cvičení 8.ledna

PRG062 Algoritmizace cvičení 1. ročník informatika - středa 12:20 liché týdny S6

Obsah cvičení