Zkouška 23.5.2022

Přednáška je věnována neprocedurálnímu programování. Většina semestru je věnována programování v jazyku Prolog, ve kterém studenti i ladí zápočtové programy. Informativně se studenti seznámí i s jazykem LISP a neprocedurálními částmi programovacích systémů.
mohy00

Zkouška 23.5.2022

Příspěvek od mohy00 »

Dneska bylo, povinné: graf je složen pouze z disjunktních kružnic (Prolog), nějaký parsování v Haskellu (implementovat words, lines (standardní funkce), pak ke každému slovu přidal číslo řádky, vyfiltrovat kratší než n, a lexikografický setřídit)

Volitelné:

Prolog: Hledání cesty mezi 2 vrcholy v obecném stromu (libovolný počet dětí, pro každý vrchol)

Haskell:

Máš multimnozinu, číslic 0-9, chceme vrátit n-te největší číslo, které z těch číslic sestavit.
BohdanQQ
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 25. 5. 2022 09:24
Typ studia: Informatika Bc.

Re: Zkouška 23.5.2022

Příspěvek od BohdanQQ »

Kompletni zadani:

1. POVINNÁ (Prolog): Rozklad orientovaného grafu na kružnice.

Orientovaný graf G je zadán jako term og(Vrcholy,Hrany), kde Vrcholy je seznam jeho vrcholů a Hrany seznam hran ve tvaru počáteční_vrchol - koncový_vrchol.

Definujte predikát kruznice(+G, -Cykly), který

zjistí, zdali G sestává z vrcholově disjunktních kružnic
přitom uvažujeme i kružnice délky 2 (2 vrcholy propojené hranami v obou měrech) a 0 (izolovaný vrchol)
v kladném případě vrátí seznam příslušných cyklů, každý reprezentovaný seznamem svých vrcholů (počáteční vrchol může být libovolný)
jinak vrátí false.
Orientovaná kružnice v (orientovaném) grafu je posloupnost po dvou různých vrcholů taková, že hrana vede z každého vrcholu této posloupnosti do vrcholu následujícího i z posledního vrcholu do prvního.

Příklad:

?- kruznice(og([a,b,c,d,e,f],[f-c, e-f, c-e, d-b, b-d]), Cykly).
Cykly = [[a],[b,d],[c,e,f]]

(a) Sestavte predikát kruznice/2.

(b) Bude váš predikát fungovat i v opačném směru jako kruznice(-G, +Cykly), tj. po zadání seznamu cyklů vrátí odpovídající graf? Proč ano / ne ?

(c) Obsahuje vaše řešení řez či negaci? Pokud ano, co se stane, když řez / negaci odstraníme? Pokud ne, dal(a) by se v něm někde smysluplně využít?

--------------------------------------------------------------------------------


Na vstupu je zadán text jako hodnota typu String. Naším cílem je definovat binární funkci

stat text n

která

obdrží takový text a přirozené číslo n
a vrátí všechna slova z tohoto textu o délce alespoň n, setříděná lexikograficky
každé slovo s čísly řádků, kde se slovo vyskytuje
(a) Sestavte funkci

radky :: String -> [String]

která obdrží text a vrátí seznam jeho řádků = nejdelších neprázdných podřetězců, které neobsahují znak '\n'. Pozor na to, že dva řádky mohou být odděleny jak jedním tak více znaky '\n'.

(b) Sestavte funkci

slova :: String -> [String]

která obdrží řádek textu (neobsahuje '\n') a vrátí seznam jeho slov = nejdelších neprázdných podřetězců, které neobsahují mezeru ' ' ani tabelátor '\t'. Pozor na to, že dvě slova mohou být oddělena jak jedním tak více znaky ' ' či '\t'.

(c) Definujte datovou strukturu pro reprezentaci oboru hodnot funkce stat.

(d) Definujte typovou signaturu funkce stat s použitím datové struktury z (c).

(e) Sestavte funkci stat, připom použijte datovou strukturu z (c) and obě funkce z (a)-(b). Budete-li využívat další pomocné funkce, popište prosím jejich význam v komentáři.

Jakmile budete mít vše definováno, odpovězte na následující otázky.

(f) Je datová struktura z části (c) polymorfní ? Pokud ne, dal by se typový polymorfismus nějak ve vaší definici využít?

(g) Využili jste ve vašem kódu nějakou standardní funkci vyššího řádu (= funkce s jedním nebo více funkcionálními argumenty)? Pokud ne, dala by se někde smysluplně využít?

--------------------------------------------------------------------------------


3. VOLITELNÁ (Prolog) : Cesta v obecném stromě.

Na vstupu je obecný strom (ne nutně binární) strom, v jehož vrcholech jsou uložena navzájem různá celá čísla. Naším cílem je definovat predikát cesta/4, který

ve stromě najde cestu z vrcholu se zadanou hodnotou x do vrcholu se zadanou hodnotou y
nalezenou cestu vrátí jako seznam čísel vrcholů tvořících tuto cestu
pokud hodnota x či y ve stromě není, predikát selže.
(a) Popište reprezentaci obecného stromu, kterou budete používat.

(b) Sestavte definici predikátu cesta(+Strom, +X, +Y, -Cesta).

(c) Najde vaše řešení požadovanou cestu na jeden průchod zadaným stromem? Pokud ne, dalo by upravit na "jednoprůchodovou" verzi?

(d) Je některý z vašich predikátů koncově rekurzivní? Pokud ne, bylo by možné nějakou definici na koncově rekurzivní upravit?

--------------------------------------------------------------------------------

4. VOLITELNÁ (Haskell): Čísla se zadanými číslicemi

Je dána multimnožina číslic desítkové soustavy, každá číslice se v ní může vyskytovat vícekrát nebo také vůbec. Uvažme čísla, která lze sestavit použitím (ne nutně všech) číslic z této multimnožiny. Naším cílem je sestavit definice funkcí

multi1, která k zadanému přirozenému číslu n a multimnožině m vrátí n-té takové číslo (v přirozeném uspořádání dle velikosti
a inverzní funkci multi2, která k takovému číslu x a multimnožině m vrátí jeho pořadí.
(a) Definujte datový typ pro reprezentaci takové multimnožiny číslic.

(b) Definujte typovou signaturu funkce multi1.

(c) Sestavte definici funkce multi1.

(d) Definujte typovou signaturu funkce multi2.

(e) Sestavte definici funkce multi2.
Odpovědět

Zpět na „PRG005 Neprocedurální programování“