Download Tarea 4

Tarea 4
CC3001 - Algoritmos y estructuras de datos
Profesores: Patricio Poblete, Nelson Baloian
Fecha de entrega: 9 de junio de 2015
No se aceptarán tareas atrasadas
Objetivo
El objetivo de esta tarea es implementar el algoritmo para encontrar el árbol de búsqueda
binaria óptimo para un conjunto de llaves con probabilidades de acceso no uniforme, así
como una forma alternativa, más rápida, de encontrar un árbol cercano al óptimo.
Descripción del problema
Dado un conjunto de llaves X1 <... < Xn, con probabilidades de acceso p1, ..., pn, en clases
vimos cómo construir un árbol de búsqueda binaria óptimo, esto es, un árbol en el cual el
costo esperado de búsqueda sea mínimo. Para los efectos de esta tarea, supondremos que
sólo hay búsquedas exitosas (esto es, que todas las probabilidades q son cero).
Usted debe escribir un programa en Java que lea un archivo de texto desde su entrada
estándar, y que:
1. Calcule la frecuencia con la cual aparece cada una de las letras. Para simplificar,
considere sólo las letras del alfabeto ASCII básico (sin acentos ni eñes) y no
distinga entre mayúsculas y minúsculas. En base a esta tabla de frecuencias,
defina la probabilidad de acceso de cada una de las letras (como la frecuencia de
cada letra dividida por la suma de las frecuencias de todas las letras).
2. Usando las probabilidades así calculadas, implemente el algoritmo visto de
orden O(n3) visto en clases para encontrar el árbol óptimo. Identifique el ciclo
más interno e inserte un contador que le permita contar el número de veces que se
ejecuta ese ciclo.
3. Implemente un algoritmo para construir un árbol que aproxime al árbol óptimo.
Su algoritmo debe escoger como raíz del árbol a aquella llave que hace que los
"pesos" de los subárboles izquierdo y derecho resultantes sean lo más parecidos
posible. (Recuerde que el peso de un subárbol es la suma de las probabilidades de
todas sus llaves). El mismo método se aplica recursivamente para la construcción
de los subárboles. Inserte un contador en el punto apropiado para llevar la cuenta
del número de iteraciones ejecutadas por este algoritmo.
Su programa debe leer el archivo de entrada e imprimir en la salida estándar la tabla de
probabilidades calculada, y luego, para cada algoritmo, el valor del contador de iteraciones
y el costo esperado de búsqueda en el árbol construido.
Restricciones
 El
programa debe ser escrito en Java. No se aceptará ningún otro lenguaje de
Programación.
 Tareas que no compilen serán calificadas con nota 1.0
 La tarea es individual.
 El plazo es absolutamente perentorio. No se corregirán tareas atrasadas.
Entrega
Deberá enviar usando Ucursos (plazo: 11:59 del último día de entrega):
 Un
informe donde debe describir y documentar el programa realizado, incluyendo
ejemplos de entradas y salidas. Además incluya información relevante para hacer
funcionar su tarea. No incluya los archivos .class, únicamente los .java
Contenido del Informe
El informe debe describir el trabajo realizado, el código fuente desarrollado y los resultados
obtenidos.
Principalmente sea breve, describiendo cada uno de los puntos que a continuación se
indican, pero sin sobrepasar las 10 páginas.
Estos son los puntos que debe contener su informe:
 Portada: indicando número de la tarea, fecha, autor, email, código del curso.
 Introducción: descripción del problema y su solución (¡muy breve!)
 Análisis del problema: exponga en detalle el problema, los supuestos que pretende
ocupar, casos de borde y brevemente la metodología usada para resolverlo.
 Solución del problema:
o Algoritmos
de solución, incluyendo toda la información y figuras que
considere necesarias.
o Partes relevantes del código fuente
o Ejemplos de entradas y salidas escogidos por usted.
 Modo de uso, explicando cualquier dato extra necesario para la compilación y
ejecución de su programa.