Programacion en prolog

´ ´ Programacion logica

Curso 2004–05

Tema 3: Programaci´n con o Prolog

Jos´ A. Alonso Jim´nez e e
Jose-Antonio.Alonso@cs.us.es http://www.cs.us.es/∼jalonso

Dpto. de Ciencias de la Computaci´n e Inteligencia Artificial o

Universidad de Sevilla

PL 2004–05

Cc Ia

Programaci´n con Prolog o

3.1

Acumuladores
x

Inversa de una lista (reverse)
u

inversa(+L1,-L2) severifica si L2 es la lista inversa de L1. Por ejemplo, ?- inversa([a,b,c],L). L = [c, b, a]

u

Definici´n de inversa con append (no recursiva final) o inversa_1([],[]). inversa_1([X|L1],L2) :inversa_1(L1,L3), append(L3,[X],L2).

u

Definici´n de inversa con acumuladores (recursiva final) o inversa_2(L1,L2) :inversa_2_aux(L1,[],L2). inversa_2_aux([],L,L). inversa_2_aux([X|L],Acum, Sal):inversa_2_aux(L,[X|Acum],Sal).

PL 2004–05

Cc Ia

Programaci´n con Prolog o

3.2

Acumuladores
u

Comparaci´n de eficiencia o ?- findall(_N,between(1,1000,_N),_L1), time(inversa_1(_L1,_)), time(inversa_2(_L1,_)). % 501,501 inferences in 0.40 seconds (1253753 Lips) % 1,002 inferences in 0.00 seconds (Infinite Lips) Yes ?- findall(_N,between(1,2000,_N),_L1), time(inversa_1(_L1,_)),time(inversa_2(_L1,_)). % 2,003,001 inferences in 1.59 seconds (1259749 Lips) % 2,002 inferences in 0.00 seconds (Infinite Lips) Yes ?- findall(_N,between(1,4000,_N),_L1), time(inversa_1(_L1,_)), time(inversa_2(_L1,_)). % 8,006,001 inferences in 8.07 seconds (992070 Lips) % 4,002 inferences in 0.02 seconds (200100 Lips) Yes

PL 2004–05

Cc Ia

Programaci´n con Prolog o

3.3

Combinatoria
xSubconjuntos
u

subconjunto(-L1,+L2) se verifica si L1 es un subconjunto de L2. Por ejemplo, ?- subconjunto(L,[a,b]). L = [a, b] ; L = [a] ; L = [b] ; L = [] ; No

u

Definici´n de subconjunto o subconjunto([],[]). subconjunto([X|L1],[X|L2]) :subconjunto(L1,L2). subconjunto(L1,[_|L2]) :subconjunto(L1,L2).

PL 2004–05

Cc Ia

Programaci´n con Prolog o

3.4

Combinatoria
x

Conjuntopotencia
u

partes(+L1,-L2) se verifica si L2 es el conjunto de las partes de L1. Por ejemplo, ?- partes([a,b,c],L). L = [[a, b, c], [a, b], [a, c], [a], [b, c], [b], [c], []]

u

Definici´n de partes o partes(L1,L2) :findall(Y,subconjunto(Y,L1),L2).

PL 2004–05

Cc Ia

Programaci´n con Prolog o

3.5

Combinatoria
x

Combinaciones
u

combinaci´n(+L1,+N,-L2) se verifica si L2es una combinaci´n N–aria de L1. Por o o ejemplo, ?- combinaci´n([a,b,c],2,L). o L = [a, b] ; L = [a, c] ; L = [b, c] ; No

u

Definiciones de combinaci´n o combinaci´n(L1,N,L2) :o combinaci´n_2(L1,N,L2). o combinaci´n_1(L1,N,L2) :o subconjunto(L2,L1), length(L2,N). combinaci´n_2(L1,N,L2) :o length(L2,N), subconjunto(L2,L1).

PL 2004–05

Cc Ia

Programaci´n con Prolog o

3.6Combinatoria
u

combinaciones(+L1,+N,-L2) se verifica si L2 es la lista de las combinaciones N–arias de L1. Por ejemplo, ?- combinaciones([a,b,c],2,L). L = [[a, b], [a, c], [b, c]]

u

Definiciones de combinaciones combinaciones(L1,N,L2) :combinaciones_2(L1,N,L2). combinaciones_1(L1,N,L2) :findall(L,combinaci´n_1(L1,N,L),L2). o combinaciones_2(L1,N,L2) :findall(L,combinaci´n_2(L1,N,L),L2). o

PL2004–05

Cc Ia

Programaci´n con Prolog o

3.7

Combinatoria
u

Comparaci´n de eficiencia: o ?- findall(_N,between(1,6,_N),_L1), time(combinaciones_1(_L1,2,_L2)), time(combinaciones_2(_L1,2,_L2)). % 429 inferences in 0.00 seconds (Infinite Lips) % 92 inferences in 0.00 seconds (Infinite Lips) Yes ?- findall(_N,between(1,12,_N),_L1), time(combinaciones_1(_L1,2,_L2)),time(combinaciones_2(_L1,2,_L2)). % 28,551 inferences in 0.01 seconds (2855100 Lips) % 457 inferences in 0.00 seconds (Infinite Lips) Yes ?- findall(_N,between(1,24,_N),_L1), time(combinaciones_1(_L1,2,_L2)), time(combinaciones_2(_L1,2,_L2)). % 117,439,971 inferences in 57.59 seconds (2039242 Lips) % 2,915 inferences in 0.00 seconds (Infinite Lips) Yes

PL 2004–05

Cc Ia

Programaci´n con Prolog o

3.8...