AED2 resumen 2C-17

Ejercicio 1

a

duplicar: secu(α)→secu(α)

duplicar(s)≡if vacía?(s) then ⟨⟩ else prim(s)•prim(s)•duplicar(fin(s)) fi

b

•≤•: secu(α) x secu(α) → bool

s ≤ t ≡ if ¬(vacía?(s) ∨ vacía?(t)) then prim(s) < prim(t) ∨ (prim(s)=prim(t) ∧ fin(s)≤fin(t)) else vacía?(s) fi

c

reverso: secu(α)→secu(α)

reverso(s) ≡ if vacía?(s) then s else reverso(fin(s)) º prim(s) fi

d

capicúa: secu(α)→bool

capicúa(s) ≡ s = reverso(s)

e

esPrefijo?: secu(α) x secu(α) → bool

esPrefijo?(⟨⟩,t) ≡ true

esPrefijo?(e • s,t) ≡ if vacía?(t) then false else e = prim(t) ∧ esPrefijo?(s,fin(t)) fi

f

buscar: secu(α) x secu(α) → nat

buscar(⟨⟩,t) ≡ true

buscar(e • s,t) ≡ if esPrefijo?(e • s,t) then 0 else 1 + buscar(e • s,fin(t)) fi

g

estaOrdenada?: secu(α) → bool

estaOrdenada?(⟨⟩) ≡ true

estaOrdenada?(e • s) ≡ if vacía?(s) then true else e ≤ prim(s) ∧ estaOrdenada?(s) fi

h

insertarOrdenada: secu(α) so x α → secu(α) {estaOrdenada?(so)}

insertarOrdenada(⟨⟩,a) ≡ a • ⟨⟩

insertarOrdenada(e • s,a) ≡ if a ≤ e then a • e • s else e • insertarOrdenada(s,a) fi

i

cantidadApariciones: secu(α) x α → nat

cantidadApariciones(⟨⟩,a) ≡ 0

cantidadApariciones(e • s,a) ≡ if e = a then 1 + cantidadApariciones(s,a) else cantidadApariciones(s,a) fi

j

aux(s,s,t): secu(α) x secu(α) x secu(α) → bool

aux(⟨⟩,s,t) ≡ true

aux(e • u,s,t) ≡ cantidadApariciones(s,e) = cantidadApariciones(t,e) ∧ aux(u,s,t)

esPermutación?: secu(α) x secu(α) → bool

esPermutación?(s,t) ≡ aux(s,s,t)

k

combinar: secu(α) a x secu(α) b → secu(α) {estaOrdenada?(a) ∧ estaOrdenada?(b)}

combinar(s,t) ≡ if vacía(s) then t else combinar(s,insertarOrdenada(t,prim(s)) fi

Ejercicio 2

a

#hojas: ab(α) → nat

#hojas(nil) ≡ 0

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

b

degeneradoAIzquierda: ab(α) → bool

degeneradoAIzquierda(a) ≡ nil?(a) ∨L if esHoja?(a) then true else nil?(der(a)) ∧ degeneradoAIzquierda(izq(a)) fi

c

zigZag: ab(α) → bool

zigZag(a) ≡ nil?(a) ∨L esHoja?(a) ∨L if nil?(izq(a)) then nil?(der(der(a))) ∧ zigZag(der(a)) else if nil?(izq(a)) then nil?(izq(izq(a))) ∧ zigZag(izq(a)) else false fi fi

d

ultimoNivelCompleto: ab(α) → nat

ultimoNivelCompleto(nil) ≡ 0

ultimoNivelCompleto(bin(a,e,b)) ≡ 1 + min(ultimoNivelCompleto(a),ultimoNivelCompleto(b))

e

espejo: ab(α) → ab(α)

espejo(a) ≡ if nil?(a) then a else bin(espejo(der(a)),raiz(a),espejo(izq(a)) fi

f

esSimétrico?: ab((α) → bool

esSimétrico?(a) ≡ a = espejo(a)

Ejercicio 3

a

agregarTodos: α x conj(conj(α)) → conj(conj(α))

agregarTodos(n,c) ≡ if ∅?(c) then Ag(Ag(n,∅),∅) else Ag(Ag(n,dameUno(c)),agregarTodos(n,sinUno(c))) fi

partesDe: conj(nat) → conj(conj(nat))

partesDe(c) ≡ if ∅?(c) then c else agregarTodos(dameUno(c),partesDe(sinUno(c))) ∪ partesDe(sinUno(c)) fi

b

combinacionesDeK: conj(α) x nat → conj(conj(α))

combinacionesDeK(∅, k) ≡ ∅

combinacionesDeK(Ag(e,c), k) ≡ if k = 0 ∨ #(Ag(e,c)) < k then ∅ else agregarTodos(e,combinacionesDeK(c,k-1)) ∪ combinacionesDeK(c,k) fi

Ejercicio 4

ntn: conj(secu(α)) x secu(α) → conj(secu(α))

blablabla

Ejercicio 5

a

nivelNormal?: at(α) x nat k → bool { ¬ k = 0 }

nivelNormal?(a,k) ≡ nil?(a) ∨L if k = 1 then ¬(nil?(izq(a)) ∨ nil?(med(a)) ∨ nil?(der(a))) else nivelNormal?(izq(a),k-1) ∧ nivelNormal?(med(a),k-1) ∧ nivelNormal?(der(a),k-1) fi

b

blablabla

Ejercicio 6

a

altura: rosetree(α) → nat

altura(rose(r,⟨⟩)) ≡ 1

altura(rose(r,e • s)) ≡ 1 + altura(masAlta(r,e • s))

masAlta: α x secu(rosetree(α)) → rosetree(α)

masAlta(a,s) ≡ if vacía?(s) then rose(a,⟨⟩) else if altura(prim(s)) > altura(masAlta(a,fin(s))) then prim(s) else masAlta(a,fin(s)) fi fi

b

cantHojas: rosetree(α) → nat

cantHojas(r) ≡ if esHoja?(r) then 1 else sumarHojas(hijos(r)) fi

esHoja?: rosetree(α) → bool

esHoja?(r) ≡ vacía?(hijos(r))

sumarHojas: secu(rosetree(α)) → nat

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

c

podar: rosetree(α) a → rosetree(α) {¬esHoja?(a)}

podar(r) ≡ rose(raíz(r),podadora(hijos(r)))

podadora: secu(rosetree(α)) → secu(rosetree(α))

podadora(s) ≡ if vacía?(s) then s else if esHoja?(prim(s)) then podadora(fin(s)) else podar(prim(s)) • podadora(fin(s)) fi fi

d

obtenerRamas: rosetree(α) → secu(secu((α))

obtenerRamas(r) ≡ if esHoja?(r) then (raíz(r) • ⟨⟩) • ⟨⟩ 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: α x secu(secu(α)) → secu(secu(α))

insertarTodos(a,s) ≡ if vacía(s) then ⟨⟩ else (a • prim(s)) • insertarTodos(a,fin(s)) fi

e

devolverNivel: nat n x rosetree(α) → secu(α) {¬ n = 0}

devolverNivel(n,r) ≡ agarrador(n,obtenerRamas(r))

agarrador: nat n x secu(secu(α)) → secu(α) {¬ n = 0}

agarrador(n,s) ≡ if vacía(s) then ⟨⟩ else if long(prim(s)) ≥ n then obtener(n,prim(s)) • agarrador(n,fin(s)) else agarrador(n,fin(s)) fi fi

obtener: nat n x secu(&alpha) s → α {(¬ n = 0) ∧ long(s) ≥ n}

obtener(n,s) ≡ if n = 1 then prim(s) else obtener(n-1,fin(s)) fi

f

masLargasConRepetidos: rosetree(α) → conj(secu(α))

masLargasConRepetidos(r) ≡ soloConRepetidos(soloUnTam(altura(r),obtenerRamas(r)))

tieneRepetido: secu(α) → bool

tieneRepetido(s) ≡ (¬ vacía(s)) ∧L (esta?(prim(s),fin(s)) ∨ tieneRepetido(fin(s)))

soloConRepetidos: secu(secu(α)) → conj(secu(α))

soloConRepetidos(s) ≡ if vacía(s) then ∅ else if tieneRepetido(prim(s)) then Ag(prim(s),soloConRepetidos(fin(s))) else soloConRepetidos(fin(s)) fi fi

soloUnTam: nat n x secu(secu(α)) → secu(secu(α)) {¬ n = 0}

soloUnTam(n,s) ≡ if vacía?(s) then ⟨⟩ else if long(s) = n then prim(s) • soloUnTam(n,fin(s)) else soloUnTam(n,fin(s)) fi fi

Ejercicio 7

evaluar(cte(a),n) ≡ a

evaluar(x,n) ≡ n

evaluar(a + b, n) ≡ evaluar(a,n) + evaluar(b,n)

evaluar(a . b, n) ≡ evaluar(a,n) . evaluar(b,n)

esRaíz: polinomio x nat → bool

esRaíz(a,n) ≡ 0 = evaluar(a,n)

Ejercicio 8

trayectoria(ubicar(c)) ≡ c • ⟨⟩

trayectoria(arriba(r)) ≡ ⟨π1(posiciónActual(r)),π2(posiciónActual(r)) + 1⟩ • trayectoria(r)

trayectoria(abajo(r)) ≡ ⟨π1(posiciónActual(r)),π2(posiciónActual(r)) - 1⟩ • trayectoria(r)

trayectoria(derecha(r)) ≡ ⟨π1(posiciónActual(r)) + 1,π2(posiciónActual(r))⟩ • trayectoria(r)

trayectoria(izquierda(r)) ≡ ⟨π1(posiciónActual(r)) - 1,π2(posiciónActual(r))⟩ • trayectoria(r)

posiciónActual(r) ≡ prim(trayectoria(r))

cuántasVecesPasó(c,r) ≡ cantidadApariciones(Trayectoria(r),c)

másALaDerecha(r) ≡ maxX(trayectoria(r))

maxX: secu(coordenada) s → coordenada {¬ vacía?(s)}

maxX(e • s) ≡if vacía?(s) then π1(e) else max(π1(e),π1(maxX(s)) fi

Ejercicio 9

TAD Electroimán

Igualdad observacional

(∀ i1:electroimán)((∀ i2:electroimán)(i1 =obs i2 ⇔ ((cinta(i1) = cinta(i2) ∧ imánPrendido?(i1) = imánPrendido?(i2)) ∧L (imánPrendido?(i1) ⇒L (imánCargado?(i1) = imánCargado?(i2))))))

Genero electroimán

Usa Bool, Nat, Cinta

Exporta Genero, Generadores, Observadores, Otras operaciones

Axiomas

cinta(arrancar(c)) ≡ c

cinta(prender(e)) ≡ if celdaActualOcupada?(cinta(e)) then sacarElem(cinta(e)) else cinta(e) fi

cinta(apagar(e)) ≡ if imánCargado?(e) then ponerElem(cinta(e)) else cinta(e) fi

cinta(←(e)) ≡ ←(cinta(e))

cinta(→(e)) ≡ →(cinta(e))

imánPrendido?(arrancar(c)) ≡ false

imánPrendido?(prender(e)) ≡ true

imánPrendido?(apagar(e)) ≡ false

imánPrendido?(→(e)) ≡ imánPrendido?(e)

imánPrendido?(←(e)) ≡ imánPrendido?(e)

imánCargado?(prender(e)) ≡ celdaActualOcupada?(e)

imánCargado?(→(e)) ≡ imánCargado?(e) ∨ celdaActualOcupada?(→(e))

imánCargado?(←(e)) ≡ imánCargado?(e) ∨ celdaActualOcupada?(←(e))

celdaActualOcupada?(e) ≡ celdaActualOcupada?(cinta(e))

#giros←(arrancar(c) ≡ 0

#giros←(prender(e) ≡  #giros←(e)

#giros←(apagar(e) ≡  #giros←(e)

#giros←(→(e) ≡  #giros←(e)

#giros←(←(e) ≡ 1 + #giros←(e)

#giros→(arrancar(c) ≡ 0

#giros→(prender(e) ≡  #giros→(e)

#giros→(apagar(e) ≡  #giros→(e)

#giros→(→(e) ≡ 1 + #giros→(e)

#giros→(←(e) ≡ #giros→(e)

Fin TAD

TAD Cinta

Igualdad observacional

(∀ c1:cinta)((∀ c2:cinta)(c1 =obs c2 ⇔ (#celdas(c1) = #celdas(c2) ∧L (celdaActual(c1) = celdaActual(c2) ∧ #giros←(c1) = #giros←(c2) ∧ #giros→(c1) = #giros→(c2) ∧ (∀i:nat)(i<#celdas(c1) ⇒(celdaOcupada?(i,c1) = celdaOcupada?(i,c2)))))))

Genero cinta

Usa Bool, Nat

Exporta Genero, Generadores, Observadores, Otras operaciones

Otras operaciones

cuentaOcupados: nat x cinta → nat

Axiomas

#celdas(arrancar(n)) ≡ n

#celdas(ponerElem(c)) ≡ #celdas(c)

#celdas(sacarElem(c)) ≡ #celdas(c)

#celdas(←(c)) ≡ #celdas(c)

#celdas(→(c)) ≡ #celdas(c)

#giros←(arrancar(n)) ≡ 0

#giros←(ponerElem(c)) ≡ #giros←(c)

#giros←(sacarElem(c)) ≡ #giros←(c)

#giros←(←(c)) ≡ 1 + #giros←(c)

#giros←(→(c)) ≡ #giros←(c)

#giros→(arrancar(n)) ≡ 0

#giros→(ponerElem(c)) ≡ #giros→(c)

#giros→(sacarElem(c)) ≡ #giros→(c)

#giros→(←(c)) ≡ #giros→(c)

#giros→(→(c)) ≡ 1 + #giros→(c)

celdaActual(arrancar(n)) ≡ 0

celdaActual(ponerElem(c)) ≡ celdaActual(c)

celdaActual(sacarElem(c)) ≡ celdaActual(c)

celdaActual(←(c)) ≡ if celdaActual(c) = 0 then #celdas(c) - 1 else celdaActual(c) - 1 fi

celdaActual(→(c)) ≡ if celdaActual(c) = #celdas(c) - 1 then 0 else celdaActual(c) + 1 fi

celdaOcupada?(n,arrancar(a)) ≡ false

celdaOcupada?(n,ponerElem(c)) ≡ if n = celdaActual(c) then true else celdaOcupada?(n,c) fi

celdaOcupada?(n,sacarElem(c)) ≡ if n = celdaActual(c) then false else celdaOcupada?(n,c) fi

celdaOcupada?(n,←(c)) ≡ celdaOcupada?(n,c)

celdaOcupada?(n,→(c)) ≡ celdaOcupada?(n,c)

celdaActualOcupada?(c) ≡ celdaOcupada?(celdaActual(c),c)

#elem(c) ≡ cuentaOcupados(0,c)

cuentaOcupados(n,c) ≡ 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