Maîtriser les bases des notions fondamentales

Notions fondamentales

2.1 Définition d'un algorithme

Un algorithme est une suite finie d'instructions ou d'étapes permettant de résoudre un problème ou d'accomplir une tâche spécifique. En informatique, les algorithmes sont utilisés pour manipuler des données et effectuer des calculs.

2.2 Caractéristiques d'un algorithme

Pour être considéré comme un algorithme, une suite d'instructions doit posséder les caractéristiques suivantes :

• Finitude : L'algorithme doit toujours se terminer après un nombre fini d'étapes.
• Précision : Chaque étape de l'algorithme doit être définie de manière claire et précise.
• Entrée : L'algorithme doit recevoir des données d'entrée.
• Sortie : L'algorithme doit produire une ou plusieurs sorties.
• Efficacité : L'algorithme doit être conçu pour minimiser le temps d'exécution et l'utilisation de ressources.

Exemple de code en JavaScript pour une fonction quadratique :

// Exemple de calcul de la complexité temporelle avec une fonction quadratique
function sommeCarres(n) {
    // Initialisation de la somme à zéro
    let somme = 0;
    // Boucle pour chaque entier de 1 à n
    for (let i = 1; i <= n; i++) {
        // Ajout du carré de i à la somme
        somme += i * i;
    }
    return somme;
}

// Calcul de la somme des carrés de 1 à 10
console.log(sommeCarres(10));  // Output: 385

Vulgarisation de la Complexité des Algorithmes

La complexité d'un algorithme, c'est un peu comme évaluer combien de temps et d'énergie il faut pour accomplir une tâche. Imagine que tu es un chef cuisinier et que tu dois préparer des plats pour une fête. La complexité temporelle, c'est le temps que tu passes à cuisiner, et la complexité spatiale, c'est l'espace nécessaire dans ta cuisine (comme le nombre de casseroles, la taille du four, etc.).

1. Complexité Temporelle (Time Complexity)

Exemple amusant : Les Crêpes

Imagine que tu fais des crêpes. Chaque crêpe prend 2 minutes à cuire. Si tu dois faire 10 crêpes, tu passes 20 minutes à les cuire. Si tu dois en faire 20, tu passes 40 minutes. Le temps que tu passes à faire des crêpes augmente proportionnellement au nombre de crêpes. En algorithmie, on appelle ça une complexité linéaire, notée $O(n)$.

// Faire des crêpes avec une complexité linéaire
function faireCrepes(n) {
    for (let i = 0; i < n; i++) {
        console.log(`Cuire la crêpe ${i + 1}`);
        // Simuler 2 minutes de cuisson
    }
}

faireCrepes(5);  // Output: Cuire la crêpe 1 à 5

Autre exemple : Les Partitions de Pizza

Imagine que tu veux couper une pizza en morceaux. Si tu veux 4 morceaux, tu fais 4 coupures. Si tu veux 8 morceaux, tu fais 8 coupures. Le nombre de coupures augmente proportionnellement au nombre de morceaux. C'est aussi une complexité linéaire $O(n)$.

Imagine que tu veux couper une pizza en morceaux. Si tu veux 4 morceaux, tu fais 4 coupures. Si tu veux 8 morceaux, tu fais 8 coupures. Le nombre de coupures augmente proportionnellement au nombre de morceaux. C'est aussi une complexité linéaire $O(n)$.

Ecrit le code