DAA - Présentation

Un algorithme est un ensemble d'étapes d'opérations pour résoudre un problème en effectuant des 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 une quantité limitée de temps et d'espace.

Un algorithme est le meilleur moyen de représenter la solution d'un problème particulier d'une 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 lealgorithm is independent from any programming languages.

Conception d'algorithmes

Les aspects importants de la conception d'algorithmes 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, tandis que d'autres approches peuvent être efficaces en mémoire. Cependant, il faut garder à l'esprit 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 en moins de temps, nous devons investir dans plus de mémoire et si nous avons besoin d'un algorithme pour fonctionner avec moins de mémoire, nous avons besoin de plus de temps.

Étapes de développement du problème

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

Définition du problème
Développement d'un modèle
Spécification d'un algorithme
Concevoir un algorithme
Vérification de l'exactitude d'un algorithme
Analyse d'un algorithme
Implémentation d'un algorithme
Test de 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 un ensemble défini explicitement 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 limité. Les algorithmes ne doivent pas fonctionner à 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é associée au texte brut, mais aussi sans avoir besoin de connaître la syntaxe d'un langage de programmation particulier.

Le temps d'exécution peut être estimé d'une manière plus générale en utilisant le pseudocode pour représenter l'algorithme comme un ensemble d'opérations fondamentales qui peuvent ensuite être comptées.

Différence entre l'algorithme et le pseudocode

Un algorithme est une définition formelle avec certaines caractéristiques spécifiques qui décrit un processus, qui pourrait être exécuté par une machine informatique complète 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 lisible par l'homme informelle et (souvent rudimentaire) d'un algorithme en laissant de nombreux détails granulaires. L'écriture d'un pseudocode n'a aucune restriction de style et son seul objectif est de décrire les étapes de haut niveau de l'algorithme d'une manière très réaliste en langage naturel.

Par exemple, voici un algorithme pour le tri par insertion.

Algorithm: Insertion-Sort 
Input: A list L of integers of length n  
Output: A sorted list L1 containing those integers present in L 
Step 1: Keep a sorted list L1 which starts off empty  
Step 2: Perform Step 3 for each element in the original list L  
Step 3: Insert it into the correct position in the sorted list L1.  
Step 4: Return the sorted list 
Step 5: Stop

Voici un pseudo-code qui décrit comment le processus abstrait de haut niveau mentionné ci-dessus dans l'algorithme Insertion-Sort pourrait être décrit d'une manière plus réaliste.

for i <- 1 to length(A) 
   x <- A[i] 
   j <- i 
   while j > 0 and A[j-1] > x 
      A[j] <- A[j-1] 
      j <- j - 1 
   A[j] <- x

Dans ce didacticiel, les algorithmes seront présentés sous la forme d'un pseudocode, similaire à bien des égards à C, C ++, Java, Python et d'autres langages de programmation.