Introducción (AyE1)

En Algoritmos y Estructuras de Datos 1 se estudia el concepto de Especificación durante el desarrollo de Software; el paso intermedio entre un problema y su programa correspondiente. La especificación será la metodología aplicada para programas funcionales e imperativos. Se retoman conceptos de Introducción a los Algoritmos.

Entre algunos objetivos se encuentran: poder analizar algoritmos y verificarlos, identificar abstracciones al abordar problemas, e implementar soluciones eficientes.

Especificaciones y construcción de programas

El proceso de construcción de programas se establece de la siguiente forma:

Problema

(Impreciso/Informal, poco detallado)

⇓

Especificación

(Preciso/Formal, poco detallado)

⇙

Derivación

(Crear la definición)

⇘

⇖

Verificación

(Demostrar su validez)

⇗

Programa

(Preciso/Formal, detallado)

En programación funcional, un programa consiste en la definición de funciones y la reducción de expresiones.

Podemos resolver problemas a través de funciones, las cuales tendrán la siguiente estructura:

1) Nombre de la función
2) Tipo de la función (Input / Output)
3) Predicado que indica qué debe satisfacer la función (lo sabremos al derivar).

Ejemplo: “quisiera saber si un número es impar…“

1) \(esImpar\)
2) \(Int \to Bool\)
3) \(mod.x.2 \neq 0\)

Nuestro programa sería:

\[\begin{array}{l} \Big\vert\ esImpar : Int \to Bool \\ \overline{\Big\vert \; esImpar.x \doteq } \; mod.x.2 \neq 0 \end{array} \]

Y también podemos definirlo en Haskell:


esImpar :: Int -> Bool
esImpar x = mod x 2 /= 0

En programación imperativa, un programa es una secuencia de sentencias que modifican el estado (conjunto de variables con valores) de un sistema.

Podemos resolver problemas a través de instrucciones, siguiendo esta estructura:

1) Constantes
2) Variables
3) Precondición
4) Programa incógnita (S)
5) Postcondición

Ejemplo: “Dado el entero \(N > 0\), contar cuántos números entre \(0\) y \(N\) son múltiplos de \(6\)…“

1) \(\textnormal{Const} \; N : Int;\)
2) \(\textnormal{Var} \; resultado : Int ;\)
3) \(\{ \; P : N > 0 \; \} \)
4) \(S\)
5) \(\{ \; Q : resultado = \bigl \langle \textnormal{N} i : 0 \leq i \leq N : i \; mod \; 6 = 0 \; \bigr \rangle \; \} \)

Nuestro programa sería:

\[\begin{aligned} &\{ \; N > 0 \; \} \\ &numero\_actual, \; resultado := 0, \; 0 \\ &\mathbf{do} \; numero\_actual \leq N \ \rightarrow \\ &\quad \mathbf{if} \; numero\_actual \; mod \; 6 = 0 \rightarrow \\ &\quad \quad resultado := resultado + 1 \; ; \\ &\quad □ \; numero\_actual \; mod \; 6 \neq 0 \rightarrow \\ &\quad \quad \mathbf{skip} \; ; \\ &\quad \mathbf{fi} \; ; \\ &\quad numero\_actual := numero\_actual + 1 \; ; \\ &\mathbf{od} \; ; \\ &\{ \; numero\_actual = N + 1 \; \land \; resultado = \bigl \langle \textnormal{N} i : 0 \leq i \leq N : i \; mod \; 6 = 0 \; \bigr \rangle \; \} \end{aligned} \]

(La especificación no declara \(numero\_actual\) puesto que es parte del programa final)

Esto puede definirse en C:


#include <stdio.h>
#define N 5
 
int main() {
    int numero_actual = 0;
    int resultado = 0;
 
    do {
        if (numero_actual % 6 == 0) {
            resultado += 1; 
        }         
        numero_actual += 1; 
    } while (numero_actual <= N); 
 
    printf("Resultado: %d\n", resultado); 
 
    return 0;
}