MA265 Sesión Relaciones - Manipulación LD

UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 1 Invariante de un algoritmo CONTENIDO Unidad 2: LÓGICA Y ALGORITMOS 2.4 Invariante de un algoritmo ▪ Introducción ▪ Invariante de un algoritmo iterativo UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 2 Análisis de algoritmos Introducción Un algoritmo es una secuencia de pasos lógicos necesarios para llevar a cabo una tarea específica, como la solución de un problema. Los algoritmos son independientes tanto del lenguaje de programación en que se expresan como de la computadora que los ejecuta. Invariante de un algoritmo iterativo En informática se conoce como invariante a una condición que se sigue cumpliendo después de la ejecución de determinadas instrucciones. Se cumple tanto antes como después de estas instrucciones, permaneciendo sin variación, por ello se denomina invariante. Las invariantes se pueden utilizar para demostrar el buen funcionamiento de algoritmos y cumplen con un papel importante en el diseño. Ejemplo 1 Para el siguiente algoritmo: 𝑆𝑈𝐵𝑅𝑈𝑇𝐼𝑁𝐴 𝑆𝑈𝑀𝐴 (𝑋, 𝑌; 𝑍) 1. 𝑍 ← 𝑋/𝑌 2. 𝑊 ← 𝑌 𝑊𝐻𝐼𝐿𝐸 (𝑊 > 0) 𝑎. 𝑍 ← 𝑍 + 𝑋 𝑏. 𝑊 ← 𝑊 − 1 3. 𝑅𝐸𝑇𝑈𝑅𝑁 𝐹𝐼𝑁 𝐷𝐸 𝐿𝐴 𝑆𝑈𝐵𝑅𝑈𝑇𝐼𝑁𝐴 𝑆𝑈𝑀𝐴 a) Determine el invariante. b) Pruebe la validez de la invariante mediante inducción matemática. Resolución Cálculo de la invariante Antes del ciclo 𝑍 0 = 𝑋/𝑌 𝑊 0 = 𝑌 En el ciclo 𝑍 1 = 𝑍 0 + 𝑋 = 𝑋 𝑌 + 𝑋 𝑊 1 = 𝑊 0 − 1 = 𝑌 − 1 𝑍 2 = 𝑍 1 + 𝑋 = 𝑋 𝑌 + 2𝑋 𝑊 2 = 𝑊 1 − 1 = 𝑌 − 2 𝑍 3 = 𝑍 2 + 𝑋 = 𝑋 𝑌 + 3𝑋 𝑊 3 = 𝑊 2 − 1 = 𝑌 − 3 ………… ………… UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 3 ………… ………… 𝑍 𝑛 = 𝑋 𝑌 + 𝑛𝑋 𝑊 𝑛 = 𝑌 − 𝑛 Despejando, 𝑛 = 𝑌 − 𝑊 𝑛 , reemplazamos en 𝑍 𝑛 𝑍 𝑛 = 𝑋 𝑌 + (𝑌 − 𝑊 𝑛 )𝑋 𝑍 𝑛 = 𝑋 𝑌 + 𝑌𝑋 − 𝑊 𝑛 𝑋 Invariante: 𝒁 𝒏 + 𝑾 𝒏 𝑿 = 𝑿 𝒀 + 𝒀𝑿 Se observa que la invariante es una expresión independiente de 𝑛 Demostración de la validez de la invariante 𝑷(𝒏): 𝒁 𝒏 + 𝑾 𝒏 𝑿 = 𝑿 𝒀 + 𝒀𝑿, 𝒑𝒂𝒓𝒂 𝒕𝒐𝒅𝒐 𝒏 ≥ 𝟎 Demostremos que 𝑃(0) es verdadero 𝑃(0): 𝑍 0 + 𝑊 0 𝑋 = 𝑋 𝑌 + 𝑌𝑋 𝑋 𝑌 + 𝑌 𝑋 = 𝑋 𝑌 + 𝑌𝑋 …………. Verdadero Asumimos que 𝑃(𝑛) es verdadero y por lo tanto 𝑃(𝑘) es verdadero 𝑃(𝑘): 𝑍 𝑘 + 𝑊 𝑘 𝑋 = 𝑋 𝑌 + 𝑌𝑋 Debemos demostrar que 𝑃(𝑘 + 1) es verdadero 𝑃(𝑘 + 1): 𝑍 𝑘+1 + 𝑊 𝑘+1 𝑋 = 𝑋 𝑌 + 𝑌𝑋 𝑃(𝑘 + 1): 𝑍 𝑘 + 𝑋 + (𝑊 𝑘 − 1)𝑋 = 𝑋 𝑌 + 𝑌𝑋 𝑃(𝑘 + 1): 𝑍 𝑘 + 𝑋 + 𝑊 𝑘 𝑋 − 𝑋 = 𝑋 𝑌 + 𝑌𝑋 𝑃(𝑘 + 1): 𝑍 𝑘 + 𝑊 𝑘 𝑋 = 𝑋 𝑌 + 𝑌𝑋 𝑃(𝑘 + 1): 𝑋 𝑌 + 𝑌𝑋 = 𝑋 𝑌 + 𝑌𝑋 …………….. Verdadero Por lo tanto 𝑃(𝑛) se cumple para todo 𝑛 ≥ 0 Ejemplo 2 Para el siguiente algoritmo: 𝑆𝑈𝐵𝑅𝑈𝑇𝐼𝑁𝐴 𝑃𝑅𝑂𝐷𝑈𝐶𝑇𝑂 𝑆𝑈𝑀𝐴 (𝑋, 𝑌; 𝑍) 1. 𝑍 ← 𝑋 2. 𝑊 ← 𝑌 𝑊𝐻𝐼𝐿𝐸 (𝑊 > 0) 𝑎. 𝑍 ← 𝑌𝑍 + 𝑋 𝑏. 𝑊 ← 𝑊 − 1 3. 𝑅𝐸𝑇𝑈𝑅𝑁 𝐹𝐼𝑁 𝐷𝐸 𝐿𝐴 𝑆𝑈𝐵𝑅𝑈𝑇𝐼𝑁𝐴 𝑃𝑅𝑂𝐷𝑈𝐶𝑇𝑂 𝑆𝑈𝑀𝐴 UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 4 a) Determine el invariante. b) Pruebe la validez de la invariante mediante inducción matemática. Resolución Cálculo de la invariante Antes del ciclo 𝑍 0 = 𝑋 𝑊 0 = 𝑌 En el ciclo 𝑍 1 = 𝑌𝑍 0 + 𝑋 = 𝑌𝑋 + 𝑋 𝑊 1 = 𝑊 0 − 1 = 𝑌 − 1 𝑍 2 = 𝑌𝑍 1 + 𝑋 = 𝑌 2 𝑋 + 𝑌𝑋 + 𝑋 𝑊 2 = 𝑊 1 − 1 = 𝑌 − 2 𝑍 3 = 𝑌𝑍 2 + 𝑋 = 𝑌 3 𝑋 + 𝑌 2 𝑋 + 𝑌𝑋 + 𝑋 𝑊 3 = 𝑊 2 − 1 = 𝑌 − 3 ………… ………… 𝑍 𝑛 = 𝑌 𝑛 𝑋 + 𝑌 𝑛−1 𝑋 + ⋯ + 𝑌𝑋 + 𝑋 𝑊 𝑛 = 𝑌 − 𝑛 𝑍 𝑛 = 𝑋 ( 𝑌 𝑛+1 −1 𝑌−1 ) 𝑊 𝑛 = 𝑌 − 𝑛 Despejando, 𝑛 = 𝑌 − 𝑊 𝑛 , reemplazamos en 𝑍 𝑛 𝑍 𝑛 (𝑌 − 1) = 𝑋𝑌 𝑌−𝑊 𝑛 +1 − 𝑋 𝑍 𝑛 (𝑌 − 1) = 𝑋𝑌 𝑌+1 𝑌 𝑊 𝑛 − 𝑋 𝑍 𝑛 (𝑌 − 1) + 𝑋 = 𝑋𝑌 𝑌+1 𝑌 𝑊 𝑛 (𝑍 𝑛 (𝑌 − 1) + 𝑋)𝑌 𝑊 𝑛 = 𝑋𝑌 𝑌+1 Invariante: (𝒁 𝒏 (𝒀 − 𝟏) + 𝑿)𝒀 𝑾 𝒏 = 𝑿𝒀 𝒀+𝟏 Se observa que la invariante es una expresión independiente de 𝑛 Demostración de la validez de la invariante 𝑷(𝒏): (𝒁 𝒏 (𝒀 − 𝟏) + 𝑿)𝒀 𝑾 𝒏 = 𝑿𝒀 𝒀+𝟏 , 𝒑𝒂𝒓𝒂 𝒕𝒐𝒅𝒐 𝒏 ≥ 𝟎 Demostremos que 𝑃(0) es verdadero 𝑃(0): (𝑍 0 (𝑌…