Fórum studentů MFF UK

Tak pridam taky zazitek z ustni zkousky
...Dr. Kryl mel dnes opravdu dobrou naladu. Prvni dva priklady jsem mel dobre, dokonce si u nich napsal poznamku hezke, z tretiho prikladu jsem mel jen jednu polovinu, a ctvrty jsem nemel vubec. Po zkusenosti z minula jsem myslel, ze me zase vyhodi, ale k memu prekvapeni mi rekl, ze jsem nad dvojkou a jestli chci jednicku, tak ze se mne jeste na neco zepta. Dal mi tri otazky ... lazy vyhodnocovani, lazy patterns, rozdilove seznamy ... mrknul na to a poslal me domu s jednickou v indexu

Tak preju hodne stesti tem, co s neprockem stale zapasi

Ustnu mam za sebou: 1, 3, 4 som mal dobre. V 2 som mal logicke chyby (pridaval som i postupnosti s 'dieram', napr 1 3 5 7 11 (diera v 9)). Nakoniec som dostal aj tak za jedna a to bez teoretickych otazok.

Este dodam k 4, ze pan Kryl mal na mysli nie cesty dlzky n, ale sledy dlzky n.

[quote="Lukas Mach"]Rict si, ze graf budes reprezentovat matici incidence. Tu matici umocnit na n-tou. Volitelne tu vyslednou matici projit a cisla >= 1 nahradit jen jednickou.[/quote]
Joj, dufam, ze bude akceptovat i taketo riesenie. Bohuzial, ma jednu chybicku: pomocou matica susednosti najdes sledy dlzky n a nie cesty ako stoji v zadani.

oprava: matica incidence -> matica susednosti

[quote="Lukas Mach"]Souhlasim, Kryl byl (u me teda minulej tyden) naprosto v pohode. Taky rikal neco ve stylu "Tady je to sice osklivy, ale vzhledem k te konkurenci..." Takze pokud je pisemka tezsi, je asi taktictejsi vybrat si pozdejsi termin a tak jiz az pote, co byla laťka snizena těmi, ktere vyrazil.[/quote]

Hmm, tak to doufam, ze byla tahle pisemka hodne tezka, protoze du az jako uplne posledni :).

Souhlasim, Kryl byl (u me teda minulej tyden) naprosto v pohode. Taky rikal neco ve stylu "Tady je to sice osklivy, ale vzhledem k te konkurenci..." Takze pokud je pisemka tezsi, je asi taktictejsi vybrat si pozdejsi termin a tak jiz az pote, co byla laťka snizena těmi, ktere vyrazil.

Tak zazitek z ustni... Projdete spolu ty priklady, o syntakticky detaily a chybky se moc nezajima a nevadi mu, za to je problem jakakoliv chyba v algoritmu, treba zapomenout na odstranovani tech casti polynomu kde vyjde koef 0 pri nasobeni. 2ku jsem mel dobre, ve 3ce sem mel jenom prvni pulku a s chybou, 4ku OK. Celkove pry horsi 2, ale "v dnesni konkurenci" jsem dostal za 2 i bez doplnujici otazky.

Preju hodne stesti vsem..

Me napadlo udelat si reprezentaci pomoci seznamu nasledniku a potom pro kazdy vrchol najit vsechny cesty delky n. Pak ten vrchol bude mit novy seznam nasledniku, obsahujici vrcholy v kterych koncily ty cesty delky n.
Bohuzel jsem tento napad nestacil zrealizovat, protoze sem se rozhod psat vsechny ulohy nejdriv nanecisto a pak prepsat a to prepisovani mi zabralo strasne casu ...

BTW: Hodilo by se kdyby nekdo prispel zazitkem z ustni.

[quote="stnicolaus"]nevíte někdo, jak se měla řešit 4. úloha?[/quote]
Rict si, ze graf budes reprezentovat matici incidence. Tu matici umocnit na n-tou. Volitelne tu vyslednou matici projit a cisla >= 1 nahradit jen jednickou.

Teda moc jsem o tom nepremyslel, takze me treba nekdo opravi.

nevíte někdo, jak se měla řešit 4. úloha?

jen oprava> nebylo to nasobeni ridkych matic, ale polynomu

1. Ridky polynom je reprezentovan jako (vhodne usporadany) seznam dvojic
                      <nenulovy koeficient,exponent>.
Definujte prislusny datovy typ - nezapomente na nulovy polynom.
Naprogramujte funkce pro
  a) nasobeni ridkych polynomu
  b) skladani ridkych polynomu

2. Vytvorte funkci, ktera k danemu cislu n najde seznam vsech aritmetickych posloupnosti prvocisel mensich nez n, ktere nejdou prodlouzit (zadna z techto posloupnosti se ve vystupnem seznamu nesmi opakovat).
(mezi posloupnosti uvazujte jen ty, ktere maji aspon tri cleny.)

3. Vytvorte predikaty, ktere
  a) k dane permutaci nalezne jeji poradove cislo
  b) k poradovemu cislu c vyrobi c-tou permutaci z cisel 1..N

Je dan orientovany graf G, jeho N-tou mocninou je graf G^N se stejnou mnozinou vrcholu, v nemz hrana vede z vrcholu A do vrcholu B pokud v grafu G vede z vrcholu A do B cesta delky N.

Haskell
[code]1. Ridky polynom je reprezentovan jako (vhodne usporadany) seznam dvojic
<nenulovy koeficient,exponent>.
Definujte prislusny datovy typ - nezapomente na nulovy polynom.
Naprogramujte funkce pro
a) nasobeni ridkych polynomu
b) skladani ridkych polynomu[/code]

[code]2. Vytvorte funkci, ktera k danemu cislu n najde seznam vsech aritmetickych posloupnosti prvocisel mensich nez n, ktere nejdou prodlouzit (zadna z techto posloupnosti se ve vystupnem seznamu nesmi opakovat).
(mezi posloupnosti uvazujte jen ty, ktere maji aspon tri cleny.)[/code]

Prolog
[code]3. Vytvorte predikaty, ktere
a) k dane permutaci nalezne jeji poradove cislo
b) k poradovemu cislu c vyrobi c-tou permutaci z cisel 1..N[/code]

[code]Je dan orientovany graf G, jeho N-tou mocninou je graf G^N se stejnou mnozinou vrcholu, v nemz hrana vede z vrcholu A do vrcholu B pokud v grafu G vede z vrcholu A do B cesta delky N.[/code]