PràctiquesGrans

 

 

·         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.