Pràctiques “Grans”
·
Heu de
triar si feu una pràctica individual (3 punts) o una en equip de dues persones
(5 punts). Llavors, poseu-vos en contacte amb el professor per indicar quina
voleu fer. El professor us donarà la conformitat o us suggerirà una altra pràctica
per tal que no tothom faci la mateixa.
·
Heu de
lliurar un llistat amb les definicions de les funcions que hauran de tenir el
NOM QUE S’INDICA a L’ENUNCIAT i la DEFINICIÓ DE TIPUS. Per a les
definicions de tipus i funcions auxiliars feu servir el nom que vulgueu.
·
Si considereu que alguna funció que feu servir
és quelcom “fosca”, expliqueu-la. Feu servir noms adients i doneu
els tipus de totes les funcions.
·
Per a
poder optar a la primera convocatòria, heu de lliurar la pràctica durant la
setmana del 24-28 de Novembre.
·
Es
valorarà positivament l’ús de funcions d’ordre superior i la instanciació dels tipus en diverses classes.
Pràctiques
Individuals
1) (3 punts) Construeix un tipus de dades Arbrenari que sigui arbre n-ary polimòrfic,
(per a qualsevol n).
·
Defineix-ne
una espècie de funció de plegament tipus fold per a les llistes, de manera que el pugui utilitzar per a definir:
o
sumaarbre_n_ari : tal que donat
un Arbrenari ens
calculi la suma de tots els seus números, suposant que aquests siguin enters.
o
mesgranarbre_n_ari: tal que donat un Arbrenari ens
digui quin és el número més gran que hi apareix.
·
Deriva’l correctament de la classe Eq i de la classe Show usant Instance.
·
Defineix una funció
amplada i que ens digui quina és l’amplada màxima
d’un nivell i quins són els elements
que la formen.
·
Defineix la funció
que fa recorregut en preordre preordre_n_ari.
2) (3 punts) Defineix el tipus Matriu i les següents funcions per al seu tractament:
deriva-la de la classe Show de manera que les mostri per pantalla en forma de matrius.
3) (3 punts) Defineix el tipus Polinomi i les següents funcions per al seu tractament:
derivala
de la classe Show de manera que les mostri per pantalla en forma de polinomis.
Pràctiques
Per Parelles
4) (5 punts) Construiu
un tipus de dades Autodetregular que correspongui
als autòmates regulars deterministes i un tipus Autoindetregular que correspongui
als autòmates regulars indeterministes per al reconeixement de llenguatges regulars. Construeix-ne les funcions:
·
pertanydet: tal que donat un Autodetregular i una paraula, ens digui
si pertany al llenguatge o
no.
·
pertanyindet: tal que donat un Autoindetregular i una paraula, ens digui
si pertany al llenguatge o
no.
·
paraula: tal que donat un Autodetregular , ens
torni una paraula reconeguda per l’autòmata
(si és possible)
·
Deriveu-lo correctament
de la classe classe Show mitjançant
la redefinició de showsPrec.
5) (5 punts) Construiu un tipus de dades polimòrfic Arbretriari (arbre amb tres fills).
·
Deriveu-lo correctament
de Eq, Ord i Show de manera que es vegi de forma escalada, p. Ex:
b
a1 - c
d
a - a2
a3
·
Feu-ne les
funcions:
o
nivells: que donat
un Arbretriari, en dongui
el recorregut per nivells
o
amplada: que donat
un Arbretriari digui
quina és la màxima amplada d’un nivell i quins valors el formen
o
fondaria: que donat
un Arbretriari digui
quina és la màxima fondària d’una branca i quins valors la formen
6) (5 punts) Definiu el tipus de dades TaulaEmpleats a partir d’un tipus
Empleat,
·
tal que se li pugui aplicar Inserts, Selects (simples) i Deletes.
·
Deriva TaulaEmpleats de Show de manera que es vegi per pantalla:
NOMS | COGNOMS |
EDAT | SOU | ANTIGUITAT | SEXE
------------------------------------------------------
Pep | daunos |
29 | 200000 |
2 | home
Maria | perez |
26 | 200000
| 1 | dona
Deriveu també el sexe de Show , Empleat de Eq, i el que us faci falta.
7) (5 punts) Definiu un arbre binari Abin i:
·
construi-ne la funció rank: donat un Abin, ens diu quin rank te
l’arbre segons la següent definició:
rank Fulla
x =0
rank Arrela x a1 a2
= rank a1 +1 si
rank a1 = rank a2
= max {Rank a1, Rank a2} altrament
·
Definiu també el tipus recorregut d’un Abin, que
serà una llista de valors dels node visitats, indicant en quin ordre s’han
recorregut, així, per exemple, un possible recorregut
d’un arbre com:
f(f(a,b), c) === [(f,[1,2]), (f,[1,2]), (a,[]), (b,[]), (a,
[])]
·
Feu les funcions:
·
quinarbre: tal que donat un recorregut ens
construeixi l’arbre del que n’és recorregut.
·
recorregutoptim: tal que donat un Abin, ens
calculi el recorregut que passi primer pels subarbres de menys rank, i en cas d’igualtat,
el de més a l’esquerra, indicant
quina es la permutació que segueix,
per exemple:
recorregutoptim
f(f(a,b), c) === [(f,[2,1]) (c,[]) (f,[1,2])
(a,[]), (b,[])]
·
mateixarbre: tal que donats dos recorregut, ens
digui si ho són del mateix arbre.
·
permdif: tal que donat un recorregut ens
digui en quantes permutacions difereix del recorregut òptim.