ALGORITMOS

ALGORITMOS ALEATORIOS

EL ALGORITMO DE ALEATORIEDAD ES MALO SI EL GENERADOR DE NUMEROS ALEATORIOS PRODUCE UNA PERMUTACION MALA.

PARA CONTRA ATACAR EL PROBLEMA UNICAMENTE SE NECESITA UN CAMBIO EN EL CODIGO DEL ARREGLO DE PERMUTACION DE ALEATORIEDAD.

ALGORTIMO MODIFICADO

RANDOMIZED-HIRE-ASSISTENT(N)

RANDOMLY PERMUTE THE LIS OF CANDIDATES

BEST=0 // EL CANDIDATO 0 ES EL MENOS CALIFICADO

FOR I=0 TO N

INTERVIEW CANDIDATE I

IF CANDIDATE I IS BETTER THAN CANDIDATE BEST

BEST = I

HIRE CANDIDATE

EL COSTO DEL PROCEDIMIENTO DEL ALGORITMO RANDOMLY PERMUTE THE LIS OF CANDIDATES

ES O(Chln n)

En el código anterior del tema 5.2 hacemos una suposición sobre las entradas, mientras que en el algoritmo actual no hacemos ninguna suposición, aunque aleatorizar las entradas toma tiempo adicional

Permutando arreglos aleatorizados

Varios algoritmos aleatorizados, aleatorizan las entradas por permutar las entradas dadas de los arreglos. En este tema checaremos dos formas de algoritmos aleatorizados.

Un método común es el de asignar a cada elemento del arreglo una prioridad de azar, a contiunuacion ordenar los elementos del arreglo de acuerdo a las prioridades.

Por ejemplo tenemos el arreglo A= <1,2,3,4> y luego elegimos las prioridades de azar

P= <36,3,62,19>, producimos un arreglo B= <2,4,1,3> a este método lo llamamos permute by sorting (permutar por clasificación).

Permute by sorting

N = A.length

Let P[1..n] be a new array

For I = 1 to n

P [i]=Random (1,n^3)

Sort A, using P as sort keys

La linea 4 elige un numero de aleatoriedad entre el 1 y n^3, es en donde iremos asignando las prioridades de aleatoriedad.

El procedimiento del algoritmo produce una aleatoriedad de permutación uniforme de las entradas, asumiendo que todas las prioridades son distintas.

El mejor método para generar permutación al azar es el de permutar el arreglo en su lugar. El procedimiento RANDOMIZE IN PLACE (ALEATORIAMENTE EN SU LUGAR) tiene un costo de O(n).

En la interacion i escoge el lemento A[i] al azar entre los elementos A[i] atraves de A[n], subsecuentemente la iteración i A[i] nunca es alterada.

RANDOMIZE IN PLACE

N = A.length

For I = 1 to n

SWAP A[i] with A [Random (I,n)]

Vamos a utilizar un bucle invariante para mostrar el procedimeinto de randomize in place produciendo una permutacion aleatoria uniforme.

...