Slides TD Parcial1-1-10

Vista previa del material en texto

Especi�cación: explicar el qué
Recordemos que la especi�cación (o contrato) de una función...
I ...de�ne su nombre, parámetros de entrada y tipo de retorno
(Encabezado)
I ...establece los requisitos sobre los parámetros de entrada
(Requiere)
I ...formaliza las propiedades que cumple el resultado de ejecutarse
(Asegura)
I sobre el valor de retorno
I sobre los parámetros que hayan sido modi�cados por referencia
Ejemplo de TD1:
Calcular el volumen de un cilindro de radio r y altura h.
I Encabezado: volumen_cilindro(r:float, h:float) →
float
I Requiere: r > 0; h > 0
I Devuelve: aproximadamente π · r2 · h, donde π ≈ 3.1415927
3
Contratos: Sintaxis en TD3
En esta materia, nuestro formato de especi�cación será
I la declaración de la función en C++ como encabezado
I un apartado Pre que especi�ca la Precondición (requiere) de la
función
I un apartado Post que especi�ca la Postcondición (asegura) de la
función
El mismo ejemplo de TD1
Calcular el volumen de un cilindro de radio r y altura h.
float volumen_cilindro(float r, float h)
Pre: r > 0 ∧ h > 0
Post: res = π ∗ r2 ∗ h
• la variable especial res representa al valor de retorno de la función
Pre y Post estarán escritos en un lenguaje formal :
Lógica de Primer Orden
4
Lógica de Primer Orden
Elementos sintácticos:
I variables de individuo (x , y , z);
I conectivos lógicos proposicionales (∧,∨,¬, =⇒ );
I cuanti�cadores de individuos ((∀x), (∃x));
I predicados (P,Q,R) y funciones (f , g , h);
I las funciones serán las operaciones provistas por cada tipo de datos.
I el símbolo de igualdad =.
Reglas de formación de fórmulas y términos. Si P es un predicado, ti es
un término, f es una función, y F y G son fórmulas:
I una variable es un término;
I la expresión f (t1, . . . , tn) es un término;
I la expresión P(t1, . . . , tn) es una fórmula;
I la expresión t1 = t2 es una fórmula;
I ¬F es una fórmula;
I si ∗ es algún conectivo lógico, (F ∗ G ) es una fórmula;
I Si x es una variable, (∀x)F y (∃x)F son fórmulas.
5
Lógica de Primer Orden Tipada
Agregados sintácticos
I especi�cación de tipos a los cuanti�cadores: (∀x : tipo) y
(∃x : tipo)
I los predicados y las funciones incluyen el tipo de cada uno de sus
parámetros: P(t1 : T1, . . . , tn : Tn) y f (t1 : T1, . . . , tn : Tn)
I un término y una fórmula estarán bien formados si los tipos de sus
variables son coherentes con los tipos esperados por sus fórmulas y
funciones involucradas.
Semántica. Análoga a la de la LPO, pero con una partición del dominio
de discurso diferente para cada tipo.
Sintaxis de escritura de un predicado. Para escribir un predicado, damos
su nombre y parámetros con sus tipos y escribimos a continuación su
fórmula. Ejemplo:
esPar(x : int) ≡ x mód 2 = 0
6
Tipos de datos
En nuestro lenguaje de especi�cación usaremos un subconjunto de los
tipos disponibles en C++:
I bool: valores de verdad
I char: caracteres 'a', 'b', 'c'
I int: números enteros con signo
I float: números en punto �otante
I vector<T> secuencias de elementos de tipo T .
En el lenguaje de especi�cación no existen las referencias, pues no
de�ne un modelo de memoria en el cual podamos hablar de la
ubicación de un elemento.
7
Tipos de datos: bool
Su conjunto de valores son las constantes {true, false}.
I Operadores lógicos && || !, devuelven bool.
I Comparación (= y 6=) (fórmulas; devuelven V/F)
Notar que true/false no son Verdadero / Falso de la lógica y no
son intercambiables. Es decir, la siguiente fórmula para b : bool es
incorrecta:
b =⇒ i > 0
La manera correcta de escribirlo es comparar b con una constante
bool lo cual devolverá un valor lógico Verdadero/Falso:
b = true =⇒ i > 0
8
Tipos de datos: int
Su conjunto de valores son los enteros (Z).
Ejemplos: 1, -2, 333, 0.
Operadores aritméticos
I suma (c + d), resta (c − d), valor absoluto (|c |)
I Producto (*) y división entera(/)
I módulo (c mód b), potenciación (cd)
Fórmulas de comparación
I menor, menor o igual (c < d , c ≤ d)
I mayor, mayor o igual (c > d , c ≥ d)
I igual, distinto (=, 6=)
9
Tipos de datos: char
Su conjunto de valores son las constantes de caracteres de�nidas por el
codigo ASCII:
 !"#$%&\'()*+,-./0123456789:;<=>?
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_
`abcdefghijklmnopqrstuvwxyz{|}~
Se escriben entre comillas simples; por ejemplo 'a', 'b', 'c'.
Operadores
I ord(c) devuelve un int con el número de orden de c .
I char(n) devuelve el char correspondiente al int n.
Se cumple que char(ord(c)) = c para todo c char.
Fórmulas de comparación
I El tipo char soporta los mismos tipos de comparación que int:
< ≤ > ≥ = 6=
I El orden relativo entre elementos de tipo char es el mostrado arriba;
en particular se cumple que '0' < '9', 'a' < 'z', y 'A' < 'Z'.
10
Tipos de datos: float
Su conjunto de valores son los reales (R).
Se admite escribir cualquier constante real (por ejemplo 7.28, e, π).
Operadores aritméticos
I suma (c + d), resta (c − d), valor absoluto (|c |)
I Producto (*) y división (/); si alguno de los dos parámetros es int,
se convierte a float primero
I potenciación y logaritmo (cd , logc d)
I parte entera superior e inferior (d.e b.c); devuelve int
Fórmulas de comparación
I menor, menor o igual (c < d , c ≤ d)
I mayor, mayor o igual (c > d , c ≥ d)
I igual, distinto (=, 6=)
11
Tipos de datos: vector<T>
Representa a una secuencia de elementos de tipo T .
Las constantes de tipo vector<T> se denotan {v1, v2, . . . , vn} donde vi
es algún valor de tipo T ; por ejemplo el vector<int> {1, -5, 3, 0}.
Para vector<char> usaremos la sintaxis simpli�cada
"hola mundo"
para referirnos al vector
{'h','o','l','a',' ','m','u','n','d','o'}
Operadores
I tamaño de un vector v: |v |, equivale a v.size() (devuelve int)
I acceso a la posición i de un vector v : v[i]; sólo de�nido si
0 ≤ i < |v |, devuelve un elemento de tipo T .
Fórmulas de comparación
I igual, distinto (=, 6=), que comparan longitud e igualdad elemento a
elemento usando el operador =T (igualdad de�nida para T ).
12