PROLOG 

1) Permutaci prvku od 1 do n muzeme reprezentovat bud jako "vektor obrazu" 
napr. pro n=7 termem v(7, [3,2,4,1,6,5,7]) 
nebo jako seznam netrivialnich cyklu prislusneho zobrazeni 
c(7, [ [1,3,4], [5,6] ] ) (cykly [2] a [7] jsme vynechali). 
Soucin permutaci P1 a P2 je permutace P3, ktera vznikne slozenim zobrazeni P1 P2, tj. P3(x)=P1(P2(x)). 
Sestavte predikaty, ktere realizuji nasobeni a umocnovani permutaci reprezentovanych pomoci cyklu. 

2)Mate k dispozici predikat modry/1, ktery uspeje, pokud argument je modry. Sestavte predikat 
natretiny(+Seznam, -Prvni, -Druhy, -Treti), 
ktery rozdeli efektivnim zpusobem vstupni seznam na tri seznamy obsahujici priblizne stejne modrych prvku (Zretezeni seznamu Prvni, Druhy a Treti je seznam Seznam, pocty modrych prvku v seznamech Prvni, Druhy a Treti se mohou lisit nejvyse o 1). Pri jeho konstrukci nesmite pouzit zadnou aritmetiku (ani predikat length). 

HASKELL 

3) Ridka matice je reprezentovana jako trojice (m,n,s), kde m je pocet radek, n je pocet sloupcu a s je seznam trojic (i,j,aij) {kde i je cislo radky, j je cislo sloupce a aij je nenulova hodnota} usporadany vzestupne podle i a uvnitr radek podle j. 
Naprogramujte funkce, ktere v teto reprezentaci realizuji 
a) transpozici matic 
b) nasobeni matic 
c) umocnovani matic (dobrovolne 
Nejedna se tedy o pole v Haskellu 

4) Definujte prirozenou reprezentaci binarniho stromu, v jehoz uzlech je ulozena informace nejakeho typu (podtridy Ord). 
Naprogramujte funkci, ktera ze zadaneho binarniho vyhledavaciho stromu vypusti vsechny uzly, ktere obsahuji hodnotu klice, na kterem zadana funkce krit vrati hodnotu True.

HASKELL 
1) Definujte typ reprezentující orientovaný graf. Vytvořte funkci, která k zadanému grafu vydá buď 
- údaj, že graf nejde topologicky uspořádat a jeden z cyklů, který to dokazuje 
- nebo údaj, že graf jde topologicky uspořádat a seznam vrcholů určující jedno z topologických uspořádání 

2) Definujte typ reprezentující mocninnou řadu. Vytvořte funkce, které počítají 
a) součin dvou mocninných řad 
b) derivaci mocninné řady 
c) K-tou drivaci mocninné řady 


PROLOG 
3) Sestavte predikáty, které realizují průchody do šířky a do hloubky obecným stromem, který je zadán svojí kanonickou reprezentací pomocí binárního stromu (levý syn - prvorozený syn, pravý syn - mladší bratr). 

4) Sestavte predikát, který bude realizovat dělení dvou čísel zadaných jako seznamy cifer jejich dvojkového zápisu.

Haskell 
Kód: Vybrat vše
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


Kód: Vybrat vše
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.)


Prolog
Kód: Vybrat vše
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


Kód: Vybrat vše
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 
1. 
Kód: Vybrat vše
Sestavte funkci, ktera ke vstupujici (nekonecne) posloupnosti realnych cisel a prirozenemu cislu N vyda posloupnosti "klouzavych prumeru s intevalem N". Klouzavy prumer s intervalem N je prumer poslednich prvku.

2.
Kód: Vybrat vše
Mocninna rada je reprezentovana (nekonecnou posloupnosti) posloupnosti jejich koeficientu. Vytvorte funkce, ktere spocitaji
a) Soucet dvou mocninnych rad
b) Soucin dvou mocninnych rad
c) K-tou derivaci mocninne rady


Prolog
1.
Kód: Vybrat vše
Ke kazdemu obecnemu (korenovemu) stromu existuje kanonicka reprezentace pomoci binarniho stromu, v niz
  levy syn znamena prvorozeny syn v puvodnim strome a
  pravy syn znamena mladsi bratr v puvodnim strome
sestavte predikat(y) pro transformaci z obecneho na binarni a zpet.

2.
Kód: Vybrat vše
Definujet predikat odpov (r1,r2) dvou promennych, ktery pro kazde dva seznamy (cisel a specialnich znaku *, ?) r1 a r2 uspeje pokud existuji "substituce jednoho cisla za kazdy zolik ? a substituce posloupnosti (treba prazdne) cisel za znak * takove, ze po provedeni techto substituci dostanete stejne seznamy."
Napr:
  odpov ( [1,5,*,7,?,1] , [*,7,7,5,1] ).
  odpov ( [1,*,5,7,?,1] , [?,?,7,5,1] ).
Muzete predpokladat, ze v jednom seznamu je maximalne jedna hvezdicka.

<b><i>HASKELL</i></b> 

1) Definujte prirozenou reprezentaci bin. stromu, v jehoz uzlech je ulozena informace nejakeho typu (podtridy Ord). 
Sestavte fci, ktera na zaklade rost. seznamu S a cisla N vytvori z prvnich N prvku tohoto seznamu dokonale vyvazeny binarni vyhledavaci strom T (pro kazdy uzel plati ze velikost L a P podstromu se lisi nejvic o 1) a spolu s timto stromem vrati i seznam, ktery zbyl ze seznamu S po postaveni stromu T. (S bez prvnich N clenu) 

2) Ridka matici je reprezentovana jako trojice (m,n,s), kde m a n jsou rozmery matice a s je seznam trojic (i,j,aij) - i,j souradnice, aij nenulove cislo na tech souradnicich - usporadany vzestpne podle i a uvnitr radek podle j. 
Naprogramujte: 
a, transpozici 
b, nasobeni 2 matic 

<b><i>PROLOG</i></b> 

3) Naprogramujte setrideni seznamu primym slevanim (dokud neni v seznamu jen jeden beh (beh=rostouci usek), rozdeluj behy do dvou seznamu, pak slevam atd. ) 
Pozn. :- tady kreslil na tabuli takovy obr. ze kteryho jsem pochopil, ze ty behy se maji rozdelit na 2 seznamy: sude b. a liche b. - ty dva seznamy rekursivne setridit a pak slejt - ale podle nekterych jinych ucastniku se ty behy mohly rozdelit i jinak, jak se vam hodilo...


HASKELL
1) Vsechna k-ciferna cisla, v jejichz dekadickem zapisu jsou vsechny cifry ruzne, jsme "myslenkove" seradili podle velikosti. Napiste procedury ci funkce, ktere k zadanemu cislu primo spoctou jeho poradi a naopak na zaklade poradi naleznou prislusne cislo.

2) Mobil je bud jednoduchy (zavazi na zavesu) nebo slozeny (rameno na zavesu, na jehoz koncich visi mobily). Vahu ramen a zavesu zanedbavame. Mobil je vyvazeny, kdyz v kazdem miste, kde je zaveseno rameno plati momentova veta. Nacrhnete vhodnou datovou reprezentaci mobilu.
Vytvorte funkci, ktera zjisti, zda je dany mobil vyvazeny.

PROLOG
3) Souctovym seznamem nazveme datovou strukturu tvaru A+B, kde A a B jsou seznamy. Oznacime-li OB otoceny seznam B, pak souctovy seznam A+B reprezentuje seznam, ktery vznikne konkatenaci seznamu OB za seznam A.
Sestavte predikaty, ktere realizuji
a) pridani prvku na konec souctoveho seznamu
b) odebrani posledniho prvku souctoveho seznamu
c) Pridani prvku na zacatek SS
d) Odebrani 1. prvku SS
e) konkatenaci 2 SS

4)Vytvorte predikaty, ktere realizuji kodovani a dekodovani pro sifru "Novy Monte Christo". Vstupem je soubor, vystupem opet soubor.
Sifra "NMC" je zadana mrizkou - ctvercovou matici 4x4, kde jsou 4 policka vyriznuta. Sifrovani se deje postupne po 16 znacich. Napiseme je do matice 4x4 a prilozime mrizku, opiseme znaky, ktere vidime pod vyriznutymi mezerami, mrizku otocime a stejne vypiseme druhe 4 znaky atd.

Uvedomte si, ze ne kazda mrizka je korektni - Vas program musi umet korektnost mrizky proverit. Snazte se o efektivni reseni.

HASKELL
(_ je spodni index :))
1) K permutaci PI (prvku od 1 do N) muzeme definovat vektor inverzi OMEGA jako posloupnost delky N, pro niz plati, ze
OMEGA_i = pocet prvku {j<i | (PI_j > PI_i)}.
Tedy napr. k permutaci PI = [3,2,1,4] je prislusnym vektorem inverzi OMEGA = [0,1,2,0].
Sestavte fce, ktere
a) k dane p.ci urci prislusny v.i.
b) k danemu v.i. urci prislusnou p.ci
c) k vektoru urci zda je v.i. nejake posloupnosti

2. najdete komponenty v neorientovanem grafu a mosty v nich

PROLOG
3) Permutaci prvku od 1 do n muzeme reprezentovat bud jako "vektor obrazu" 
napr. pro n=7 termem v(7, [3,2,4,1,6,5,7]) 
nebo jako seznam netrivialnich cyklu prislusneho zobrazeni 
c(7, [ [1,3,4], [5,6] ] ) (cykly [2] a [7] jsme vynechali). 
Sestavte predikat, ktery realizuje umocnovani permutaci reprezentovanych pomoci cyklu. 
4) sestavte predikat
	taut(+Formule)
ktery uspeje pokud je Formule spravne utvoroena formule vyrokoveho poctu (spojky: unarni ~ (negace),
	binarni: & (konjunkce), #(disjunkce), =>implikace s obvyklymi prioritami; zavorky pro zmenu poradi vyhodnocovani; vyrokove promenne - mala pismena)
a sdeli, zda formule je nebo neni tautologii.
Napiste i predikaty, ktere zajisti pouziti prislusnych spojek jako operatoru.

HASKELL
1) definujte funkci APL se ctyrmi parametry:
	S - seznam prvku nejakeho typu
	f - unarni fce aplikovatelna na prvky tohoto typu
	g - binarni (vlevo asociativni) funkce aplikovatelna na prvky tohoto typu
	p - pocatecni hodnota
,
ktera
	"provede funkci f na vsechny prvky seznamu S, za takto vznikly seznam pripoji prvek p a spocita vysledek, ktery vznikne tim, ze do vsech mezer noveho seznamu vlozime funkci g".

To neni navod k programovani, ale popis funkce.
Na zaklade funkce APL vytvorte nasledujici fce:
a) minimum z prvku neprazdneho seznamu
b) aritmeticky prumer z p.n.s.
c) geometricky prumez z p.n.s. (n-ta odmocnina ze soucinu jeho prvku - n je delka seznamu)
d) harmonicky prumer z p.n.s (2-ha odmocnina ze souctu druhych mocnin jeho prvku)

Navod: maji funkce b) az d) neco spolecneho?

2) Definujte typ usporadaneho stromu s libovolnym stupnem. Jsou v nem modre, cervene a bezbarve prvky.
Ohodnoceni je definovano takto:
	bezbarvy prvek - minimum z poctu modrych prvku na jedne ceste z daneho prvku do listu
	modry prvek - pocet bezbarvych v podstromu, ktereho je dany prvek korenem, minus pocet cervenych na ceste od korene k nemu
	cerveny prvek - soucet vysek vsech cervenych v podstromu, ktereho je dany prvek korenem.
Sestavte funkci, ktera na zaklade stromu vrati seznam prvku v nem. Tyto prvku budou usporadany tak, aby jejich ohodnoceni neklesala - a uvnitr stejne ohodnocenych odleva doprava podle polohy ve stromu.

PROLOG
(_ je spodni index :))
3) K permutaci PI (prvku od 1 do N) muzeme definovat vektor inverzi OMEGA jako posloupnost delky N, pro niz plati, ze
OMEGA_i = pocet prvku {j<i | (PI_j > PI_i)}.
Tedy napr. k permutaci PI = [3,2,1,4] je prislusnym vektorem inverzi OMEGA = [0,1,2,0].
Sestavte fce, ktere
a) k dane p.ci urci prislusny v.i.
b) k danemu v.i. urci prislusnou p.ci
c) k vektoru urci zda je v.i. nejake posloupnosti

4) Souctovym seznamem nazveme datovou strukturu tvaru A+B, kde A a B jsou seznamy. Oznacime-li OB otoceny seznam B, pak souctovy seznam A+B reprezentuje seznam, ktery vznikne konkatenaci seznamu OB za seznam A.
Sestavte predikaty, ktere realizuji
a) pridani prvku na konec souctoveho seznamu
b) odebrani posledniho prvku souctoveho seznamu
c) Pridani prvku na zacatek SS
d) Odebrani 1. prvku SS
e) konkatenaci 2 SS

Haskell
1.
Vytvořte funkci, která pro (nekonečný) seznam reálných čísel [xi] vstup a (krátký) konečný rostoucí seznam intervaly malých integerů [a1,a2,...,an] - představte si třeba [2,5,10,25] vytvoří nekonečný seznam, jehož k-tý prvek je "n-tice" klouzavých průměrů s intervaly [a1,a2,...,an] konče k-tým.

2. Definujte si typy reprezentující binární strom a obecný uspořádaný kořenový strom. Sestavte funkce, realizující převod seznamu (lesa) obecných stromů na jeho kanonickou reprezentaci pomocí binárního stromu ("levý syn" = "prvorozený syn", "pravý syn" = "mladší bratr") a zpět

Prolog
3. Sestavte predikáty hladiny(+Strom, -Seznam_Hladin) kde výstupní parametr je seznam seznamu prvků na jednotlivých hladinách vstupního binárního stromu Strom a k němu inverzní strom(-Strom, +Seznam_Hladin). Pochopitelně to může být jeden oboustranný predikát, bude-li efektivní (to inverzní musí vracet postupně všechny možnosti stromu)

4. Definujte predikát odpov(r1,r2) dvou proměnných, který pro každé dva seznamy (přirozených čísel a znaků * a ?) r1 a r2 uspěje pokud existuje "substituce jedno čísla za žolík ? a substituce posloupnosti čísel za znak *" takové, že dostanete stejné seznamy.
Můžete předpokládá, že v každém ze seznamů, které jsou parametry, může být nanejvýše jedna hvězdička.

PROLOG:
1) Máte k dispozici predikát modry/1, který uspěje, pokud argument je modry. Sestavte prodikát na5tiny(+Seznam,-Seznam5tin), který rozdělí efektivním způsobem vstupní seznam na 5 seznamů obsahujících přibližně stejně modrých prvků. Výstupní parametr Seznam5in obsahuje právě 5 prvků. Jsou to seznamy, jejichž zřetězením by vznikl seznam Seznam a počty modrých prvků v libovolných dvou prvcích seznamu Seznam5in se liší nejvýše o 1.
Při konstrukci predikátu nesmíte používat žádnou aritmetiku (ani predikát length)
2) Sestavte proceduru-y, pro kódování a dekódování (dlouhého) seznamu pomocí šifry "Monte Christo".
Text se zakóduje do čtvercové matice 4x4. Kódovacím klíčem je čtvercová mřížka stejných rozměrů s vhodně vyřezanými otvory. Text se vypisuje do otvorů ve mřížce postupně po řádcích, vždy do každého otvoru jedno písmeno. Pak se mřížka otočí o 90° doprava a další text es opět vypisuje do otvorů. Toto se opakuje celkem čtyřikrát. Po zaplnění celé matice se mřížka odstraní a obsah matice se vypíše po řádcích na výstup. Je-li šifrovaná zpráva delší než jeden čtverec (tj. delší než 4x4 písmen), rozdělí se na více úseků, každý o délce jednoho čtverce. Napište kódovací a dekódovací proceduru, musíte otestovat, zda je mřížka přípustná.

HASKELL
3) Definujte přirozenou reprezentaci binárního stromu, v jehož uzlech je uložena informace nějakého typu (podtřídy Eq). Každý stakový strom T určuje relaci mezi prvky onoho typu: A ~ B, jestliže ve stromě T existují uzly a(v němž je uložena informace A) a b (v němž je uložena informace B) takové, že uzel a leží ve stromě T nad uzlem b.
Sestavte funkci, která pro dva stromy rozohdne o tom, zda reprezentují stejnou relaci.
4) Definujte typ vhodný k reprezentaci multimnožiny desítkových cifer (každá z cifer se v ní může vyskytovat vícekrát). Uvažme čísla, která lze sestavit z cifer takové multimnožiny (nemusíme použít všechny). Naprogramujte dvě funkce:
a) první, která nalezne k číslu N a multimnožině M N-té takové číslo
b) druhou "inverzní", která k takovému číslu X spočítá jeho pořadové číslo

Prolog
1. Prevest permutaci zadanou ve tvaru "v(7,[4,3,5,6,2,7,1])" (tedy prvni cifra udava rozsah hodnot v permutaci, zde od 1 do 7, pak nasleduje seznam, kde prvek na pozici i se zobrazi na cislo na te pozici) do zapisu ve tvaru cyklu "c(7,[[1,4,6,7],[2,3,4]])" , tedy nepsat jednoprvkove cykly.

2. Vytvorit predikat, ktery 
a) prijme 2 permutace v zapisu cyklu a vrati jejich soucin (tedy slozeni permutaci)
b) prijme permutaci a vrati jeji druhou mocninu (slozeni 2 stejnych permutaci, zde se melo postupovat pres NSN/LCM delek cyklu)

Haskell
1. Reprezentovat BVS a pak funkci na vypousteni vsech vrcholu s hodnotou mezi Min a Max
2. Soucin a podil dlouhych cisel - dlouhe cislo je trojice Znamenko, [Int], Pozice desetinne carky od prvni cifry