This part of my homepage is in Czech only -- I don't think anyone else than my students would use it.

zimni semestr 2001/2002

Vyuka

V letnim semestru 2001/2002 vedu cviceni k predmetu Programovani I; s tim je take spojeno (v lepsim pripade) udileni zapoctu z Rocnikoveho projektu I. Konzultacni hodiny nemam, nicmene pokud budete chtit s cimkoliv poradit/pomoci, nejak se dohodneme (pokud se to bude tykat tohoto predmetu, slibuji, ze si cas najdu, ale i pokud to bude cokoliv jineho, o cem budu neco vedet, tak se pokusim).

Za co je zapocet:

• Zapoctovy program, rocnikovy projekt -- tema byste mi meli oznamit do 15.4.2002, pokud vas nic nenapada, zkuste se podivat sem (primerena obtiznost je 5-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).
  Zapoctaky jsou ve skutecnosti 2, jeden se maskuje jako Rocnikovy projekt. Rocnikovy projekt by mel byt psan v Delphi (v oduvodnenych pripadech jsem ochoten udelat vyjimku (to ze nemate radi Delphi neni akceptovany duvod :-)) Je mozne tyto dva zapoctaky zkombinovat, tj. udelat neco jako zapoctak a po pridani user interface to udat jako RP (nicmene predpoklada se, ze to UI bude alespon trochu na urovni, jedno okenko se dvema tlacitky se nebere).
• 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) div 3 domacich ukolu, kde n je pocet domacich ukolu, ktere zadam (toto nemusi byt uplne pravda, pokud bude vychazet, ze z vas podle tohohle kriteria 3/4 vyhodim, upravim pravidla). Zatim zadane ukoly:
  • (Do 28.2.2002) Napiste program, ktery dostane zadanu posloupnost dvojic (retezec, cislo) (retezce jsou navzajem ruzne), nasledovanou posloupnosti dotazu. Dotazy jsou retezce, odpovedi na dotaz by melo byt cislo, s nimz je tento retezec ve dvojici, pripadne ze takove cislo neexistuje.
    Casova slozitost vaseho reseni by mela byt nanejvys O(delka nejdelsiho retezce * log (pocet dvojic)) na jeden dotaz (plus pripadne nejaky cas na predzpracovani); iniciative se nicmene meze nekladou, existuje nekolik reseni (hashovani, trie), dosahujicich casove slozitosti O(delka nejdelsiho retezce).
    Vyresili:
    • Vaclav Krajicek
    • Petr Kratochvil
    • Jan Kodym
    • Michal Kovac
  • (Do 7.3.2002, prodlouzeno do doby, nez si budu jisty, ze trideni zvladate) Totez co minuly ukol s jedinou drobnou zmenou -- pouzijete-li v predzpracovani trideni, jeho slozitost by nemela byt vyssi nez O(n.log n.delka nejdelsiho retezce), kde n je pocet dvojic (a vic by se mi libila reseni s casovou slozitosti O(n.delka nejdelsiho retezce)).
    Vyresili:
    • Pavel Janda
  • (Do 14.3.2002) Binomialni stromy jsou definovany takto:
    1. B₀ je pouze koren (tj. jeden vrchol)
    2. B_n dostaneme tak, ze vezmeme B₀, B₁, ..., B_n-1 a udelame z nich syny noveho korene.
    Binomialni halda je mnozina binomialnich stromu (tj. kazde B_i se v ni muze vyskytnout maximalne jednou -- rozmyslete si, ze pro dany pocet vrcholu k existuje prave jedna takova mnozina), v jejichz vrcholech jsou ulozeny hodnoty; dale musi byt splnena haldova podminka, tj. hodnota ve vrcholu musi by mensi nez hodnoty vsech jeho synu.
    Vymyslete, jak binomialni haldy efektivne (v O(log k)) spojovat (tj. mame-li dany dve haldy, vytvorit z nich jednu obsahujici vsechny jejich prvky). Dale si rozmyslete, jak za pomoci spojovani implementovat ostatni operace (pridani prvku a odebrani minima).
    Vyresili:
    • Pavel Janda
  • (Do 10.4.2002) Mate zakoreneny strom, pro kazdy vrchol znate jeho nejlevejsiho syna, praveho bratra a otce (existuji-li). Vypiste strom v preorderu. Nepouzivejte zasobnik ani rekurzi.
    Vyresili:
    • Erik Kratochvil
    • Jakub Kotowski
    • Pavel Janda
    • Michal Kovac
    • Vaclav Krajicek
  • (Do 2.4.2002) Mate dan (nikoliv nutne konvexni) mnohouhelnik v rovine a bod X. Rozhodnete, zda X lezi uvnitr mnohouhelnika.
    Napoveda: ignorujte napovedu, kterou jsem dal na cviceni, je to nesmysl :-)
    Vyresili:
    • Vaclav Krajicek
    • Michal Kovac
  • (Do 16.5.2002) Mate dan strom. Naleznete v nem nejmensi dominujici mnozinu (tj. takovou, ze kazdy vrchol je bud v ni, nebo sousedi s nejakym vrcholem z ni). Vyresili:
    • Vaclav Krajicek
    • Michal Kovac