Inteligencia artificial

Los Algoritmos de Estimación de Distribución (AED) constiuyen una familia de metaheurísticas derivadas de los algoritmos evolutivos.

A diferencia de los algoritmos evolutivos "clásicos", en donde se busca encontrar una solución a un problema codificando directamente sus variables, los AED buscan estimar la distribución de probabilidad de cada variable. La población de soluciones candidatas se recrea en cada generación, a partir de la distribución de probabilidad obtenida a partir de los mejores individuos de la generación anterior.

Dado que la población no se regenera a partir de individuos, sino desde las distribuciones de probabilidad obtenidas, no existen operadores de cruzamiento ni de mutación.

El pseudocódigo de un AED general es el siguiente:

Generar al azar M individuos, formando la población .

i = 0

Mientras no se cumpla la condición de término, hacer:

i = i + 1

Seleccionar N individuos (N < M) desde la población precendente (), formando la poblaciónn :.

Estimar la distribución de probabilidad  de cada variable del problema, usando la población .

Generar al azar M individuos utilizando las distribuciones obtenidas , formando la población .

Fin del ciclo.

El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito porEuclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.- .....................................................................:

https://es.wikipedia.org/w/index.php?title=Algoritmo_de_Euclides&printable=yes

Divisibilidad. El algoritmo de Euclides.

Divisibilidad: divisores y múltiplos. El teorema de la división.

Dados dos números enteros a y b (con a distinto de 0), se dice que a divide a b, y lo escribimos como a|b,si existe un c∈Z tal que b=ac.

También se dice que a es un factor o divisor de b, y que b es un múltiplo de a.

Algunas propiedades derivadas de la definición anterior:

1. 1|a
2. a|0
3. a|b y a|c ⇒ a|b+c
4. a|b y a|c ⇔ a|bx+cy para cualesquiera x, y∈ Z
5. a|b y b|a ⇒ a = b o bien a = -b

Teorema de la división.

Sean a∈ Z y b∈ N. Entonces existen q, r∈ Z con 0< r <b tales que a=bq+r. Además, q y r son únicos.

Esta es la vieja fórmula de la división entera: dividendo a es igual al divisor b multiplicado por el cociente q, más un resto r.

Sistemas de numeración

Una consecuencia importante del teorema de la división, es que nos sirve para justificar el método habitual en que representamos los números enteros (i.e. mediante un sistema de representación posicional).

Sea t > 2 un entero al que llamamos la base de cálculo. Para cualquier entero x tenemos, aplicando el teorema de la división dividiendo repetidamente el entero x por nuestra base t,

x = tq₀ + r₀

q₀ = tq₁ + r₁

....

q_n-2 = tq_n-1 + r_n-1

q_n-1 = tq_n + r_n

cada resto r_i es uno de los enteros 0,1,...,t-1, y se termina la serie cuando q_n=0. Si eliminamos los cocientes q_i , se obtiene que

x = r_ntⁿ + r_n-1t^n-1 +...+ r₁t + r₀

Puede así verse como podemos representar o expresar x en la base t, mediante la sucesión de restos obtenida, y lo escribimos comox = (r_nr_n-1...r₁r₀)_t

Esta representación del número entero x es además única para la base t

Cuando la base es t=10, decimos que estamos usando notación decimal. A la notación en base 2 se le llama binaria, a la notación en base 16 se le llama hexadecimal y a la notación en base 8 se le llama octal. La base 10 es la notación convencional para calcular habitualmente, y es por eso que en el caso decimal omitiremos el subíndice t al representar el número.

• Ejemplo en sistema decimal: 1970 = (1x10³) + (9x10²) + (7x10) + 0
• Ejemplo en sistema octal: (3662)₈ = (3x8³) + (6x8²) + (6x8) + 2 = 1970
• Expresar el decimal 220 en el sistema binario. Dividiendo sucesivamente por la base 2:

  220 = 2.110 + 0

  110 = 2.55 + 0

  55 = 2.27 + 1

  27 = 2.13 + 1

  13 = 2.6 + 1

  6 = 2.3 + 0

  3 = 2.1 + 1

  1 = 2.0 + 1

  Por tanto 220 = (11011100)₂

Aplicación de ejemplo: Conversión de un número decimal (base 10) a otra base

---

Máximo común divisor. El algoritmo de Euclides.

El máximo común divisor de dos enteros

Dados dos enteros a y b distintos de 0, decimos que el entero d>1 es un máximo común divisor, o mcd, de a y b si

d|a, d|b y para cualquier otro c ∈ Z tal que c|a y c|b, entonces c|d

Es decir, d es un entero positivo, divisor común de a y b, y cualquier otro divisor común es también un divisor de d.

Con estas condiciones, el máximo común divisor es único. Se denota por d= mcd(a,b)

Algunas propiedades del máximo común divisor

1. mcd(a,b) = mcd(|a|,|b|)
2. mcd (ka,kb) = |k| mcd(a,b)
3. Si a|b.c y mcd (a,b) =1, entonces a|c
4. mcd(a,b) = d ⇔ d|a, d|b y mcd(a/d , b/d)=1

El algoritmo de Euclides

Proposición

Sean a,b enteros no nulos. Entonces mcd(a,b) = mcd(b,r) donde r es el único 0<r<b tal que existe un entero q con a= bq + r (esto es, quer es el resto de la división de a por b)

Esta proposición nos indica que es igual de válido calcular el mcd(a,b) que el mcd(b,r), con la ventaja de que r es un entero de menor tamaño que el original a. Esto es aprovechado por el algoritmo de Euclides para el cálculo del máximo común divisor de dos números enteros.

El algoritmo de Euclides

Para calcular el mcd de dos enteros a y b (ambos >0, suponemos a > b) se definen q_i y r_i recursivamente mediante las ecuaciones:

a = bq₁ + r₁  (0<r₁

b = r₁q₂ + r₂  (0<r₂1

)

r₁ = r₂q₃ + r₃  (0<r₃2

)

....

r_k-3 = r_k-2q_k-1 + r_k-1  (0<r_k-1k-2

)

r_k-2 = r_k-1q_k  (r_k=0)

Y de la proposición anterior, se sigue que:

mcd(a,b) = mcd(b,r₁) = mcd(r₁,r₂) = ... = mcd(r_k-2,r_k-1) = r_k-1

Además se puede demostrar que el número de pasos necesarios para calcular el mcd de dos números es menor que 5 veces el número de dígitos del menor de ellos.

A continuación, figura una posible implementación en pseudocódigo del algoritmo de Euclides:

Observación

Sean a,b enteros no nulos, y sea d = mcd(a,b). Entonces d es el menor entero positivo (no nulo) que puede expresarse en la forma ax + by con x,y∈ Z

Una propiedad del algoritmo de Euclides:

El algoritmo de Euclides también nos proporciona un método para calcular dos valores enteros x e y tales que mcd(a,b) = ax + by. Este método consiste en ir despejando el resto de la última división, el que nos da el valor mcd(a,b), hacia atrás hasta llegar a los valores a y bde partida.

Corolario: primos relativos

Sean a,b enteros no nulos. Entonces mcd(a,b) = 1 si y solo si existen enteros s y t tales que as + bt = 1. Se dice en este caso que a y bson números primos entre sí, o que son primos relativos, o simplemente que a es primo con b (y viceversa).

---

Aplicación de ejemplo: El Algoritmo de Euclides

---

Ecuaciones diofánticas

Las ecuaciones de la forma ax + by = c con a,b,c ∈ Z\{0}, y con raíces enteras, se conocen como ecuaciones diofánticas de primer grado, llamadas así por Diofanto  de Alejandría, matemático griego a quien se considera el padre del álgebra.

Lema de Euclides

Sean a, b, c∈Z con mcd(a,b)=1, tales que a|bc. Entonces se puede afirmar que a|c. (Es decir, si a y b son primos entre sí, y a es un divisor de bc, entonces a es divisor de c)

Teorema

La ecuación diofántica ax + by = c, con a, b, c∈Z\{0} tiene soluciones enteras si y sólo si d|c, siendo d el mcd(a,b). Además, la solución general de esta ecuación es de la forma:

x = x1 + (tb / d)

y = y1 - (ta / d)

para todo valor t entero, en donde (x₁, y₁) es una solución particular cualquiera de la ecuación ax + by = c (que puede obtenerse, por ejemplo, a partir del algoritmo de Euclides).