sábado, 2 de enero de 2010

Trabajo para Enero: Heap vs. Thin Heap/Thick Heap: Algorithmus von Dijkstra, Algorithmus von Prim

Así es como se llama el pequeño proyecto que tenemos que hacer para la asignatura Effiziente Algorithmen, imprescindible hacerlo para presentarse al examen de la misma.

En esta asignatura estoy con dos compañeros turcos residentes en Alemania. Intentamos que nuestra comunicación sea lo más fluida posible (siempre en alemán), aunque a veces eso es difícil. Como modo de trabajo durante las navidades hemos establecido el trabajo por separado para después unificarlo por mail, aunque de momento no hay muchos resultados. La verdad es que tengo que ponerme las pilas, y en ello estoy.

No estoy realmente seguro qué tenemos que hacer en este trabajo, aunque lo supongo y así creo que es: implementar los algoritmos de Dijkstra y Prim utilizando las estructuras de datos citadas: Heap (Montículo) y sus variables Thin Heap (Montículo delgado) y Thick Heap.

Así que eso es lo que estoy mirando ahora. El algoritmo de Dijkstra lo implementé el año pasado en LP3, aunque utilizando otras estructuras de datos: HashSet, Cola de Prioridad y HashMap. El de Prim es la primera vez que lo veo, pero parece no parece más complicado de implementar que el primero.

No hay mucha información o documentación en internet sobre las Thin Heaps y las Thick Heaps, por lo que nos tenemos que agarrar como a un clavo ardiendo a este trabajo escrito por los tales Kaplan y Tarjan en los que cuentan todo lo que se necesita saber sobre estas estructuras.

Ya veremos qué pasa.

Por cierto, aprovecho para recomendar la herramienta Readability, genial para facilitar la lectura de textos importantes que anden incrustados en una web liosa. Por ejemplo, Wikipedia.

Sin comentarios en “Trabajo para Enero: Heap vs. Thin Heap/Thick Heap: Algorithmus von Dijkstra, Algorithmus von Prim”

Leave a reply

 
Esta plantilla ha sido modificada por Fer Álvarez a partir del diseño de psdvibe | Fue Bloggerizada por LawnyDesignz