Matematicas discretas

Algoritmos de 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 elproceso.
 El proceso finaliza al alcanzar el final del texto
 No existe un pre procesamiento del patrón.
Descripción:
 No requiere ninguna fase de pre procesó previo, ni un espacio extraconstante 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 ono.
 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 detienela 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.




Algoritmo Ambicioso Repetitivo.
Consisten en repetirvarias veces el proceso para encontrar un circuito de Hamilton del algoritmo ambicioso.
Escoge cualquier vértice X. Aplica el algoritmo ambicioso usando X como vértice inicial y calcula el costo totaldel circuito obtenido.
Repite el proceso usando cada uno de los vértices restantes de la gráfica como vértice inicial.
De los circuitos de Hamilton obtenidos, escoge el mejor inicial....