Tema:
Algoritmo de Fuerza Bruta

Realizado por:
Bryan Alba
Lourdes Fárez

Facultad:
Ingeniería

Escuela:
Informática

Materia:
Programación 2
Estructura de Datos y Análisis de Algoritmos

Profesor:
Ing. Malhena Sánchez

Fecha:
30 de Octubre 2012

ALGORITMO DE FUERZA BRUTA
Introducción:
Los algoritmos de Fuerza Bruta son capaces de encontrar la solución a cualquier problema por complicado que sea. Su fundamento es muy simple, probar todas las posibles combinaciones, recorrer todos los caminos hasta dar con la situación que es igual que la solución. No le importa iniciar caminos malos o muy malos, al llegar a su final y ver que su destino no es la solución, se iniciará otro camino en busca del que conduzca a ella. …ver más…

* 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.

Análisis de Complejidad (Costes): * En el mejor caso, el primer elemento del patrón no está en el texto, de manera que ningún carácter coincide con él. Tenemos un coste temporal de orden O(n), el algoritmo es lineal. * En el peor caso el coste temporal de este algoritmo es de O(mn), que sería aquel en el que encontramos el patrón en todas las subcadenas del texto. * En promedio el coste temporal es menor que O(mn), ya que no precisamos comparar cada vez los m caracteres, sólo comparamos hasta que se detecta un fallo y las probabilidades de falsos comienzos son muy inferiores a 1 en general. Si buscamos en textos normales será de orden O(m+n) en la mayoría de los casos. * El coste espacial es nulo, salvo que consideremos