Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
Buscando Principios Gráficos
para Visualizaciones de Técnicas
de Diseño de Algoritmos
Natalia Esteban, Antonio Pérez, Belén
Sáenz, Ángel Velázquez
Departamento de Lenguajes y Sistemas
Informáticos I
Universidad Rey Juan Carlos
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
Índice
1. Problema
2. Principios de Diseño de Visualizaciones
3. Principios de Diseño de Visualizaciones de
Algoritmos
4. Análisis provisional
1.
2.
3.
4.
Divide y vencerás
Vuelta atrás
Programación dinámica
Conclusiones globales
5. Conclusiones y trabajo futuro
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
1. Problema
• Dificultad de aprendizaje de la
programación
• Varias “soluciones”:
– Visualización y animación
–…
• Campo de investigación en animación de
algoritmos:
– Nació en los 80
– Énfasis técnico inicial
– En los 90, se da más énfasis a los aspectos
docentes
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
1. Problema
• Cuestiones docentes:
–
–
–
–
–
Difusión de los sistemas
Integración con las asignaturas
Esfuerzo de generación de las animaciones
Eficacia educativa
Implicación del alumno
• Un olvido:
– ¡Las propias visualizaciones!
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
1. Problema
• Nuestra pregunta:
– ¿Qué características deben tener las
visualizaciones de algoritmos?
• Otros autores:
– Recomendaciones sobre los sistemas
– Recomendaciones sobre elementos del diseño
gráfico (p.ej. color)
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
2. Principios de diseño de vis.
• Campos con criterios claros sobre cómo
representar sus objetos:
– Estadística
– Grafos
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
2. Principios de diseño de vis.
• Trabajos de Maneesh Agrawala:
– Mapas de rutas
– Mapas turísticos
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
2. Principios de diseño de vis.
• Trabajos de Maneesh Agrawala:
– Instrucciones de ensamblaje
– Ilustraciones con cortes o expansiones
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
2. Principios de diseño de vis.
• Metodología de desarrollo de sistemas de
visualización:
– Identificación de principios de diseño:
• Reglas de alto nivel que describen las características
de las visualizaciones más eficaces
• Análisis de visualizaciones manuales
• Uso de trabajos previos en percepción y cognición
• Realización de experimentos de percepción o
cognición
– Implementación del sistema
– Evaluación del sistema
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
3. Principios de diseño de vis. de algoritmos
• Metodología de identificación de principios:
– Análisis de ilustraciones de libros
– Visualizaciones basadas en técnicas de
diseño de algoritmos:
• Divide y vencerás
• Vuelta atrás
• Programación dinámica
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
3. Principios de diseño de vis. de algoritmos
• Pasos:
1. Recogida de ilustraciones:
• Escaneado, recopilación y etiquetado básico
2. Análisis preliminar:
• Análisis exploratorio, informal
• Conclusiones preliminares
3. Análisis detallado:
• Definición de categorías y valores de
etiquetado
• Análisis iterativo
4. Principios de diseño y especificación del
sistema
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
3. Principios de diseño de vis. de algoritmos
• Ilustraciones de muestra:
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
3. Principios de diseño de vis. de algoritmos
• Ilustraciones de muestra:
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
3. Principios de diseño de vis. de algoritmos
• Ilustraciones de muestra:
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4. Análisis provisional
• Valores e identificadores
• Representaciones gráficas:
–
Propias de la informática:
•
•
–
Propias de cada técnica de diseño (árbol de
recursión…)
Otras (grafo…)
Propias del dominio (tablero…)
• Objetivos:
–
–
–
E/S
Explicación
Ejecución
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4. Análisis provisional
• Genericidad:
–
–
–
Genéricas
Semigenéricas
Concretas
• Tratamiento del tiempo:
–
–
–
–
Ilustración única
Secuencia de 2 ilustraciones
Secuencia de más de 2 ilustraciones
Representación con memoria
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4. Análisis provisional
• Completitud:
–
–
–
Completas
Parciales
Simplificadas
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.1. Divide y vencerás
• Cinco categorias
– Matemáticos
(3 problemas: 17,64%; 5 representaciones: 7,81%)
– Estructuras con valor de retorno
(5 problemas: 29,41%; 11 representaciones: 17,19%)
– Estructuras sin valor de retorno
(4 problemas: 23,53%; 25 representaciones: 39,06%)
– Geométricos
(4 problemas: 23,53%; 22 representaciones: 38,38%)
– Otros
(1 problema: 5,88%; 1 representación: 1,56%)
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.1. Divide y vencerás
• Relación entre la
categoría del
algoritmo y el
objetivo de la
representación
(representación de
ejemplo concreto,
explicación general o
carácter doble)
SITIAE 2012, 8 Junio 2012
CategoríaObjetivo
MAT-Conc
2
3,08%
MAT-Expl
3
4,62%
MAT-Doble
0
0,00%
EVS-Conc
3
4,62%
EVS-Expl
8
12,31%
EVS-Doble
0
0,00%
EVN-Conc
16
24,62%
EVN-Expl
9
13,85%
EVN-Doble
0
0,00%
GEO-Conc
15
23,08%
GEO-Expl
8
12,31%
GEO-Doble
1
1,54%
OTR-Conc
1
1,54%
OTR-Expl
0
0,00%
OTR-Doble
0
0,00%
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.1. Divide y vencerás
• Objetivos de las
representaciones
Objetivos
Concretas
36
56,25%
Explicación
27
42,19%
1
1,56%
18
43,90%
Entrada
0
0,00%
Salida
0
0,00%
E/S
12
29,27%
Historia
(árboles)
11
26,83%
Doble
• Objetivos concretos
de las
representaciones
SITIAE 2012, 8 Junio 2012
Objetivos
concretos
Secuencia
estados
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.1. Divide y vencerás
• Detalle de los tipos
de representaciones
• Resumen de los tipos
de representaciones
Resumen
Informática
23
35,94%
Dominio
30
46,88%
Árbol
11
17,19%
SITIAE 2012, 8 Junio 2012
Detalle
Árbol rec.
11
17,19%
1
1,56%
Vector
20
31,25%
Matriz
2
3,13%
Tablero
3
4,29%
25
39,06%
2
3,13%
Pila
Geométrica
Otros
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.1. Divide y vencerás
• Sentido de los
árboles de recursión
empleados
• Tipo de proceso
Sentido
Ascendente
5
35,71%
Descendente
2
14,29%
Ambos
4
28,57%
Indefinido
3
21,43%
DYV
44
67,69%
Recursividad
13
20,00%
8
12,31%
Tipo de
proceso
Auxiliares
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.2. Vuelta atrás
• Cuatro categorías
– Problemas de juegos y estrategia (JE)
(7 problemas: 30,43%, 23 representaciones: 38,34%; autores: 7)
– Problemas sobre grafos (G)
(4 problemas: 17,40%, 18 representaciones: 30%; autores 6)
– Otros problemas de decisión (OD)
(5 problemas: 21,74%, 11 representaciones: 18,33%; autores 6)
– Problemas de optimización(PO)
(7 problemas: 30,43%, 8 representaciones: 13,33%; autores 5)
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.2. Vuelta atrás
• Relación entre la clase de representación y
la categoría del algoritmo
Clase de representación
Total
JE
G
Dependiente del domino
18(30,00%)
17
1
Informática
9(15,00%)
Árbol de búsqueda
33(55,00%)
6
TOTAL
Representaciones con
secuencias de estados
Representaciones con
figuras compuestas
60 (100%)
23
2
2
4
1
SITIAE 2012, 8 Junio 2012
OD
PO
8
11
8
18
11
8
9
3
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.2. Vuelta atrás
• Árboles de búsqueda
Tipo de árbol
Completo
Parcial
Simplificado
Árbol potencial
21(35,00%)
11
Árbol generado
12(20,00%)
5
6
1
33
16(48,48%)
6(18,18%)
11(33,33%)
TOTAL
SITIAE 2012, 8 Junio 2012
10
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.2. Vuelta atrás
• Objetivos de representación y categoría de
algoritmo
Objetivo
Total
JE
G
OD
PO
Explicación
28(46,67%)
9
9
6
4
Proceso de
cómputo
21(35,00%)
8
4
5
4
Entrada
6(10,00%)
1
5
Solución
5(8,33%)
5
TOTAL
60(100%)
23
11
8
SITIAE 2012, 8 Junio 2012
18
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.2. Vuelta atrás
• Objetivos de representación y tipo de
representación
Árbol
completo
Árbol
parcial
Árbol
abreviado
Objetivo
Total
Explicación
28(46,67%)
6
Proceso de
cómputo
21(35,00%)
10
Entrada
6(10,00%)
1
Solución
5(8,33%)
5
TOTAL
60(100%)
SITIAE 2012, 8 Junio 2012
16
6
6
Tablero
9
8
2
3
11
17
Grafo
4
MAPA
1
5
9
1
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.3. Programación dinámica
• Siete categorías
–
Problemas de cadenas (Cadenas)
(7 problemas: 19,44%, 19 representaciones: 12,1%; autores: 7)
–
Problemas sobre árboles (Árboles)
(2 problemas: 5,56%, 34 representaciones: 21,66%; autores 5)
–
Problemas sobre grafos (Grafos)
(8 problemas: 22,22%, 43 representaciones: 27,39%; autores 11)
–
Problemas matemáticos (Matemáticos)
(4 problemas: 11,11%, 12 representaciones: 7,64%; autores 8)
–
Problemas sobre matrices (Matrices)
(1 problemas: 2,78%, 12 representaciones: 7,64%; autores 7)
–
Problemas de planificación (Planificación)
(8 problemas: 22,22%, 30 representaciones: 19,11%; autores 11)
–
Otros problemas (Otros)
(6 problemas: 16,67%, 7 representaciones: 4,46%; autores 4)
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.3. Programación dinámica
• Siete categorías
Tipos de Problemas
Problemas
Ilustraciones
Autores
1 Cadenas (Cad.)
7 (19,44%)
19 (12,1%)
7
2 Árboles (Arb.)
2 (5,56%)
34 (21,66%)
5
3 Grafos (Graf.)
8 (22,22%)
43 (27,39%)
11
4 Matemáticos (Mate.)
4 (11,11%)
12 (7,64%)
8
5 Matrices (Matri.)
1 (2,78%)
12 (7,64%)
7
6 Planificación (Plan.)
8 (22,22%)
30 (19,11%)
11
7 Otros (Otros)
6 (16,67%)
7 (4,46%)
4
36
157
14
Total
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.3. Programación dinámica
• Relación entre la entre la clase de
representación y la categoría del algoritmo
Clase de
representación
Árbol Recursión
TOTAL
Cad.
Graf.
11(7,75%)
1
Ilustración
24 (16,9%)
4
Informática
48 (33,8%)
3
Tabla
54 (38,03%)
148
SITIAE 2012, 8 Junio 2012
Mate.
5
Grafo Dependencia 11(7,75%)
TOTAL
Arb.
5
Matri. Plan.
1
4
Otros
1
1
1
3
7
2
9
24
17
1
2
10
4
14
4
10
9
3
18
33
39
13
13
25
7
2
1
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.3. Programación dinámica
• Clase Representación - Tablas
Representación Tabla
TOTAL
Cad.
37(40,43%)
9
3(6,38%)
tabla decisiones
tabla ambas
7 (14,89%)
(decisiones - valores)
TOTAL
47
1
tabla valores
SITIAE 2012, 8 Junio 2012
10
Arb.
1
Graf.
Mate.
5
4
Matri. Plan.
7
1
1
3
2
1
4
8
4
9
9
Otros
2
1
9
3
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.3. Programación dinámica
• Objetivos de representación y tipo de
representación
Objetivo
TOTAL
Cad.
explicación
39 (26,35%)
3
ejecución
109 (73,65%)
• e/s
10 (9,17%)
• entrada
17 (15,6%)
• historia
47 (43,12%)
Graf.
Mate.
7
8
4
5
8
4
15
26
31
9
8
17
3
2
1
4
5
12
8
2
10
Matri. Plan.
Otros
3
8
7
11
1
1
1
2
1
1
1
2
• intermedio
2 (1,83%)
• salida
• secuencia
estados
23 (21,1%)
1
10 (9,17%)
2
SITIAE 2012, 8 Junio 2012
Arb.
12
5
6
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.4. Conclusiones globales
• Hay problemas que se apoyan más en
ilustraciones
• Las representaciones dependientes del
dominio surgen cuando no hay
representaciones informáticas adecuadas
• Conviven las presentaciones informáticas
generales, propias del dominio y propias
de la técnica de diseño
• Los datos se visualizan para E/S y, si es
posible, para las explicaciones y la
ejecución
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
4.4. Conclusiones globales
• Las explicaciones suelen tener
representaciones genéricas y las
ejecuciones, concretas
• La ejecución lineal como secuencia de
estados
• Cada técnica utiliza representaciones
adecuadas para la ejecución no lineal
• Las representaciones parciales se usan
más en ejecuciones y las simplificadas, en
explicaciones
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
5. Conclusiones y trabajo futuro
• Investigación en marcha sobre las
características de las visualizaciones
eficaces de los algoritmos
• Análisis de ilustraciones, clasificadas por
técnicas de diseño:
– Proceso iterativo, muy laborioso
• Conclusiones provisionales:
– Muy prometedoras
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
5. Conclusiones y trabajo futuro
• Trabajo futuro:
1. Con la experiencia ganada, debemos
realizar una definición final de
categorías y valores
2. Evaluación de conclusiones con análisis
de algoritmos voraces
3. Formulación de principios de diseño
4. Especificación de características del
sistema de visualización
5. Desarrollo y evaluación…
SITIAE 2012, 8 Junio 2012
Buscando Principios Gráficos para Visualizaciones de Técnicas de Diseño de Algoritmos
¡Muchas gracias!
SITIAE 2012, 8 Junio 2012
Descargar

Título de una línea o de dos líneas, separado del logotipo