====== 8. cvičení - 20.11.2009 ======

===== Důležité =====

  * **termín specifikace [[informace#zapoctove_programy|zápočtového programu]] - 30. listopadu 2009!**
  * od víkendu 21.-22.11.2009 se bude **v CodExu výlučně používat [[http://wiki.freepascal.org/|FreePascal]]**

===== Co bylo? =====

  * problémy s řešením domácích úloh v CodExu
    * řešení úlohy Palindromní věta - [[domaci-ulohy#palindromni_veta|vzorový zdroják]], diskuse
    * [[rady#typicke_problemy_-_rady|časté problémy a nich vyplývající rady]]
    * co znamenají hlášky CodExu, případně Borland/Free Pascalu
  * jak programovat rozumně a slušně a nedělat prasárny
    * dekompozice do modulů, podprogramů
    * pojmenování proměnných
    * komentáře
    * komunikace přes rozhraní, nespoléhání se na implementaci
    * rozumná optimalizace
      * vyhnutí se duplikování kódu
      * společné podvýrazy
      * inkrementální výpočty
      * předzpracování
  * ukázka instalace [[http://wiki.freepascal.org/|FreePascalu]]
  * práce s textovými soubory - [[http://home.pf.jcu.cz/~edpo/program/kap09.html|příklad]]
  * úlohy
    * inkrementální výpočty
      * kolikrát se vyskytuje v posloupnosti s opakováním prvků nejčastější prvek?
      * nejdelší hladká spojitá podposloupnost posloupnosti přirozených čísel
  * předzpracování
    * počet výskytů nejčastějšího prvku posloupnosti

==== Co se nestihlo ====

  * úlohy
    * inkrementální výpočty
      * spojitá podposloupnost CELÝCH čísel s největším součtem
  * co znamenají hlášky CodExu, případně Borland/Free Pascalu
    * co znamenají hlášky CodExu, případně Borland/Free Pascalu
  * optimalizace
    * předčasná optimalizace je kořenem všeho zla
    * vyhnutí se pesimalizaci

==== Inkrementální výpočty ====

Často můžeme výpočet algoritmu urychlit tím, že nové hodnoty počítáme s pomocí předchozích hodnot. Sice tím zvýšíme paměťovou složitost, ale většinou ne přilíš výrazně.

Pár definic pro následující úlohy: //Podposloupnost// je posloupnost vytvořená výběrem některých prvků původní posloupnosti tak, že zachováme jejich pořadí. //Spojitá podposloupnost// je úsek přímo po sobě jdoucích prvků posloupnosti. 

=== Nejdelší hladká spojitá podposloupnost ===

Definice: //Hladká podposloupnost// je taková spojitá podposloupnost, že každé dva prvky posloupnosti se liší nejvýš o 1, tj. v posloupnosti se vyskytují prvky nejvýše dvou hodnot.

Máme posloupnost přirozených čísel. Úkolem je najít délku libovolné její nejdelší hladké podposloupnosti.

Horší řešení běží v čase O(N^2), lepší v čase O(N).

  * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/MAXHLAD.PAS|ukázkový zdroják]] - [[materialy|doc. Pavel Töpfer]]

=== Spojitá podposloupnost celých čísel s největším součtem ===

Máme posloupnost **celých** čísel. Počítáme součet prvků jejích spojitých podposloupností. Úkolem je najít největší takový součet.

Triviální řešení běží v čase O(N^3), ne úplně dobré v čase O(N^2), dobré v čase O(N).

  * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/MAXSOUC.PAS|ukázkový zdroják]] - [[materialy|doc. Pavel Töpfer]]

==== Předzpracování ====

Výpočet rozložíme do několika fází.

=== Počet výskytů nejčastějšího prvku posloupnosti ===

Máme posloupnost např. přirozených čísel, kde hodnoty prvků se mohou opakovat. Nějaká hodnota (nebo i více hodnot) se bude vyskytovat v největším počtu prvků. Cílem je zjistit tento počet výskytů nejčastěji se objevující hodnoty. Hodnota samotná nás ovšem nezajímá. Posloupnost čísel je konečná a máme uloženou v poli.

  - Triviální řešení: Pro každou hodnotu projdeme pole a spočítáme počet výskytů. Průběžně si pamatujeme a aktualizujeme největší počet výskytů nějaké hodnoty. Označíme N jako délka posloupnosti. Časová složitost: O(N^2). Vyskytuje-li se každá hodnota pouze jednou, projdeme pole N-krát. Paměťová složitost: O(N). Musíme si pamatovat celé pole a potřebujeme konstantní místo pro proměnnou pro průběžné maximum počtu výskytů nějaké hodnoty.
  - Rychlejší řešení: V první fázi si posloupnost setřídíme. Tento problém má složitost O(N*log(N)). V další fázi procházíme postupně setříděnou posloupnost a pamatujeme si a aktualizujeme nejdelší konstatní úsek. Jelikož je posloupnost setříděná, prvky se stejnou hodnotou jsou v jednom úseku bezprostředně u sebe, a jakmile takový úsek skončí, víme, že daná hodnota už se dále v posloupnosti neobjeví. Jeden průchod nám dává složitost druhé fáze O(N). Časová složitost: O(N*log(N)). Paměťová složitost: O(N), stejně jako u předchozího řešení.