programa prometeo – escuela superior politécnica de chimborazo 1 máster universitario en...
TRANSCRIPT
![Page 1: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/1.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo1
Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez
Sesión 5: Enseñanza de los algoritmos
Ángel Velázquez
Universidad Rey Juan CarlosEspaña
![Page 2: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/2.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo2
Seminario “Enseñanza de la Programación”
Objetivos de la sesión 5• Ilustrar muchos de los temas de
investigación mediante asignaturas de algoritmos:– Taxonomías educativas y alineamiento– Informática educativa– Modelos conceptuales– Modelos mentales (malentendidos)
![Page 3: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/3.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo3
Seminario “Enseñanza de la Programación”
Índice• Planteamiento de la asignatura• Objetivos de aprendizaje• Visualización de la recursividad• Instrucción de los algoritmos voraces• Asignatura de algoritmos avanzados• Asignatura de programación avanzada
![Page 4: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/4.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo4
Seminario “Enseñanza de la Programación”
Planteamiento de la asignatura
![Page 5: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/5.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo5
Seminario “Enseñanza de la Programación”
Planteamiento de la asignatura• Tres planteamientos de una asignatura de
algoritmos:– Basado en estructuras de datos:
• Algoritmos de manipulación
– Basado en problemas:• Ordenación• Grafos• …
– Basado en técnicas de diseño:• Divide y vencerás• Vuelta atrás• …
![Page 6: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/6.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo6
Seminario “Enseñanza de la Programación”
Planteamiento de la asignatura• Contenidos comunes:
– Análisis de complejidad:• En profundidad variable
– Algunos algoritmos de ordenación:• Por mezcla• Rápida
– Algunos algoritmos de grafos:• Kruskal y Prim• Dijsktra• Floyd
![Page 7: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/7.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo7
Seminario “Enseñanza de la Programación”
Objetivos de aprendizaje
![Page 8: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/8.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo8
Seminario “Enseñanza de la Programación”
Objetivos de aprendizaje• Ejemplo de una asignatura “Diseño y Análisis
de Algoritmos”, 3º curso• Temario:
1. Introducción2. Análisis de eficiencia3. Optimización de algoritmos4. Introducción a la técnicas de diseño de
algoritmos5. Divide y vencerás6. Algoritmos voraces7. Vuelta atrás
![Page 9: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/9.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo9
Seminario “Enseñanza de la Programación”
Objetivos de aprendizaje• Objetivos generales de la asignatura:
![Page 10: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/10.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo10
Seminario “Enseñanza de la Programación”
Objetivos de aprendizaje• Objetivos del tema 1 (introducción):
![Page 11: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/11.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo11
Seminario “Enseñanza de la Programación”
Objetivos de aprendizaje• Objetivos del tema 2 (eficiencia):
![Page 12: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/12.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo12
Seminario “Enseñanza de la Programación”
Objetivos de aprendizaje• Objetivos del tema 3 (optimización):
![Page 13: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/13.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo13
Seminario “Enseñanza de la Programación”
Objetivos de aprendizaje• Objetivos del tema 4 (introducción a las
técnicas de diseño):
![Page 14: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/14.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo14
Seminario “Enseñanza de la Programación”
Objetivos de aprendizaje• Objetivos del tema 5 (divide y vencerás):
![Page 15: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/15.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo15
Seminario “Enseñanza de la Programación”
Objetivos de aprendizaje• Objetivos del tema 6 (algoritmos voraces):
![Page 16: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/16.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo16
Seminario “Enseñanza de la Programación”
Objetivos de aprendizaje• Objetivos del tema 7 (vuelta atrás):
![Page 17: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/17.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo17
Seminario “Enseñanza de la Programación”
Objetivos de aprendizaje• Algunas notas:
– No se espera alcanzar el nivel de creación en ningún tema, sino el de aplicación:
• Soluciones generales para ecuaciones recurrentes (varias, divide y vencerás)
• Esquemas de código (eliminación de recursividad lineal, memorización, divide y vencerás, vuelta atrás para una solución, todas y óptima)
• Esquemas de árbol de búsqueda (permutaciones, subconjunto)
• Metodologías de desarrollo (eliminación de la recursividad múltiple redundante)
• Explicitar otras decisiones de diseño (estructuras de datos auxiliares y comprobaciones en vuelta atrás)
![Page 18: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/18.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo18
Seminario “Enseñanza de la Programación”
Objetivos de aprendizaje• Algunas notas:
– No son obligatorias todas las prácticas– Repensar el tema de algoritmos voraces:
• Aburrido
– Uso de software educativo:• Sistema de visualización de la recursividad Srec• Sistema de experimentación con algoritmos voraces
GreedEx
![Page 19: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/19.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo19
Seminario “Enseñanza de la Programación”
Evaluación• Cinco prácticas:
1. Introducción2. Eliminación de recursividad redundante3. Divide y vencerás4. Experimentación con algoritmos voraces5. Vuelta atrás
• Examen final
![Page 20: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/20.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo20
Seminario “Enseñanza de la Programación”
Visualización de la recursividad
![Page 21: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/21.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo21
Seminario “Enseñanza de la Programación”
Sistema SRec• Recursividad:
– Construcción fundamental en muchos algoritmos
• Sistema de visualización de la recursividad (SRec)
![Page 22: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/22.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo22
Sistema SRec• Tres vistas:
– Árbol de recursión
– Pila de control
– “Traza”
Seminario “Enseñanza de la Programación”
![Page 23: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/23.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo23
Sistema SRec• Técnica de divide y vencerás:
Seminario “Enseñanza de la Programación”
![Page 24: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/24.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo24
Sistema SRec• Técnica de divide y vencerás:
Seminario “Enseñanza de la Programación”
![Page 25: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/25.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo25
Sistema SRec• Técnica de programación dinámica:
– Análisis de redundancia:
Seminario “Enseñanza de la Programación”
![Page 26: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/26.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo26
Sistema SRec• Trabajos futuros:
– Revisión de la interfaz de usuario– Mejora y simplificación de las vistas– Ampliación para soportar algunas técnicas de
diseño
Seminario “Enseñanza de la Programación”
![Page 27: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/27.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo27
Seminario “Enseñanza de la Programación”
Instrucción de los algoritmos voraces
![Page 28: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/28.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo28
Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez
• Técnica de diseño de algoritmos para resolver problemas de optimización
• Esquema de programación:
Aprendizaje de algoritmos voraces
public static {int} algVoraz ({int} candidatos) { for ({int} sol = {}; (candidatos!={}) && !(esSolucion(sol)); ) { int sig = seleccionar(candidatos); candidatos = candidatos – {sig}; if (esValida(sol{sig})) sol = sol{sig}; } return sol;}
![Page 29: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/29.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo29
Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez
• Aprendizaje tradicional, pasivo• Ejemplo (problema de selección de actividades):
Una solución válida: {3,8,2} Una solución óptima: {9,5,4,2}
• Función de selección óptima:– selección en orden creciente de finalización
• Demostración de optimidad
Aprendizaje de algoritmos voraces
![Page 30: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/30.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo30
Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez
• Código:
• Orden de complejidad: O(n) Con la ordenación: O(nlogn)
Aprendizaje de algoritmos voraces
public static boolean[] selectActivs (int[] c, int[] f) { boolean[ ] s = new boolean [c.length]; s[0] = true; int i = 0; for (int j = 1 ; j < c.length ; j++){ if (<< activities i, j do not overlap >>){ s[j] = true; i = j; } else s[j] = false; } return s;}
public static boolean[] selectActivs (int[] c, int[] f) { boolean[ ] s = new boolean [c.length]; s[0] = true; int i = 0; for (int j = 1 ; j < c.length ; j++){ if (<< activities i, j do not overlap >>){ s[j] = true; i = j; } else s[j] = false; } return s;}
![Page 31: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/31.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo31
Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez
Esfuerzos preliminares• Instrucción de algoritmos
voraces:– Aprendizaje pasivo, como
recetas– Difícil realizar actividades
• Sistemas de visualización de algoritmos:– Análisis de figuras de
libros para varias técnicas de diseño de algoritmos:
• No hay representación común para los algoritmos voraces
![Page 32: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/32.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo32Método experimental y GreedEx
• Método experimental:– Descubrir cuáles son las funciones de
selección óptimas para cierto problema:• partimos de un algoritmo voraz genérico• identificamos y aplicamos diversas funciones de
selección con el algoritmo genérico, y• evaluamos la optimalidad de estas funciones de
selección
– Funciones “razonables” para el problema de selección de actividades:• Por inicio /• Por fin /• Por duración /
![Page 33: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/33.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo33Método experimental y GreedEx
• Aplicar las funciones de selección a ciertos datos de entrada:
![Page 34: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/34.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo34Método experimental y GreedEx
• Aplicación a varios conjuntos de datos:– Acumulación de evidencia– Contrajemplos
![Page 35: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/35.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo35Método experimental y GreedEx
• Sistema GreedEx:
![Page 36: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/36.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo36
Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez
Método experimental y GreedEx• Usabilidad de GreedEx:
– 5 evaluaciones de usuario final:• Resultados generales (1-5):
– Atención al apoyo a actividades docentes:• Exportación de tablas y figuras
![Page 37: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/37.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo37
Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez
Evaluación del método experimental• Características de los productos generados
(informes):– Problema: prácticas mal hechas, incluso
malentendidos
• Factores distintivos de los informes:1.Propuesta de estrategias subóptimas2.Incoherencia del razonamiento3.Criterio de optimización adicional:
• Maximizar ocupación de la sala• Minimizar tiempo de espera
4.Propuesta dependiente de los datos de entrada
![Page 38: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/38.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo38
Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez
Evaluación del método experimental• Categorías encontradas:
– Categorías viables: A1, A2– Categorías casi viables: B– Categorías inviables: C, D, E, F
![Page 39: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/39.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo39
Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez
Evaluación del método experimental• Evolución de las categorías:
![Page 40: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/40.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo40
Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez
Método instruccional• Método instruccional final:
– Método experimental
– “Ayudante interactivo” GreedEx– Apuntes– Integración en la asignatura
![Page 41: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/41.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo41
Seminario “Enseñanza de la Programación”
Asignatura de algoritmos avanzados
![Page 42: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/42.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo42
Seminario “Enseñanza de la Programación”
Objetivos de la asignatura• Asignatura “Algoritmos Avanzados”, 4º curso• Temario:
1. Introducción2. Algoritmos voraces3. Algoritmos aproximados4. Vuelta atrás5. Ramificación y acotación6. Eliminación de recursividad redundante7. Programación dinámica8. Algoritmos aproximados
![Page 43: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/43.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo43
Seminario “Enseñanza de la Programación”
Objetivos de la asignatura• Algunas notas:
– Algoritmos de búsqueda:• Repaso y aplicación de vuelta atrás a problemas de
optimización• Ampliación de ramificación y poda• Panorama de otras variantes:
– ¿Sistematización?
– Programación dinámica:• No se incluye el diseño de las ecuaciones recursivas:
– Sólo eliminación de recursividad y determinación de decisiones
![Page 44: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/44.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo44
Seminario “Enseñanza de la Programación”
Objetivos de la asignatura• Algunas notas:
– Espiralado:• Reafirmar y profundizar en técnicas conocidas• Presentar técnicas relacionadas (o necesarias)• Mismo problema para varias prácticas
– Prácticas:• Alineación completa de prácticas con lo explicado:
– Sin examen final
• Pueden repetir las prácticas para corregir sus errores, subiendo su nota:
– Aprendizaje y motivación
– Trabajos de ampliación:• Trabajos voluntarios para profundizar• No reevaluables
![Page 45: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/45.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo45
Seminario “Enseñanza de la Programación”
Objetivos de la asignatura• Cinco prácticas:
1. Algoritmos voraces2. Vuelta atrás y ramificación y acotación3. Eliminación de recursividad redundante4. Programación dinámica5. Algoritmos aproximados
• Cuatro trabajos de ampliación:1. Implementación eficiente de algoritmos voraces2. Analizar e implementar un algoritmo de vuelta
atrás3. Generar soluciones únicas4. Analizar e implementar un algoritmo de
programación dinámica
![Page 46: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/46.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo46
Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez
Modelos conceptuales de algoritmos voraces• Preguntas: ¿porqué en unos algoritmos se
ordenan los candidatos y en otros no? ¿es posible adaptarlos al esquema?
• Conclusión:– No todos los algoritmos voraces conocen sus
candidatos desde el principio y sin cambiar
• Consecuencias sobre modelos conceptuales:– Esquema voraz más general– Explicitación del tratamiento eficaz de la selección
de candidatos:• ordenación,• …
![Page 47: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/47.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo47
Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez
Modelos conceptuales de algoritmos voraces• Nuevo esquema, más general:
– Estudio y diseño del nuevo modelo– ¡Ya estaba descubierto!
public static {int} algVoraz ({int} candidatos) { for ({int} sol = {}; (candidatos!={}) && !(esSolucion(sol)); ) { int sig = seleccionar(candidatos); candidatos = candidatos – {sig}; if (esValida(sol{sig})) sol = sol{sig}; } return sol;}
public static {int} algVoraz ({int} problema) { {int} candidatos = extraer (problema); for ({int} sol = { }; (candidatos != { }) && !(esSolucion(sol)); ) { int sig = seleccionar(candidatos); candidatos = candidatos – {sig}; if (esValida(sol{sig})) { sol = sol{sig}; actualizar(candidatos,sig,problema); } } return sol;}
![Page 48: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/48.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo48
Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez
Modelos conceptuales de algoritmos voraces• Ordenación de candidatos:
– Problema práctico de difícil comprensión:• ¿Usar aprendizaje por descubrimiento?
• Otros casos de selección eficiente de los candidatos:– Trabajo de ampliación
![Page 49: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/49.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo49
Seminario “Enseñanza de la Programación”
Experimentación con optimalidad• Experimentación con la optimalidad de los
algoritmos aproximados:– Comparación con algoritmos óptimos y
subóptimos:• Diseñados con varias técnicas de diseño• Falta de curiosidad de algunos alumnos por resultados
contradictorios
![Page 50: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/50.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo50
Seminario “Enseñanza de la Programación”
Trabajos futuros• Posibles retos futuros:
– Aprendizaje por descubrimiento de la ordenación de candidatos en algoritmos voraces
– Sistematización de técnicas de búsqueda:• Consultar bibliografía de IA y optimización
– Aprendizaje de la corrección:• Diseño de contraejemplos (todas las técnicas)• Principio de vuelta atrás• Principio de optimalidad (programación dinámica)• Ampliación de correctores automáticos (tipo OptimEx)
– Aprendizaje de la optimalidad:• Mejorar la comparación entre técnicas exactas y
aproximadas• Ampliar OptimEx• ¿Otras técnicas: algoritmo probabilísticos…?
![Page 51: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/51.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo51
Seminario “Enseñanza de la Programación”
Asignatura de programación avanzada
![Page 52: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/52.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo52
Seminario “Enseñanza de la Programación”
Objetivos de la asignatura• Asignatura “Programación Avanzada”, 4º
curso, ESPOCH• Temario:
1. Introducción2. Recursividad3. Eliminación de la recursividad4. Eficiencia de algoritmos5. Divide y vencerás6. Vuelta atrás
![Page 53: Programa Prometeo – Escuela Superior Politécnica de Chimborazo 1 Máster Universitario en Informática Interactiva y Multimedia Ángel Velázquez Sesión 5:](https://reader035.vdocumento.com/reader035/viewer/2022062808/5665b4db1a28abb57c944e4e/html5/thumbnails/53.jpg)
Programa Prometeo – Escuela Superior Politécnica de Chimborazo53
Seminario “Enseñanza de la Programación”
Objetivos de la asignatura• Retos:
– Recursividad:• Aplicar conocimientos didácticos• Evaluación de dificultades de alumnos• Aprendizaje de técnicas de divide y vencerás y de vuelta
atrás
– Eficiencia de algoritmos:• Conseguir aprendizaje más activo