documente1

Algoritmos y Estructuras de Datos I

Primer cuatrimestre de 2015

Departamento de Computacion - FCEyN - UBA

Especificacion - clase 1

Introduccion a la especificacion de problemasLogica proposicional

1


Objetivo: Aprender a programar en lenguajes imperativos.

I Especificar problemas.

I Describirlos en lenguaje formal.

I Escribir programas.

I En esta materia nos concentramos en programas paratratamiento de secuencias.

I Razonar acerca de estos programas.

I Obtener una vision abstracta del computo.I Definir un manejo simbolico y herramientas para demostrar

propiedades de nuestros programas.I Probar correccion de un programa respecto de su

especificacion.

2


Contenidos

1. Especificacion de problemas

I Lenguaje formal cercano a la logica proposicional

2. Introduccion a la programacion imperativa

I Semantica por transformacion de estadosI Correctitud para especificacion dada

3. Estructuras de datos

I Especificacion de tipos de datosI Implementacion de tipos mediante estructuras de datos

4. Algoritmos sobre secuencias

I Busqueda linealI Busqueda binariaI Algortimos de ordenamientoI Intercalacion ordenada (merge) y otros con dos secuencias

5. Nocion de complejidad tiempo.

6. Algoritmos y estructuras de datos dinamicas.

3


Regimen de aprobacion

I Parciales

I 2 parcialesI 2 recuperatorios (al final de la cursada)

I Trabajos practicos

I 2 entregasI 2 recuperatorios (cada uno a continuacion)I Grupos de 4 alumnos

I Examen final o un coloquio (en caso de tener dado el final deAlgebra I al finalizar la cursada)

Calificacion final: promedio de la cursada y el nota del coloquio, donde:

cursada =p1 + p2 + t1 + t2

4

4

[email protected]

[email protected]

5

Bibliografa

I The Science of ProgrammingDavid GriesSpringer Verlag, 1981

I A Method of ProgrammingEdsger Dijkstra, W. H. FeijenAddison-Wesley Longman, 1988

I Structured ProgrammingEdsger Dijkstra, C. A. R. Hoare, Ole-Johan DahlAcademic Press, 1972

I A Discipline of ProgrammingEdsger DijkstraPrentice Hall , 1976

I Mathematical Logic: A Course With Exercises, Part 1Rene Cori, Daniel Lascar.Oxford University Press, 2000

I Reasoned programmingK. Broda, S. Eisenbach, H. Khoshnevisan, S. Vickers,Prentice-Hall, 1994

6

Que es una computadora?

I Una computadora es una maquina que procesa informacionautomaticamente de acuerdo con un programa almacenado.

1. Es una maquina.2. Su funcion es procesar informacion, y estos terminos deben

entenderse en sentido amplio.3. El procesamiento se realiza en forma automatica.4. El procesamiento se realiza siguiendo un programa.5. Este programa esta almacenado en una memoria interna de la

misma computadora.

7

Que es un algoritmo?

I Un algoritmo es la especificacion de una sucesion de pasosprimitivos para resolver un problema a partir de datos de entradaadecuados.

1. Es la especificacion de los pasos a dar.2. Especifica una sucesion de pasos primitivos.3. El objetivo es resolver un problema.4. Un algoritmo tpicamente trabaja a partir de datos de entrada.

8

Que es un programa?

I Un programa es la descripcion de un algoritmo en un lenguaje deprogramacion.

1. Corresponde a la implementacion concreta del algoritmo paraser ejecutado en una computadora.

2. Se describe en un lenguaje de programacion.

9

Especificacion, algoritmo, programa

1. Especificacion: descripcion del problema a resolver.

I Que problema tenemos?I Habitualmente, dada en lenguaje formal.I Es un contrato que da las propiedades de los datos de entrada

y las propiedades de la solucion.

2. Algoritmo: descripcion de la solucion escrita para humanos.

I Como resolvemos el problema?

3. Programa: descripcion de la solucion para ser ejecutada en unacomputadora.

I Tambien, como resolvemos el problema?I Escrito en un lenguaje de programacion.

10

Etapas en el desarrollo de programas

1. EspecificacionDefinicion formal del problema.

2. Diseno generalDeterminar las componentes de la solucion.

3. Diseno de algoritmosDar algoritmos para cada componente.

4. Programacion y validacionImplementar los algoritmos y asegurarse de que la implementaciones correcta.

5. Instrumentacion y mantenimientoPuesta en practica del programa implementado. Correccion deerrores e introduccion de cambios para responder a nuevosrequerimientos.

11

1. Especificacion

I El planteo inicial del problema puede ser vago y ambiguo.

I Al especificar damos una descripcion clara y precisa en lenguajeformal, por ejemplo, el lenguaje de la logica matematica.

I Por ejemplo, calcular de edad de una persona es una definicionimprecisa del problema (por que?).

I +Info: AED1, AED2.

12

2. Diseno general

I Varios programas o uno muy complejo?

I Como dividirlo en partes?

I Distintas partes en distintas maquinas?

I Programas ya hechos con los que interactuar?

I +Info: AED2, IS1, IS2.

13

3. Diseno de algoritmos

I Escribir un algoritmo para dar solucion a cada componente en laque se subdividio la solucion.

I El objetivo mas importante es que los algoritmos propuestos seancorrectos.

I Objetivos secundarios (o no tanto!):

1. Tiempo de ejecucion.2. Uso de memoria.3. Uso de otros recursos.4. etc.

I +Info: AED1, AED2, AED3.

14

4. Programacion y validacion

I Traducimos el algoritmo a un lenguaje adecuado para ser ejecutadopor una computadora.

I Lenguajes naturales vs lenguajes formales.

I Tomamos las acciones necesarias para asegurarnos de que laimplementacion reproduce adecuadamente el algoritmo propuesto.

I +Info: TL, IS1, IS2.

15

5. Instrumentacion y mantenimiento

I Poner en practica el programa en el entorno final.

I Si tiempo despues encontramos errores o cambian losrequerimientos, es necesario volver a las etapas anteriores pararevisar el programa.

I +Info: IS1, IS2.

16

Especificacion de problemas

I Una especificacion es un contrato que define que se debe resolver yque propiedades debe tener la solucion.

1. Define el que y no el como.

I Ademas de cumplir un rol contractual, la especificacion delproblema es insumo para las actividades de ...

1. testing,2. verificacion formal de correccion,3. derivacion formal (construir un programa a partir de la

especificacion).

17

Parametros y tipos de datos

I La especificacion de un problema incluye un conjunto deparametros: datos de entrada cuyos valores seran conocidos recienal ejecutar el programa.

I Cada parametro tiene un tipo de datos.

I Tipo de datos: Conjunto de valores provisto de ciertasoperaciones para trabajar con estos valores.

I Ejemplo 1: parametros de tipo fecha

I valores: ternas de numeros enterosI operaciones: comparacion, obtener el ano, ...

I Ejemplo 2: parametros de tipo dinero

I valores: numeros reales con dos decimalesI operaciones: suma, resta, ...

18

Contratos

I Una especificacion es un contrato entre el programador de unafuncion y el usuario de esa funcion.

I Ejemplo: calcular la raz cuadrada de un numero real.

I Como es la especificacion (informalmente, por ahora) de esteproblema?

I Para hacer el calculo, el programa debe recibir un numero nonegativo.

I Obligacion del usuario: no puede proveer numeros negativos.I Derecho del programador: puede suponer que el argumento

recibido no es negativo.

I El resultado va a ser la raz cuadrada del numero recibido.

I Obligacion del programador: debe calcular la raz, siempre ycuando haya recibido un numero no negativo

I Derecho del usuario: puede suponer que el resultado va a sercorrecto

19

Partes de una especificacion (contrato)

1. Encabezado

2. Precondicion o clausula requiere

I Condicion sobre los argumentos, que el programador da porcierta.

I Especifica lo que requiere la funcion para hacer su tarea.I Por ejemplo: el valor de entrada es un real no negativo

3. Postcondicion o clausula asegura

I Condicion sobre el resultado, que debe ser cumplida por elprogramador siempre y cuando el usuario haya cumplido laprecondicion.

I Especifica lo que la funcion asegura que se va a cumplirdespues de llamarla (si se cumpla la precondicion).

I Por ejemplo: la salida es la raz cuadrada del valor deentrada

20

El contrato

I Contrato: El programador escribe un programa P tal que si elusuario suministra datos que hacen verdadera la precondicion,entonces P termina en una cantidad finita de pasos retornando unvalor que hace verdadera la postcondicion.

I El programa P es correcto para la especificacion dada por laprecondicion y la postcondicion exactamente cuando se cumple elcontrato.

I Si el usuario no cumple la precondicion y P se cuelga o no cumple laposcondicion...

I el usuario tiene derecho a quejarse?I Se cumple el contrato?

I Si el usuario cumple la precondicion y P se cuelga o no cumple laposcondicion...

I el usuario tiene derecho a quejarse?I Se cumple el contrato?

21

Lenguaje de especificacion

22

Encabezado de un problema

problema nombre(parametros) = nombreRes : tipoRes

I nombre: nombre que le damos al problema

I sera resuelto por una funcion con ese mismo nombre

I nombreRes: nombre que le damos al resultado

I tipoRes: tipo de datos del resultado

I parametros: lista que da el tipo y el nombre de cada uno

23

Ejemplos

problema rcuad(x : Float) = result : Float {requiere x 0;asegura result result == x ;

}

problema suma(x : Int, y : Int) = result : Int {asegura result == x + y ;

}

problema resta(x : Int, y : Int) = result : Int {asegura result == x y ;

}

problema cualquieramayor(x : Int) = result : Int {asegura result > x ;

}

24

Argumentos que se modifican (modifica y usa pre())

Problema: Incrementar en 1 el argumento de entrada.

I Alternativa sin modificar la entrada (usual).

problema incremento(a : Int) = res : Int{asegura res == a + 1;

}

I Alternativa que modifica la entrada: usamos el mismo argumentopara la entrada y para la salida.

problema incremento-modificando(a : Int){modifica a;

asegura a == pre(a) + 1;

}

I Observar que en este caso la funcion no tiene un resultado en sunombre.

25

Otro ejemplo

Dados dos enteros dividendo y divisor, obtener el cociente entero entreellos.

problema cociente(dividendo : Int, divisor : Int) = result : Int {requiere divisor > 0;asegura (result divisor dividendo)asegura ((result + 1) divisor > dividendo)

}

Que sucede si ejecutamos ...

I cociente(1,0)?

I cociente(-4,-2) y retorna 2?

I cociente(-4,-2) y retorna 0?

I cociente(4,-2) y no termina?

26

Argumentos de salida (modifica, no usa pre())

Problema: Calcular el cociente y el resto entre dos enteros.

I Cociente: el resultado de la funcion.

I Resto: argumento modificable.

problema cocienteModificaResto(a, b, r : Int) = q : Int {requiere b > 0;modifica r ;asegura a == q b + r 0 r < b; }

27

Dos argumentos de salida (modifica, no usa pre)

Problema: Calcular el cociente y el resto entre dos enteros

I Cociente y resto: ambos argumentos modificables

I La funcion no retorna un resultado.

problema ModificaCocienteYModificaResto(a, b, q, r : Int){requiere b > 0;modifica q, r ;asegura a == q b + r 0 r < b; }

28

Sobre-especificacion

I Consiste en dar una postcondicion mas restrictiva que lo que senecesita, o bien dar una precondicion mas laxa.

I Limita excesivamente los posibles algoritmos que resuelven elproblema, porque impone mas condiciones para la salida, o amplalos datos de entrada.

I Ejemplo:

problema distinto(x : Int) = res : Int {asegura res == x + 1;

}... en vez de:

problema distinto(x : Int) = res : Int {asegura not(res == x)

}

29

Sub-especificacion

I Consiste en dar una una precondicion mas restrictiva que lorealmente necesario, o bien una postcondicion mas debil que la quese podra dar.

I Deja afuera datos de entrada o ignora condiciones necesarias para lasalida (permite soluciones no deseadas).

I Ejemplo:

problema distinto(x : Int) = res : Int {requiere x > 0;

asegura not(res == x)

}... en vez de:

problema distinto(x : Int) = res : Int {asegura not(res == x)

}30

Especificar los siguientes problemas

I Calcular la funcion signo.problema signo(x : Float) = r : Int {asegura(r == 0 x == 0) (r == 1 x < 0) (r == 1 x > 0)}

I Calcular el area de un triangulo rectangulo.problema area(x , y : Float) = r : Float {

requiere x > 0

requiere y > 0

asegura r == x y/2}

I Encontrar una raz de un polinomio de grado 2.problema raizPolinmioGrado2(a, b, c : Float) = r : Int {

requiere a 6= 0requiere b b 4 a casegura a r r + b r + c == 0}

31

Ultimo ejemplo (por hoy)

Dada una hora, minutos y segundos correspondientes a una hora de lamanana, dar la cantidad de segundos que faltan hasta el medioda.

problema hastamediodia(h,m, s : Int) = r : Int {requiere 0 h < 12requiere 0 m < 60requiere 0 s < 60asegura r + (h 60 + m) 60 + s == 12 60 60

}

32

Logica proposicional

33

Logica proposicional - sintaxis

I Smbolos:

true , false , , , , , , , ( , )

I Variables proposicionales (infinitas)

p , q , r , . . .

I Formulas

1. true, false y son formulas2. Cualquier variable proposicional es una formula3. Si A es una formula, A es una formula4. Si A1,A2, . . . ,An son formulas, (A1 A2 An) es una

formula5. Si A1,A2, . . . ,An son formulas, (A1 A2 An) es una

formula6. Si A y B son formulas, (A B) es una formula7. Si A y B son formulas, (A B) es una formula

34

Semantica clasica

I Dos valores de verdad posibles

1. verdadero (1)2. falso (0)

I El valor de verdad de una formula se obtiene a partir del valor deverdad de sus subformulas.

I true siempre vale 1I false siempre vale 0I A se interpreta como no, se llama negacionI se interpreta como y, se llama conjuncionI se interpreta como o (no exclusivo), se llama disyuncionI se interpreta como si... entonces, se llama implicacionI se interpreta como si y solo si, se llama doble implicacion

o equivalencia

35

Semantica clasica

Conociendo el valor de las variables proposicionales de una formula,conocemos el valor de verdad de la formula

p p1 00 1

p q (p q)1 1 11 0 00 1 00 0 0

p q (p q)1 1 11 0 10 1 10 0 0

p q (p q)1 1 11 0 00 1 10 0 1

p q (p q)1 1 11 0 00 1 00 0 1

36

Ejemplo: tabla de verdad para ((p q) r)

p q r (p q) ((p q) r)1 1 1 1 11 1 0 1 01 0 1 0 11 0 0 0 10 1 1 0 10 1 0 0 10 0 1 0 10 0 0 0 1

37

Un ejercicio

Escribir la siguiente frase como una formula de logica proposicional.

Si Juan esta cursando y no conoce a nadie entonces Juan todava no tiene grupo

I Solucion:p = Juan esta cursando

q = Juan no conoce a nadie

r = Juan no tiene grupo

(p q) = r

38

Otro ejercicio

Sean p = Juan esta cursando; q= Juan no conoce a nadie; r= Juan no tiene grupo.Como se formalizan las siguientes afirmaciones?

1. Si Juan esta cursando entonces no tiene grupo.

Solucion: (p = r)2. Si Juan no tiene grupo entonces Juan no conoce a nadie.

Solucion: (r = q)3. Si Juan esta cursando y no tiene grupo entonces Juan no conoce a nadie.

Solucion: (p r) = q4. Si Juan no conoce a nadie entonces esta cursando y no tiene grupo.

Solucion: q = (p r)5. Si Juan no conoce a nadie entonces esta cursando o no tiene grupo.

Solucion: q = (p r)6. Si Juan tiene grupo entonces Juan conoce a alguien.

Solucion: r = q7. Si Juan tiene grupo, es imposible que este cursando y no conozca a nadie

Solucion: r = (p q)

39

Otro ejercicio

Cuales de las siguientes son una especificacion adecuada para el problema de decidirsi un numero entero es positivo?

problema esPositivo (x : Int) = r : Bool

1. asegura(x > 0 r == true)2. asegura(x > 0 r == true) (x 0 r == true) (x 0 = r == true)5. asegura(x > 0 = r == true) (x 0 = r == true)7. asegura(x > 0 r == true)8. asegura(x

documente1

Documents