PDF de programación - Implementación de algoritmos y cálculo simbólico

Dpto. de Álgebra, Computación, Geometría y Topología

Universidad de Sevilla

Implementación de algoritmos

y cálculo simbólico

(Curso 90–91)

José A. Alonso Jiménez

Sevilla, 1990

Contenido

1 Cálculo aritmético en Lisp

1.1 Operaciones aritméticas

. . . . . . . . . . . . . . . . . . . .

1.2 Asignación de valores a variables

. . . . . . . . . . . . . . .

1.3 Definición de nuevas funciones . . . . . . . . . . . . . . . . .

1.4 Programación descendente . . . . . . . . . . . . . . . . . . .

1.5 Las variables locales

. . . . . . . . . . . . . . . . . . . . . .

2 El cálculo simbólico

2.1 Los objetos básicos . . . . . . . . . . . . . . . . . . . . . . .

2.2 La función QUOTE . . . . . . . . . . . . . . . . . . . . . . .

2.3 Las funciones SET y SETQ . . . . . . . . . . . . . . . . . .

2.4 Funciones de búsqueda en listas . . . . . . . . . . . . . . . .

2.5 Funciones de construcción de listas

. . . . . . . . . . . . . .

2.6 Funciones de modificación física de listas . . . . . . . . . . .

3 El control

3.1 Funciones de comparación de números

. . . . . . . . . . . .

3.2 Funciones de comparación de símbolos y listas . . . . . . . .

3.3 Condicionales . . . . . . . . . . . . . . . . . . . . . . . . . .

4 La programación recursiva

4.1 Funciones recursivas

. . . . . . . . . . . . . . . . . . . . . .

4.2 Las funciones de trazado . . . . . . . . . . . . . . . . . . . .

4.3 Aritmética entera positiva . . . . . . . . . . . . . . . . . . .

2

2

3

4

5

6

7

7

8

8

8

11

12

13

13

14

15

19

19

19

19

ii

4.4 La aritmética ordinaria del lisp . . . . . . . . . . . . . . . .

4.5 Simulación de primitivas sobre listas

. . . . . . . . . . . . .

4.6 Definición de funciones sobre listas

. . . . . . . . . . . . . .

4.7 Funciones sobre árboles . . . . . . . . . . . . . . . . . . . . .

4.8 Funciones sobre conjuntos

. . . . . . . . . . . . . . . . . . .

5 La iteración en Lisp

5.1 El grupo PROG, GO, RETURN . . . . . . . . . . . . . . . . . . .

5.2 Las funciones DO y DO* . . . . . . . . . . . . . . . . . . . . .

5.3 Las funciones DOTIMES y DOLIST . . . . . . . . . . . . .

5.4 La función MAPCAR . . . . . . . . . . . . . . . . . . . . . . .

5.5 La función APPLY . . . . . . . . . . . . . . . . . . . . . . . .

6 Funciones anónimas

6.1 La función LAMBDA . . . . . . . . . . . . . . . . . . . . . . .

6.2 Las funciones EVERY y SOME . . . . . . . . . . . . . . . . . .

7 Las A–listas (listas de asociación)

7.1 Pares punteados . . . . . . . . . . . . . . . . . . . . . . . . .

7.2 A–listas

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 Las P–listas (listas de propiedades)

8.1 P–listas

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8.2 Bases de datos . . . . . . . . . . . . . . . . . . . . . . . . . .

8.3 Programación dirigida por los datos . . . . . . . . . . . . . .

8.4 Funciones con memoria . . . . . . . . . . . . . . . . . . . . .

9 Lectura y escritura

9.1 Funciones de lectura y escritura . . . . . . . . . . . . . . . .

9.2 Funciones de lectura y escritura sobre ficheros . . . . . . . .

21

22

23

24

26

28

28

28

29

30

30

31

31

31

33

33

33

36

36

38

39

40

42

42

44

1

Capítulo 1

Cálculo aritmético en Lisp

1.1 Operaciones aritméticas

1.1.1 Calcular en LISP:

1. 3 + 5

2. 2 + 3 + 4

3. 20/5

4. 5/20

5. (24/3)/2

6. 1/0.5

1.1.2 Calcular en LISP:

1. (1 − 2)(4 + 5)
2. (15 + 5) + (100 − 45)

1.1.3 Calcular en LISP:

2(4 − 1)6

18

+ (8 − 6)7

1.1.4 Calcular el valor de las siguientes expresiones:

2

(+)
(+ 3)
(+ 3 7 5)
(+ 32000 32000)
(+ 32000.0 32000)

(- 3)
(- 123 7 5)

(ABS 3)
(ABS -3.6)

(*)
(* 3)
(* 3 7 5)
(* 32000 32000)
(* 32000.0 32000)

(/ 6 2)
(/ 5 2)

(/ 2)
(/ 0.5)

(MOD 7 2)

(MAX 1 2 3 4 5 2)
(MAX -2.3 7 0)

(MIN 3)
(MIN 1 2 3 4 5 2)
(MIN -2.3 7 0)

1.2 Asignación de valores a variables

1.2.1 Escribir el resultado de las siguientes formas:

(SETQ PRECIO 80)
(SETQ IVA 10)
PRECIO

3

(/ (* PRECIO IVA) 100)

1.2.2 Escribir el resultado de las siguientes formas:

(+ 1 2 X 3)
(SETQ X (* 2 5))
(+ 1 2 X 3 )
(SETQ X 1 Y 2 Z (+ X Y))
(+ X Y Z)

1.2.3 Calcular el valor de C después de la evaluación de la expresión

(SETQ A 3 C (+ (SETQ B 4) (+ A B)))

1.2.4 Calcular el valor de las siguientes expresiones:

(SETQ X 3)
(INCF X)
X
(DECF X 3)
X

1.3 Definición de nuevas funciones

1.3.1 Definir de la función

(CUBO X)

de forma que devuelva el valor del cubo de X. Por ejemplo,

(CUBO 2)
8
(CUBO (+ 2 3)) => 25

=>

1.3.2 Definir de la función

(SUMA-BINARIA X Y)

que devuelva la suma del valor de X y el de Y. Por ejemplo,

(SUMA-BINARIA 2 3)
(SUMA-BINARIA 2 (* 2 3))
(* (SUMA-BINARIA (+ 50 50) 1) 3) => 303

=> 5
=> 8

4

1.3.3 Calcular el valor de las siguientes expresiones:

(DEFUN NUMERO () (SETQ X (1+ X)))
(SETQ X 0)
(+ (NUMERO) (NUMERO) (NUMERO))
X

1.3.4 Calcular el valor de las siguientes expresiones:

(SETQ DOS 2)
(DEFUN DOS () 3)
(+ DOS (DOS))

1.4 Programación descendente

1.4.1 Definir la función

(MEDIA-CUADRADO X Y)

que devuelva la media de los cuadrados de X e Y. Por ejemplo,

(MEDIA-CUADRADO 2 4) =>

10.0

1.4.2 Definir la función

(CUADRADO-MEDIA X Y)

que devuelva el cuadrado de la media de X e Y. Por ejemplo,

(CUADRADO-MEDIA 2 4) =>

9.0

1.4.3 Escribir una función

(P2 A B C X)

que devuelva el valor del polinomio ax2 + bx + c. Por ejemplo,

(P2 4 3 2 2)

=> 24

1.4.4 Definir, utilizando la función P2, la función

(P4 X)

que calcule el valor del polinomio 3x4 + 7x2 + 4.

5

1.5 Las variables locales

1.5.1 Calcular el valor de las siguientes expresiones:

(SETQ X 1)
(LET ((X 2) (Y 3)) (+ X Y))
X

1.5.2 Definir la función

(F1 b c)

que calcule la media de los cuadrados de las raíces de la ecuación a x2 +
bx + c = 0. Por ejemplo,

(F1 1 -5 6) => 6.5

6

Capítulo 2

El cálculo simbólico

2.1 Los objetos básicos

2.1.1 Determinar si los siguientes objetos son números, símbolos, listas o
no son expresiones Lisp:

123
ATOMO
(ESTO ES UN ATOMO)
((A B) (C D)) 3 (3)
(LISTA 3)
(/ (+ 3 1) (- 3 1))
)(
((()))
(() ())
((ABC

2.1.2 Determinar el número de elementos y la profundidad de las siguientes
listas:

(1 DOS 3 CUATRO)
(SOCRATES (- 43 1))
((X 1) (Y 2) (Z 3))
(- (* 2 (+ A 3)))
(((1)))
(DEFUN SUMA (X Y) (+ X Y))
()

7

2.2 La función QUOTE

2.2.1 Determinar el valor de las siguientes expresiones:

A
(SETQ A 3)
(QUOTE A)
’A

2.2.2 Determinar el valor de las siguientes expresiones:

(A B C)
(QUOTE (A B C))
’(A B C)
(+ 2 3)
’(+ 2 3)

2.3 Las funciones SET y SETQ

2.3.1 Determinar el valor de las siguientes expresiones:

(SETQ HOMBRE ’SOCRATES)
HOMBRE
(SETQ SOCRATES 1)
HOMBRE
(SETQ MORTAL HOMBRE)
MORTAL
(SET ’HOMBRE ’PLATON)
HOMBRE
MORTAL
(SET HOMBRE ’SOCRATES)
HOMBRE
PLATON

2.4 Funciones de búsqueda en listas

2.4.1 Determinar el valor de las siguientes expresiones:

(CAR ’(A B C))

8

(CAR ’((D E) F (G H)))
(SETQ L ’(10 20))
(CAR L)
(CAR (SETQ M ’(+ 1 2)))
(CDR ’ (A B C))
(CDR ’((D ((E F))) G (H I)))
(CDR L)
(CDR M)
(CAR (CDR M))
(CAR (CDR (CDR M)))
(CDR (CAR (CDR (CAR ’((D (E F)) G (H I))))))

2.4.2 Definir las funciones

(SEGUNDO L)
(TERCERO L)

que devuelven el segundo o tercer elemento de la lista L. Por ejemplo,

(SEGUNDO ’(A B C D))
(TERCERO ’(A B C D))

=> B
=> C

2.4.3 Determinar el valor de las siguientes expresiones:

(SETQ M ’(A (B C) D E))
(CADR M)
(CADDR M)

2.4.4 Escribir los árboles binarios de la siguientes listas:

((A B) C (D E))
(DEFUN SUMA (X Y) (+ X Y))

y encontrar los CADDR y CADADDR de dichas listas.

2.4.5 Determinar el valor de las siguientes expresiones:

(SETQ L ’(A (B C) D E))
(NTH 0 L)
(NTH 2 L)
(NTH 8 L)
(NTHCDR 0 L)

9

(NTHCDR 2 L)
(NTHCDR 8 L)
(LAST L)
(LENGTH L)

(SETQ L ’(DEFUN SUMA (X Y) (+ X Y)))
(NTH 2 L)
(NTHCDR 2 L)
(LAST L)
(LENGTH L)

2.4.6 Escribir sucesiones de CAR y CDR para obtener DINERO de las sigu-
ientes expresiones:

(AGUA PAPEL DINERO TIERRA)
((AGUA PAPEL) DINERO TIERRA)
((AGUA PAPEL) (DINERO TIERRA))
(AGUA (PAPEL DINERO) TIERRA)
((AGUA PAPEL) ((DINERO) TIERRA))

2.4.7 Definir la función

(ULTIMO L)

que devuelva el último elemento de la lista L. Por ejemplo,

(ULTIMO ’(A B C)) => C

2.4.8 Definir la función

(PENULTIMO L)

que devuelva el penúltimo elemento de la lista L. Por ejemplo,

(PENULTIMO ’(A B C)) => B

2.4.9 Definida la variable AGENDA por

(SETQ AGENDA ’((PEPE SIERPES-12 "531420")

(JUAN CUNA-5 "243568")
(PABLO CERVANTES-45 "456345")))

10

Definir las funciones

(NOMBRE N)
(DIRECCION N)
(TELEFONO N)

de forma que devuelvan el nombre, la dirección o el teléfono n-ésimo de la
lista. Por ejemplo,

(NOMBRE 1)
(DIRECCION 2)
(TELEFONO 3)

2.5 Funciones de construcción de listas

2.5.1 Determinar el valor de las siguientes expresiones:

(CONS ’A ’(B C D))
(CONS ’(A B) ’(C D))
(CONS ’JB (CONS 0 (CONS 0 (CONS 7 NIL))))
(CONS NIL NIL)
(CONS (CAR ’(A B)) (CDR ’(B C)))

2.5.2 Determinar el valor de las siguientes expresiones:

(SETQ L (CONS (- 5 3) ’(ES UN NUMERO)))
(CONS ’7+ L)
L

2.5.3 Determinar el valor de las siguientes expresiones:

(LIST ’A ’B ’C)
(LIST ’A 1 ’B 2)
(SETQ L (LIST ’EL ’NUMERO 3))
(LIST (CAR L) ’DIGITO (CADDR L))
(LIST ’* (+ 2 3) ’(/ X 2))
(LIST NIL)

2.5.4 Determinar el valor de las siguientes expresiones:

11

(APPEND ’(A B) ’(C D))
(APPEND ’(1 2) ’ (3 4) ’(5 6 7))
(APPEND (LIST ’* (+ 2 3)) ’(4 5))
(APPEND NIL ’(A B))

2.5.5 Determinar el valor de las siguientes expresiones:

(CONS ’(A B) ’(C D))
(LIST ’(A B) ’(C D))
(APPEND ’(A B) ’(C D))

2.5.6 Definir la función

(ROTAR-IZQ L)

de forma que devuelva la lista obtenida pasando el primer elemento de L al
último lugar. Por ejemplo,

(ROTAR-IZQ ’(A B C D))

2.5.7 Definir la función

(PASA-1-A-3 L)

de forma que coloque el primer elemento de la lista L en tercer lugar. Por
ejemplo,

(PASA-1-A-3 ’(A B C D))

2.6 Funciones de modificación física de listas

2.6.1 Determinar el valor de las siguientes expresiones:

(SETQ L ’(Y Z))
(PUSH ’X L)
L

2.6.2 Determinar el valor de las siguientes expresiones:

(SETQ A ’(X Y Z))
(POP A)
A

12

Capí