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