Initiation à l'algorithmique

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

Introduction à l'algorithmique

Un algorithme est un ensemble d'étapes d'opérations permettant de résoudre un problème lié à l'exécution de tâches de calcul, de traitement de données et de raisonnement automatisé. Un algorithme est une méthode efficace qui peut être exprimée dans un temps et un espace définis.

Un algorithme est le meilleur moyen de représenter la solution d'un problème particulier de manière très simple et efficace. Si nous avons un algorithme pour un problème spécifique, nous pouvons l'implémenter dans n'importe quel langage de programmation, ce qui signifie que l'algorithme est indépendant de tout langage de programmation.

Pourquoi étudier l'algorithmique 

Au fur et à mesure que la vitesse du processeur augmente, il est souvent dit que les performances sont moins essentielles que d'autres caractéristiques de qualité logicielle (telles que la sécurité, l'extensibilité, la réutilisabilité, etc.). Cependant, les problèmes de grande taille sont courants dans le domaine de la science informatique, ce qui fait de la performance un facteur très important. Ceci est dû à un temps de calcul plus long.

L'étude de l'algorithmique nous donne donc un langage pour exprimer la performance en fonction de la taille du problème.

Conception d'un algorithme 

Les aspects importants de la conception d'un algorithme incluent la création d'un algorithme efficace pour résoudre un problème de manière efficace en utilisant un minimum de temps et d'espace.

Pour résoudre un problème, différentes approches peuvent être suivies. Certaines d'entre elles peuvent être efficaces en termes de consommation de temps, alors que d'autres approches peuvent utiliser efficacement la mémoire. Cependant, il ne faut pas oublier que la consommation de temps et l'utilisation de la mémoire ne peuvent pas être optimisées simultanément.

Si nous avons besoin d'un algorithme pour s'exécuter plus rapidement, nous devons investir dans plus de mémoire et si nous avons besoin d'un algorithme pour s'exécuter avec moins de mémoire, nous devons disposer de plus de temps.

Etapes de résolution d'un problème 

Les étapes suivantes sont impliquées dans la résolution de problèmes de calcul.

  •  Définition du problème
  •  Développement d'un modèle
  •  Spécification d'un algorithme
  •  Concevoir un algorithme
  •  Vérifier l'exactitude d'un algorithme
  •  Analyse d'un algorithme
  •  Implémentation d'un algorithme
  •  Test du programme
  •  Documentation

Caractéristiques des algorithmes 

Les principales caractéristiques des algorithmes sont les suivantes :

  •  Les algorithmes doivent avoir un nom unique
  •   Les algorithmes doivent avoir explicitement défini un ensemble d'entrées et de sorties
  •   Les algorithmes sont bien ordonnés avec des opérations sans ambiguïté
  •   Les algorithmes s’arrêtent dans un laps de temps fini. Les algorithmes ne doivent pas être exécutés à l'infini, c'est-à-dire qu'un algorithme doit se terminer à un moment donné

Pseudocode 

Le pseudocode donne une description de haut niveau d'un algorithme sans l'ambiguïté, mais également sans la nécessité de connaître la syntaxe d'un langage de programmation particulier.

Le temps d'exécution peut être estimé de manière plus générale en utilisant un pseudocode pour représenter l'algorithme sous la forme d'un ensemble d'opérations fondamentales pouvant ensuite être comptées.

Différence entre algorithme et pseudocode 

Un algorithme est une définition formelle avec certaines caractéristiques spécifiques décrivant un processus, qui pourrait être exécuté par une machine de Turing pour effectuer une tâche spécifique. Généralement, le mot "algorithme" peut être utilisé pour décrire toute tâche de haut niveau en informatique.

D'autre part, le pseudocode est une description informelle et lisible par un algorithme en laissant de nombreux détails granulaires. L'écriture de pseudo-code n'a aucune restriction de styles et son seul objectif est de décrire les étapes de haut niveau de l'algorithme de manière très réaliste en langage naturel.

Exemple

Si nous avons besoin de trier une suite de nombres en ordre croissant. Voici comment nous définissons le problème de tri en utilisant le tri par insertion

  • Algorithme Tri_Insertion
  •   Entrée - Une liste L d'entiers de longueur n
  •   Sortie - Une liste triée L1 contenant les entiers présents dans L
  •  Etape 1 - Initialiser une liste L1 vide d'éléments triés
  •  Etape 2 - Faire pour chaque élément de L
    •  Etape 3 - Insérez-le à la position correcte dans la liste triée L1.
  •   Etape 4 - Renvoyez la liste triée
  •  Etape 5 - Arrêtez

Voici un pseudocode qui décrit comment le processus abstrait de haut niveau mentionné ci-dessus dans l’algorithme Tri_Insertion pourrait être décrit de manière plus réaliste.

Pour i=0 à Taille(L) Faire
    x <- L(i)
    j <- i
    Tantque j > 0 ET L(j-1) > x Faire
        L(j) <- L(j-1) 
        j <- j - 1 
    L(j) <- x

Propriétés d'un algorithme

  •   Exactitude - il doit produire la sortie selon les exigences de l'algorithme
  •   Finitude - L'algorithme doit être terminé après l'exécution d'un nombre fini d'instructions.
  •   Une Absence d'ambiguïté - chaque étape doit être définie, avec une seule interprétation.
  •   Définition de la séquence - chaque étape doit avoir une étape précédente et une étape suivante uniques. La première et la dernière étape doivent être notées.
  •   Entrée/sortie - Le nombre et la classification des entrées et des résultats nécessaires doivent être indiqués.
  •   Faisabilité - Il doit être possible d'exécuter chaque instruction.
  •   Flexibilité - il devrait également être possible de modifier l’algorithme sans y mettre autant d’efforts.
  •   Efficace - L’efficacité est toujours mesurée en termes de temps et d’espace requis pour la mise en œuvre de l’algorithme. L’algorithme utilise donc un minimum de temps d’exécution et d’espace mémoire dans les limites du temps de développement acceptable.
  •   Indépendant - un algorithme doit se concentrer sur ce que sont les entrées, les sorties et comment obtenir une sortie sans connaître le langage dans lequel il est défini. Par conséquent, on peut dire que l'algorithme est indépendant de la langue.

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :