Algorithmes Probabilistes

Introduction

Les algorithmes probabilistes utilisent des éléments de hasard pour prendre des décisions durant leur exécution. Ils sont souvent utilisés pour résoudre des problèmes où les méthodes déterministes seraient inefficaces ou trop coûteuses en termes de temps. Il existe principalement deux types d'algorithmes probabilistes : les algorithmes de Monte Carlo et les algorithmes de Las Vegas.

Algorithmes de Monte Carlo

Les algorithmes de Monte Carlo sont utilisés pour estimer des résultats où une solution exacte serait difficile à obtenir. Ils reposent sur des échantillons aléatoires et fournissent des réponses avec une certaine probabilité d'erreur.

Caractéristiques

• Probabilité d'erreur : Ils fournissent des résultats qui peuvent être incorrects avec une certaine probabilité.
• Complexité temporelle : Souvent plus rapide que les algorithmes déterministes, surtout pour les grandes instances de problèmes.
• Applications : Utilisés dans les simulations, les intégrations numériques, et les problèmes d'optimisation.

Exemple : Estimation de la valeur de π

Un exemple classique de l'algorithme de Monte Carlo est l'estimation de la valeur de π en utilisant des points aléatoires dans un carré et un cercle inscrit.

Implémentation en JavaScript

function estimatePi(numPoints) {
    let insideCircle = 0;

    for (let i = 0; i < numPoints; i++) {
        const x = Math.random();
        const y = Math.random();

        if (x * x + y * y <= 1) {
            insideCircle++;
        }
    }

    return (insideCircle / numPoints) * 4;
}

// Exemple d'utilisation
const numPoints = 1000000;
const piEstimate = estimatePi(numPoints);
console.log(`Estimation de π : ${piEstimate}`);

Explication du Code

1. Génération de Points : Des points (x, y) sont générés aléatoirement dans un carré de côté 1.
2. Vérification : Pour chaque point, on vérifie s'il tombe à l'intérieur du cercle de rayon 1 centré à l'origine.
3. Estimation : Le rapport du nombre de points à l'intérieur du cercle au nombre total de points, multiplié par 4, donne une estimation de π.

Algorithmes de Las Vegas

Les algorithmes de Las Vegas sont des algorithmes probabilistes qui toujours fournissent des solutions correctes, mais leur temps d'exécution peut varier. Contrairement aux algorithmes de Monte Carlo, ils ne tolèrent pas d'erreur dans le résultat.

Caractéristiques

• Exactitude : Fournissent toujours des résultats corrects.
• Complexité temporelle : Le temps d'exécution est variable et dépend des résultats des essais aléatoires.
• Applications : Utilisés pour les problèmes de tri, de recherche, et de génération de structures combinatoires.

Exemple : Tri Rapide Randomisé

Le tri rapide randomisé est une version de l'algorithme de tri rapide où le pivot est choisi de manière aléatoire pour améliorer les performances moyennes.

Implémentation en JavaScript

function quickSortRandom(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    const pivotIndex = Math.floor(Math.random() * arr.length);
    const pivot = arr[pivotIndex];
    const left = [];
    const right = [];

    for (let i = 0; i < arr.length; i++) {
        if (i !== pivotIndex) {
            if (arr[i] < pivot) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
    }

    return [...quickSortRandom(left), pivot, ...quickSortRandom(right)];
}

// Exemple d'utilisation
const arr = [38, 27, 43, 3, 9, 82, 10];
const sortedArr = quickSortRandom(arr);
console.log(sortedArr); // Output: [3, 9, 10, 27, 38, 43, 82]

Explication du Code

1. Choix du Pivot : Un pivot est choisi aléatoirement dans le tableau.
2. Partition : Les éléments sont répartis dans deux sous-tableaux selon qu'ils sont inférieurs ou supérieurs au pivot.
3. Appel Récursif : Le tri rapide est appliqué récursivement aux sous-tableaux gauche et droit.

Comparaison Monte Carlo vs Las Vegas

Applications et Exemples

1. Intégration Numérique (Monte Carlo)

Problème : Calculer l'intégrale d'une fonction complexe.

Solution : Utiliser des points aléatoires pour estimer l'aire sous la courbe.

Exemple en JavaScript

function integrateMonteCarlo(func, a, b, numPoints) {
    let sum = 0;

    for (let i = 0; i < numPoints; i++) {
        const x = a + (b - a) * Math.random();
        sum += func(x);
    }

    return (b - a) * (sum / numPoints);
}

// Fonction à intégrer
function f(x) {
    return Math.sin(x);
}

// Intégration de sin(x) de 0 à π
const numPoints = 100000;
const result = integrateMonteCarlo(f, 0, Math.PI, numPoints);
console.log(`Résultat de l'intégration : ${result}`);

2. Génération de Graphes Aléatoires (Las Vegas)

Problème : Générer un graphe avec des propriétés spécifiques.

Solution : Utiliser un algorithme de Las Vegas pour générer le graphe et vérifier ses propriétés.

Exemple en JavaScript

function generateGraph(numNodes, numEdges) {
    const graph = Array.from({ length: numNodes }, () => []);
    
    let edges = 0;
    while (edges < numEdges) {
        const u = Math.floor(Math.random() * numNodes);
        const v = Math.floor(Math.random() * numNodes);

        if (u !== v && !graph[u].includes(v)) {
            graph[u].push(v);
            graph[v].push(u);
            edges++;
        }
    }

    return graph;
}

// Génération d'un graphe avec 5 nœuds et 6 arêtes
const graph = generateGraph(5, 6);
console.log(graph);

Conclusion

Les algorithmes probabilistes, tels que Monte Carlo et Las Vegas, offrent des solutions efficaces et pratiques pour de nombreux problèmes complexes. Les algorithmes de Monte Carlo sont utilisés pour les estimations et les simulations, tandis que les algorithmes de Las Vegas sont utilisés pour garantir des résultats corrects avec un temps d'exécution variable. Comprendre ces algorithmes et leurs applications permet d'optimiser la performance et l'efficacité des solutions dans divers domaines.