PDF de programación - Tema 3 - Tecnología de la Programación

UNIVERSIDAD DE A CORUÑA
FACULTAD DE INFORMÁTICA

DEPARTAMENTO DE COMPUTACIÓN

Tecnología de la Programación
Tecnología de la Programación

Ingeniería Técnica en Informática de Sistemas
Ingeniería Técnica en Informática de Sistemas

Elena Mª Hernández Pereira
Elena Mª Hernández Pereira

Óscar Fontenla Romero
Óscar Fontenla Romero

Bloque didáctico I: Introducción
Bloque didáctico I: Introducción

Tema 3
Tema 3

oo Título

Título: Arrays, notación y simplificación de
: Arrays, notación y simplificación de
expresiones
expresiones

oo Unidades de contenido
Unidades de contenido
Arrays de una dimensión
•• Arrays de una dimensión
•• Simplificación de expresiones
Simplificación de expresiones
•• Arrays multidimensionales
Arrays multidimensionales

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

22

1

Tema 3: Arrays
Tema 3: Arrays

Bloque didáctico I:

Introducción

oo Declaración
Declaración
••

var b: array [0:2] of integer
var b: array [0:2] of integer
b[0:2]:integer
b[0:2]:integer

••
Dos formas de entender el array:
oo Dos formas de entender el array:
Conjunto de identificadores clasificados por un índice
1.1. Conjunto de identificadores clasificados por un índice
•• Ej: b[0], b[1], b[2]
s = { (b[0],4), (b[1],--2), (b[2],7) }
s = { (b[0],4), (b[1],
Ej: b[0], b[1], b[2]
2), (b[2],7) }
2.2. Un solo identificador cuyos valores son funciones
Un solo identificador cuyos valores son funciones
•• Ej:Ej:

s = { (b,(4, --2, 7)) }
s = { (b,(4,
2, 7)) }

b: {0, 1, 2} fi
b: {0, 1, 2}
0 fi
0
1 fi
1
2 fi
2

integer
integer
44
--22
77

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

33

Tema 3: Arrays
Tema 3: Arrays

Notación
Notación

Bloque didáctico I:

Introducción

oo

b.sup ⇒⇒ valores extremos del índice de
valores extremos del índice de

b.infb.inf y y b.sup
posiciones del array
posiciones del array

••

Ej: Ej:

oo

oo

oo

b.inf = 0
b.inf = 0

b.sup }
b.sup }

b.sup = 2
b.sup = 2
i i £
dominio(b)
dominio(b)

dominio(b) = { i | b.inf £
dominio(b) = { i | b.inf
ya que 15 15 ˇˇ
s(b[15]) = U
s(b[15]) = U ya que
¿Significado de
¿Significado de b[1] := 8
b[1] := 8 ??
Cambiar el valor de b[1] por 8
1.1. Cambiar el valor de b[1] por 8
2.2. Cambiar el valor de b por (4, 8, 7)
Cambiar el valor de b por (4, 8, 7)
oo Nueva notación: El array (b; i : e) es tal que
Nueva notación: El array (b; i : e) es tal que

eib
;(

:

)[

j

]

=





e

i
si

=

j

b[j]

si

i

j

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

44

2

fi
fi
fi
fi
£
£
„
Bloque didáctico I:

Introducción

Tema 3: Arrays
Tema 3: Arrays

Notación
Notación

(b; i:e; j:f; k:g) = (((b; i:e); j:f); k:g)
oo (b; i:e; j:f; k:g) = (((b; i:e); j:f); k:g)
Omisión de paréntesis
•• Omisión de paréntesis
•• Los pares i:e más a la derecha son dominantes y
Los pares i:e más a la derecha son dominantes y
tienen preferencia
tienen preferencia
oo Predicado auxiliar

Predicado auxiliar perm(b,c)
perm(b,c)
El array c c es permutación de
•• El array
es permutación de bb
Ej: b[0:2] = (4, 8, 7)
•• Ej: b[0:2] = (4, 8, 7)
perm(b,c) es cierto para los valores de c:
•• perm(b,c)
es cierto para los valores de c:
 (4, 8, 7), (4, 7, 8), (8, 4, 7), (8, 7, 4), (7, 4, 8), (7, 8,4)
(4, 8, 7), (4, 7, 8), (8, 4, 7), (8, 7, 4), (7, 4, 8), (7, 8,4)

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

55

Tema 3: Arrays
Tema 3: Arrays

Bloque didáctico I:

Introducción

oo Simplificación de expresiones:

Simplificación de expresiones: (b; i : 5 )[ j ]
(b; i : 5 )[ j ]

Definición

5=5 es T + Ley de
simplificación del AND

Leyes distributivas

Ley del medio excluido

Ley de simplificación del AND

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

66

3

Tema 3: Arrays
Tema 3: Arrays

oo Secciones de un array
Secciones de un array
b[0:Nb[0:N--1]1]:integer,

:integer, i,ji,j expresiones enteras con

expresiones enteras con i i ££

Bloque didáctico I:

Introducción

j+1j+1

array b restringido al rango i:ji:j

•• b[i:j]b[i:j] ⇒⇒ array b restringido al rango
•• b[0:Nb[0:N--1]1] ⇒⇒ array completo
array completo
•• b[i:j]b[i:j] sección vacía si
sección vacía si i > j
i > j
•• Todos los elementos de
: b[I] < x) ”” b < x
b < x

Todos los elementos de bb son menores que
son menores que xx
 ((""
El array bb sólo contiene ceros
sólo contiene ceros
 ((""

I I ˛˛
•• El array
I I ˛˛

[0,N[0,N〉〉: b[I] = 0)

: b[I] = 0) ”” b = 0
b = 0

[0,N[0,N〉〉: b[I] < x)

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

77

Tema 3: Arrays
Tema 3: Arrays

Bloque didáctico I:

Introducción

def

oo Algunas abreviaturas
Algunas abreviaturas
I I ˛˛
b[1:4] = x (""
•• b[1:4] = x (
I I ˛˛
b[1:4] „„ x (
x (""
•• b[1:4]
I I ˛˛
b[0:3] ££ b[3:6] (
b[3:6] (""
•• b[0:3]
def
••
(b[1:4] = x) ($$
I I ˛˛
(b[1:4] = x) (
def

def

[1,4]: b[I] = x)
[1,4]: b[I] = x)
[1,4]: b[I] „„ x)x)
[1,4]: b[I]
[0,3], J ˛˛
[0,3], J
[1,4]: b[I] „„ x)x)
[1,4]: b[I]

[3,6]: b[I] ££ b[J])b[J])
[3,6]: b[I]

oo x x ˛˛

bb ⇒⇒ El valor

El valor xx es igual a uno al menos de los
es igual a uno al menos de los

valores de
valores de b[i]b[i]
I I ˛˛
(($$
•• x x ˛˛

b b ””

dominio(b): x= b[I])
dominio(b): x= b[I])

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

88

4

Tema 3: Arrays
Tema 3: Arrays

Cuadros con arrays
Cuadros con arrays

Bloque didáctico I:

Introducción

b[0:n--1]1] con valores
con valores

oo Ej: Ordenar un array

Ej: Ordenar un array b[0:n
iniciales
iniciales B[0:nB[0:n--1]1]
a)a) b[0:k

b[0:k--1]1] ordenado y todos sus elementos son como
ordenado y todos sus elementos son como
mucho
mucho xx
El valor correspondiente a b[k]b[k] está en
está en xx
Cada valor en b[k+1:n
b[k+1:n--1]1] es al menos
es al menos xx

b)b) El valor correspondiente a
c)c) Cada valor en
oo Formalmente
Formalmente

0

k

n

ordenado

:0[(
b

k

])1

perm

((

ordenado

:0[(
b

k

])1

"=
(

I

,0[

k

][:1

Ib

[
Ib

+

])1

Bxkb

),

;

:

)

b

:0[

k

]1

kbx

[

+

:1

n

]1

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

99

Tema 3: Arrays
Tema 3: Arrays

Cuadros con arrays (II)
Cuadros con arrays (II)

Bloque didáctico I:

Introducción

oo Notación gráfica
Notación gráfica
0 £ k £ n

b

0 k-1 k+1 n-1

Orden ≤ ≥ x

perm(B,(b;k:x))

k k+1 n-1
≥ x

•• Partición vacía
Partición vacía
Inconveniente
Inconveniente
•• Se pueden olvidar casos particulares
Se pueden olvidar casos particulares

b

oo

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

1010

5

-
£
£
-


-

£
£
£
-
˛
-

Tema 3: Arrays
Tema 3: Arrays

multidimensionales
multidimensionales

Bloque didáctico I:

Introducción

Declaración
oo Declaración
•• var b: array [0:1] of array [1:3] of integer
var b: array [0:1] of array [1:3] of integer
oo b[i][j] = b[i,j]
b[i][j] = b[i,j]
Ej: b[0:1][1:3]= { (16,17,18), (21, 22, 23)}
oo Ej: b[0:1][1:3]= { (16,17,18), (21, 22, 23)}
b[1] = (21, 22, 23)
•• b[1] = (21, 22, 23)
•• b[1][2] = b[1,2] = 22
b[1][2] = b[1,2] = 22
Notación
oo Notación
•• b[i][j] := e
b[i][j] := e ⇒⇒(b;[i][j]:e)
(b;[i][j]:e)
•• Se incluyen los corchetes por claridad
Se incluyen los corchetes por claridad

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

1111

Tema 3: Arrays
Tema 3: Arrays

multidimensionales (II)
multidimensionales (II)

Bloque didáctico I:

Introducción

selector ((s
oo Un Un selector

) es una secuencia de subíndices
) es una secuencia
de subíndices

entre corchetes
entre corchetes
Selector nulo ((e
oo Selector nulo
): contiene cero subíndices
): contiene cero subíndices
de secuencias ((o
Concatenador de secuencias
oo Concatenador
oo Con ello, tenemos:
Con ello, tenemos:
••
•• xx variable simple
•• b b o
•• b[0]

variable simple ⇒⇒ xx o
array completo
completo
b[0] ⇒⇒ identificador b + selector [0]
identificador b + selector [0]

))

= = s

⇒⇒ array

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

1212

6

s
e
o
s
s
o
o
e
e
s
o
e
e
o
e
e
Bloque didáctico I:

Introducción

Tema 3: Arrays
Tema 3: Arrays

multidimensionales (III)
multidimensionales (III)

Notación (b; s
oo Notación (b;
Definición recursiva sobre la longitud de ss
•• Definición recursiva sobre la longitud de

: e)
: e)

(b; e
(b;

(1)(1)

: e) = e (caso base)
: e) = e (caso base)

(2)(2)

os
ib
][;(

:

e

)[

j

]

s

];

i
e
si ):

=

j


jb
[(
=

b[j]


i
si

j

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

1313

Tema 3: Arrays
Tema 3: Arrays

multidimensionales (IV)
multidimensionales (IV)

Bloque didáctico I:

Introducción

Ejercicio
oo Ejercicio
•• Sea c[1:3] = (6,7,8) y b[0:1][1:3] ={(0, 1, 2), (3, 4, 5)}
Sea c[1:3] = (6,7,8) y b[0:1][1:3] ={(0, 1, 2), (3, 4, 5)}
oo Evaluar
Evaluar
••

(b; [1][3] : 9)[0]
(b; [1][3] : 9)[0]
(b; [1][3] : 9)[1]
(b; [1][3] : 9)[1]
(b; [1][3] : 9)[1][3]
(b; [1][3] : 9)[1][3]
(b; [1][3] : 9)[1][2]
(b; [1][3] : 9)[1][2]

: b[1])
: b[1])
: b[1])[2]
: b[1])[2]

(c; e
(c;
(c; e
(c;
(c; 1 : 3)[1]
(c; 1 : 3)[1]
(c;