Vyuka - Programovani I

Kdy a kde:

I/1-Z/48, MIU/1/75 : St 14:00 v E2

Za co je zapocet:

Zapoctovy program -- tema vcetne specifikace, v niz shrnete, co ma vami vytvoreny program umet, byste mi meli oznamit do 30.11.2004, pokud vas nic nenapada, zkuste se podivat na muj seznam napadu na zapoctaky, pripadne podstatne rozsahlejsi seznam na strankach Martina Marese. (primerena obtiznost je 3-4). I pokud uz nejake tema mate, stejne se vyplati tam podivat -- vicemene vsechny tam uvedene informace (dokumentace, osetreni vstupu, ...) plati i u me (jen jsem liny je sem psat).
Presto zduraznim: soucasti zapoctaku je dokumentace. Rady jak ji napsat (a nepsat) od RNDr R. Kryla a RNDr. J. Hrice.
Ucast na cviceni neni povinna; na druhou stranu, pokud po me bude chtit zapocet nekdo, koho jsem na cviceni nikdy nevidel, asi bude mit problem.
Vyreseni alespon 2*n/3 domacich ukolu, kde n je pocet domacich ukolu, ktere zadam (n bude radove 6). Ukol dodany po terminu (kterym obvykle byva pristi cviceni) se pocita za 2/3 -- tj. pokud behem semestru nebudete nic delat, nezbyva vam, nez ve zkouskovem obdobi vyresit a odevzdat vsechny ukoly. Reseni prikladu se (neni-li receno jinak) sklada z popisu algoritmu, programu v Pascalu, ktery ho implementuje, a zduvodneni spravnosti a casove slozitosti. Zduraznuji: je pozadovan popis algoritmu, nikoliv programu. Priklad:
Spatne: Nastavim sum na 0 a pak pro i od 1 do n pricitam a[i] k sum.
Lepe: Sectu zadane prvky (ulozene v poli a).
Spravne: Zalezi na okolnostech. Scitat cisla v poli jen tak pro radost je vicemene k nicemu. Spise nez na detailne popisovat to, jak je secteme, je lepsi se zamerit na vysvetleni toho, proc je vlastne chceme secist.
Zatim vypsane priklady:
- Navrhnete minimalni sadu zavazi, kterou lze na rovnoramennych vahach zvazit s presnosti na jeden gram libovolny predmet o vaze nanejvys n gramu. Soucasti ukolu je take dokazat, ze zadna mensi sada splnujici podminky zadani neexistuje.
- Varianta hry NIM: mame k hromadek sirek, pocet sirek na i-te hromadce je n_i. Hraci se pravidelne stridaji, ten, kdo je na tahu, odebere libovolny kladny pocet sirek z nejvetsi hromadky (pokud je vic nejvetsich hromadek, z jedne libovolne z nich). Prohral ten, kdo nema jak tahnout. Urcete (a dokazte), kdy ma zacinajici hrac vyhravajici strategii.
- Mate danou nejakou funkci
  function f(x:integer):integer;
  
  Posloupnost 0, f(0), f(f(0)), f(f(f(0))), ... je vzdy periodicka (pripadne s predperiodou). Napiste program, ktery urci periodu teto posloupnosti.
  
  Program by mel byt rozumne rychly. Presneji, je-li n delka predperiody a m delka periody posloupnosti, mel by volat funkci f nanejvys c(m+n) krat, kde c je nejaka konstanta.
- Mate dano prirozene cislo N, spocitejte dolni celou cast log₂ N v case lepsim nez O(log₂ N).
- Kazde permutaci na N prvcich muzeme priradit cislo timto zpusobem: Vezmeme si vsech N! permutaci na N a seradime je lexikograficky (tj. nejprve je seradime podle hodnoty prirazene 1, ty co maji tuto hodnotu stejnou podle hodnoty prirazene 2, atd.). k-ta permutace v tomto poradi ma pak cislo k.
  
  Napiste program, ktery pro zadanou permutaci urci jeji cislo (rozumne rychle -- tj. postup vygeneruj vsechny permutace a najdi tu zadanou neni prijatelny).
- V organizaci je n zamestnancu a m sefu. Kazdy zamestnanec i sef muze mit nekolik nadrizenych sefu (ale nevznikaji cykly -- tj. nestane se, ze by nekdo byl svym "transitivnim" zamestnancem). Plat zamestnancu jsou dany pevne. Plat sefa je urcen jako maximum z platu jeho podrizenych + 1. Napiste program, ktery urci, kolik tato organizace utrati na platech.
  
  Format vstupu muze byt napriklad tento (zamestnanci jsou cislovani 1,2,..., n, sefove n + 1, ..., n + m):
```
4 3
1 2 3 4
1 5
2 5 7
1 7
2 5 7
1 6
0
1 6
```
  To znamena: jsou 4 zamestnanci a 3 sefove. Platy zamestnancu jsou 1,2,3 a 4. Prvni zamestnanec ma prave jednoho sefa -- cislo 5. Druhy zamestnanec ma 2 sefy -- 5 a 7. Atd.
  
  Spravny vystup pro tento vstup je 26.

Obsah cviceni:

(6.10.) Ulozky o vazeni, dolni odhady na pocet vazeni.
(13.10.) Cviceni odpadlo.
(20.10.) Hledani nejvetsiho a druheho nejvetsiho prvku, NIM a jeho varianty.
(27.10.) Programovalo se. Hledani nejvetsiho a druheho nejvetsiho prvku, vyhodnoceni polynomu zepredu a zezadu, nejdelsi rostouci usek, nejdelsi usek s nejvyse jednim poklesem.
(3.11.) Hratky s cisly -- N-ta mocnina v O(log N) nasobenich, vypocet odmocniny pulenim intervalu, zjisteni, zda N=x⁸+y⁸.
(10.11.) Procvicovani prace s poli -- slozeni a inverze permutace, cykly permutace, rad permutace. Pocitani NSN a NSD.
(17.11.) Svatek.
(24.11.) Priklady na rekurzi (generovani permutaci, podmnozin).
(1.12.) Mergesort. Nejdelsi podpalindrom.
(8.12.) Minimax aplikovany na hledani nejhorsiho vstupu pro algoritmus. Jednoduche ulozky na backtracking s ukladanim vysledku (pripadne dynamicke programovani).
(15.12.) Operace se spojovymi seznamy.
(22.12.) Prace s dlouhymi cisly. Reprezentace grafu.
(5.1.) Cviceni odpadlo, mozna bude nekdy nasledujici tyden nahrazeno.