Définition – Algorithme et Problème | Algorithmique Seconde

Énoncé : Trouver les racines d'une équation du second degré ax² + bx + c = 0

Données : Coefficients a, b, c

Objectif : Trouver les valeurs de x qui vérifient l'équation

Énoncé : Trier une liste de nombres par ordre croissant

Données : Liste de nombres

Objectif : Renvoyer la liste triée

Énoncé : Calculer le temps de trajet entre deux villes

Données : Distance, vitesse moyenne

Objectif : Calculer le temps de trajet

Un algorithme est une suite finie et non ambiguë d'instructions permettant de résoudre un problème.

Il doit respecter les critères suivants :

• Finitude : Un nombre fini d'étapes
• Bonne définition : Chaque instruction est claire
• Entrées : Zéro ou plusieurs données d'entrée
• Sorties : Une ou plusieurs données de sortie
• Efficacité : Résout le problème en un temps raisonnable

Un algorithme est comparable à une recette de cuisine :

• Ingrédients → Données d'entrée
• Étapes précises → Instructions de l'algorithme
• Plat final → Résultat attendu

Chaque étape doit être clairement formulée pour aboutir au résultat escompté.

Un algorithme doit se terminer après un nombre fini d'étapes. Il ne doit pas boucler indéfiniment.

Exemple : L'algorithme de recherche d'un élément dans une liste se termine quand l'élément est trouvé ou quand toute la liste a été parcourue.

Pour les mêmes données d'entrée, un algorithme doit toujours produire le même résultat.

Chaque instruction est exécutée de manière prévisible et cohérente.

L'algorithme doit résoudre le problème en un temps raisonnable et utiliser des ressources limitées.

On mesure souvent l'efficacité par la complexité algorithmique.

Un problème est une question ou une tâche à accomplir.

Un algorithme est une méthode systématique pour résoudre ce problème.

Un même problème peut avoir plusieurs algorithmes de résolution.

Problème : Trier une liste de nombres

Algorithmes possibles :

• Tri à bulles
• Tri rapide (QuickSort)
• Tri fusion
• Tri par insertion

Chaque algorithme a ses avantages et inconvénients en termes de performance.

ALGORITHME Maximum
    VARIABLES a, b, max : NOMBRES
DEBUT
    AFFICHER "Entrez le premier nombre"
    LIRE a
    AFFICHER "Entrez le second nombre"
    LIRE b
    
    SI a > b ALORS
        max ← a
    SINON
        max ← b
    FIN SI
    
    AFFICHER "Le maximum est ", max
FIN
                                        

• Entrées : Deux nombres a et b
• Processus : Comparaison des deux nombres
• Sortie : Le plus grand des deux nombres

Cet algorithme respecte toutes les propriétés d'un bon algorithme : finitude, déterminisme, efficacité.

Langage proche de la programmation mais simplifié, indépendant de tout langage spécifique.

Avantages : Lisible, facile à comprendre, proche de la programmation.

Représentation graphique avec des formes géométriques et des flèches.

Symboles courants : ovale (début/fin), rectangle (traitement), losange (condition), parallélogramme (entrée/sortie).

Description en français des étapes de l'algorithme.

Moins formel mais parfois plus accessible pour les débutants.

• Ovale : Début/Fin de l'algorithme
• Rectangle : Traitement ou affectation
• Rhombus : Test conditionnel
• Flèches : Ordre d'exécution des instructions

L'organigramme permet de visualiser le déroulement logique de l'algorithme.

Permettent de ranger des éléments dans un ordre particulier (croissant, décroissant).

Exemples : Tri à bulles, tri rapide, tri fusion, tri par insertion.

Permettent de trouver un élément dans une structure de données.

Exemples : Recherche linéaire, recherche dichotomique.

Effectuent des calculs mathématiques complexes.

Exemples : Algorithme d'Euclide, calcul de PGCD, approximation de racines.

Utilisés pour traiter des structures en forme de graphes.

Exemples : Algorithme de Dijkstra, parcours en profondeur.

• Donnée d'entrée : Un entier n positif
• Donnée de sortie : La somme S = 1 + 2 + ... + n
• Opération : Addition successive des entiers de 1 à n

ALGORITHME SommeEntiers
    VARIABLES n, i, somme : ENTIER
DEBUT
    AFFICHER "Entrez un entier positif n"
    LIRE n
    somme ← 0
    
    POUR i ALLANT DE 1 À n FAIRE
        somme ← somme + i
    FIN POUR
    
    AFFICHER "La somme des ", n, " premiers entiers est ", somme
FIN
                                        

On sait que la somme des n premiers entiers est égale à n(n+1)/2

ALGORITHME SommeEntiersOptimise
    VARIABLES n, somme : ENTIER
DEBUT
    AFFICHER "Entrez un entier positif n"
    LIRE n
    
    somme ← n * (n + 1) / 2
    
    AFFICHER "La somme des ", n, " premiers entiers est ", somme
FIN
                                        

• Données d'entrée : Une liste de nombres et un élément à rechercher
• Donnée de sortie : Position de l'élément ou message d'absence
• Opération : Comparaison successive avec chaque élément de la liste

ALGORITHME RechercheLineaire
    VARIABLES liste[1..n], element, i, position : ENTIER
    TROUVE : BOOLEEN
DEBUT
    AFFICHER "Entrez la taille de la liste"
    LIRE n
    
    AFFICHER "Entrez les éléments de la liste"
    POUR i ALLANT DE 1 À n FAIRE
        LIRE liste[i]
    FIN POUR
    
    AFFICHER "Entrez l'élément à rechercher"
    LIRE element
    
    TROUVE ← FAUX
    i ← 1
    
    TANT QUE i ≤ n ET NON TROUVE FAIRE
        SI liste[i] = element ALORS
            TROUVE ← VRAI
            position ← i
        SINON
            i ← i + 1
        FIN SI
    FIN TANT QUE
    
    SI TROUVE ALORS
        AFFICHER "L'élément est trouvé à la position ", position
    SINON
        AFFICHER "L'élément n'est pas dans la liste"
    FIN SI
FIN
                                        

La complexité algorithmique mesure l'efficacité d'un algorithme en fonction de la taille des données d'entrée.

Elle s'exprime généralement en notation "grand O" (O(n), O(n²), O(log n), etc.).

• O(1) : Temps constant - Indépendant de la taille des données
• O(log n) : Logarithmique - Très efficace
• O(n) : Linéaire - Proportionnel à la taille des données
• O(n log n) : Efficace pour les grands ensembles
• O(n²) : Quadratique - Moins efficace pour les grandes tailles

• Situation qui nécessite une solution
• Caractérisé par des données d'entrée et un objectif
• Doit être bien posé pour avoir une solution

• Suite finie et non ambiguë d'instructions
• Respecte les propriétés de finitude, déterminisme, efficacité
• Méthode systématique pour résoudre un problème

• Pseudo-code : Langage proche de la programmation
• Organigramme : Représentation graphique
• Langage naturel : Description en français