Algoritmos

Algoritmos

Es una sucesión finita de pasos no ambiguos que se pueden ejecutar en un tiempo finito, cuya razón de ser la de resolver problemas. Problemas serian aquellas cuestiones, conceptuales o practicas, cuya solución es expresable mediante un algoritmo.

Análisis del problema

El objetivo de este análisis es el de ayudar al programador a llegar a una cierta comprensión de la naturaleza del mismo.

Este análisis propone los siguientes pasos

• Definir el problema con total precisión

• Especificar los datos de partida necesarios para la resolución del mismo.

• Especificar la información que debe proporcionarse al resolverse

Diseños de algoritmos

Algoritmo voraz:

El algoritmo más sencillo que puede ocurrírsenos es, partiendo de un agregado solución vacío, recorrer el agregado de entrada, y añadir el elemento considerado en cada paso al agregado solución siempre que se cumplan las condiciones derivadas de la propiedad que se apuntó.

Un ejemplo muy sencillo puede aportar más luz al anterior párrafo.

Así, sea un agregado de números enteros positivos de tamaño n. Supongamos, para mayor sencillez, que lo tenemos almacenado en un array c de enteros de tamaño n. El siguiente algoritmo resuelve nuestro problema:

class Pares{

static int[] c={3,5,1,7,8,9,34,56,122,44};

static boolean[] solución=null;

static int n=c.length;

static boolean[] algoritmo1(int p, int s){

int n=s-p+1;

boolean[] ss=new boolean[n]; //agregado solución vacío

int i=-1,k;

while(i<n-1){ //condición de terminación del recorrido

k=i+1; //candidato

i++; //eliminar candidato del agregado

if(par(c[k+p])){ //condición de prometedor

ss[k]=true; //añadir candidato a la solución

}

}

return ss;

}

static boolean par(int i){

return (i%2==0);

}

public static void main(String[] args){

solucion=algoritmo1(0,n-1);

System.out.println("Los pares son: ");

for(int k=0;k<n;k++){

if(solución[k]){

System.out.println(c[k]+" es par");

}

}

}

}

Algoritmo divide y vencerás:

Un segundo algoritmo que puede ocurrírsenos es dividir el agregado en el número de partes que queramos, siempre que el tamaño sea superior a un tamaño umbral que admitamos. Obtener la solución de cada parte y combinar dichas soluciones para construir la solución al agregado completo. Para el caso de que el tamaño sea inferior o igual a umbral, la solución se obtiene mediante el algoritmo anterior (o cualquier otro conocido que no divida el agregado en partes).

El siguiente algoritmo divide el agregado en dos partes:

class Pares{

static int[] c={3,5,1,7,8,9,34,56,122,44};

static boolean[] solución=null;

static int umbral=2,n=c.length;

... //código de algoritmo1 y par

static boolean[] algoritmo2(int p,int s){

boolean[] ss=null;

if(p>s){ //parte vacía

;

}

else{

if(s-p+1<=umbral){ //la parte no se divide

ss=algoritmo1(p,s); //algoritmo conocido

}

else{

int m=(p+s)/2;//dividir

boolean[] ss1=algoritmo2(p,m-1);

boolean[] ss2=algoritmo2(m,s);

ss=unión(ss1,ss2); //combinar

}

}

return ss;

}

static boolean[] unión(boolean[] s1,boolean[] s2){

boolean[] s=null;

if(s1==null){

s=s2;

}

else if(s2==null){

s=s1;

}

else{

s=new boolean[s1.length+s2.length];

for(int i=0;i<s1.length;i++){

s[i]=s1[i];

}

for(int j=0;j<s2.length;j++){

s[s1.length+j]=s2[j];

}

}

return s;

}

public static void main(String[] args){

solucion=algoritmo2(0,n-1);

System.out.println("Los pares son: ");

for(int k=0;k<n;k++){

if(solución[k]){

System.out.println(c[k]+" es par");

}

}

}

}

Algoritmo de programación dinámica:

Un tercer algoritmo que puede ocurrírsenos es, a partir de la de la relación que establece cómo combinar las soluciones para distintas partes de los datos de entrada, establecer los casos en que puede obtenerse la solución sin utilizar dicha relación (casos base), y partiendo de dichos casos, guardar la solución para los mismos en una matriz de registros (multidimensional), y reconstruir la solución al problema utilizando los valores almacenados en la matriz de registros.

El siguiente algoritmo soluciona el problema de encontrar los pares de un conjunto dado de esta última manera:

class Pares{

static int[] c={3,5,1,7,8,9,34,56,122,44};

static boolean[] solución=null;

static int n=c.length;

static boolean[][] pares= new boolean[n+1][];

//una posición más para la parte vacía

static boolean[] algoritmo3(){

pares[0]=null;

...