View
265
Download
1
Category
Preview:
Citation preview
Opti malDivide & Query
David Insa Cabrera
IntroducciónDepuración Algorítmica
Divide & QueryLimitaciones de Divide & QueryOptimal Divide & Query
DemostraciónDDJ
Conclusiones
Contenido
¿Qué es un Árbol de Ejecución?
Depuración algorítmica [Shapiro 82] Paradigma Lógico
DOS FASES:• Generar el árbol de ejecución• Recorrer el árbol de ejecución haciendo preguntas hasta encontrar el error
Si se detecta el efecto de un errorentonces la DA encontrará el error
main = 4
listSum [] = 1
1+3 = 4
2+1 = 3
listSum [1,2] = 4
listSum [2] = 3
Depuración Algorítmica
Ejemplo:
main = listSum [1,2]
listSum [] = 1listSum (x:xs) = x + (listSum xs)
Recorriendo el árbol de ejecución
• REGLA DE ORO: Cuando un nodo incorrecto no tiene hijos incorrectos, entonces este nodo es erróneo.
Ejemplo:
main = listSum [1,2]
listSum [] = 1listSum (x:xs) = x + (listSum xs)
main = 4
listSum [] = 1
1+3 = 4
2+1 = 3
listSum [1,2] = 4
listSum [2] = 3
Depuración Algorítmica
Recorriendo el árbol de ejecución
• REGLA DE ORO: Cuando un nodo incorrecto no tiene hijos incorrectos, entonces este nodo es erróneo.
Ejemplo:
main = listSum [1,2]
listSum [] = 0listSum (x:xs) = x + (listSum xs) + 1
main = 5
listSum [] = 0
1+3+1 = 5
2+0+1 = 3
listSum [1,2] = 5
listSum [2] = 3
Depuración Algorítmica
(1) do(2) node = selectNode(T)(3) answer = askNode(node)(4) if (answer = NO)(5) then M(node) = Wrong(6) buggyNode = node(7) N = {n ∈ N | (node n) ∈ E*}(8) else N = N \ {n ∈ N | (node n) ∈ E*}(9) while (∃n ∈ N, M(n) = Undefined)(10) return buggyNode
Depuración Algorítmica
IntroducciónDepuración Algorítmica
Divide & QueryLimitaciones de Divide & QueryOptimal Divide & Query
DemostraciónDDJ
Conclusiones
• Estrategias de la DA• Sesión de depuración
Contenido
Estrategias
Top Down - Left to RightTop Down - Heaviest FirstTop Down - More Rules First
Divide & Query (by Shapiro)Divide & Query (by Hirunkitti)Divide by Rules & Query
Single Stepping
Hat Delta - More WrongsHat Delta - Less RightsHat Delta - Best Division
Top Down
Hat Delta
Divide & Query
Single Stepping
Estrategias de la Depuración Algorítmica
Sesión de depuración
main = sqrTest [1,2]
sqrTest x = test (squares (listSum x))
test (x,y,z) = (x==y) && (y==z)
listSum [] = 0listSum (x:xs) = x + (listSum xs)
squares x = ((square1 x),(square2 x),(square3 x))
square1 x = square x square x = x*x square2 x = listSum (list x x) list x y | y==0 = [] | otherwise = x:list x (y-1)
square3 x = listSum (partialSums x)
partialSums x = [(sum1 x),(sum2 x)]
sum1 x = div (x * (incr x)) 2sum2 x = div (x + (decr x)) 2
incr x = x + 1decr x = x - 1
Sesión de depuración
Sesión de depuración con la búsqueda Divide & Query (by Hirunkitti).
main = False
sqrTest [1,2] = False
test (9,9,8) = False squares 3 = (9,9,8) listSum [1,2] = 3
squares1 3 = 9 squares2 3 = 9 squares3 3 = 8listSum [2] = 2
listSum [] = 0square 3 = 9 listSum [3,3,3] = 9
listSum [3,3] = 6
listSum [3] = 3
listSum [] = 0
list 3 3 = [3,3,3]
list 3 2 = [3,3]
list 3 1 = [3]
list 3 0 = []
listSum [6,2] = 8
listSum [2] = 2
listSum [] = 0
partialSums 3 = [6,2]
sum1 3 = 6 sum2 3 = 2
incr 3 = 4 decr 3 = 2
Empezando la sesión de depuración…
1) square2 3 = 9? SI
2) square3 3 = 8? NO
3) partialSums 3 = [6,2]? NO
4) sum1 3 = 6? SI
5) sum2 3 = 2? NO
6) decr 3 = 2? SI
Error encontrado en la regla:
sum2 x = div (x + (decr x)) 2
Sesión de depuración
IntroducciónDepuración Algorítmica
Divide & QueryLimitaciones de Divide & QueryOptimal Divide & Query
DemostraciónDDJ
Conclusiones
Contenido
Contraejemplo 1
2
3
1
2
3
1
2
3
1
2
3
1
4
1
8
11
5 11
1
2
3
2
2
2
3 2
9 8
111
1
1
1
11
Contraejemplo 2
4
2 1
5
12
2 3
3
3
3
4
2 1
5
13
3 3
3
2
2
16 16
3
6
2
1
1
2
3
6
2
1
1
2
3,5
6,5
2
1
1
2,5
Limitaciones
IntroducciónDepuración Algorítmica
Divide & QueryLimitaciones de Divide & QueryOptimal Divide & Query
DemostraciónDDJ
Conclusiones
Contenido
8
6 2
14 1
2 1
1
Up y Down
Ecuación 1: wn = Up(n’) + Down(n’) + win’
Ecuación 2: wn’ = Down(n’) + win’
x/2 x0
x/2 * x/2
0 * x
Up(n’) = Down(n’)
|un’ – dn’| < |un’’ - dn’’|
d u
Ecuación
Ecuación
8
6 2
14 1
2 1
1
Camino
Caso 1 Caso 2 Caso 3 Caso 4
5
7
2
1
3
1 1
4
5
7
2
1
3
1 1
4
5
7
2
1
3
1 1
4
5
7
2
1
3
1 1
4
Algoritmo
(1) Candidate = root
(2) do(3) Best = Candidate(4) Children = {m | (Best → m) ∈ E}(5) if (Children = ∅) then return Best(6) Candidate = n‘ | ∀n’’ with n’, n’’ ∈ Children, wn’
≥ wn’’
(7) while (wCandidate > wroot/2)
(8) if (M(Best) = Wrong) then return Candidate(9) if (wroot ≥ wBest + wCandidate – wiroot) then return Best
(10) else return Candidate
Algoritmo
(1) Candidate = root
(2) do(3) Best = Candidate(4) Children = {m | (Best → m) ∈ E}(5) if (Children = ∅) then return Best(6) Candidate = n‘ | ∀n’’ with n’, n’’ ∈ Children, wn’
≥ wn’’
(7) while (wCandidate > wroot/2)
(8) if (M(Best) = Wrong) then return Candidate(9) if (wroot ≥ wBest + wCandidate – wiroot) then return Best(10) else return
Candidate
2
8
5
1
12
3
20
5
4
1 1 2
1
1
4
1 11
2
17
121 5
11
81 3
(1) Candidate = root
(2) do(3) Best = Candidate(4) Children = {m | (Best → m) ∈ E}(5) if (Children = ∅) then return Best(6) Candidate = n | n with n , n Children, w′ ∀ ′′ ′ ′′ ∈ n’ ≥ wn′′
(7) while (wCandidate − wiCandidate/2 > wroot/2)(8) Candidate = n‘ ∈ Children | ∀n’’ ∈ Children, wn′ − win′/2 ≥ wn′′ −
win′′/2
(9) if (M(Best) = Wrong) then return Candidate(10) if (wroot ≥ wBest + wCandidate – wiBest/2 – wiCandidate/2) then return
Best(11) else return
Candidate
Algoritmo general
IntroducciónDepuración Algorítmica
Divide & QueryLimitaciones de Divide & QueryOptimal Divide & Query
DemostraciónDDJ
Conclusiones
Contenido
Demostración
7
10
2
17
42
1 5
22
1 111
1 1 1
7
IntroducciónDepuración Algorítmica
Divide & QueryLimitaciones de Divide & QueryOptimal Divide & Query
DemostraciónDDJ
Conclusiones
Contenido
3
6
2
1
1
2
3
6
2
1
1
2
3,5
6,5
2
1
1
2,5
3,5
6,5
2
1
1
2,5
Conclusiones
Adaptación de Divide & Query a nuevas situaciones
Raíz marcada como Undefined
Peso individual variable
Algoritmo para cada tipo de árbol
Completitud
Benchmark Nodes D&QO D&QH D&QS DR&Q … AverageNumReader 12 28,99 28.99 31,36 29,59 … 41,80 %Ordering 46 12,04 12,09 12,63 14,40 … 19,88 %Factoricer 62 9,83 9,83 9,93 20,03 … 16,94 %Sedgewich 12 30,77 30,77 33,14 30,77 … 38,46 %Clasifier 23 19,79 20,31 22,40 21,88 … 28,47 %LegendGame 71 8,87 8,87 8,95 16,72 … 16,01 %Cues 18 31,58 32,41 32,41 32,41 … 37,60 %Romanic 123 6,40 10,84 11,23 13,56 … 15,00 %FibRecursive 4.619 0,27 0,27 0,28 1,20 … 5,59 %Risk 33 16,78 16,78 18,08 19,38 … 24,76 %FacTrans 198 3,89 3,89 3,93 6,22 … 10,06 %RndQuicksort 72 8,73 8,73 8,73 11,41 … 15,19 %BinaryArrays 128 5,52 5,52 5,71 7,13 … 11,21 %FibFactAna 351 2,44 2,44 2,45 5,38 … 9,68 %NewtonPol 7 39,06 39,06 43,75 39,06 … 44,03 %RegresionTest 18 23,27 23,27 25,21 25,21 … 30,45 %BoubleFib 171 4,40 4,41 4,57 11,40 … 13,75 %ComplexNums 60 10,02 10,02 10,32 11,31 … 16,53 %Integral 5 44,44 44,44 47,22 44,44 … 48,74 %TestMath 48 11,91 11,91 12,16 12,99 … 20,46 %TestMath2 228 3,51 3,51 3,51 9,73 … 14,57 %Figures 113 6,72 6,75 6,79 8,09 … 12,36 %FastCalc 59 10,11 10,14 10,42 11,53 … 18,28 %SpaceLimits 127 12,95 16,07 19,15 21,74 … 22,31 %Argparser 129 12,10 12,10 13,08 20,48 … 18,04 %Cglib 1.216 1,93 1,93 2,33 2,12 … 8,12 %Kxml 1.172 2,86 2,86 3,01 3,56 … 9,00 %Javassist 1.357 4,34 4,34 5,44 4,49 … 9,59 %Average 374,21 13,34 13,66 14,58 16,29 … 20,60 %
Conclusiones
Divide by Queries
David Insa Cabrera
IntroducciónDepuración Algorítmica
Divide & QueryLimitaciones de Divide & QueryDivide by Queries
Conclusiones y trabajo futuro
Contenido
IntroducciónDepuración Algorítmica
Divide & QueryLimitaciones de Divide & QueryDivide by Queries
Conclusiones y trabajo futuro
Contenido
3
3
3
3
3 4 5
5
2
1 1 1
4
9
4
3
2
1
Contraejemplo 1
31
3
4
4
3
2 3 4
4
3
1 1 1
4
9
4
3
2
1
30
4
4 4 4
4 4
4
4 3 4 5
7 3
3
6 71 1 1
6
16
8
4
2
1
1
2
1
1
1
1 1
Contraejemplo 2
4
4 4 4
4 5
5
4 2 3 4
6 5
5
5 61 1 1
6
16
8
4
2
1
1
2
1
1
1
1 1
70
70
IntroducciónDepuración Algorítmica
Divide & QueryLimitaciones de Divide & QueryDivide by Queries
Conclusiones y trabajo futuro
Contenido
3
n3
1 41
n4
5
n5
1 6
n6
1
6[n3,n4,n5,n6]n2
19
4
n8
1 51
n9
5[n8,n9]n7
8 41
n10
4
[n2,n7,n10]46n1
Secuencia
1 1 1 1
5
1 1
3 1
10
1 1 1 1
5
3 4 5 6
6
42
53
3 5 14
[n2,n7,n10] = (19 + 1 * 5) (8 + 2 * 3)+ (1 + 3 * 1)+ (4)+ = 46(24) + (14) + (4) + (4) =[n7,n2,n10] = (8 + 1 * 3) (19 + 2 * 5)+ (1 + 3 * 1)+ (4)+ = 48(11) + (29) + (4) + (4) =
[n10,n2,n7] = (1 + 1 * 1) (19 + 2 * 5)+ (8 + 3 * 3)+ (4)+ = 52(2) + (29) + (17) + (4) =
+1 +2 +32 3 4 5
+3+1
(1) SPn = calcularSP(T, n) (2) spOptima = spn ∈ SPn | ∀sp’n ∈ SPn, calcularQ(T, n, spn) ≤ calcularQ(T, n,
sp’n)(3) QOptima = calcularQ(T, n, spOptima)
(4) return (spOptima, QOptima)
(1) O = {n’’ N | (n’ → n’’) ∈ ∈ E*}(2) N = N \ O(3) n’ = n’’ | (n’’ → n’) ∈ E(4) while (n’ ≠ n)(5) (_, Qn’) =
calcularSpOptima(T, n’)(6) wn’ = wn’ - |O|(7) n’ = n’’ | (n’’ → n’) ∈ E(8) end while(9) return T
Algoritmos
n4
1
n5
1
[n4, n5]n3
8
[n3]n2
13n7
1
[n7]n6
4
[n3, n6, n2]n1
27
1 1
3
4
1
2
7
[n2,n6] = (13 + 1 * 4) +
= (17) + (8) + (3)
(4 + 2 * 2)
= 28
+ (3)
[n3,n6,n2] = (8 + 1 * 3) +
= (11) + (8) + (4) + (4)
(4 + 2 * 2) + (1 + 3 * 1)
= 27
+ (4)
[n2, n6,]
+2(1) pregAcumuladas = 1(2) while ({n’ | (n → n’) ∈ E*} ≠ {n})(3) nodo = spn[indiceNodo](4) indiceNodo = indiceNodo + 1(5) preguntas = preguntas + (Qnodo + pregAcumuladas *
wnodo)(6) pregAcumuladas = pregAcumuladas + 1(7) T = ajustarNodosIntermedios(T, n, nodo)(8) end while(9) preguntas = preguntas + (pregAcumuladas)(10) return preguntas
(1) tiempoAcumulado = tin(2) while ({n’ | (n → n’) ∈ E*} ≠ {n})(3) nodo = spn[indiceNodo](4) indiceNodo = indiceNodo + 1(5) preguntas = preguntas + (Qnodo + tiempoAcumulado
* wnodo)(6) tiempoAcumulado = tiempoAcumulado + tinodo
(7) T = ajustarNodosIntermedios(T, n, nodo)(8) end while(9) preguntas = preguntas + (tiempoAcumulado * win)(10) return preguntas(1) O = {n’’ N | (n’ → n’’) ∈ ∈ E*}(2) N = N \ O(3) n’ = n’’ | (n’’ → n’) ∈ E(4) while (n’ ≠ n)(5) (_, Qn’) =
calcularSpOptima(T, n’)(6) wn’ = wn’ - |O|(7) n’ = n’’ | (n’’ → n’) ∈ E(8) end while(9) return T
Algoritmos
n4 n5
n3
n2
n7
n6
n1
1 1
3
6|2
1
2
9
(1) SPn = calcularSP(T, n) (2) spOptima = spn ∈ SPn | ∀sp’n ∈ SPn, calcularQ(T, n, spn) ≤ calcularQ(T, n,
sp’n)(3) QOptima = calcularQ(T, n, spOptima)
(4) return (spOptima, QOptima)
IntroducciónDepuración Algorítmica
Divide & QueryLimitaciones de Divide & QueryDivide by Queries
Conclusiones y trabajo futuro
Contenido
Conclusiones
Demostración de que Divide & Query no es óptima
Encontrar los nodos óptimos es un problema decidible
Probabilidad de cada nodo de ser buggy
Primera versión de una estrategia óptima
Trabajo futuro
Construcción composicional
Buscar un método para reducir la cantidad de secuencias posibles
Obtener un método para aproximar la dificultad de las preguntas
Tiempo en contestar cada nodo
Aproximar la probabilidad de que los nodos sean incorrectos
Recommended