Recuperatorio Segundo Parcial 1er Cuat 2007 (Paradigmas)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Ejercicio 1: Programación Lógica[editar]

Dado un grafo G (no dirigido), representado por una lista de nodos y una lista de ejes (cada eje esta dado por un par de nodos), se desea hallar con Prolog un cubrimiento mınimo de ejes por nodos. Vale decir, se busca un conjunto S de nodos de G tal que todos los ejes del grafo incidan en S (tengan algun extremo en S) y ademas S sea lo mas chico posible. Escribir los siguientes predicados respetando en cada caso la instanciacion pedida. Ninguno de los predicados perdidos debe dar soluciones repetidas. No utilizar cut (!) ni predicados de alto orden (como setof). La unica excepcion es el not, que esta permitido.

Item A[editar]

Escribir el predicado incide(+G, +N, +S) que evalua si en el grafo G, si algun eje de S incide en el nodo N.

Ejemplos

incide(([a, b, c], [(a,b), (b,c), (a,c)]), a, [(a,b), (a,c), (d,f)]).
Yes
incide(([a, b, c], [(a,b), (b,c), (a,c)]), a, [(a,b), (a,c), (b, c), (d,f)]).
No
incide(([a, b, c], [(a,b), (b,c), (a,c)]), a, [(a, b),(b, c)]).
No

Respuesta

incideNodo(N,(N,_)).
incideNodo(N,(_,N)).

incide((_,ES),N,[]).
incide((NS,ES),N,[S|SS]) :- member(S,ES), incideNodo(N,S), incide((NS,ES),N,SS).
incide((NS,ES),N,[S|SS]) :- not(member(S,ES)), incide((NS,ES),N,SS).

Item B[editar]

Escribir el predicado cubre(+G, +S) que evalua si el conjunto de nodos S cubre a todos los ejes de G. Ejemplos

cubre(([a, b, c], [(a,b), (b,c), (a,c)]), [a]).
No
cubre(([a, b, c], [(a,b), (b,c), (a,c)]), [a,c]).
Yes

Respuesta

ejeCubierto(E,[N|_]) :- incideNodo(N,E).
ejeCubierto(E,[N|NS]) :- not(incideNodo(N,E)),ejeCubierto(E,NS).

cubre((_,ES),SS) :- ejesCubiertos(ES,SS).
ejesCubiertos([],_).
ejesCubiertos([E|ES],SS) :- ejeCubierto(E,SS), ejesCubiertos(ES,SS).

Item C[editar]

Escribir el predicado minCub(+G, -M) que determina en M un mınimo cubrimiento de G (podrıa haber varias soluciones). Ejemplo

cubrimientoMinimo(([a, b, c], [(a,b), (b,c), (a,c)]), C).
C = [b, c] ;
C = [a, c] ;
C = [a, b] ;
No

Respuesta

Ejercicio 2: Resolución[editar]

Utilizando resolución SLD si es posible, o general si no, determinar si es tautología, contradicción, o nada:

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle [(\forall x \exists y P(x, y)) \land (\forall x \forall y P(x,y) \Rightarrow P(y, x))] \Rightarrow (\forall y \exists x P(x, y))}

Respuesta

Pareciera que es tautología, por el teorema de la deducción (semántico) de Lógica y Computabilidad, sabemos que esta fórmula es válida si y solo si tomamos el antecedente como premisa y podemos probar el consecuente. Tomemos cada uno por separado.

Antecedente 1

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall x \exists y P(x, y)}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall x P(x, f(x))}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \{P(x, f(x))\} \;}

Antecedente 2

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall x \forall y P(x,y) \Rightarrow P(y, x)}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall x \forall y (\neg P(x,y) \lor P(y, x))}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \neg P(x,y) \lor P(y, x)}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \{\neg P(x,y), P(y, x)\} \;}

Consecuente negado (Goal)

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \neg \forall y \exists x P(x, y)}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists y \neg \exists x P(x, y)}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists y \forall x \neg P(x, y)}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall x \neg P(x, c)}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \{\neg P(x, c)\} \;}

Resolvemos usando SLD (se puede porque todas son cláusulas de Horn)

  1. Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \{P(x, f(x))\} \;}
  2. Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \{\neg P(y,z), P(z, y)\} \;}
  3. Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \{\neg P(w, c)\} \;}
  4. 3 con 2: Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \{\neg P(c, z)\} \;\; \sigma = \{y \mapsto c, w \mapsto z\}}
  5. 4 con 1: Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \{\square\} \;\; \sigma = \{x \mapsto c, z \mapsto f(c)\}}

Ejercicio 3: Smalltalk[editar]

Ejercicio 4: Subtipado[editar]

Contar cuántos tipos T existen tales que:

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Top \rightarrow \{x: Bool, y:Nat, z:Int\} <: \ T \ <: (Nat \rightarrow Top) \rightarrow \{x:Int, y:Int\} }

Nota: Las permutaciones de un registro con los mismos labels se consideran un mismo tipo.

Respuesta

Para calcularlo uso algo no probado pero que es bastante razonable, que la cantidad de tipos X tales que: Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow B <: X <: C \rightarrow D} es la cantidad de tipos entre C y A y entre B y D. O sea, usando como notación "entre(A, B)" como la cantidad de tipos no estrictos entre A y B:

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle entre(A \rightarrow B, C \rightarrow D) = entre(C, A) \times entre(B, D)}

Voy a calcular esas cantidad de forma no estricta y al final restaré 2 por los dos tipos originales que no queremos contar.

1) Entonces, la cantidad de tipos Y tales que Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Nat \rightarrow Top <: Y <: Top } es igual a la cantidad de supertipos de Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Nat \rightarrow Top } .

  • Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle sup(Nat \rightarrow Top) = sub(Nat) \times sup(Top) = 2 \times 1= 2} (recordar que contamos sub y sup no estrictos)

2) Para calcular la cantidad de tipos Z tales que Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \{x: Bool, y:Nat, z:Int\} <: \ Z \ <: \{x:Int, y:Int\} } podemos notar que sería:

  • Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle entre(Bool, Int) = 3} , Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle entre(Nat, Int) = 2 } , Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle entre(Int, Top) + 1 = 4 } (el +1 viene de que z podría no esta directamente). Entonces la cantidad de posibles Z Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle = entre(Bool, Int)\times entre(Nat, Int) \times (entre(Int, Top) + 1) = 3 \times 2 \times 4 = 24 }

Entonces, usando 1) y 2) la cantidad final de tipos sería Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 2 \times 24 - 2 = 46} .