PRM045 - cvičení 1. ročník matematika
skupina 53 ZS 2008/9 - pondělí 9:00 K11

Obsah cvičení a úkoly
1. cvičení 23.února
2. cvičení 2.března
3. cvičení 9.března
4. cvičení 16.března
5. cvičení 23.března
6. cvičení 30.března
7. cvičení 6.dubna
8. cvičení 20.dubna
9. cvičení 27.dubna
10. cvičení 4.května
11. cvičení 18.května

Obsah cvičení

cvičení 23.února
- O zápočtech
- Opakování práce s textovými soubory
- Složitější příklad

cvičení 2.března
- Vyčíslování hodnoty aritmetického výrazu metodou shora dolů
- Rekursivní implementace tohoto algoritmu
- Odstraňování rekurse pomocí zásobníku
- Nerekursivní implementace vyčíslování hodnoty aritmetického výrazy metodou shora dolů

cvičení 9.března

cvičení 16.března
- Opakování ukazatelů a dynamické alokace
- Hledání prvku v uspořádaném seznamu
- Vkládání prvku do uspořádaného seznamu
- Domácí úkol: slévání dvou uspořádaných seznamů do jednoho

cvičení 23.března
- Množina je reprezentována jako rostoucí seznam svých prvků, funkce jako seznam dvojic rostoucí vzhledem k první složce
  - Obraz množniny
  - Vzor množiny
- Domácí úkol:
  1. uspořádání seznam (je lepší "vytvářet ho rovnou uspořádaný - vlkádáním"
  2. naprogramovat vzor množiny

cvičení 30.března
- Komentář k některým řešením v domácích úkolech
- jednoduché podprogramy pro práci se stromy
  - kopírování stromu
  - průchod inorder
  - počet prvků stromu
  - procedura search pro binární vyhledávací stromy
  - myšlenka vypouštění z binárního vyhledávacího stromu
  - "otáčení" stromu tak, aby v každém uzlu bylo v levém podstromu bylo alespoň tolik prvků jako v pravém
    verze s voláním procedury pro výpočet počtu prvků ve stromě má exponenciální složitost
    rozmyslet:odstranit tuto neefektivitu
- Zápočtové úlohy za zimu.
- Domácí úkol: Množina je reprezentovaná jako binární vyhledávací strom jejich prvků.
  Sestavte podprogramy pro výpočet destruktivního a nedestruktivního průniku dvou množin.
  Domácí úkol pošlete do Codexu na fiktivní úlohu, na první řádek napište komentář se svým jménem a názvem úlohy.

cvičení 6.dubna
- O zápočtových úlohách na letní semestr. Je třeba
  1. Nejpozději do 1.května se dohodnout na tématu
  2. Nejpozději do 17.května zaslat podrobnou specifikaci
- Krátká písemka
- Dožeňte domácí úkoly, které jste případně ještě neposlali
- rozmyslete "otáčení" stromu z minula
- nové domácí úkoly
  1. vytvořit proceduru, která realizuje násobení řídkých matic v reprezentaci, která byla na přednášce
  2. procedura pro vyřazení konzervy ze skladiště
  3. nepovinně: vytvoření reprezentace řídké matice na základě dat přečtených ze vstupu
    (vhodně uspořádaná posloupnost trojic {i,j, a[i,j]} )
  Domácí úkol pošlete do Codexu na fiktivní úlohu, na první řádek napište komentář se svým jménem a názvem úlohy.

cvičení 20.dubna
- Analýza počítačového zabezpečení modelu "vícekolového" volebního systému s jedním hlasováním viličů
- Hledání optimální cesty s více kriterii
- Domácí úkol:
  Napiště část programu, která najde k zadanému grafu (s kladně ohodnocenými hranami), startovnímu a cílovému vrcholu, limitů času a peněz, které mám k dispozici, nekratší cestu, která vyhovuje zadání a pokud je takových nejkratších víc, takt tu nejlacinější. Použijte Dijkstrův algoritmus.
  Není nutné programovat vstupty a výstupy, pošlete do Codexu jako fiktivní úloh
- Poslední možnost dohanat "bez ztráty kytičky" domácí úkoly

cvičení 27.dubna
- Objektové programování - opakování
- dva jednoduché příklady objektového návrhu

cvičení 4.května
- komentář k objektovému programování
- dynamické programování
- nejdelší společný podřetězec
- nejdelší rostoucí vybranná posloupnost
- nalezení optimálního binárního sromu na základě frekvencí dotazů na prvky v něm
- návod na modifikaci algoritmu, aby měl složitost jen O(n²)
- návod na modifikaci, která by počítala i s frekvencemi "vnějších uzlů" stromu, t.j. frekvencemi neúspěšných dotazů
- zadání zápočtových programů

cvičení 11.května odpadá