técnicas de cotas inferiores teoría de la información técnica del adversario
DESCRIPTION
Análisis y Diseño de Algoritmos. Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario. Análisis y Diseño de Algoritmos. Teoría de la Información Para representar m cosas (alternativas) se necesitan a lo menos log 2 m bits de decisiones. - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/1.jpg)
Técnicas de Cotas Inferiores• Teoría de la Información• Técnica del adversario
Análisis y Diseño de Algoritmos
![Page 2: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/2.jpg)
• Teoría de la Información Para representar m cosas (alternativas) se necesitan a
lo menos log2m bits de decisiones.
Aquí podemos representar esto, a través de un árbol de decisiones, donde cada comparación es un bit.
Análisis y Diseño de Algoritmos
Cualquier algoritmo que compara puede representarse con un árbol de decisión
![Page 3: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/3.jpg)
• Caso cuando el árbol es totalmente balanceado
• Peor caso
Análisis y Diseño de Algoritmos
![Page 4: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/4.jpg)
Ejemplo: Ordenar usando comparaciones de n números m=n!
Ejemplo: Buscar un número entre n números, m=n+1
No es buena cota inferior si los números están desordenados. Búsqueda secuencias es óptima para buscar en n objetos (sin orden y distintos)
Análisis y Diseño de Algoritmos
![Page 5: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/5.jpg)
Si los elementos o eventos no están distribuidos uniformemente, podemos usar la entropía como cota inferior. Si hay n eventos, cada uno con probabilidad pi, entonces el número mínimo de bits (decisiones) para representar los n elementos es :
n
H(p)= ∑ pi log2 pi
i=1
Por ejemplo, si n es igual a 2, y los pi están distribuidos uniformemente, entonces necesitamos 1 bit.
Análisis y Diseño de Algoritmos
![Page 6: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/6.jpg)
Técnica del Adversario
Está técnica consiste en diseñar un adversario que conteste lo que da menos información a un algoritmo. Luego en base a este diseño, obtenemos un número mínimo de decisiones para cualquier algoritmo.
Notar que tanto la teoría de la información como la técnica del adversario son válidos sólo para algoritmos que utilizan decisiones binarias.
Análisis y Diseño de Algoritmos
![Page 7: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/7.jpg)
Ejemplo: Buscar un elemento en n números desordenados.
Adversario:• Si el algoritmo ha preguntado por j posiciones distintas
(j<n), el adversario siempre contesta que no está, y es coherente con esta respuesta si se repite la pregunta.
• Cuando el algoritmo pregunta por la última posición (Pn), si el elemento está en el arreglo lo coloca en esa posición, sino dice que no está.
Análisis y Diseño de Algoritmos
![Page 8: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/8.jpg)
En otras palabras, el adversario escoge donde poner el elemento buscado.
• Hay que hacer al menos n preguntas.• Búsqueda secuencial es óptima en este caso
Problema: Encontrar el máximo y el mínimo, n-1+ n-2 = 2n-3
Análisis y Diseño de Algoritmos
![Page 9: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/9.jpg)
Problema: Encontrar el máximo y el segundo.
Algoritmo y Cota Inferior
2n-3 no es óptimo
Análisis y Diseño de Algoritmos
![Page 10: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/10.jpg)
Fuerza Bruta: n-1 + n-2 = 2n-3
El algoritmo óptimo es:
Análisis y Diseño de Algoritmos
![Page 11: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/11.jpg)
MEDIDAS DE COMPLEJIDAD• Tiempo: Lo más importante se abstrae de un
cierto conjunto de operaciones.• Espacio: Memoria que ocupa el algoritmo, se
abstrae en ciertos objetivos.
En general, la complejidad del espacio u otros recursos no puede ser mayor que el tiempo ( a menos que la condición inicial sea especial).
Análisis y Diseño de Algoritmos
![Page 12: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/12.jpg)
Modelo de Computador
Para analizar la complejidad de un algoritmo, se debe establecer un modelo adecuado de la tecnología sobre la que se ejecutará, incluyendo un modelo de los recursos y de sus costos de uso. El modelo que utilizaremos corresponde a una máquina monoprocesador con memoria de acceso aleatorio.
Análisis y Diseño de Algoritmos
![Page 13: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/13.jpg)
Técnicas de Diseño
Inducción:• Simple: Sabemos resolver el problema de tamaño
m<n, y a partir de ello resolvemos un problema de tamaño n.
Ejemplo:
Búsqueda:
Resolvemos el problema para n-1
Vemos si es el n-ésimo (si no lo hemos encontrado)
Análisis y Diseño de Algoritmos
![Page 14: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/14.jpg)
Análisis y Diseño de Algoritmos
Ejemplo:
Búsqueda:
• Resolvemos el problema para n-1
• Vemos si es el n-ésimo (si no lo hemos encontrado)
(implementación ?)
![Page 15: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/15.jpg)
Análisis y Diseño de Algoritmos
Ejemplo:
Ordenamiento
• Ordenamos n-1 números
• Agregamos el n-ésimo al conjunto manteniendo el orden.
• n=0, no hacemos nada
¿Qué tipo de ordenamiento es este?
![Page 16: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/16.jpg)
Análisis y Diseño de Algoritmos
Ejemplo:
Ordenamiento
• Sabemos como resolver el problema de tamaño m1 y m2.
• Mezclo ambos conjuntos obteniendo uno de tamaño n=m1+m2.
• n<=1, entonces no hago nada.
¿Qué tipo de ordenamiento es este?
![Page 17: Técnicas de Cotas Inferiores Teoría de la Información Técnica del adversario](https://reader036.vdocumento.com/reader036/viewer/2022081817/56815259550346895dc08c8b/html5/thumbnails/17.jpg)
• Corolario: Dividir para reinar, es un caso particular de inducción.
Análisis y Diseño de Algoritmos