algorithm - pseint - metodos de busqueda java

Bucle invariante de búsqueda lineal.

Question

Como se ve en Introducción a los algoritmos ( http://mitpress.mit.edu/algorithms ), el ejercicio establece lo siguiente:

Entrada: Array A [1 ... n]

Salida: i, donde A [i] = v o NIL cuando no se encuentra

Escriba un pseudocódigo para LINEAR-SEARCH, que escanea a través de la secuencia, buscando v. Usando un bucle invariante, pruebe que su algoritmo es correcto. (Asegúrese de que su invariante bucle cumpla con las tres propiedades necesarias: inicialización, mantenimiento, terminación).

No tengo problemas para crear el algoritmo, pero lo que no entiendo es cómo puedo decidir cuál es mi invariante de bucle. Creo que entendí el concepto de invariante de bucle, es decir, una condición que siempre es cierta antes del comienzo del bucle, al final / comienzo de cada iteración y aún así cuando el bucle termina. Este suele ser el objetivo, por ejemplo, en la ordenación por inserción, al comenzar con j, comenzando en j = 2, los elementos [1, j-1] siempre se ordenan. Esto tiene sentido para mí. ¿Pero para una búsqueda lineal? No puedo pensar en nada, simplemente suena demasiado simple como para pensar en un bucle invariante. ¿Entendí algo mal? Solo puedo pensar en algo obvio como (es NIL o entre 0 y n). ¡Muchas gracias por adelantado!

Answer 1

Bucle invariante sería

siempre 0 <= i <k, donde k es el valor actual de la variable de iteración de bucle, A [i]! = v

En terminación de bucle:

si A [k] == v, entonces el bucle termina y genera k

si A [k]! = v, y k + 1 == n (tamaño de la lista), el bucle termina con un valor nulo

Prueba de corrección: a la izquierda como ejercicio.

Answer 2

El algoritmo LS que escribí es-

LINEARSEARCH(A, v)
  for i=0 to A.length-1
    if(A[i] == v)
      return i
  return NIL

Hice mis propias suposiciones para el bucle invariable para verificar la corrección de la búsqueda lineal ... Tal vez sea totalmente incorrecto, así que necesito sugerencias sobre mis suposiciones.

1) En la inicialización- en i = 0, estamos buscando v en i = 0.

2) En sucesivas iteraciones, estamos buscando v hasta i <A.length-1

3) En la terminación- i = A.length y hasta A.length seguimos buscando v.

Answer 3

El invariante para la búsqueda lineal es que cada elemento antes de i no es igual a la clave de búsqueda. Una invariante razonable para la búsqueda binaria podría ser para un rango [bajo, alto], cada elemento antes de bajo es menor que la clave y cada elemento después de alto es mayor o igual. Tenga en cuenta que hay algunas variaciones de la búsqueda binaria con propiedades y invariantes ligeramente diferentes: esta es la invariante para una búsqueda binaria de "límite inferior" que devuelve el índice más bajo de cualquier elemento igual o mayor que la clave.

Fuente: https://www.reddit.com/r/compsci/comments/wvyvs/what_is_a_loop_invariant_for_linear_search/

Me parece correcto.

Answer 4

En el caso de la búsqueda lineal , la variante de bucle será el almacén de respaldo utilizado para guardar el índice (salida).

Permite nombrar el almacén de respaldo como índice que inicialmente se establece en NIL. La variante del bucle debe estar de acuerdo con tres condiciones:

• Inicialización: esta condición es válida para la variable de índice. Desde entonces, contiene NIL, lo que podría ser un resultado resultante y verdadero antes de la primera iteración.
• Mantenimiento: el índice mantendrá NIL hasta que se encuentre el elemento v. También es cierto antes de la iteración y después de la siguiente iteración. Como se establecerá dentro del bucle después de que la condición de comparación sea satisfactoria.
• Terminación: el índice contendrá NIL o el índice de matriz del elemento v.

.

Answer 5

Suponga que tiene una matriz de longitud i, indexada de [0 ... i-1], y el algoritmo está comprobando si v está presente en esta matriz. No estoy totalmente seguro, pero creo que el bucle invariante es el siguiente: si j es el índice de v, entonces [0..j-1] será una matriz que no tiene v.

Inicialización: antes de iterar desde 0..i-1, la matriz actual verificada (ninguna), no consiste en v.

Mantenimiento: Al encontrar v en j, la matriz de [0..j-1] será una matriz sin v.

Terminación: a medida que el bucle termina al encontrar v en j, [0..j-1] será una matriz sin j.

Si la matriz en sí no tiene v, entonces j = i-1, y las condiciones anteriores seguirán siendo verdaderas.

Answer 6

Después de haber mirado el índice i , y no haber encontrado v todavía, ¿qué puede decir acerca de v con respecto a la parte de la matriz antes de i y con respecto a la parte de la matriz después de i ?

Answer 7

LINEAR-SEARCH(A, ν)
1  for i = 1 to A.length
2      if A[i] == ν 
3          return i
4  return NIL 

Invariante del bucle: al comienzo de la iteración del ciclo for (líneas 1–4),

∀ k ∈ [1, i) A[k] ≠ ν.  

Inicialización:

i == 1 ⟹ [1, i) == Ø ⟹ ∀ k ∈ Ø A[k] ≠ ν,

lo cual es cierto, ya que cualquier declaración con respecto al conjunto vacío es verdadera ( verdad vacía ).

Mantenimiento: supongamos que el invariante del bucle es verdadero al comienzo de la iteración del bucle for . Si A[i] == ν , la iteración actual es la final (ver la sección de terminación ), como se ejecuta la línea 3; de lo contrario, si A[i] ≠ ν , tenemos

∀ k ∈ [1, i) A[k] ≠ ν and A[i] ≠ ν ⟺ ∀ k ∈ [1, i+1) A[k] ≠ ν,

lo que significa que el bucle invariante seguirá siendo verdadero al comienzo de la siguiente iteración (la i+1 ).

Terminación: el bucle for puede terminar por dos razones:

1. return i (línea 3), si A[i] == ν ;

2. i == A.length + 1 (última prueba del bucle for ), en cuyo caso estamos al comienzo de la A.length + 1 iteración, por lo que el bucle invariante es

   ∀ k ∈ [1, A.length + 1) A[k] ≠ ν ⟺ ∀ k ∈ [1, A.length] A[k] ≠ ν

   y se devuelve el valor NIL (línea 4).

En ambos casos, LINEAR-SEARCH termina como se esperaba.