Descargar

Estructuras de datos y algoritmos II (página 2)

Enviado por Pablo Turmero


Partes: 1, 2
edu.red

Circularidad Comparar primer ejemplo con:

(y análogamente para el segundo ejemplo) Estas versiones (iterativas) originan ejecuciones infinitas pero no por ello desbordan la memoria int P(){   while(1==1)}

edu.red

Otro ejemplo int Fact(int n){   if (n == 0)     return 1   else     return ( n * Fact(n-1));   } ¿Que calcula esta función?

edu.red

Otro ejemplo (continuación) Cada ejecución de Fact(n) para n NATURAL es finita En este ejemplo, para valores no demasiado grandes de n, Fact(n) puede ser demasiado grande ("integer overflow ") 15! = 1,3 x 1012 Existirá un rango de valores de tipo NATURAL para los cuales la función anterior computa efectivamente los correspondientes factoriales.

edu.red

Comparar con versión iterativa int Fact (int n){ int i, f;   f = 1;   for( i= 2;i< n;i++)     f := f * i;   return f; }

edu.red

Comparar con versión iterativa (continuación) La versión recurrente es más simple análoga a una definición matemática La versión iterativa es más eficiente (no usa pila) Se acomoda mejor al esquema de máquinas de estados En particular, podría darse que: La versión recurrente terminara por desbordar la pila en casos en que la versión iterativa terminaría normalmente

edu.red

Primeras Conclusiones Usamos subprogramas recurrentes Operando sobre nuevos datos Produciendo además otros efectos

Esto le da sentido a la circularidad Nos aseguramos que en algún momento "pare" de ejecutar

edu.red

Primeras Conclusiones Por ejemplo, podemos decir que la función Fact está definida en términos de sí misma. Esto sugeriría una circularidad de la definición pero en realidad es una afirmación no demasiado precisa. En realidad, para cada n, Fact(n) no está definido circularmente (pe. en términos de sí mismo) sino en términos de Fact(n-1) o bien (si n = 0) directamente (pe. sin usar Fact)

edu.red

Primeras Conclusiones El cómputo de Fact(n) se realiza: directamente (n = 0) reduciéndolo a Fact en un número más chico (mas cercano a 0) Esto garantiza que toda ejecución de Fact(n) es finita y que por lo tanto Fact(n) esta bien definida para todo n (a menos del problema de "INTEGER OVERFLOW" o eventualmente "STACK OVERFLOW", en otros casos)

edu.red

Primeras Conclusiones

El uso de recurrencia permite escribir programas cuyas computaciones son de largo variable

edu.red

Primeras Conclusiones recurrencia/iteración ¿Existe redundancia al tener ambos conceptos? De hecho, pueden considerarse lenguajes: sin iteración sin asignación (ver FACT recurrente, alcanza con el concepto de función que retorna un valor) sin variables de estado

edu.red

Primeras Conclusiones Esto es la base de los llamados LENGUAJES DECLARATIVOS Lenguajes Declarativos Funcionales – son particularmente interesantes Lógicos

edu.red

Primeras Conclusiones Los lenguajes con variables de estado, asignación e iteración son llamados lenguajes IMPERATIVOS La mayoría de los lenguajes imperativos modernos admite recurrencia El uso de recurrencia permite desarrollar soluciones simples y elegantes, en muchos casos en que las correspondientes soluciones iterativas son demasiado complejas También se da lo inverso (pe. Fact)

edu.red

Orígenes En Matemática, los números naturales usualmente se asumen como bien conocidos se escriben en notación decimal (También en MODULA-2, PASCAL, C, . ) En lógica, los naturales se definen explícitamente

edu.red

Orígenes La idea es abstraerse de cualquier sistema de numeración posicional Un sistema de numeración es de hecho un sistema de representación de números El sistema en base b usa b símbolos Ej: dígitos : dn dn-1 …. d0

de tal forma que el número representado es:

dn * bn + ….. + d0 * b0 (un polinomio)

edu.red

Orígenes Tratamos de abstraernos de todas estas representaciones. Pe. buscar una "más general" que podamos tomar como la definición (lo esencial) del concepto de número natural Esto nos lleva a considerar el sistema de numeración más simple posible SISTEMA UNARIO

edu.red

SISTEMA UNARIO Sistema unario de numeración: hay un sólo dígito : | representamos los números como secuencias de ese dígito: || 2 ||||| 5 es conveniente tener una representación para el 0 (cero) Esto nos lleva a la definición de los números naturales

edu.red

Naturales Es el caso de Definición Inductiva de un conjunto. Damos reglas para construir todos los elementos del conjunto:   Regla 1 – 0 es un natural Regla 2 – Si n es un natural entonces Sucesor(n) es otro natural Regla 3 – Esos son todos los naturales

0 y Sucesor son llamados (operadores) CONSTRUCTORES del conjunto N

edu.red

Naturales La Regla 3 permite justificar el PRINCIPIO de DEMOSTRACIÓN por INDUCCIÓN MATEMÁTICA NATURAL

Sea P una propiedad de números naturales o sea: P(n) es una proposición enunciado (matemático)

edu.red

INDUCCIÓN MATEMÁTICA NATURAL Ejemplos n es par, n > 2 Si n es primo entonces no es par

Entonces es un principio (esquema) de demostraciones de enunciados de la forma: P(n) vale para todo n. (Obviamente no es un método para probar "P(n) vale para todo n" cualquiera sea P, sino para hacer evidente que "P(n) vale para todo n" para ciertas P)

edu.red

INDUCCIÓN MATEMÁTICA NATURAL Si (1) P(0) vale. ("caso base") y (2) asumiendo que P(n) vale. Y podemos demostrar que P(S (n)) vale. ("paso inductivo") entonces :P(n) vale para todo natural n

edu.red

INDUCCIÓN MATEMÁTICA NATURAL Idea: "Juego de fichas de dominó"

Para tirar todas: tirar la primera la distancia entre dos sucesivas debe ser tal que asegure que si cae la previa, entonces ella tira a la siguiente.

edu.red

INDUCCIÓN MATEMÁTICA NATURAL La misma idea sirve para definir funciones sobre los naturales: f : N -> X "tirar" -> asociarle su imagen en f,  Definir f(n)

f(0) = x0 (no depende de f) ("caso base") f(S(n)) = c (n,f(n)) (donde la función c no depende de f)

Si la función está definida en 0 y podemos definirla en S(n) usando que está definida en n) entonces queda definida para todo n (RECURRENCIA PRIMITIVA)

edu.red

Ejemplos fac: N -> N fac 0 = 1 fac (S(n)) = (S(n)) * fac(n)

Ej: fac 3 = 3 * fac 2 = 3 * 2 * fac 1 = 3 * 2 * 1 * fac 0 = 3 * 2 * 1 * 1 = 6 Método mecánico de cálculo (simple sustitución) Otro modelo de cómputo (programa) mecánico (funciones recurrentes (recursivas))

edu.red

Ejemplos (continuación) +: N x N -> N m + 0 = m m + (S n) = S (m + n)

*: N x N -> N m * 0 = 0 m * (S n) = (m * n) + m

edu.red

INDUCCIÓN MATEMÁTICA NATURAL En C usamos notación decimal en lugar de la unaria.

Las ecuaciones de la definición de fac se expresan:

int fact(n){ if ( n == 0 ) return 1; else return n * fact(n-1); }

edu.red

Otro ejemplo en C (más complejo) Fib: N -> N (los números de Fibonacci) Fib(0) = 1 Fib(1) = 1 Fib(n+2) = Fib(n) + Fib(n+1) (dos llamadas en distintos puntos)

(no es un caso de recurrencia primitiva)

edu.red

Principio de Inducción Completa Si podemos probar P(n) asumiendo P(z) para todo z < n entonces vale P(n) para todo n.

En términos de las fichas de domino: Si una cualquiera se cae toda vez que todas sus predecesoras se caen entonces todas se caen. Notar que toda aplicación de este principio requiere probar la propiedad para 0. (¿Por qué?)

edu.red

Principio de Inducción Completa Caso general de definición recurrente de funciones f : N -> X

Casos Base (no aparece f en las bi) f(n0) = b0 … f(nk) = bk Casos Recurrentes (las ei pueden depender de f) f(nk+1) = e1 … f(nk+r) = er

edu.red

Principio de Inducción Completa Para que f esté definida como función debe probarse, para todo n: EXISTENCIA Y UNICIDAD de f(n) para cada n debe haber una ecuación (caso) que se aplique (exhaustividad) Las llamadas recurrentes deben ser de la forma: f(n) = c(f(m1), …… , f(mp))   (donde c no depende de f y está bien definida) donde mi < n para cada mi

edu.red

Principio de Inducción Completa Se justifica por INDUCCION COMPLETA (notar que < es "bien fundado")

Metodológicamente pensar los casos de n: Base Reducción a un predecesor (o algunos predecesores)

edu.red

Listas (ejemplo) Vamos a definir el conjunto de las listas secuenciales finitas de naturales. Inductivamente: [] es una Lista de Naturales SI n : Natural y L : ListaNaturales ENTONCES n.L : ListaNaturales Esas son todas las listas Donde . es la concatenación de listas.

edu.red

Ejemplos de Listas [] 1.[]   ([1]) 2.1.[] ([2,1]) notación resumida: x1.x2……xn.[] se representa:   [x1,x2,…,xn]

edu.red

Listas (continuación) Tomamos en consecuencia: Principio de INDUCCIÓN PRIMITIVA ESTRUCTURAL: si P([]) y para todos n y S podemos probar P(n.S) asumiendo P(s) entonces P(S) vale para toda S : NLista Tenemos también el esquema de definición de funciones sobre NListas por RECURRENCIA PRIMITIVA ESTRUCTURAL: f : NLista -> x f([]) = x0 f(x.S) = c(x, S, f(s))

edu.red

Listas (continuación) Todo lo anterior se generaliza trivialmente a listas de elementos de cualquier tipo: AListas donde A es cualquier tipo (el tipo de los elementos de la lista) Notar que NLista es un conjunto infinito (comparar con tipos de vectores, que son conjuntos de secuencias de un largo dado) !!!

edu.red

Ejemplos de funciones sobre listas definidas por recurrencia primitiva largo: ALista -> N largo([]) = 0 largo(x.S) = 1 + largo(S)

snoc: A x Alista -> Alista snoc(x,[]) = [x] snoc(x,y.S) = y.(snoc(x,S)) ¿Que hace la función snoc?

edu.red

¿Que hace la función snoc? La función snoc inserta al elemento x al final de la lista S

edu.red

Descomposición de listas Problema Escribir una función Pal : NLista -> Bool tal que Pal(S) = true sii S es palíndromo (capicúa)

edu.red

Descomposición de listas (cont.) Una manera de resolverla: Pal([]) = true Pal([x]) = true Pal(S) = (Primero(S) = Ultimo(S)) & (Pal(Medio(S)) (para S con al menos 2 elementos) donde las funciones Primero, Ultimo y Medio se definirán separadamente

edu.red

La función Medio La función Medio no puede definirse para toda lista. De hecho: Medio : {S : ALista / S tiene al menos dos elementos} -> Alista Podemos decir:   Medio : ALista -> Lista con la precondición: el argumento debe tener al menos dos elementos

edu.red

La función Medio Ejemplos similares puenden darse con naturales: mcd : N x N -> N (máximo común divisor) Precondición : los argumentos no pueden ser ambos nulos

edu.red

La función Medio Medio([x,y]) = [] Medio(x.y.S) = y.Medio(y.S) (S no vacía)

Notar los casos considerados. El espacio (dominio) son las listas de al menos dos elementos. Se cumplen exhaustividad y exclusión En el caso de recurrencia, la llamada recurrente respeta la precondición de la función.

edu.red

La función Medio Fundamental: si se usa una función sin respetar la precondición, no se puede tener ninguna garantía acerca del resultado.

Ver que la definición es correcta: Dado S = [z1, … , zn, zn+1]: Medio(y.S) = [z1, … , zn] Porque: Medio(x.y.S) = Medio ([x,y,z1, … , zn,zn+1]) = [y,z1, … , zn] = y.Medio(y.S) tal como está definido

Partes: 1, 2
 Página anterior Volver al principio del trabajoPágina siguiente