Inteligencia artificial

El algoritmo de Dekker es un algoritmo de programación concurrente para exclusión mutua, que permite a dos procesos o hilos de ejecución compartir un recurso sin conflictos. Fue uno de los primeros algoritmos de exclusión mutua inventados, implementado porEdsger Dijkstra.

Si ambos procesos intentan acceder a la sección crítica simultáneamente, el algoritmo elige un proceso según una variable de turno. Si el otro proceso está ejecutando en su sección crítica, deberá esperar su finalización.

Existen cinco versiones del algoritmo Dekker, teniendo ciertos fallos los primeros cuatro. La versión 5 es la que trabaja más eficientemente, siendo una combinación de la 1 y la 4.

• Versión 1: Alternancia estricta. Garantiza la exclusión mutua, pero su desventaja es que acopla los procesos fuertemente, esto significa que los procesos lentos atrasan a los procesos rápidos.
• Versión 2: Problema interbloqueo. No existe la alternancia, aunque ambos procesos caen a un mismo estado y nunca salen de ahí.
• Versión 3: Colisión región crítica no garantiza la exclusión mutua. Este algoritmo no evita que dos procesos puedan acceder al mismo tiempo a la región crítica.
• Versión 4: Postergación indefinida. Aunque los procesos no están en interbloqueo, un proceso o varios se quedan esperando a que suceda un evento que tal vez nunca suceda.

 shared int cierto = 1;

 ''/* Definición de variables compartidas */ ''
 shared int bandera[2] = {0,0};   
 shared int turno      = 0; 
 
 while (cierto)
 {
    bandera[proc_id] = cierto;  // Está listo para acceder a la Sección Crítica
    while (bandera[1-proc_id] == cierto) { // Mientras el otro esté procesando
       if (turno == 1-proc_id) {           // si es su turno
          bandera[proc_id] = 0;            // indicar que no está listo y
          while (turno == (1-proc_id)) {}  // esperar activamente.
          bandera[proc_id] = 1;            // Cuando terminó de esperar, está listo
       }
    }
    /* ''Sección crítica'' */
    turno = 1-proc_id; // Indicar el turno del otro proceso
    bandera[proc_id] = 0;  // Indicar que ya no está listo (para acceder a la Sección Crítica)
    /* ''Sección no crítica'' */
 }

El algoritmo de Earley1 es un algoritmo no determinista de análisis sintáctico para las gramáticas libres de contexto descrito originalmente por Jay Earley. Se ordena, a los lados de los algoritmos CYK y GLR, entre los algoritmos que usan la noción de reparto (de cálculos y de estructuras) y que construyen todos los análisis posibles de una frase (y no sólo uno de estos análisis). Es uno de los algoritmos no deterministas que usan ideas de la programación dinámica.

Consider




e la siguiente gramática simple para expresiones aritméticas:
 P → S      # La regla de principio
 S → S + M
    | M
 M → M * T
    | T
 T → número


Con la entrada:
 2 + 3 * 4


Esto es la secuencia de conjuntos de estados:
 (declare no.) Producción       (Origen) # Comentario
 ---------------------------------
 == S(0): • 2 + 3 * 4 ==
 (1)  P → • S         (0)    # regla de principio
 (2)  S → • S + M     (0)    # predecir de (1)
 (3)  S → • M         (0)    # predecir de (1)
 (4)  M → • M * T     (0)    # predecir de (3)
 (5)  M → • T         (0)    # predecir de (3)
 (6)  T → • número    (0)    # predecir de (5)
 
 == S(1): 2 • + 3 * 4 ==
 (1)  T → número  •   (0)    # scan de S(0)(6)
 (2)  M → T •         (0)    # completo de S(0)(5)
 (3)  M → M • * T     (0)    # completo de S(0)(4)
 (4)  S → M •         (0)    # completo de S(0)(3)
 (5)  S → S • + M     (0)    # completo de S(0)(2)
 (6)  P → S •         (0)    # completo de S(0)(1)
 
 == S(2): 2 + • 3 * 4 ==
 (1)  S → S + • M     (0)    # scan from S(1)(5)
 (2)  M → • M * T     (2)    # predecir de (1)
 (3)  M → • T         (2)    # predecir de (1)
 (4)  T → • número    (2)    # predecir de (3)
 
 == S(3): 2 + 3 • * 4 ==
 (1)  T → número  •   (2)    # scan from S(2)(4)
 (2)  M → T •         (2)    # completo de S(2)(3)
 (3)  M → M • * T     (2)    # completo de S(2)(2)
 (4)  S → S + M •     (0)    # completo de S(2)(1)
 (5)  S → S • + M     (0)    # completo de S(0)(2)
 (6)  P → S •         (0)    # completo de S(0)(1)
 
 == S(4): 2 + 3 * • 4 ==
 (1)  M → M * • T     (2)    # scan from S(3)(3)
 (2)  T → • número    (4)    # predecir de (1)
 
 == S(5): 2 + 3 * 4 • ==
 (1)  T → número  •   (4)    # scan from S(4)(2)
 (2)  M → M * T •     (2)    # completo de S(4)(1)
 (3)  M → M • * T     (2)    # completo de S(2)(2)
 (4)  S → S + M •     (0)    # completo de S(2)(1)
 (5)  S → S • + M     (0)    # completo de S(0)(2)
 (6)  P → S •         (0)    # completo de S(0)(1)


El estado (P → S •, 0) representa un análisis completado. Este estado también aparece en S(3) y S(1), que son sentencias completas.