Edición de «AED2 resumen 2C-17»

== Ejercicio 1 ==

=== a ===

duplicar: secu(&alpha;)&rarr;secu(&alpha;)

duplicar(s)&equiv;if vacía?(s) then &lang;&rang; else prim(s)&bull;prim(s)&bull;duplicar(fin(s)) fi

=== b ===

&bull;&le;&bull;: secu(&alpha;) x secu(&alpha;) &rarr; bool

s &le; t &equiv; if &not;(vacía?(s) &or; vacía?(t)) then prim(s) < prim(t) &or; (prim(s)=prim(t) &and; fin(s)&le;fin(t)) else vacía?(s) fi

=== c ===

reverso: secu(&alpha;)&rarr;secu(&alpha;)

reverso(s) &equiv; if vacía?(s) then s else reverso(fin(s)) &ordm; prim(s) fi

=== d ===

capicúa: secu(&alpha;)&rarr;bool

capicúa(s) &equiv; s = reverso(s)

=== e ===

esPrefijo?: secu(&alpha;) x secu(&alpha;) &rarr; bool

esPrefijo?(&lang;&rang;,t) &equiv; true

esPrefijo?(e &bull; s,t) &equiv; if vacía?(t) then false else e = prim(t) &and; esPrefijo?(s,fin(t)) fi

=== f ===

buscar: secu(&alpha;) x secu(&alpha;) &rarr; nat

buscar(&lang;&rang;,t) &equiv; 0

buscar(s, t) &equiv; if esPrefijo?(s, t) then 0 else 1 + buscar(s, fin(t)) fi

=== g ===

estaOrdenada?: secu(&alpha;) &rarr; bool

estaOrdenada?(&lang;&rang;) &equiv; true

estaOrdenada?(e &bull; s) &equiv; if vacía?(s) then true else e &le; prim(s) &and; estaOrdenada?(s) fi

=== h ===

'''''InsertarOrdenada''''', que dados una secuencia '''''so''''' (que debe estar ordenada) y un elemento '''''e''''' (de género &alpha;) inserta '''''e''''' en '''''so''''' de manera ordenada.

insertarOrdenada: secu(&alpha;) so x &alpha; &rarr; secu(&alpha;) {estaOrdenada?(so)}

insertarOrdenada(&lang;&rang;, e) &equiv; e &bull; &lang;&rang;

insertarOrdenada(a &bull; s, e) &equiv; if e &le; a then e &bull; a &bull; s else a &bull; insertarOrdenada(s, e) fi

=== i ===

cantidadApariciones: secu(&alpha;) x &alpha; &rarr; nat

cantidadApariciones(&lang;&rang;,a) &equiv; 0

cantidadApariciones(e &bull; s,a) &equiv; if e = a then 1 + cantidadApariciones(s,a) else cantidadApariciones(s,a) fi

=== j ===

aux(s,s,t): secu(&alpha;) x secu(&alpha;) x secu(&alpha;) &rarr; bool

aux(&lang;&rang;,s,t) &equiv; true

aux(e &bull; u,s,t) &equiv; cantidadApariciones(s,e) = cantidadApariciones(t,e) &and; aux(u,s,t)

esPermutación?: secu(&alpha;) x secu(&alpha;) &rarr; bool

esPermutación?(s,t) &equiv; if long(s) = long(t) then aux(s,s,t) else false

=== k ===

combinar: secu(&alpha;) a x secu(&alpha;) b &rarr; secu(&alpha;) {estaOrdenada?(a) &and; estaOrdenada?(b)}

combinar(s,t) &equiv; if vacía(s) then t else combinar(fin(s),insertarOrdenada(t,prim(s)) fi

== Ejercicio 2 ==

=== a ===

 #hojas: ab(&alpha;) &rarr; nat

 #hojas(nil) &equiv; 0

 #hojas(bin(a,e,b)) &equiv; if esHoja?(bin(a,e,b)) then 1 else #hojas(a) + #hojas(b) fi

=== b ===

degeneradoAIzquierda: ab(&alpha;) &rarr; bool

degeneradoAIzquierda(a) &equiv; nil?(a) &or;L if esHoja?(a) then true else nil?(der(a)) &and; degeneradoAIzquierda(izq(a)) fi

=== c ===

zigZag: ab(&alpha;) &rarr; bool

zigZag(a) &equiv; nil?(a) &or;L esHoja?(a) &or;L if nil?(izq(a)) then nil?(der(der(a))) &and; zigZag(der(a)) else if nil?(izq(a)) then nil?(izq(izq(a))) &and; zigZag(izq(a)) else false fi fi

=== d ===

ultimoNivelCompleto: ab(&alpha;) &rarr; nat

ultimoNivelCompleto(nil) &equiv; 0

ultimoNivelCompleto(bin(a,e,b)) &equiv; 1 + min(ultimoNivelCompleto(a),ultimoNivelCompleto(b))

=== e ===

espejo: ab(&alpha;) &rarr; ab(&alpha;)

espejo(a) &equiv; if nil?(a) then a else bin(espejo(der(a)),raiz(a),espejo(izq(a)) fi

=== f ===

esSimétrico?: ab((&alpha;) &rarr; bool

esSimétrico?(a) &equiv; a = espejo(a)

== Ejercicio 3 ==

=== a ===

agregarTodos: &alpha; x conj(conj(&alpha;)) &rarr; conj(conj(&alpha;))

agregarTodos(n,c) &equiv; if &empty;?(c) then Ag(Ag(n,&empty;),&empty;) else Ag(Ag(n,dameUno(c)),agregarTodos(n,sinUno(c))) fi

partesDe: conj(nat) &rarr; conj(conj(nat))

partesDe(c) &equiv; if &empty;?(c) then c else agregarTodos(dameUno(c),partesDe(sinUno(c))) &cup; partesDe(sinUno(c)) fi

=== b ===

combinacionesDeK: conj(&alpha;) x nat &rarr; conj(conj(&alpha;))

combinacionesDeK(&empty;, k) &equiv; &empty;

combinacionesDeK(Ag(e,c), k) &equiv; if k = 0 &or; #(Ag(e,c)) < k then &empty; else agregarTodos(e,combinacionesDeK(c,k-1)) &cup; combinacionesDeK(c,k) fi

== Ejercicio 4 ==

ntn: conj(secu(&alpha;)) x secu(&alpha;) &rarr;  conj(secu(&alpha;))

blablabla

== Ejercicio 5 ==

=== a ===

nivelNormal?: at(&alpha;) x nat k &rarr; bool { &not; k = 0 }

nivelNormal?(a,k) &equiv; nil?(a) &or;L if k = 1 then &not;(nil?(izq(a)) &or; nil?(med(a)) &or; nil?(der(a))) else nivelNormal?(izq(a),k-1) &and; nivelNormal?(med(a),k-1) &and; nivelNormal?(der(a),k-1) fi

=== b ===

blablabla

== Ejercicio 6 ==

=== a ===

altura: rosetree(&alpha;) &rarr; nat

altura(rose(r,&lang;&rang;)) &equiv; 1

altura(rose(r,e &bull; s)) &equiv; 1 + altura(masAlta(r,e &bull; s))

masAlta: &alpha; x secu(rosetree(&alpha;)) &rarr; rosetree(&alpha;)

masAlta(a,s) &equiv; if vacía?(s) then rose(a,&lang;&rang;) else if altura(prim(s)) > altura(masAlta(a,fin(s))) then prim(s) else masAlta(a,fin(s)) fi fi

=== b ===

cantHojas: rosetree(&alpha;) &rarr; nat

cantHojas(r) &equiv; if esHoja?(r) then 1 else sumarHojas(hijos(r)) fi

esHoja?: rosetree(&alpha;) &rarr; bool

esHoja?(r) &equiv; vacía?(hijos(r))

sumarHojas: secu(rosetree(&alpha;)) &rarr; nat

sumarHojas(s) &equiv; if vacía?(s) then 0 else cantHojas(prim(s)) + sumarHojas(fin(s)) fi

=== c ===

podar: rosetree(&alpha;) a &rarr; rosetree(&alpha;) {&not;esHoja?(a)}

podar(r) &equiv; rose(raíz(r),podadora(hijos(r)))

podadora: secu(rosetree(&alpha;)) &rarr; secu(rosetree(&alpha;))

podadora(s) &equiv; if vacía?(s) then s else if esHoja?(prim(s)) then podadora(fin(s)) else podar(prim(s)) &bull; podadora(fin(s)) fi fi

=== d ===

obtenerRamas: rosetree(&alpha;) &rarr; secu(secu((&alpha;))

obtenerRamas(r) &equiv; if esHoja?(r) then (raíz(r) &bull; &lang;&rang;) &bull; &lang;&rang; else if long(hijos(r)) = 1 then insertarTodos(raíz(r),obtenerRamas(prim(hijos(r)))) else insertarTodos(raíz(r),obtenerRamas(prim(hijos(r)))) & obtenerRamas(rose(raíz(r),fin(hijos(r)))) fi fi

insertarTodos: &alpha; x secu(secu(&alpha;)) &rarr; secu(secu(&alpha;))

insertarTodos(a,s) &equiv; if vacía(s) then &lang;&rang; else (a &bull; prim(s)) &bull; insertarTodos(a,fin(s)) fi

=== e === 

devolverNivel: nat n x rosetree(&alpha;) &rarr; secu(&alpha;) {&not; n = 0}

devolverNivel(n,r) &equiv; agarrador(n,obtenerRamas(r))

agarrador: nat n x secu(secu(&alpha;)) &rarr; secu(&alpha;) {&not; n = 0}

agarrador(n,s) &equiv; if vacía(s) then &lang;&rang; else if long(prim(s)) &ge; n then obtener(n,prim(s)) &bull; agarrador(n,fin(s)) else agarrador(n,fin(s)) fi fi

obtener: nat n x secu(&alpha) s &rarr; &alpha; {(&not; n = 0) &and; long(s) &ge; n}

obtener(n,s) &equiv; if n = 1 then prim(s) else obtener(n-1,fin(s)) fi

=== f ===

masLargasConRepetidos: rosetree(&alpha;) &rarr; conj(secu(&alpha;))

masLargasConRepetidos(r) &equiv; soloConRepetidos(soloUnTam(altura(r),obtenerRamas(r)))

tieneRepetido: secu(&alpha;) &rarr; bool

tieneRepetido(s) &equiv; (&not; vacía(s)) &and;L (esta?(prim(s),fin(s)) &or; tieneRepetido(fin(s)))

soloConRepetidos: secu(secu(&alpha;)) &rarr; conj(secu(&alpha;))

soloConRepetidos(s) &equiv; if vacía(s) then &empty; else if tieneRepetido(prim(s)) then Ag(prim(s),soloConRepetidos(fin(s))) else soloConRepetidos(fin(s)) fi fi

soloUnTam: nat n x secu(secu(&alpha;)) &rarr; secu(secu(&alpha;)) {&not; n = 0}

soloUnTam(n,s) &equiv; if vacía?(s) then &lang;&rang; else if long(s) = n then prim(s) &bull; soloUnTam(n,fin(s)) else soloUnTam(n,fin(s)) fi fi

== Ejercicio 7 ==

evaluar(cte(a),n) &equiv; a

evaluar(x,n) &equiv; n

evaluar(a + b, n) &equiv; evaluar(a,n) + evaluar(b,n)

evaluar(a . b, n) &equiv; evaluar(a,n) . evaluar(b,n)

esRaíz: polinomio x nat &rarr; bool

esRaíz(a,n) &equiv; 0 = evaluar(a,n)

== Ejercicio 8 ==

trayectoria(ubicar(c)) &equiv; c &bull; &lang;&rang;

trayectoria(arriba(r)) &equiv; &lang;&pi;1(posiciónActual(r)),&pi;2(posiciónActual(r)) + 1&rang; &bull; trayectoria(r)

trayectoria(abajo(r)) &equiv; &lang;&pi;1(posiciónActual(r)),&pi;2(posiciónActual(r)) - 1&rang; &bull; trayectoria(r)

trayectoria(derecha(r)) &equiv; &lang;&pi;1(posiciónActual(r)) + 1,&pi;2(posiciónActual(r))&rang; &bull; trayectoria(r)

trayectoria(izquierda(r)) &equiv; &lang;&pi;1(posiciónActual(r)) - 1,&pi;2(posiciónActual(r))&rang; &bull; trayectoria(r)

posiciónActual(r) &equiv; prim(trayectoria(r))

cuántasVecesPasó(c,r) &equiv; cantidadApariciones(Trayectoria(r),c)

másALaDerecha(r) &equiv; maxX(trayectoria(r))

maxX: secu(coordenada) s &rarr; coordenada {&not; vacía?(s)}

maxX(e &bull; s) &equiv;if vacía?(s) then &pi;1(e) else max(&pi;1(e),&pi;1(maxX(s)) fi

== Ejercicio 9 ==

'''TAD Electroimán'''

''Igualdad observacional''

(&forall; i1:electroimán)((&forall; i2:electroimán)(i1 =obs i2 &hArr; ((cinta(i1) = cinta(i2) &and; imánPrendido?(i1) = imánPrendido?(i2)) &and;L (imánPrendido?(i1) &rArr;L (imánCargado?(i1) = imánCargado?(i2))))))

''Genero'' electroimán

''Usa'' Bool, Nat, Cinta

''Exporta'' Genero, Generadores, Observadores básicos, Otras operaciones

''Axiomas''

cinta(arrancar(c)) &equiv; c

cinta(prender(e)) &equiv; if celdaActualOcupada?(cinta(e)) then sacarElem(cinta(e)) else cinta(e) fi

cinta(apagar(e)) &equiv; if imánCargado?(e) then ponerElem(cinta(e)) else cinta(e) fi

cinta(&larr;(e)) &equiv; &larr;(cinta(e))

cinta(&rarr;(e)) &equiv; &rarr;(cinta(e))

imánPrendido?(arrancar(c)) &equiv; false

imánPrendido?(prender(e)) &equiv; true

imánPrendido?(apagar(e)) &equiv; false

imánPrendido?(&rarr;(e)) &equiv; imánPrendido?(e)

imánPrendido?(&larr;(e)) &equiv; imánPrendido?(e)

imánCargado?(prender(e)) &equiv; celdaActualOcupada?(e)

imánCargado?(&rarr;(e)) &equiv; imánCargado?(e) &or; celdaActualOcupada?(&rarr;(e))

imánCargado?(&larr;(e)) &equiv; imánCargado?(e) &or; celdaActualOcupada?(&larr;(e))

celdaActualOcupada?(e) &equiv; celdaActualOcupada?(cinta(e))

 #giros&larr;(arrancar(c) &equiv; 0

 #giros&larr;(prender(e) &equiv;  #giros&larr;(e)

 #giros&larr;(apagar(e) &equiv;  #giros&larr;(e)

 #giros&larr;(&rarr;(e) &equiv;  #giros&larr;(e)

 #giros&larr;(&larr;(e) &equiv; 1 + #giros&larr;(e)

 #giros&rarr;(arrancar(c) &equiv; 0

 #giros&rarr;(prender(e) &equiv;  #giros&rarr;(e)

 #giros&rarr;(apagar(e) &equiv;  #giros&rarr;(e)

 #giros&rarr;(&rarr;(e) &equiv; 1 + #giros&rarr;(e)

 #giros&rarr;(&larr;(e) &equiv; #giros&rarr;(e)

'''Fin TAD'''

'''TAD Cinta'''

''Igualdad observacional''

(&forall; c1:cinta)((&forall; c2:cinta)(c1 =obs c2 &hArr; (#celdas(c1) = #celdas(c2) &and;L (celdaActual(c1) = celdaActual(c2) &and; #giros&larr;(c1) = #giros&larr;(c2) &and; #giros&rarr;(c1) = #giros&rarr;(c2) &and; (&forall;i:nat)(i<#celdas(c1) &rArr;(celdaOcupada?(i,c1) = celdaOcupada?(i,c2)))))))

''Genero'' cinta

''Usa'' Bool, Nat

''Exporta'' Genero, Generadores, Observadores básicos, Otras operaciones

''Otras operaciones''

cuentaOcupados: nat x cinta &rarr; nat

''Axiomas''

 #celdas(arrancar(n)) &equiv; n

 #celdas(ponerElem(c)) &equiv; #celdas(c)

 #celdas(sacarElem(c)) &equiv; #celdas(c)

 #celdas(&larr;(c)) &equiv; #celdas(c)

 #celdas(&rarr;(c)) &equiv; #celdas(c)

 #giros&larr;(arrancar(n)) &equiv; 0

 #giros&larr;(ponerElem(c)) &equiv; #giros&larr;(c)

 #giros&larr;(sacarElem(c)) &equiv; #giros&larr;(c)

 #giros&larr;(&larr;(c)) &equiv; 1 + #giros&larr;(c)

 #giros&larr;(&rarr;(c)) &equiv; #giros&larr;(c)

 #giros&rarr;(arrancar(n)) &equiv; 0

 #giros&rarr;(ponerElem(c)) &equiv; #giros&rarr;(c)

 #giros&rarr;(sacarElem(c)) &equiv; #giros&rarr;(c)

 #giros&rarr;(&larr;(c)) &equiv; #giros&rarr;(c)

 #giros&rarr;(&rarr;(c)) &equiv; 1 + #giros&rarr;(c)

celdaActual(arrancar(n)) &equiv; 0

celdaActual(ponerElem(c)) &equiv; celdaActual(c)

celdaActual(sacarElem(c)) &equiv; celdaActual(c)

celdaActual(&larr;(c)) &equiv; if celdaActual(c) = 0 then #celdas(c) - 1 else celdaActual(c) - 1 fi

celdaActual(&rarr;(c)) &equiv; if celdaActual(c) = #celdas(c) - 1 then 0 else celdaActual(c) + 1 fi

celdaOcupada?(n,arrancar(a)) &equiv; false

celdaOcupada?(n,ponerElem(c)) &equiv; if n = celdaActual(c) then true else celdaOcupada?(n,c) fi

celdaOcupada?(n,sacarElem(c)) &equiv; if n = celdaActual(c) then false else celdaOcupada?(n,c) fi

celdaOcupada?(n,&larr;(c)) &equiv; celdaOcupada?(n,c)

celdaOcupada?(n,&rarr;(c)) &equiv; celdaOcupada?(n,c)

celdaActualOcupada?(c) &equiv; celdaOcupada?(celdaActual(c),c)

 #elem(c) &equiv; cuentaOcupados(0,c)

cuentaOcupados(n,c) &equiv; if n < #celdas(c) then if celdaOcupada?(n,c) then 1 + cuentaOcupados(n+1,c) else cuentaOcupados(n+1,c) fi else 0 fi

'''Fin TAD'''

== Ejercicio 10 ==

== Ejercicio 11 ==

== Ejercicio 12 ==

TAD Producto es String

'''TAD Stock'''

''Igualdad observacional''

(&forall; s1:stock)((&forall; s2:stock)(s1 =obs s2 &hArr; ((&forall; p:producto)(estaRegistrado(p,s1) &hArr; estaRegistrado(p,s2)) &and;L (&forall; p1:producto)((&forall; p2:producto)((estaRegistrado(p1,s1) &and; estaRegistrado(p2,s1)) &rArr;L (mínimo(p1,s1) = mínimo(p1,s2) &and; compras(p1,s1) = compras(p1,s2) &and; ventas(p1,s1) = ventas(p1,s2) &and; esSus(p1,p2,s1) = esSus(p1,p2,s2)))))))

''Genero'' stock

''Usa'' Bool, Nat, Conj(&alpha;)

''Exporta'' Genero, Generadores, Observadores básicos, stocksBajos

''Observadores básicos''

estaRegistrado: producto x stock &rarr; bool

esSus: producto a x producto b x stock s &rarr; bool {estaRegistrado(a,s) &and; estaRegistrado(b,s)}

compras: producto p x stock s &rarr; nat {estaRegistrado(p,s)}

ventas: producto p x stock s &rarr; nat {estaRegistrado(p,s)}

mínimo: producto p x stock s &rarr; nat {estaRegistrado(p,s)}

''Generadores''

crearStock: . &rarr; stock

registrarProducto: producto p x nat x stock s &rarr; stock {&not; estaRegistrado(p,s)}

comprar: nat x producto p x stock s &rarr; stock {estaRegistrado(p,s)}

vender: nat n x producto p x stock s &rarr; stock {estaRegistrado(p,s) &and;L compras(p,s) &ge; n}

infSus: producto a x producto b x stock s &rarr; stock {(estaRegistrado(a,s) &and; estaRegistrado(b,s)) &and;L &not;(&exist; p:producto)(esSus(p,b,s)) &and; a &ne; b}

''OtrasOperaciones''

stocksBajos: stock &rarr; conj(producto)

tieneSus: producto p x stock s &rarr; bool {estaRegistrado(p,s)}

obtenerSus: producto p x stock s &rarr; producto {estaRegistrado(p,s) &and;L tieneSus(p,s)}

productos: stock &rarr; conj(producto)

quitarBuenos: conj(producto) x stock &rarr; conj(producto)

''Axiomas''

estaRegistrado(p,crearStock) &equiv; false

estaRegistrado(p,registrarProducto(a,n,s)) &equiv; p = a &or; estaRegistrado(p,s)

estaRegistrado(p,comprar(n,a,s)) &equiv; estaRegistrado(p,s)

estaRegistrado(p,vender(n,a,s)) &equiv; estaRegistrado(p,s)

estaRegistrado(p,infSus(a,b,s)) &equiv; estaRegistrado(p,s)

compras(p,comprar(n,a,s)) &equiv; if p = a then n + compras(p,s) else compras(p,s) fi

compras(p,registrarProducto(a,n,s)) &equiv; if p = a then 0 else compras(p,s) fi

compras(p,vender(n,a,s)) &equiv; compras(p,s)

compras(p,infSus(a,b,s)) &equiv; compras(p,s)

ventas(p,vender(n,a,s)) &equiv; if p = a then n + ventas(p,s) else ventas(p,s) fi

ventas(p,registrarProducto(a,n,s)) &equiv; if p = a then 0 else ventas(p,s) fi

ventas(p,comprar(n,a,s)) &equiv; ventas(p,s)

ventas(p,infSus(n,a,s)) &equiv; ventas(p,s)

esSus(a,b,registrarProducto(c,n,s)) &equiv; if a = c &or; b = c then false else esSus(a,b,s) fi

esSus(a,b,infSus(c,d,s)) &equiv; (a = c &and; b = d) &or; esSus(a,b,s)

esSus(a,b,comprar(n,c,s)) &equiv; esSus(a,b,s)

esSus(a,b,vender(n,c,s)) &equiv; esSus(a,b,s)

mínimo(p,registrarProducto(a,n,s)) &equiv; if p = a then n else mínimo(p,s) fi

mínimo(p,comprar(n,a,s)) &equiv; mínimo(p,s)

mínimo(p,vender(n,a,s)) &equiv; mínimo(p,s)

mínimo(p,infSus(a,b,s)) &equiv; mínimo(p,s)

stocksBajos(s) &equiv; quitarBuenos(productos(s),s)

productos(crearStock) &equiv; &empty;

productos(comprar(n,a,s)) &equiv; productos(s) 

productos(vender(n,a,s)) &equiv; productos(s)

productos(registrarProducto(a,n,s)) &equiv; Ag(a,productos(s))

productos(infSus(a,b,s)) &equiv; productos(s)

tieneSus(p,registrarProducto(a,n,s)) &equiv; (&not; p = a) &and;L tieneSus(p,s)

tieneSus(p,comprar(n,a,s)) &equiv; tieneSus(p,s)

tieneSus(p,vender(n,a,s)) &equiv; tieneSus(p,s)

tieneSus(p,infSus(a,b,s)) &equiv; p = b &or; tieneSus(p,s)

obtenerSus(p,infSus(a,b,s)) &equiv; if p = b then a else obtenerSus(p,s) fi

obtenerSus(p,registrarPruducto(a,n,s)) &equiv; obtenerSus(p,s)

obtenerSus(p,comprar(n,a,s)) &equiv; obtenerSus(p,s)

obtenerSus(p,vender(n,a,s)) &equiv; obtenerSus(p,s)

quitarBuenos(&empty;,s) &equiv; &empty;

quitarBuenos(Ag(p,c),s) &equiv; if tieneSus(p,s) then if mínimo(p,s) > compras(p,s) + compras(obtenerSus(p,s),s) - ventas(p,s) - ventas(obtenerSus(p,s),s) then Ag(p,quitarBuenos(c,s)) else quitarBuenos(c,s) fi else if mínimo(p,s) > compras(p,s) - ventas(p,s) then Ag(p,quitarBuenos(c,s)) else quitarBuenos(c,s) fi

'''Fin TAD'''

== Ejercicio 13 ==

== Ejercicio 14 ==

== Ejercicio 15 ==

== Ejercicio 16 ==

== Ejercicio 17 ==

== Ejercicio 18 ==

== Ejercicio 19 ==

== Ejercicio 20 ==

== Ejercicio 21 ==

== Ejercicio 22 ==
@@ Línea 3: / Línea 3: @@
 === a ===
-duplicar: secu(&alpha;) &rarr; secu(&alpha;)
+duplicar: secu(&alpha;)&rarr;secu(&alpha;)
-duplicar(s) &equiv; if vacía?(s) then &lang;&rang; else prim(s) &bull; prim(s) &bull; duplicar(fin(s)) fi
+duplicar(s)&equiv;if vacía?(s) then &lang;&rang; else prim(s)&bull;prim(s)&bull;duplicar(fin(s)) fi
 === b ===
@@ Línea 11: / Línea 11: @@
 &bull;&le;&bull;: secu(&alpha;) x secu(&alpha;) &rarr; bool
-s &le; t &equiv; if &not;(vacía?(s) &or; vacía?(t)) then prim(s) < prim(t) &or; (prim(s) = prim(t) &and; fin(s) &le; fin(t)) else vacía?(s) fi
+s &le; t &equiv; if &not;(vacía?(s) &or; vacía?(t)) then prim(s) < prim(t) &or; (prim(s)=prim(t) &and; fin(s)&le;fin(t)) else vacía?(s) fi
 === c ===
@@ Línea 151: / Línea 151: @@
 ntn: conj(secu(&alpha;)) x secu(&alpha;) &rarr;  conj(secu(&alpha;))
-[ToDo]
+blablabla
-Necesito:
-* Ver si CADA secuencia del conjunto de entrada es o no subsecuencia de la secuencia de entrada (2do param)
-*  &rarr; Definir función auxiliar '''''esSubsecuencia(a &bull; s, b &bull; t)''''', <small>a,b:&alpha;, s,t:secu(&alpha;)</small>
-*  &rarr; Definir '''''ntn(Ag(a &bull; s, w), b &bull; t)'''''<small>, w: conj(secu(&alpha;))</small>
-* Ver si CADA secuencia del conjunto DE SALIDA es o no subsecuencia de alguna otra secuencia del conjunto de salida
-*  &rarr; Puedo usar la misma función auxiliar esSubsecuencia()
 == Ejercicio 5 ==
@@ Línea 171: / Línea 162: @@
 === b ===
-    // Defino auxiliar que cuente cantNodos en una secuencia de arboles ternarios:
-    cantNodos: secu( at( &alpha; ) ) -> nat
-    cantNodos( t · <> ) &equiv; if t &ne; nil then 1 else 0
-    cantNodos( t · s )  &equiv; if t &ne; nil then 1 + cantNodos(s)
-                                     else cantNodos(s)
-    acotado?: at(&alpha;) x nat -> bool
+blablabla
-    acotado?(nil, k) &equiv; true
-    // Recibo el arbol ternario como sus partes separadas: (izq,medio,der,raiz)
-    acotado?(tern(i,m,d,r), k) &equiv; if cantNodos(i · m · d · <>) &le; k then
-                                     acotado?(i) &and; acotado?(m) &and; acotado?(d)
-                                 else
-                                     false
 == Ejercicio 6 ==
@@ Línea 194: / Línea 169: @@
 === a ===
-    altura: rosetree(&alpha;) &rarr; nat
+altura: rosetree(&alpha;) &rarr; nat
-    altura(rose(r, &lang;&rang;)) &equiv; 1
+altura(rose(r,&lang;&rang;)) &equiv; 1
-    altura(rose(r, e &bull; s)) &equiv; 1 + altura(masAlta(r, e &bull; s))
+altura(rose(r,e &bull; s)) &equiv; 1 + altura(masAlta(r,e &bull; s))
-    masAlta: &alpha; x secu(rosetree(&alpha;)) &rarr; rosetree(&alpha;)
+masAlta: &alpha; x secu(rosetree(&alpha;)) &rarr; rosetree(&alpha;)
-    masAlta(a, s) &equiv; if vacía?(s) then
+masAlta(a,s) &equiv; if vacía?(s) then rose(a,&lang;&rang;) else if altura(prim(s)) > altura(masAlta(a,fin(s))) then prim(s) else masAlta(a,fin(s)) fi fi
-                        rose(a,&lang;&rang;)
-                    else if altura(prim(s)) > altura(masAlta(a, fin(s))) then
-                            prim(s)
-                        else
-                            masAlta(a, fin(s))
-                        fi
-                    fi
 === b ===
-    cantHojas: rosetree(&alpha;) &rarr; nat
+cantHojas: rosetree(&alpha;) &rarr; nat
-    cantHojas(r) &equiv; if esHoja?(r) then
+cantHojas(r) &equiv; if esHoja?(r) then 1 else sumarHojas(hijos(r)) fi
-                   else
+esHoja?: rosetree(&alpha;) &rarr; bool
-                       sumarHojas(hijos(r))
-                   fi
+esHoja?(r) &equiv; vacía?(hijos(r))
+sumarHojas: secu(rosetree(&alpha;)) &rarr; nat
-    esHoja?: rosetree(&alpha;) &rarr; bool
+sumarHojas(s) &equiv; if vacía?(s) then 0 else cantHojas(prim(s)) + sumarHojas(fin(s)) fi
-    esHoja?(r) &equiv; vacía?(hijos(r))
-    sumarHojas: secu( rosetree(&alpha;) ) &rarr; nat
-    sumarHojas(s) &equiv; if vacía?(s) then
-                    else
-                        cantHojas(prim(s)) + sumarHojas(fin(s))
-                    fi
 === c ===
-    podar: rosetree(&alpha;) a &rarr; rosetree(&alpha;) {&not;esHoja?(a)}
+podar: rosetree(&alpha;) a &rarr; rosetree(&alpha;) {&not;esHoja?(a)}
-    podar(r) &equiv; rose(raíz(r), podadora(hijos(r)))
+podar(r) &equiv; rose(raíz(r),podadora(hijos(r)))
+podadora: secu(rosetree(&alpha;)) &rarr; secu(rosetree(&alpha;))
-    podadora: secu(rosetree(&alpha;)) &rarr; secu(rosetree(&alpha;))
+podadora(s) &equiv; if vacía?(s) then s else if esHoja?(prim(s)) then podadora(fin(s)) else podar(prim(s)) &bull; podadora(fin(s)) fi fi
-    podadora(s) &equiv; if vacía?(s) then
-                      s
-                  else
-                      if esHoja?(prim(s)) then
-                          podadora(fin(s))
-                      else
-                          podar(prim(s)) &bull; podadora(fin(s))
-                      fi
-                  fi
 === d ===
-    obtenerRamas: rosetree(&alpha;) &rarr; secu(secu((&alpha;))
+obtenerRamas: rosetree(&alpha;) &rarr; secu(secu((&alpha;))
-    obtenerRamas(r) &equiv; if esHoja?(r) then
+obtenerRamas(r) &equiv; if esHoja?(r) then (raíz(r) &bull; &lang;&rang;) &bull; &lang;&rang; else if long(hijos(r)) = 1 then insertarTodos(raíz(r),obtenerRamas(prim(hijos(r)))) else insertarTodos(raíz(r),obtenerRamas(prim(hijos(r)))) & obtenerRamas(rose(raíz(r),fin(hijos(r)))) fi fi
-                          (raíz(r) &bull; &lang;&rang;) &bull;&lang;&rang;
-                      else
+insertarTodos: &alpha; x secu(secu(&alpha;)) &rarr; secu(secu(&alpha;))
-                          if long(hijos(r)) = 1 then
-                              insertarTodos(raíz(r), obtenerRamas(prim(hijos(r))))
+insertarTodos(a,s) &equiv; if vacía(s) then &lang;&rang; else (a &bull; prim(s)) &bull; insertarTodos(a,fin(s)) fi
-                          else
-                              insertarTodos(raíz(r),obtenerRamas(prim(hijos(r)))) & obtenerRamas(rose(raíz(r),fin(hijos(r))))
-                          fi
-                      fi
-    insertarTodos: &alpha; x secu(secu(&alpha;)) &rarr; secu(secu(&alpha;))
-    insertarTodos(a,s) &equiv; if vacía(s) then
-                            &lang;&rang;
-                         else
-                             (a &bull; prim(s)) &bull; insertarTodos(a,fin(s))
-                         fi
 === e ===