Informe transformación de cadenas

ENTREGA PROYECTO 2 DE FUNDAMENTOS DE ANÁLISIS Y DISEÑO DE 
ALGORITMOS  
  
  
 
 
 
 
  
 
 
 
  
  
  
  
JUAN SEBASTIAN VELASQUEZ VALENCIA 1255416 
 
RAUL STYVEN FLOREZ ​
1356321­2711 
 
OSCAR EDUARDO RAMIREZ AREVALO 1255798 
  
  
  
  
  
 
 
 
 
UNIVERSIDAD DEL VALLE 
INGENIERÍA DE SISTEMAS 
FUNDAMENTOS DE ANÁLISIS Y DISEÑO DE ALGORITMOS  
TULUÁ­VALLE 
2015 ENTREGA PROYECTO 2 DE FUNDAMENTOS DE ANÁLISIS Y DISEÑO DE 
ALGORITMOS  
  
  
  
 
 
 
 
  
  
JUAN SEBASTIAN VELASQUEZ VALENCIA 1255416 
 
RAUL STYVEN FLOREZ ​
1356321­2711 
 
OSCAR EDUARDO RAMIREZ AREVALO 1255798 
  
  
  
 
 
  
Entrega de solución a uno de los problemas de propuestos para programación 
dinámica y voraz presentado al ingeniero en sistemas CARLOS ANDRES 
DELGADO 
  
 
 
 
  
UNIVERSIDAD DEL VALLE INGENIERÍA DE SISTEMAS 
FUNDAMENTOS DE ANÁLISIS Y DISEÑO DE ALGORITMOS  
TULUÁ­VALLE 
2015 

CONTENIDO: 
 
 
ELECCIÓN DEL PROBLEMA…………………………………………………………………….4 
 
1.­ ENTENDIENDO EL PROBLEMA.……………………………………………………………5 
 
2.SOLUCIÓN DINÁMICA DEL PROBLEMA.…………………………………………………..7 
 
3.BIBLIOGRAFÍA…………...………………………………………………………………...…..11 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ELECCIÓN DEL PROBLEMA. 
 Elección de los 3 problemas posibles propuestos para el segundo proyecto de Fundamentos 
de Análisis y Diseño de Algoritmos(F.A.D.A), se optó por el siguiente: 
 
 
Conversión  de cadenas Sean u y v dos  cadenas de caracteres. Se desea transformar  u en v 
con el mínimo número de operaciones elementales del tipo siguiente: 
 
 a) Eliminar un carácter en cualquier posición.  b) Añadir un carácter al final.  
c) Cambiar un carácter en cualquier posición. 
 
 Por ejemplo, para pasar de la cadena ​
ababc​
 a ​
bccba​
 podríamos hacer: 
 
 a) ababc →(eliminar a en primer posición)  
 b) babc → bcabc (añadir c el final). 
 c) bcabc → bccbc (cambiar a por c en posición 3) 
 d) bccbc → bccba (cambiar c por a en posición 5).  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 
 
 1.­ ENTENDIENDO EL PROBLEMA: 
 
1.1 REPRESENTACIÓN DE ENTRADAS Y SALIDAS: 
 
Las  entradas  para  la  función  transformación,  serán m  y n, donde m= longitud de cadena u y 
n= longitud de cadena v. Dando como resultado un T(m,n), con las siguientes condiciones.  
 

 
Nota: 
Min ​
consiste en una función “auxiliar” que calculará el menor de tres enteros, esto definirá la 
operación a seguir. 
 
 
1.2​
 ​SALIDA ANTE UNA ENTRADA SELECCIONADA: 
 
La entrada seleccionada para el ejemplo: transformacion(abcabc, bcabca). 
 
Procedimiento: 
 
 a) abcabc → bcabc(eliminar a en primer posición)  
 b) bcabc→ bcabca (añadir a al final). 
 
Se llega a la solución en dos operaciones. 
 
 
1.3 ESTUDIO DE SU COMPLEJIDAD EN TÉRMINOS DE O(f(n)). 
 
La  función  transformación(m,n),  al  ser   m  y  n  la  longitud  de  una cadena  de  caracteres  
diferentes, la complejidad del algoritmo será de la siguiente manera 
 
 
A)Mejor de los casos:  
 
En  el  mejor  de  los  casos,  en el que  u=v, la complejidad  del algoritmo será O(n) ya que sólo 
comparará y determinará la equidad de las cadenas. 
 

 
 
B)Caso promedio: 
 
Para  el  caso  promedio,  la  complejidad  del  algoritmo  para  estos  casos  será  O(m*n)  ya que 
los ciclos de operación dependen directamente de la longitud m y n. 
 
 
C) El peor de los casos: 
 
En  esta  sección  se  tendrán   dos  peores  casos;  el  primer  peor  caso   será  en  el  que  m=n,  lo 
que  generará  una  complejidad  O(n^2),  debido  al  recorrido  cuadrático  que   generará  en  los 
ciclos de ejecución. 
 
El  segundo  peor  caso  será  O(m*n)  ya  que,  como  se mencionó  anteriormente,  los  ciclos  de 
ejecución dependen directamente del tamaño de m y n. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 
2) SOLUCIÓN DINÁMICA DEL PROBLEMA: 
 
2.1)  Definición formal de la solución dinámica y estructura óptima: 
 
Se  requiere  diseñar  un  algoritmo  que  calcule  el  mínimo  de  operaciones  de  los  tres  ...