Proyecto 3 - Distance of Levenshtein

Contenido de reporte 

Recursión
Es una forma de solucionar algunos problemas un tanto drásticos ya que la mayoría de las veces aumenta las posibilidades de una forma espantosa, consta de un procedimiento que realiza una serie de pasos llamándose a sí mismo y volver a realizar la acción 1 o más veces.

Fortaleza del equipo
La investigación y el trabajo en equipo fue nuestra fortaleza más importante ya que cada integrante aporto algo al proyecto ya sea en la investigación de términos o de algoritmos para el problema presentado.

¿Qué fue tu contribución al trabajo?

La investigación de los 2 diferentes algoritmos y tratar de aportar en aprendizaje a mis compañeros.

¿Cómo compara lo que hiciste tú con el trabajo de los demás?

Mis compañeros realizaron un trabajo de investigación de términos y material, mientras yo me encargue de los algoritmos y orden asintótico del mismo.

¿Qué podrías mejorar en el futuro?

Los horarios de trabajo y la sincronización de nuestro equipo. 

Ligas a los blogs de los demás de tu grupo
http://w0oh0o.blogspot.com/
http://blankardz22.blogspot.com/
http://www.adrianaa17.blogspot.com/
http://lauraegh.blogspot.com/

    A continuación adjunto un archivo con el contenido del reporte con su respectiva codificación en c++.

http://groups.google.com/group/algcomp/web/Proyecto%203%20-%20Distance%20of%20Levenstein.zip

Proyecto 2 - Subset sum problem

Subset Sum Problem

El problema de la suma de sub conjuntos es una buena introducción para los problemas NP Completos, este es un problema de decisión y no de optimización, y tiene una definición forma muy simple.

Dada el problema puede ser resuelto con una función generadora. Considerando el numero de formas C(m,s) a seleccionar m de M números enteros {a1,….am} tales que su suma es igual a s y se define la función generada como:

Al ampliar “y” esto se convierte

pero como resultado de la ley de exponentes x^m x^n = x^(m+n), Gm(x) es precisamente la función que desee generar:

Por ejemplo:

Dado C un conjunto (15, 22, 14, 26, 32, 9, 16, 8) y s =53. Entonces una solución a G(C,53) está dado por el vector X = (1,1,0,0,0,0,1,0), porque CX = a₁ + a₂ + a₇ = 15 + 22 +16 = 53.El correspondiente del subconjunto es C’ = (15,22,16).

En general ahí puede existir varias soluciones a (C,s) como por ejemplo otra solución es X = (0,1,1,0,0,1,0,1) con el subconjunto C’ = (15,22,16).

El problema de decisión sería:

¿Existe un subconjunto m de M que contenga una suma s?     

Algorithm 1: Exact-Subset-Sum(S, t)

n  <− |S|

L0  <− h0i

Para i = 1 a n hacer:

Li  <− MergeLists (Li−1,Li−1 + xi)

Elimina para Li cada elemento más grande que t

Regresa el elemento más grande para Ln

Algoritmo de tiempo exponencial en general, ya que la duración de Li puede ser tan alta como 2^i.

El problema es NP Completo.


Bibliografía
http://en.wikipedia.org/wiki/Subset_sum_problem
http://www2-fs.informatik.uni-tuebingen.de/~reinhard/krypto/English/4.5.1.e.html
http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/nanda-scribe-3.pdf
http://mathworld.wolfram.com/SubsetSumProblem.html



    A continuación adjunto un archivo con el contenido del reporte con su respectiva codificación en c++.

http://groups.google.com/group/algcomp/web/Proyecto%202%20-%20Subset%20sum%20problem.zip