´ ´ Programacion logica
Curso 2004–05
Tema 3: Programaci´n con o Prolog
Jos´ A. Alonso Jim´nez e e
[email protected] http://www.cs.us.es/?jalonso
Dpto. de Ciencias de la Computaci´n e Inteligencia Arti?cial 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) severi?ca si L2 es la lista inversa de L1. Por ejemplo, ?- inversa([a,b,c],L). L = [c, b, a]
u
De?nici´n de inversa con append (no recursiva ?nal) o inversa_1([],[]). inversa_1([X|L1],L2) :inversa_1(L1,L3), append(L3,[X],L2).
u
De?nici´n de inversa con acumuladores (recursiva ?nal) 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 e?ciencia 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 veri?ca si L1 es un subconjunto de L2. Por ejemplo, ?- subconjunto(L,[a,b]). L = [a, b] ; L = [a] ; L = [b] ; L = [] ; No
u
De?nici´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 veri?ca 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
De?nici´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 veri?ca 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
De?niciones de combinaci´n o combinaci´n(L1,N,L2) 😮 combinaci´n_2(L1,N,L2). o combinaci´n_1(L1,N,L2) 😮 subconjunto(L2,L1), length(L2,N). combinaci´n_2(L1,N,L2) 😮 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 veri?ca 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
De?niciones 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 e?ciencia: 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…
