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

presentación

Cátedra:Profesora

Ana G. Maguitman consultas: viernes 10hs (oficina 205) email: agm@cs.uns.edu.ar

AsistenteTelma Delladio

consultas: jueves 11hs (hall DCIC) email: td@cs.uns.edu.ar

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

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

computacionales

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

preguntas

computacionales

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

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.

computacionales

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

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

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

6553712

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

⋅==+

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

no es primo

computacionales

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

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

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

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

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

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

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

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 = 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

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

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

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

+=∑=

2/)1(0

+=∑=

2/)2)(1(1

0++=∑

computacionales

∑∑=

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

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

usando hipótesis inductiva

computacionales

EjemploLos números de Fibonacci se definen como:

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

≥+===

−+ nfffff

Leonardo Fibonacci(1170 – 1250)

computacionales

Mostrar que para todo n ≥ 1.

PruebaCaso base:

Probar

010201111 =⋅=⋅=⋅ +− ffff

011)1( 2121 =−=−+f

1211111 )1(−+=⋅ +− fff

nnnn fff )1(2

11 −+=⋅ +−

computacionales

Paso inductivo:Asumamos

Probemos

kkkk fff )1(2

11 −+=⋅ +−

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

kkk fff

)1()1(

−+=−+⋅=

−++=

−−⋅+⋅=

+⋅=+=⋅

kkkkkkkk

ffffffff

computacionales

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

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

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

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

ejemplo para 8×8

computacionales

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

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

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

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

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

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

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

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

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

¿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

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

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

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

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

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

aserciones

{R1}S1

Sn-1{R}

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

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

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

Para probar que Pes correcto

computacionales

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

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

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

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

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

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)

computacionales

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

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

//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...

TÉCNICAS E INSTRUMENTOS - Tema 8: Pruebas Criteriales

TD resumido

Técnicas de Determinación del Grupo Sanguíneo y Pruebas de Compatibilidad

PRESENTACION TD&TF1

MF TD Presccxcx

Corso Projecte TD

Td Apowrpoint

TD SILENT - Soler & Palau · c l n n la lb n la lb l n reb td - 250/100,td - 350/125 td - 1000/200 td - 250/100,td - 350/125 td - 1000/200

Las pruebas objetivas Las técnicas de encuesta La observación sistemática

Soluciones Técnicas Integrales S&S1-PRUEBAS-HIDROSTATICAS-EN-TUBERIAS

CRONOGRAMA DE PRUEBAS TÉCNICAS Y … · CRONOGRAMA DE PRUEBAS TÉCNICAS Y PSICOMETRICAS 2016 Estimados/as : Para conocimiento de los participantes del concurso de méritos y oposición

tel./fax: +34 91 675 33 06 info@autentia.com - www ... · 11. EjemploNavegacion

TD - Juan Muglia

Raea td 2015

jhonnisep.files.wordpress.com€¦ · Web view-Pruebas objetivas.-registro acumulativo.-Técnicas de grupo.-Técnicas basadas en autoinformes.-Técnicas basadas en la introspección.-Técnicas

PRUEBAS FÍSICAS APLICADAS Y PROPUESTA DE BATERÍA DE ...eprints.uanl.mx/19520/1/ALONSO VEGA AMAYRANI.pdf · pruebas fÍsicas aplicadas y propuesta de baterÍa de pruebas tÉcnicas

Td Sinchi Wayra

TD SILENTcl.thinkandoo.com/docs/manual/9023010702____td's_silent's_(12_04... · c l n n la lb n la lb l n reb td - 250/100,td - 350/125 td - 1000/200 td - 250/100,td - 350/125 td

Listado pruebas técnicas. Mayo 2013

PRUEBAS PROYECTIVAS Técnicas proyectivas