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

• 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
  můžete zkusit dokázat, že nejde rychleji (ale není jednoduché)


• 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í některých 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 dcv. ř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
  
  
• 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ř. elipsa).
  
  
• 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 čísel konstanta nehraje podtstatnou roli -a u reálných algoritmů nebývý přilíš vysoká
  • v teorii algoritmů (ve všech definicích) platí tzv. věta o zrychlení (speedup therem). že výpočet každého algoritmu, který "není příliš pomalý" jde urychlit o libovolnou multimlikativní konstantu
    "aplikace" idei důkazu : dvoupatrový výhah jezdí dvakrát rychleji než jezdí
  
  
• N největších čísel z N*N čísel jde najít v čase N*N čísla si umístíme do matice N*N, přidáme k ní další (N+1)-ní řádek
  v čase N zjistíme z každého sloupce maximum a umístíme ho do přidaného řádku
  to provedem pro všechny sloupce celkově jsme tedy potřebovali N*N porovnání
  v čase N vybereme z přidaného řádku maximum - to je největší číslo
  nalezené maximum odstraníme a v jeho sloupci spočteme nové maximum a dáme ho přidaného řádku
  to opakujeme N krát. Celková složitost je tedy N*N + 2*N*N tedy O(N*N)
  Rozmyslete tento algoritmus


• 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 rychleji 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. stabilní párování
     Uvažujme N mužů a N žen. Párováním nazveme množnu 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 kdyby se rozešli, aspoň jeden by si polepšil. 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. v žádné dvojici, 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. 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

• Probrali jsme časté chyby v domácích úkolech a ukázali správná řešení
• shrnutí způsobů hledání prvku v poli z přednášky - měli byste si osvojit aniž byste nad tím museli v budoucnu uvažovat
• způsob jak najít v čase O(N*N) N největších prvků z posloupnost délky N*N
• Stabilní párování - pánská volenka
  Jedním ze způsobů jak dostat stabilní párování je tzv. pánská volenka. Algoritmus probíhá v kolech.
  V každém kole se všichni muži, kteří jsou volní jdou žádat k nejlepší ženě, která je dosud neodmítla a
  každá žena si porovná muže, kteří ji žádají a muže, kterého si drží a nově si podrží nejlepšího z nich.
  
  1. Je jasné, že algoritmus musí skončit nejdéle po N*(N-1) kolech: každá žena může odmítnout nejvýše N-1 mužů a když v daném kole žádná žena nikoho neodmítne algoritmus končí párováním
  2. toto párování je stabilní, protože:
     muž by chtěl utéct jen k ženám, které ho odmítly a
     žena by chtěla utéct jen k mužům, kteří o ni nestáli
• 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".
• 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. Pánská volenka
     Dokažte, že ve stabilním párování, které vznikne pánskou volenkou dostane každý muž nejlepší ženu, kterou může v nějakém stabilním párování mít (tj. každé párování, ve kterém by měkl lepší ženu je nutně nestabilní)
  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. 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é.
  4. Č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 jsou vyhrané pro začínajícího hráče, a nalézt vítěznou strategii hry.
  5. Obdobně tři kameny
  6. Princezna
     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 sáhnout na kterékoli dvě sklenice a podle své vůle případně změnit polohu některých z nich (výběr obou sklenic, na které sáhne musí udělat předem, není přípustné, aby sáhl na jednu a teprve podle její polohy si vybral na kterou druhou sáhne). Úč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).
     Poraďte mladíkovi, jak princeznu získat a zjistěte jak dlouho mu to bude trvat.
  7. 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ě krá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ňů"
  8. 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 cvičení jsme si ukázali, že na jedno vážení to jde z jedné koule a na dvě vážení ze čtyřech.
     
  9. 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

• probírání domácích cvičení
• vyhledávání prvku v poli - opakování z přednášky
• algoritmy třídění v kvadratickém čase: vkládání, výběr, výměna - opakování z přednášky
• pojem hromady (heap), její reprezentace v poli, základní oprace s hromadou a jejich složitost
• heapsort
• 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. 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?
  3. Sepište důkaz tvrzení, že žádný algoritmus nemůže setřídit pole dékly N za méně než N*log₂(N)
     
     bylo na přednášce, po vás se chce ucelený text, který odůvodní každý krok důkazu
  4. zůstává úkol o koulích z minula,
     pokud jste ho minule vyřešili úplně(nepletu-li se byl to jeden člověk), nemusíte to posílat znovu

• Řešení domácích úkolů:
  1. kulový besk jde ve dvou dnech
     obecně každé otočení jde vyjádřit jako složení dvou osových souměrností
  2. 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ů
• rekurzivní řešení problému Hanojských věží
• písemka třídění heapsort
• Domácí úkoly
  1. 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.
     Pro zadané S,V,N a v najděte maximální možnou vzdálenost D
     Pro zadané S,V,N a D najděte maximální možnou velikost v
  2. 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 potřebujete - nejde o minimalizaci jejich počtu, ale o jejich role/význam
  3. 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ů
  4. dobrovolný úkol Sestavte podprogram, který k zadanému přirozenému číslu N vytiskne všechny jeho různé rozklady na menší sčítance (rozklady lišící se jen pořadím sčítanců se považují za stejné).
     Např. pro N= 5 podprogram vytiskne:
     4+1
     3+2
     3+1+1
     2+2+1
     2+1+1+1
     1+1+1+1+1

Promyslete si vše, co bylo/bude na přednášce a připravte si případné otázky,
pokud potřebujete konzultaci, nestyďte se a domluvte si ji (gmail, mobil)
Máte mi dodat několik možností na pravidelné konzultace, já některou vyberu a budu vám v tédobě k dispozici

• hledání nejdelší rostoucí vybrané posloupnosti
• rekurze
• obecné schéma procházení stavovým prostorem do hloubky a do šířky, které se liší jen datovou strukturou seznamu OPEN, zjednodušení je-listavový prostor acyklický
• 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.
  
• domácí úkoly
  
  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.
  3. najděte efektivní algoritmus, který najde nejkratší cestu ze startovního políčka s indexy (i,j) do cílového políčka (k,l) v obdélníkové matici o rozměrech M x N. V matici mohou být některá políčka zakázaná a cesta může vést jen dolů nebo doprava - t.j. ve některém ze dvou směrů, ve kterých rostou indexy
  4. Dobrovolný úkol: Najděte co nejefektivnější algorimus, který k zadané matici s hodnotami 0 nebo 1, najde největší podmatici, která obsahuje samé jedničky.