Download Programación en LISP (2)

Programación en LISP (2). Inteligencia Artificial.
Tercero de Ingeniería Informática. UAM.
1.
Escribir una función recursiva que calcule el factorial de un número. Comparar esta versión de la
función con la iterativa de la hoja anterior de problemas.
2.
Escribir una función recursiva que calcula la suma de los N primeros números enteros. Escribir otra
version iterativa y compárense las longitudes de las dos definiciones contando el número de átomos
en cada una de ellas. ¿Qué otro criterio de comparación se podría utilizar a la hora de elegir una de
estas dos funciones?
3.
Definir APARECE-P, un predicado que determina si un átomo aparece en una expresión dada.
APARECE-P difiere de MEMBER en el sentido de que MEMBER busca solamente al primer nivel de
anidamiento en una expresión.
4.
Definir APLANA, una función que toma una lista como argumento y devuelve una lista no anidada
formada por todos los átomos que aparecen en la expresión inicial. Así, por ejemplo
(APLANA '(A (B (C D) E))) => (A B C D E)
5.
Escribir una función que a partir de una lista devuelva el número de sublistas contenidas en la misma
(incluido las anidadas).
6.
Escribir una función que a partir de una lista devuelva otra lista obtenida invirtiendo el orden de sus
elementos, operación que se aplica recursivamente a cada uno de los elementos que son listas.
7.
Definir un predicado de igualdad entre listas que no tenga en cuenta el orden de los elementos (a
cualquier nivel de anidamiento).
8.
Para representar posiciones en una partida de damas se utiliza la estructura de datos
TABLERO-DAMAS formada por una lista de 8 listas, siendo cada una de éstas la representación de las
filas 1 a 8, y donde las piezas se representan por los símbolos NIL (vacío), B (Blanca), N (Negra),
DB (Dama Blanca) y DN (Dama Negra), como por ejemplo:
((NIL NIL B NIL N NIL DB DN) ... (DB DB NIL NIL NIL N B NIL))
Definir VALOR-ESTATICO, una función que devuelve el número de piezas blancas (B y DB)
menos el número de piezas negras (N y DN) en la variable TABLERO-DAMAS.
9.
Definir una función PROD-CART que obtenga el producto cartesiano de dos listas del siguiente
modo:
(PROD-CART '(1 2) '(A B C)) =>
((1 A) (1 B) (1 C) (2 A) (2 B) (2 C))
10. Escribir una funcion que calcule el conjunto de las partes de cualquier conjunto, como en:
(conjunto-partes '(a b c)) =>
(() (a) (b) (c) (a b) (a c) (b c) (a b c))
11. Definir una función que transforme un string en una lista (si tiene sentido). Por ejemplo, a partir de
"(/ (* 3 4) (- 6 8))" se debe obtener la lista (/ (* 3 4) (- 6 8)).
12. Definir una función que obtenga el máximo común divisor de dos números utilizando el algoritmo de
Euclides.
13. Definir funciones de suma y multiplicación de polinomios en una variable.
14. Escribir una función que calcule el máximo común divisor de dos polinomios de una variable.
15. Definir una función que resuelva un sistema de 3 ecuaciones lineales, suponiendo que éste tenga una
única solución.
16. Escribir un programa que convierta números en decimal a romanos y viceversa.
17. Escribir una función recursiva que calcule la potencia n-ésima de una matriz. Optimizarla utilizando
anidamiento en potencias de dos (divide y vencerás). Escribir funciones iterativas que hagan los
mismos cálculos.
18. Escribir una función recursiva que calcule el valor de una función f compuesta consigo misma n
veces en el punto x. ¿Se puede optimizar utilizando anidamiento en potencias de 2? Escribir una
función iterativa que haga el mismo cálculo.
19. Escirbir una función que determine si una lista tiene ciclos (es decir, si entre los punteros que la
definen existen bucles).
20. Escribir una función que saque una copia de una lista, sacando copias nuevas de sus elementos que
sean listas. (Todos sus punteros deben ser nuevos).