El blog de Feregrino

Integración de Monte Carlo

Apelando al hecho de que una integral es la sumatoria de la infinidad de resultados de evaluar una función en un intervalo dado, se toman puntos de evaluación aleatorios dentro de ese intervalo dado, se evalúan y se van acumulando para luego realizarles un ajuste matemático, les diría que lo buscaran en Wikipedia, pero este documento me resultó especialmente revelador.

Para el caso de la implementación de POO lo que se consideró fue la creación de dos clases Random y Funcion, la primera para generar números aleatorios y la segunda para evaluar la función.

Aproximación a π

Para este caso se toma un cuarto de círculo de radio = 1, y se lanzan n dardos hacia él de esos n dardos supongamos que m aciertan en él entonces mediante matemágia, podemos encontrar que  π ≈ 4 * m / n

Para (mal) aplicar la POO, existe una clase que hace uso de Random, la clase definida en el ejericio anterior y de otra, llamada Aproximación en la cual se realiza la simulación de los dardos

Comprobación de primalidad (Algoritmo Monte Carlo)

Existe un test de primalidad, inventado por Fermat que nos dice que si tomamos la siguiente frómula a^(n-1) % n para cualquier número a ∈ [1,n-1] y si el resultado de eso es distinto de 1 entonces sabemos que n no es primo. Tomando una gran cantidad de números con valores aleatorios para a ∈ [1,n-1] podríamos asegurar con cierta probabilidad si un número n es primo. Si el test falla, es decir el resultado para cualquiera a es distinto de 1 podemos asegurar que n no es primo.

Resolución del problema de las N reinas (Algoritmo Las Vegas)

El ya conocidísimo problema delas N reinas también se puede resolver mediante probabilidad, es decir, tomamos la columna 1 y colocamos la primera reina, después para la segunda columna tratamos de colocar la siguiente reina en una posición elegida aleatoriamente, si se logró, continuamos con la siguiente columna, y así hasta colocar las N reinas o no poder colocar una, en ese caso falla.

Bastante simple.

• Se usa una lista para para ir almacenando las frecuencias de cada caracter
• Se usa un arreglo de árboles para generar el árbol único de códificación
• Se usa una cola para obtener el código asignado a cada símbolo

FUNC Fibonacci (↓n: NATURAL): NATURAL
   VARIABLES
       tabla: ARRAY [0..n] DE NATURALES
       i: NATURAL
   INICIO
       SI n = 0 ENTONCES
           DEVOLVER 0
       SINOSI n = 1 ENTONCES
           DEVOLVER 1
       SINO
           tabla[0] := 0
           tabla[1] := 1
           PARA i = 2 HASTA n HACER
               tabla[i] := tabla[i-1] + tabla[i-2]
           FINPARA
           DEVOLVER tabla[n]
       FINSI
   FIN

long long fibonacciArreglo(int n) {
    long long * lista;
    if(n == 0) return 0;
    if(n == 1) return 1;
    lista = (long long *) malloc(sizeof(long long) * n);
    lista[0] = 0;
    lista[1] = 1;
    int i;
    for (i = 2; i <= n; i++) {
        lista[i] = lista[i-1] + lista[i-2];
    }
    return lista[n];
}

long long fibonacciCola(int n) {
    Cola cola;
    if (n == 0) return 0;
    if (n == 1) return 1;
    creaLista(&cola);
    formar(&cola, 0);
    formar(&cola, 1);
    int i;
    for (i = 2; i <= n; i++) {
        // Quitamos el elemento menos reciente
        long long fi1 = atender(&cola);
        // Obtenemos el valor del siguiente más reciente
        long long fi2 = valorPrincipio(&cola);
        // Almacenamos el resultado en la cola
        formar(&cola, fi1 + fi2);
    }
    return valorFinal(&cola);
}

Práctica 1: "Pruebas a posteriori (Algoritmos de ordenamiento)"

• Burbuja (Bubble Sort)
• Burbuja Simple
• Burbuja Mejorada
• Inserción (Insertion Sort)
• Selección (Selection Sort )
• Shell (Shell Sort)
• Ordenamiento con árbol binario de busqueda (Binary Search Tree)

Práctica 2: "Análisis temporal y notación de orden (Algoritmos de busqúeda)"

• Búsqueda lineal o secuencial (No recursiva)
• Búsqueda binaria o dicotómica (No recursiva)
• Búsqueda en un árbol binario de búsqueda (No recursiva)
• Modificar los tres algoritmos para trabajar con procesos ligeros (Hilos).

Práctica 3: "Divide y vencerás (Rotación de una imagen)"