Algoritmo

Algoritmo Fuerza Bruta

Características

 Es el algoritmo más simple posible.

 Consiste en probar todas las posibles posiciones del patrón en el texto.

 Requiere espacio constante.

 Realiza siempre saltos de un carácter.

 Compara de izquierda a derecha.

 Realiza la búsqueda del patrón en un tiempo O(mn).

 Realiza 2n comparaciones previstas de los caracteres del texto.

Lógica

 Se sitúa el patrón en la primera posición, y se compara carácter a carácter hasta encontrar un fallo o llegar al final del patrón.

 Se pasa a la siguiente posición y se repite el proceso.

 El proceso finaliza al alcanzar el final del texto

 No existe un preprocesamiento del patrón.

Descripción

 No requiere ninguna fase de preproceso previo, ni un espacio extra constante además del espacio asignado al patrón y al texto.

 Para la búsqueda:

 Consiste en la comparación de todas las posiciones del texto entre 0 y el n-m, si una ocurrencia del patrón corresponde o no.

 Si encuentra una no ocurrencia, o una ocurrencia total del patrón, salta un carácter hacia la derecha.

Ejemplo

Se alinea la primera posición del patrón con la primera posición del texto, y se comparan los caracteres uno a uno hasta que se acabe el patrón, esto es, se encontró una ocurrencia del patrón en el texto, o hasta que se encuentre una discrepancia.

Si se detiene la búsqueda por una discrepancia, se desliza el patrón en una posición hacia la derecha y se intenta calzar el patrón nuevamente.

Algoritmos voraces

Los algoritmos voraces suelen ser bastante simples. Se emplean sobre todo para resolver problemas de optimización, como por ejemplo, encontrar la secuencia óptima para procesar un conjunto de tareas por un computador, hallar el camino mínimo de un grafo, etc. Habitualmente, los elementos que intervienen son:

• un conjunto o lista de candidatos (tareas a procesar, vértices del grafo, etc);

• un conjunto de decisiones ya tomadas (candidatos ya escogidos);

• una función que detemina si un conjunto de candidatos es una solución al problema (aunque no tiene por qué ser la óptima);

• una función que determina si un conjunto es completable, es decir, si añadiendo a este conjunto nuevos candidatos es posible alcanzar una solución al problema, suponiendo que esta exista;

• una función de selección que escoge el candidato aún no seleccionado que es más prometedor;

• una función objetivo que da el valor/coste de una solución (tiempo total del proceso, la longitud del camino, etc) y que es la que se pretende maximizar o minimizar;

Para resolver el problema de optimización hay que encontrar un conjunto de candidatos que optimiza la función objetivo. Los algoritmos voraces proceden por pasos. Inicialmente el conjunto de candidatos es vacío. A continuación, en cada paso, se intenta añadir al conjunto el mejor candidato de los aún no escogidos, utilizando la función de selección. Si el conjunto resultante no es completable, se rechaza el candidato y no se le vuelve a considerar en el futuro. En caso contrario, se incorpora al conjunto de candidatos escogidos y permanece siempre en él. Tras cada incorporación se comprueba si el conjunto resultante es una solución del problema. Un algoritmo voraz es correcto si la solución así encontrada es siempre óptima. El esquema genérico del algoritmo voraz es:

funcion voraz(C:conjunto):conjunto

{ C es el conjunto de todos los candidatos }

S <= vacio { S es el conjunto en el que se construye la solucion}

mientras ¬solucion(S) y C <> vaciohacer

x <= el elemento de C que maximiza seleccionar(x)

C <= C \ {x}

si completable(S U {x}) entonces S <= S U {x}

si solucion(S)

entonces devolver S

si no devolver no hay solucion

El nombre voraz proviene de que, en cada paso, el algoritmo escoge el mejor "pedazo" que es capaz de "comer" sin preocuparse del futuro. Nunca deshace una decisión ya tomada: una vez incorporado un candidato a la solución permanece ahí hasta el final; y cada vez que un candidato es rechazado, lo es para siempre.

Ejemplo:

Se desea pagar una cantidad de dinero a un cliente enmpleando el menor número posible de monedas. Los elementos del esquema anterior se convierten en:

• candidato: conjunto finito de monedas de, por ejemplo, 1, 5, 10 y 25 unidades, con una moneda de cada tipo por lo menos;

• solucion: conjunto de monedas cuya suma es la cantidad a pagar;

• completable: la suma de las monedas escogidas en un momento dado no supera la cantidad a pagar;

• funcion de seleccion: la moneda de mayor valor en el conjunto de cnadidatos aún no considerados;

• función objetivo: número de monedas utilizadas en la solución

algoritmo divide y vencerás

La técnica de diseño de algoritmos llamada "divide y vencerás" (divide and conquer) consiste en descomponer el problema original en varios sub-problemas más sencillos, para luego resolver éstos mediante un cálculo sencillo. Por último, se combinan los resultados de cada sub-problema para obtener la solución del problema original. El pseudocódigo sería:

funcion divide_y_venceras_1(problema)

{

descomponer el problema en n subproblemas más pequeños;

para i=1 hasta n hacer

resolver el subproblema k;

combinar las n soluciones;

}

Un ejemplo de "divide y vencerás" es la ordenación rápida, o quicksort, utilizada para ordenar arrays. En ella, se dividía el array en dos sub-arrays, para luego resolver cada uno por separado, y unirlos (ver algoritmos de ordenación). El ahorro de tiempo es grande: el tiempo necesario para ordenar un array de elementos mediante el método de la burbuja es cuadrático: kN2. Si dividimos el array en dos y ordenamos cada uno de ellos, el tiempo necesario para resolverlo es ahora k(N/2)2+k(N/2)2=(kN2)/2. El tiempo necesario para ordenarlo es la mitad, pero sigue siendo cuadrático.

Pero ahora, si los subproblemas son todavía demasiado grandes, ¿por qué no utilizar la misma táctica con ellos, esto es, dividirlos a ellos también, utilizando un algoritmo recursivo (ver recursividad) que vaya dividiendo más el sub-problema hasta que su solución sea trivial? Un algoritmo del tipo:

funcion divide_y_venceras(problema)

{

si el problema es trivial

entonces resolver

...