1 L ENGUAJE DE E SPECIFICACIÓN Algoritmos y Estructuras de Datos I Especificación – Práctica 2 AEDI Especificación – Práctica 2 1

2 E SPECIFICACIÓN DE PROBLEMAS Expresamos formalmente qué debe cumplir una función para ser solución al problema dado. No expresamos cómo solucionarlo Puede no haber solución al problema que planteamos. O tal vez, no sabemos escribirla. Recordemos que lo que queremos especificar es el contrato que debe cumplir la función para ser considerada solución del problema planteado. AEDI 2 Especificación – Práctica 2

3 E SPECIFICACIÓN DE PROBLEMAS N OTACIÓN problema nombre(parámetros) = salida { modifica: parámetro; requiere: expresión1; asegura: expresión2; -- DEFINICIÓN DE AUX – } AEDI 3 Especificación – Práctica 2

4 E JERCICIOS Especificar el problema de, dados dos enteros, devolver cualquiera de ellos. Especificar el problema de, dados dos enteros, devolver el máximo. AEDI 4 Especificaión – Práctica 2

5 O PERACIONES CON SECUENCIAS long(a) ó |a| indice(s,i) ó s[i] ó s i cab(s) cola(s) en(e,s) ó e en s ó e  s cons(e,s) ó e:s conc(s,t) ó s++t sub(s, e, f) ó s[e..f] cambiar (s, i, e) AEDI 5 Especificación – Práctica 2

6 O PERACIONES CON SECUENCIAS alguno(s) todos(s) sum(s) ó  s prod(s) ó  s AEDI 6 Especificación – Práctica 2

7 R ECORDANDO Para todo: (  selectores, condiciones) propiedad Equivale a todos([propiedad | selectores, condiciones]) Existe: (  selectores, condiciones) propiedad Equivale a alguno([propiedad | selectores, condiciones]) Nota: cuando decimos “propiedad” nos referimos a expresiones de tipo Bool. AEDI 7 Especificación – Práctica 2

8 S ECUENCIAS POR COMPRENSIÓN Notación: [expresión | selectores, condiciones] selectores: variable  secuencia (o

10 E SPECIFICACIÓN DE PROBLEMAS E JERCICIO – SOLUCIÓN Especificar el problema de, dados dos enteros, devolver el máximo. problema mayor(a, b: Int) = result: Bool{ asegura: result == (if (a > b) then a else b); } problema mayor(a, b: Int) = result: Bool{ asegura: result == Beta(a > b)*a + Beta(a

11 E SPECIFICACIÓN DE PROBLEMAS E JERCICIO – SOLUCIÓN Especificar el problema de, dados dos enteros, devolver cualquiera de ellos. problema dameUno(a, b: Z) = result: Z{ asegura: (result == a) || (result == b); } AEDI 11 Especificación – Práctica 2

12 U SANDO LISTAS POR COMPRENSIÓN [x | x  [5,7,4,2,8,6,4,5,8,2,7,4], x  4] = [4,2,4,2,4] [x+y | x  a, y  b, x  y], qué indica esta expresión? Por ejemplo: a = [1,2,3] y b = [1,2,3]  [3,4,3,5,4,5] Sea a una secuencia, obtener la secuencia inversa de a: aux reverso(a:[T]):[T] = [x[|a|-i-1] | i

13 M ÁS EJERCICIOS CON SECUENCIAS Especificar el problema de, dadas dos listas de enteros, devolver la suma de las cabezas de cada una. problema sumaCabezas (a, b: [Z]) = result : Z { requiere : |a| > 0 && |b| > 0; asegura : result == cab(a) + cab(b); } AEDI 13 Especificaión – Práctica 2

15 M ÁS EJERCICIOS CON SECUENCIAS Especificar el problema de, dadas dos listas con números enteros (que posean igual longitud), devolver la suma elemento a elemento. problema sumaListas (a, b: [Z]) = result : [Z] { requiere : |a| == |b|; asegura : result == [ a[i] + b[i] | i

16 M ÁS EJERCICIOS CON SECUENCIAS Variante: no requerir que sean de igual longitud y suponer que se devuelve la suma hasta que alguna se acaba. problema sumaListas (a, b: [Z]) = result : [Z] { asegura : result == [a[i] + b[i] | i

17 M ÁS EJERCICIOS CON SECUENCIAS Encontrar el índice (la posición) del menor elemento en una secuencia de números reales distintos no negativos. problema indiceMenorDistintos(a:[Float])=result:[Z]{ requiere noNegativos: (  x

18 M ÁS EJERCICIOS CON SECUENCIAS Especificar el problema de, dada una lista de enteros, devolver una que tenga los mismo elementos pero ordenada. problema ordenar(a:[Z])=result:[Z]{ asegura : mismos(result,a); asegura : (  i