Exactitud de algoritmos

Contenido

Exactitud de algoritmos        1

¿Todos las ejecuciones del algoritmo producen la misma coincidencia?        1

Estrategia de fuerza bruta        2

Problema de la mochila definición formal        2

Ayudantías        2

Solución: Búsqueda Exhaustiva        2

Estrategia de backtracking o retroceso        2

¿A qué nos referimos como candidato?        3

¿Cómo sabemos si un candidato es una solución?        3

Sobre el taller: Backtracking una técnica        3

Esquemas de solución        4

Ayudantías        4

Solución: Árbol de estado        4

Tema de examen 2019 - 2020        4

Exactitud de algoritmos

Para ver si rigurosamente cierto o correcto.

Algoritmo para resolver el problema de emparejamiento estable.

Cuando encontramos una función con un puntito adentro, es que todavía no se le han puesto los parámetros. Por ejemplo: [pic 1]

Una correspondencia S es estable si: (i) es perfecta y (ii) no hay inestabilidad con respecto a S.

Correspondencia perfecta -> todos los elementos están emparejados

Inestabilidad -> Un elemento está emparejado con varios.

¿Todos las ejecuciones del algoritmo producen la misma coincidencia?

Considere un algoritmo que se ejecuta de forma asincrónica, con diferentes componentes independientes que realizan acciones que pueden ser intercalas de forma compleja, y se desea saber cuánta variabilidad provoca esta asincronía en el resultado final.

Algoritmo asincrónico: Pone en espera una instrucción y para poder avanzar tiene que terminar el algoritmo.

Demostrar:

[pic 2][pic 3]

Estrategia de fuerza bruta

Consiste en revisar todas las posibilidades de solución.

Ventaja -> Vas a llegar al resultado en algún momento

Desventaja -> tiempo de ejecución exponencial

Pasos a seguir:

1. Enumerar las posibles soluciones “candidatas”
2. Chequear si la opción “candidata” soluciona el problema.

Problema de la mochila definición formal

Tenemos qi ítems disponibles, Cada item tiene asociado un valor vi y un peso wi

La mochila tiene un peso máximo de W[pic 4]

Entonces el problema es maximizar el valor de los ítems siempre que no supere el peso máximo W.

SI qi = 1 para i= 1, 2, 3…. Entonces es el problema de la mochila 0-1.

Conjunto potencia.

Ayudantías

Prueba todas las posibles condicionas

En n grandes es menos eficiente

Si hay una coincidencia (el mejor de los casos es O(n+m) ) – a  la primera.

El peor de los casos es O(nm), cuando busca todas las posibles coincidencias – al final.

Solución: Búsqueda Exhaustiva

Listas las posibles soluciones

Evaluar cada solución descartando las correctas y manteniendo las mejores

Selecciona la solución

Estrategia de backtracking o retroceso

Consiste en seguir un camino buscando una solución.

Si por ese camino no se llega a la solución:

• Se retrocede por dicho camino hasta que se encuentre otro camino
• O hasta que se llegue al inicio -> Si se llega al inicio no hay solución.

Solución general:

[pic 5]

Sucesores(.) es una función que dado un candidato, genera todos los candidatos que son extensiones del mismo.

 ¿A qué nos referimos como candidato?

Son los caminos a los que podemos llegar a una posible solución.  Un candidato es una solución parcial, no se refiere a todos los elementos de una solución, si no solo a una parte.

...