Kdy a kde:

• I1-X/35 : Ct 15:40 v T6
• I1-X/36 : Po 10:40 v E4

Pro ucastniky techto cviceni take zadavam (cti schvaluji zadani) a hodnotim rocnikove projekty. Rocnikovy projekt by mel byt psan v Delphi a mit clickoidni uzivatelske rozhrani (tyto pozadavky je mozne v oduvodnenych pripadech po domluve se mnou modifikovat). Je take mozne jeden (narocnejsi) program udat jako rocnikovy projekt i zapoctak. Tema rocnikoveho projektu je treba mi nahlasit do 15.4.2003.

Za co je zapocet:

• Zapoctovy program -- tema byste mi meli oznamit do 15.4.2003, pokud vas nic nenapada, zkuste se podivat na muj seznam napadu na zapoctaky, pripadne podstatne rozsahlejsi seznam na strankach Martina Marese. (primerena obtiznost je 4-6). 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 musi byt dokumentace. Rady jak ji napsat (a nepsat) od RNDr R. Kryla .
• 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 cca 6). Ukol dodany po terminu se pocita za 2/3 -- tj. pokud behem semestru nebudete nic delat, nezbyva vam, nez ve zkouskovem obdobi vyresit a odevzdat vsechny ukoly. Zatim zadane ukoly:
• (Do 3. (resp. 6.) 3. 2003, prodlouzeno do 10. (13.) 3. 2003) Mame dano castecne usporadani U mnoziny M (tj. mnozinu nerovnosti typu A<B, B<C, A<D, D<C) a cele cislo k; vystupem by mela byt mnozina prvku X takovych, ze existuje linearni usporadani rozsirujici U takove, ze X je v nem k-ty nejmensi prvek (pro nas priklad a k=2 je resenim mnozina {B,D}). Program resici tuto ulohu by mel pracovat v case O(n+m), kde n je pocet zadanych nerovnosti, m velikost mnoziny M. Oprava Zjistil jsem, ze takhle to neumim vyresit ani ja; takze povolena casova slozitost se timto meni na O(nm).
• (Do 10. (13.) 3. 2003) Cisla, v jejichz prvociselnem rozkladu se nachazi pouze 2, 3 a 37, jsou dabelska. Napiste program, ktery pro zadane k nalezne k-te nejmensi dabelske cislo (tj. napriklad pro k = 46 je odpoved 666). Pozadovana casova slozitost: O(k).
• (Do 24. (27.) 3. 2003) Napiste 'kompilator', ktery
  • dostane na vstupu vyraz, ktery muze obsahovat zavorky, operace +, - a * a promenne ri (i je nejake cele cislo > 0). Vsechny operace pracuji nad nezapornymi celymi cisly (v neomezene presnosti). + je secteni, - odecteni s tim, ze pokud by mel vysledek vyjit zaporny, je to misto toho 0. * je operace bitoveho prolozeni -- tj. jsou-li vstupem cisla x = x₀+2x₁+4x₂+... a y = y₀+2y₁+4y₂+..., vysledkem je cislo r = x₀+2y₀+4x₁+8y₁+16x₂+32y₂+... * ma vyssi prioritu nez + a -, + a - maji stejnou prioritu. Operace se stejnou prioritou se zavorkuji doleva, tj. a - b - c + d = ((a - b) - c) + d.
  • vystupem je program pro nize popsany stroj, ktery dany vyraz vyhodnocuje. Stroj ma nekonecne mnozstvi registru r0, r1, r2, ... a registr pc (adresa aktualni instrukce). Na zacatku jsou v registrech, ktere jsou pouzity v zadanem vyrazu, hodnoty vstupu, ostatni registry jsou rovny 0, pc = 1. Na konci vypoctu by v registru r0 mela byt hodnota zadaneho vyrazu. Dale ma stroj nekonecnou pamet pro kod, jejiz bunky jsou ocislovany 1, 2, ... Stroj funguje tak, ze vzdy provede instrukci v bunce, jejiz cislo je v registru pc, a zkonci tehdy, jestlize v pc bude 0. Stroj ma jedinou instrukci X(c1,c2,d1,d2,L1,L2), kde ci, di jsou registry (nikoliv nutne navzajem ruzne), Li jsou cisla bunek v pameti pro kod. Instrukce ma tento vyznam:

    if c1 = c2 then
      begin
        d1 := d2 + 1;
        d2 := 0;
        pc := L1;
      end;
    else
      pc := L2;
    

• (Do 30.3. (2.4.) 2003) Mejme zadan strom (seznamem hran); naleznete v nem nejdelsi cestu.
• (Do 14.4. (17.4.) 2003) Na ulici je N zhasnutych lamp, mame k nim N prepinacu. Kazdy z techto prepinacu ma dan seznam lamp a jeho stistenim se zmeni stav techto lamp (tj. svitila-li dana lampa, po stisteni tlacitka nesviti a naopak). Urcete, ktera tlacitka je potreba stisknout, aby vsechny lampy svitily.
• Mejme ke kazdemu pismenu A .. Z danu jeho cetnost c. Sestrojte binarni strom v jehoz listech budou ulozena tato pismena takovy, ze prumerna hloubka pismenek v tomto strome je minimalni Prumer je vazeny zadanymi cetnostmi, t.j. chceme minimalizovat c(A)hloubka(A) + c(B)hloubka(B)+...+c(Z)hloubka(Z).