Página web: td/lfyacs.uns.edu.ar/~td/lfya2013/downloads/TEORICAS/t01.2013.presenta… · técnicas...

técnicas de pruebas

computacionales

LENGUAJESLENGUAJESFORMALES FORMALES

YYAUTAUTÓÓMATASMATAS

11

presentación

Cátedra:Profesora

Ana G. Maguitman consultas: viernes 10hs (oficina 205) email: [email protected]

AsistenteTelma Delladio

consultas: jueves 11hs (hall DCIC) email: [email protected]

AyudantesCecilia BaggioVirginia CardosoMariana EtcheberNicolás KomañskyMaría Virginia SabandoMaximiliano Vera

Página web: http://cs.uns.edu.ar/~td/lfya


computacionales



22

presentación

Régimen de cursado:Dos parciales y un recuperatorio

Primer Parcial fecha: 30 de septiembreunidades 1, 2, 3

Segundo Parcialfecha: 11 de noviembre unidades 4, 5 y 6

Recuperatoriofecha: 27 de noviembre

CalificacionesA, B o C: aprobadoD: desaprobado

Para promocionar se necesitaobtener A en ambos parciales y aprobar un examen teórico el día 27 de noviembre


computacionales



33

preguntas


computacionales



44

técnicas de pruebas computacionales

CONTENIDOTeoremas y pruebas informales [G2.1]. Pruebas exhaustivas [G2.1]. Pruebas directas [G2.1]. Contraposición [G2.1]. Contradicción [G2.1]. Inducción [G2.2]. Primer principio de inducción [G2.2]. Pruebas por inducción matemática [G2.2]. Segundo principio de inducción [G2.2]. Pruebas de correctitud de un algoritmo [G1.6,G2.3].

GERSTING, JUDITH L. “Mathematical Structures forComputer Science: A Modern Approach to DiscreteMathematics”. W H Freeman & Co, 2006.


computacionales



55

conjeturas

En la práctica o investigación observamos casos en los que Q es verdadero siempre que P es verdadero.

A partir de estas experiencias se puede formular la conjetura:

Si P es verdadero entonces Q es verdadero.

P→Q


computacionales



66

conjeturas vs. teoremas

Sin embargo, es necesario utilizar algún tipo de razonamiento deductivo para verificar la verdad o falsedad de una conjetura. Cuando una conjetura es probada pasa a

ser un teorema. O podríamos encontrar un contraejemplo

para mostrar que la conjetura es falsa, un caso en que P sea verdadera y Q falsa.


computacionales



77

técnicas de prueba

Existen diversas técnicas para probar que una conjetura es verdadera o mostrar que es falsa.• Mostrar que es falsa utilizando un

contraejemplo.• Prueba exhaustiva.• Prueba directa.• Contrapositiva.• Contradicción.• Prueba por inducción.


computacionales



88

contraejemplos

Ejemplo:¿Es la siguiente conjetura un teorema?

“para cada entero positivo n, n! ≤ n2”

n =1, n! = 1, n2 = 1 SIn =2, n! = 2, n2 = 4 SIn =3, n! = 6, n2 = 9 SIn =4, n! = 24, n2 = 16 NO (contraejemplo)


computacionales



99

6553712

25712

1712

512

312

4

3

2

1

0

2

2

2

2

2

más sobre conjeturas, teoremas y contraejemplos

=+

=+

=+

=+

=+En el siglo XVII Fermat conjeturóque los números de la forma son primos para todo entero positivo n.

122 +n

417,700,6641297,967,294,412

52

⋅==+

100 años más tarde Euler refutó esta conjetura mediante un contraejemplo:

no es primo

http://en.wikipedia.org/wiki/Image:Pierre_de_Fermat.jpg


computacionales



1010

pruebas exhaustivas

Los contraejemplos sirven para probar que algo es falso pero generalmente las pruebas basadas en ejemplos no son útiles para probar que algo es verdadero. Sin embargo, cuando las conjeturas se refieren a una colección finita podemos mostrar que la conjetura es verdadera para cada elemento de la colección. A esto se lo llama prueba exhaustiva.


computacionales



1111

pruebas exhaustivas

Ejemplo:“si un entero entre 1 y 13 es divisible por

6 también es divisible por 3”Prueba

6 es divisible por 6, también es divisible por 3

12 es divisible por 6, también es divisible por 3

1, 2 ,3, 4, 5, 7, 8, 9, 10, 11, y 13: no son divisibles por 6.


computacionales



1212

prueba directa

La manera más natural de probar P → Q (si P es verdadero, entonces Q es verdadero) es mediante la prueba directa:Asumiendo la hipótesis P deducir Q.

La prueba puede serFormal (construyendo un argumento válido

basado en la lógica).Menos formal.


computacionales



1313

prueba directa

Ejemplo“si x e y son enteros pares, entonces el

producto xy es también un entero par”Prueba

Sean x = 2m, y=2n.Luego xy=2m2n=2(2mn).


computacionales



1414

prueba por contrapositiva

A veces es difícil probar directamente la conjetura P → Q. Podría ser más fácil probar ¬Q → ¬P. A esto se lo conoce como prueba por contrapositiva. ¬Q → ¬P es la contrapositiva de P → Q.

Ejemplo“para un entero x, si x2 es impar, entonces

x es impar”Podemos probarlo mostrando que “si x es

par, entonces x2 es par” (lo cual ya fue realizado).


computacionales



1515

prueba por contradicción

Las pruebas por contradicción se obtienen asumiendo que la conjetura es falsa y mostrando que esa suposición implica que una propiedad conocida es falsa.Para probar P→Q asumo PΛ¬Q y llego a una contradicción. Si no existe una premisa P, para probar Q, asumo ¬Q y llego a una contradicción.A esta técnica de prueba también se la conoce como prueba por el absurdo.


computacionales



1616


Ejemplo“Si x + x = x, entonces x = 0”.Prueba

Asumir x + x = x y x ≠ 0, entonces 2x = x y dado que x ≠ 0, podemos dividir ambos lados de 2x = x por x. Obtenemos 2 = 1 (contradicción).


computacionales



1717


EjemploProbar que no es racionalPruebaAsumamos que es racional.

Entonces =p/q donde q≠0 y p,q son enteros y no tienen factores comunes

2

22

2 = p2/q2

2 q2= p2

2 divide a p2

2 divide a p4 divide a p2

2 q2 = 4xq2 = 2x

2 divide a q2

2 divide a q 2 divide a p y q (contradicción)


computacionales



1818

ejercicios

¿Dónde está el error?Sean a y b enteros no negativos tales

que a = b.a = ba2 = aba2 − b2 = ab − b2

(a + b)(a − b) = (a − b)ba + b = b2b = b2 = 1


computacionales



1919

resumiendo

Técnica de prueba

Método para probar P→Q

Acotaciones

prueba exhaustiva Demostrar P → Q para todos los casos posibles

Sólo puede ser usado para probar un número finito de casos

prueba directa Asumir P y deducir Q Método más estándar

prueba por contrapositiva

Asumir ¬Q y deducir ¬P

Usar si ¬Q tiene más potencia como hipótesis que P.


Asumir P∧¬Q, deducir una contradicción

Usar cuando ¬Q nos lleva a un absurdo.


computacionales



2020 1. P(1)2. Para todo entero positivo k,

P(k) → P(k+1)

Entonces P(n) para todo entero n a partir de 1.

caso base

paso inductivo

primer principio de inducción

Sea P(n) una propiedad definida para el entero n y supongamos:

hipótesis inductiva


computacionales



2121


EjemploProbar para n > 0

Prueba Caso base: n = 1, es verdadero ya que

0+1 = 1(1+1)/2Hipótesis inductiva:

asumir que es verdadero para n=k, es decir,

Paso inductivo:probar que es verdadero para n=k+1, es decir

2/)1(0

+=∑=

nnin

i

2/)1(0

+=∑=

kkik

i

2/)2)(1(1

0++=∑

+

=

kkik

i


computacionales



2222


∑∑=

+

=

++=k

i

k

iiki

0

1

01

)1(2/)1( +++= kkk

2/)2)(1( ++= kk

usando hipótesis inductiva


computacionales



2323


EjemploLos números de Fibonacci se definen como:

Los primeros números de Fibonacci son:0, 1, 1, 2, 3, 5, 8, 13, 21,…

1,1,0

11

10

≥+===

−+ nfffff

nnn

Leonardo Fibonacci(1170 – 1250)


computacionales



2424


Mostrar que para todo n ≥ 1.

PruebaCaso base:

Probar

010201111 =⋅=⋅=⋅ +− ffff

011)1( 2121 =−=−+f

1211111 )1(−+=⋅ +− fff

nnnn fff )1(2

11 −+=⋅ +−


computacionales



2525


Paso inductivo:Asumamos

Probemos

kkkk fff )1(2

11 −+=⋅ +−

1212 )1( +++ −+=⋅ k

kkk fff

121

111

111

111

2112

)1()1(

)1()(

)1(

)(

++

+++

+−+

+−+

+++

−+=−+⋅=

−++=

−−⋅+⋅=

+⋅=+=⋅

kk

kkk

kkkk

kkkkk

kkkkkkkk

fff

fff

ffff

ffffffff


computacionales



2626

seguimos con inducción …

Los métodos de inducción pueden ser aplicados a estructuras diferentes a los enteros. Por ejemplo matrices, árboles secuencias, etc.

La propiedad crucial es que exista un principio de buen ordenamiento: debe existir una noción de tamaño de tal manera que todos los objetos tengan un tamaño finito y cada conjunto de objetos deberácontener un objeto menor (el más chico de todos).

Ejemplos: profundidad de un árbol, dimensión de matrices o grillas, longitud de secuencias, etc.


computacionales



2727


Ejemplo¿Cuantos nodos tiene un árbol binario completo de altura n?

ProbarNodos(n)= 2n+1-1

PruebaTras realizar un análisis descubrimos la siguiente

definición recursiva:Nodos(0) = 1Nodos(n) = Nodos(n-1) + 2n

Caso base: n=1 es verdadero ya que 1 + 2 = 21+1-1


computacionales



2828


Paso inductivo:Asumamos: Nodos(k)= 2k+1-1Queremos probar:

Nodos(k+1)= 2k+2-1.

Nodos(k+1) = (Def)Nodos(k) +2k+1 = (HI)2k+1-1 + 2k+1= 2k+2-1


computacionales



2929


EjemploTomar un cuadrado de 2n×2n con una baldosa faltantePodemos cubrirlo con L’s?

ejemplo para 8×8


computacionales



3030


Caso base (2×2) es fácil.

Paso inductivo:Asumir que es posible para 2n×2n

Para un cuadradode 2n+1×2n+1

miramos los 4cuadrados menoresy usamos una L para cubrir los 3espacios indicadosen la figura.Aplicar hipótesisinductiva.


computacionales



3131

BNF e inducción sobre derivaciones y secuencias

La forma normal de Backus-Naur(BNF) es una notación usada para describir lenguajes formales.

Una especificación de BNF es un sistema de reglas de derivación, de la forma

<simbolo> ::= <expresión>donde <símbolo> es un no-terminal, y <expresión> consiste en secuencias de símbolos y/o secuencias separadas por la barra vertical, '|' (indicando una opción). La secuencia de símbolos puede contener otros símbolos no-terminales, símbolos terminales, o ε (la cadena nula).

John Warner Backus (1924 –2007)


computacionales



3232


EjemploSea L={ab, aabb,aaabbb,…} el lenguaje de cadenas que contienen n a’s seguidas de n b’s con n ≥ 1. Este lenguaje también puede denotarse como L={anbn n ≥ 1}

La gramática G en notación BNF que usamos para describir L es la siguiente

<cadena> ::= ab | a<cadena>bProbar por inducción que L(G)=L


computacionales



3333


L(G) ⊆ LToda secuencia de símbolos que podemos derivar a partir de <cadenas> consiste en cadenas de la forma akbk. La prueba se realiza por inducción sobre el número de pasos en la derivación.

Caso base: n=1 <cadena> ⇒ ab, es de la forma a1b1

Hipótesis inductiva: Supongamos que derivaciones con n pasos producen cadenas de la forma akbk.

Paso inductivo: Consideremos una derivación con n+1 pasos

<cadena> ⇒ a<cadena>b ⇒ axbPor la hipótesis inductiva x es de la forma akbk y por lo tanto axb = ak+1bk+1.


computacionales



3434


L ⊆ L(G)Toda cadena de la forma akbk puede derivarse a partir de <cadena>. La prueba se realiza por inducción sobre la longitud de la cadena.

Caso base: |ω| = 2, <cadena>⇒ abHipótesis inductiva: Asumamos que anbn de longitud

2n puede ser derivada a partir de <cadena>Paso inductivo: Consideremos una cadena ω de

longitud 2(n+1). Entonces ω = an+1bn+1=aanbnb. Dado que |anbn|= 2n, puede derivarse a partir de <cadena> por la hipótesis inductiva. Por lo tanto <cadena> ⇒ a<cadena>b ⇒ aanbnb = ω. Concluimos que ω puede derivarse a partir de <cadena>.


computacionales



3535 1. P(1)2. Si P(r) es verdadero para

todo entero positivo r,1≤r≤kimplica P(k+1) es verdadero

Entonces P(n) para todo entero n a partir de 1.

caso base

paso inductivo

segundo principio de inducción

Sea P(n) una propiedad definida para el entero n y supongamos:

hipótesis inductiva


computacionales



3636


EjemploMostar que podemos sumar cualquier monto de 8¢ o

más utilizando sólo estampillas de 3¢ y 5¢.PruebaCaso base: P(8) 8 = 5+3También lo vemos para dos casos adicionales: P(9) 9=3+3+3 y P(10) 10=5+5

Hipótesis inductiva: P(r) vale para 8 ≤ r ≤ kPaso inductivo: Probemos P(k+1) donde k+1 es al

menos 11. Si k+1 ≥ 11, entonces k+1-3 = k-2≥8. Por hipótesis inductiva P(k-2) es verdadera y por lo tanto k-2 puede ser escrito como suma de 3’s y 5’s. Sumando 3 obtenemos k+1 como suma de 3’s y 5’s. Luego P(k+1) se verifica.


computacionales



3737


EjemploSea L={ε,(),()(), (()),(()())…} el lenguaje

de los paréntesis bien balanceados.La gramática G en notación BNF que

utilizamos para describir L es la siguiente:

<pbb> ::= (<pbb>)<pbb> | ε

Probar que L(G)=L


computacionales



3838


L(G) ⊆ LToda secuencia de símbolos que podemos derivar a partir de <pbb> consiste en cadenas de paréntesis bien balanceados. La prueba se realiza por inducción sobre el número de pasos en la derivación.

Caso base: n=1 <pbb> ⇒ ε, es balanceadoHipótesis inductiva: Supongamos que derivaciones

con n o menos pasos producen cadenas balanceadas.

Paso inductivo: Consideremos una derivación con n+1 pasos

<pbb> ⇒ (<pbb>)<pbb> ⇒ (x) <pbb> ⇒ (x)yLas cadenas x e y fueron derivadas en n o menos pasos. Por la hipótesis inductiva x e y son balanceadas y por lo tanto (x)y es balanceada.


computacionales



3939


L ⊆ L(G)Toda cadena balanceada puede derivarse a partir de <pbb>. La prueba se realiza por inducción sobre la longitud de la cadena.

Caso base: |ω| = 0, <pbb> ⇒ εHipótesis inductiva: Asumamos que toda cadena

balanceada de longitud menor o igual que 2n puede ser derivada a partir de <pbb>

Paso inductivo: Consideremos una cadena balanceada ω de longitud 2(n+1) y sea (x) el prefijo más corto de ω que está bien balanceado. Entonces ω = (x)y, donde x e y están balanceados. Dado que |x|, |y| ≤ 2n, pueden derivarse a partir de <pbb> por la hipótesis inductiva. Por lo tanto <pbb> ⇒(<pbb>)<pbb> ⇒ (x)<pbb> ⇒ (x)y = ω. Concluimos que (x)y puede derivarse a partir de <pbb>.


computacionales



4040


¿Dónde está el error?Todos los números naturales son pares (P(n) para todo n).

PruebaCaso base: n= 0 es par, entonces P(0) es verdadero.Hipótesis inductiva: asumamos que vale

P(0), P(1), . . . , P(n) Paso inductivo: probemos P(n + 1),Consideremos n + 1. De acuerdo a P(n), n es par, y de

acuerdo a P(1), 1 es par. Por lo tanto n+1 es par ya que la suma de dos números pares es par. Por lo tanto P(n+1) es verdadero.

De acuerdo al segundo principio de inducción podemos concluir que P(n) se verifica para todos los números naturales n.


computacionales



4141

correctitud de algoritmos

Un algoritmo es correcto si para cualquier entrada (input) legal termina y produce la salida (output) deseada.

Las pruebas de correctitud no pueden ser automatizadas.

Pero existen técnicas prácticas y formalismos rigurosos que ayudan a razonar sobre la correctitud de los algoritmos.


computacionales



4242

correctitud parcial y total

Correctitud parcial

entrada legal Algoritmo salida

Si este punto es alcanzado entonces esta es la salida deseada

Correctitud total

entrada legal Algoritmo salida

Este punto es alcanzado y esta es la salida deseada


computacionales



4343

aserciones

Para probar correctitud parcial asociamos una serie de aserciones (sentencias sobre el estado de la ejecución) a puntos específicos del algoritmo.

Precondiciones: aserciones que deben ser válidas antes de ejecutarse un algoritmo o subrutina.

Poscondiciones: aserciones que deben ser válidas luego de ejecutarse un algoritmo o subrutina.


computacionales



4444

aserciones

{Q}P{R} es llamada tripla de Hoare.Q: precondición para el programa PR: poscondición para el programa P

Anthony Hoare(nacido en 1934){Q}

S0{R1}S1

{R2}

Sn-1{R}

P es el programa compuesto por las sentencias S0,S1,…,Sn-1

M Para probar la correctitud de Pse debe probar que para toda entrada X:Q(X) implica R(X,P(X))


computacionales



4545

aserciones

{Q}S0

{R1}S1

{R2}

Sn-1{R}

P es el programa compuesto por las sentencias S0,S1,…,Sn-1

M

{Q} S0 {R1} {R1} S1 {R2}{R2} S2 {R3}

{Rn-1} Sn-1{R}M

Para probar que Pes correcto


computacionales



4646

regla de asignación

{Ri} x=e {Ri+1}

Ejemplo{x-1>0}

x=x-1{x>0} {x-1 > 0} x =x-1 {x>0}


computacionales



4747

regla de condicional

if condición B thenP1

elseP2

end if

Ejemplo{n=5}

if n >= 10 theny =100

elsey=n+1

end if{y=6}

{Q} si {R}{Q ΛB} P1 {R}{Q Λ¬B} P2 {R}

{n = 5 Λ n >= 10} y=100 {y=6}{n = 5 Λ n < 10} y=n+1 {y=6}

{n = 5} y=n+1 {y=6}


computacionales



4848

regla del ciclo (loop)

while condición B doP

end while

EjemploProducto(enteros no negativos x e y)variables locales: enteros i,j

i=0j=0while i<> x do

j=j+yi=i+1

end whilereturn j

{Q} si {QΛ ¬B}{QΛB} P {Q}

Q se llama invariante de ciclo

Q: j=i*y


computacionales



4949

invariante de ciclo

Prueba de Q: j=i*y utilizando inducción Caso base:

Q(0): j0=i0*yHipótesis inductiva:

Asumamos Q(k): jk=ik*yPaso inductivo:Probemos Q(k+1): jk+1=ik+1*y

Por el programa jk+1=jk+y , ik+1=ik+1Luego jk+1 = jk+y (por programa)

= ik*y+y (por HI)= (ik+1)*y = ik+1*y (por programa)


computacionales



5050

regla del ciclo (loop)

Producto(enteros no negativos x e y)variables locales: enteros i,j

i=0j=0while i<> x do

j=j+yi=i+1

end whilereturn j

Probamos que la invariante esQ: j=i*y.

Al finalizar el ciclo while se verificai=x.

Por lo tanto la función computaj = x* y.


computacionales



5151

algoritmo de Euclides

¿Cómo encontrar el máximocomún divisor de dosenteros no negativos a y b, donde a y b no son simultáneamente 0?

El algoritmo de Euclides se basa en el siguiente hecho:

(∀ a, b, q, r) [(a=qb+r) (mcd(a,b)=mcd(b,r))]

Euclides(300 AC)

http://images.google.com/imgres?imgurl=http://lahabra.seniorhigh.net/pages/teachers/pages/math/timeline/mathHist/euclid.gif&imgrefurl=http://lahabra.seniorhigh.net/pages/teachers/pages/math/timeline/MpreAndAncient.html&h=372&w=298&sz=40&hl=en&start=5&sig2=P2CxA0Pu5KmhgYFub1P8kA&um=1&tbnid=gGZ2E5iKQNstJM:&tbnh=122&tbnw=98&ei=bKfLRoDBLaeSePec9L8I&prev=/images%3Fq%3Deuclid%26svnum%3D10%26um%3D1%26hl%3Den%26rls%3DSNYI,SNYI:2005-31,SNYI:en


computacionales



5252

algoritmo de Euclides (cont.)

//a,b son enteros no negativos y a>=bmcd(a,b){

i=aj=bwhile j <> 0 do

computar r tal que i=qj+r, 0<=r<ji=jj=r

end whilereturn i;

}

Q: mcd(i,j)=mcd(a,b)


computacionales



5353


Probar que se verifica la invariante de ciclo Q: mcd(i,j)=mcd(a,b)

Caso baseQ(0): mcd(i0,j0)=mcd(a,b)

Hipótesis inductivaQ(k): mcd(ik,jk)=mcd(a,b)

Paso inductivoProbar Q(k+1): mcd(ik+1,jk+1)=mcd(a,b)

Por programa ik+1= jk ; jk+1= rk+1mcd(ik+1,jk+1) = mcd(jk,rk+1) (por programa)

= mcd(ik,jk) (por Euclides)= mcd(a,b) (por H. I)


computacionales



5454


//a,b son enteros no negativos y a>=bmcd(a,b){

i=aj=bwhile j <> 0 do

computar r tal quei=qj+r, 0<=r<j

i=jj=r

end whilereturn i;

}

Probamos que la invariante esQ: mcd(i,j) = mcd(a,b)

Al finalizar el ciclo while se verificaj=0.

Luego mcd(i,j) = mcd(a,b). Sabemos además que mcd(i,0) =i.Por lo tanto la función computa

mcd(a,b)

Página web: td/lfyacs.uns.edu.ar/~td/lfya2013/downloads/TEORICAS/t01.2013.presenta… · técnicas...

Documents

Transcript of Página web: td/lfyacs.uns.edu.ar/~td/lfya2013/downloads/TEORICAS/t01.2013.presenta… · técnicas...