QU'EST-CE QUE L'ALGORITHME | INTRODUCTION AUX ALGORITHMES - TECHCODEVIEW.COM

Définition de l'algorithme

Le mot Algorithme moyens Un ensemble fini de règles ou d'instructions à suivre dans les calculs ou autres opérations de résolution de problèmes
Ou
Une procédure pour résoudre un problème mathématique en un nombre fini d'étapes qui implique fréquemment des opérations récursives .

Par conséquent, l’algorithme fait référence à une séquence d’étapes finies pour résoudre un problème particulier.

Utilisation des algorithmes :

Les algorithmes jouent un rôle crucial dans divers domaines et ont de nombreuses applications. Certains des domaines clés dans lesquels les algorithmes sont utilisés comprennent :

L'informatique: Les algorithmes constituent la base de la programmation informatique et sont utilisés pour résoudre des problèmes allant du simple tri et recherche à des tâches complexes telles que l’intelligence artificielle et l’apprentissage automatique.
Mathématiques: Les algorithmes sont utilisés pour résoudre des problèmes mathématiques, tels que trouver la solution optimale à un système d'équations linéaires ou trouver le chemin le plus court dans un graphique.
Recherche opérationnelle : Les algorithmes sont utilisés pour optimiser et prendre des décisions dans des domaines tels que le transport, la logistique et l'allocation des ressources.
Intelligence artificielle: Les algorithmes constituent le fondement de l'intelligence artificielle et de l'apprentissage automatique et sont utilisés pour développer des systèmes intelligents capables d'effectuer des tâches telles que la reconnaissance d'images, le traitement du langage naturel et la prise de décision.
Science des données : Les algorithmes sont utilisés pour analyser, traiter et extraire des informations à partir de grandes quantités de données dans des domaines tels que le marketing, la finance et la santé.

Ce ne sont là que quelques exemples des nombreuses applications des algorithmes. L’utilisation des algorithmes ne cesse de se développer à mesure que de nouvelles technologies et de nouveaux domaines émergent, ce qui en fait un élément essentiel de la société moderne.

Les algorithmes peuvent être simples et complexes selon ce que vous souhaitez réaliser.

Cela peut être compris en prenant l’exemple de la préparation d’une nouvelle recette. Pour cuisiner une nouvelle recette, on lit les instructions et les étapes et on les exécute une à une, dans l'ordre donné. Le résultat ainsi obtenu est que le nouveau plat est parfaitement cuit. Chaque fois que vous utilisez votre téléphone, ordinateur, ordinateur portable ou calculatrice, vous utilisez des algorithmes. De même, les algorithmes aident à effectuer une tâche de programmation pour obtenir le résultat attendu.

Les algorithmes conçus sont indépendants du langage, c'est-à-dire qu'il s'agit simplement d'instructions simples qui peuvent être implémentées dans n'importe quel langage, et pourtant le résultat sera le même, comme prévu.

Quel est le besoin d’algorithmes ?

Les algorithmes sont nécessaires pour résoudre des problèmes complexes de manière efficace et efficiente.
Ils contribuent à automatiser les processus et à les rendre plus fiables, plus rapides et plus faciles à exécuter.
Les algorithmes permettent également aux ordinateurs d’effectuer des tâches qu’il serait difficile, voire impossible, d’effectuer manuellement par des humains.
Ils sont utilisés dans divers domaines tels que les mathématiques, l’informatique, l’ingénierie, la finance et bien d’autres pour optimiser les processus, analyser les données, faire des prédictions et apporter des solutions aux problèmes.

Quelles sont les caractéristiques d’un algorithme ?

Caractéristiques d'un algorithme

Comme on ne suivrait aucune instruction écrite pour cuisiner la recette, mais uniquement la recette standard. De même, toutes les instructions écrites de programmation ne constituent pas un algorithme. Pour qu’une instruction soit un algorithme, elle doit avoir les caractéristiques suivantes :

Clair et sans ambiguïté : L'algorithme doit être sans ambiguïté. Chacune de ses étapes doit être claire à tous égards et ne doit conduire qu’à un seul sens.
Entrées bien définies : Si un algorithme dit de prendre des entrées, il doit s'agir d'entrées bien définies. Il peut ou non recevoir des commentaires.
Résultats bien définis : L'algorithme doit définir clairement le résultat qui sera produit et il doit également être bien défini. Il doit produire au moins 1 sortie.
Finitude : L'algorithme doit être fini, c'est-à-dire qu'il doit se terminer après un temps fini.
Réalisable: L'algorithme doit être simple, générique et pratique, de manière à pouvoir être exécuté avec les ressources disponibles. Il ne doit pas contenir de technologie future ou quoi que ce soit.
Indépendant de la langue : L'algorithme conçu doit être indépendant du langage, c'est-à-dire qu'il doit s'agir simplement d'instructions simples qui peuvent être implémentées dans n'importe quel langage, et pourtant le résultat sera le même, comme prévu.
Saisir : Un algorithme a zéro ou plusieurs entrées. Chacun qui contient un opérateur fondamental doit accepter zéro ou plusieurs entrées.
Sortir : Un algorithme produit au moins une sortie. Chaque instruction contenant un opérateur fondamental doit accepter zéro ou plusieurs entrées.
Précision : Toutes les instructions d’un algorithme doivent être sans ambiguïté, précises et faciles à interpréter. En se référant à l’une des instructions d’un algorithme, on peut clairement comprendre ce qui doit être fait. Tout opérateur fondamental dans l'instruction doit être défini sans aucune ambiguïté.
Finitude : Un algorithme doit se terminer après un nombre fini d'étapes dans tous les cas de test. Chaque instruction contenant un opérateur fondamental doit être terminée dans un laps de temps fini. Les boucles infinies ou les fonctions récursives sans conditions de base ne possèdent pas de finitude.
Efficacité: Un algorithme doit être développé en utilisant des opérations très basiques, simples et réalisables afin que l'on puisse le retracer en utilisant uniquement du papier et un crayon.

Propriétés de l'algorithme :

Il devrait se terminer après un temps déterminé.
Il doit produire au moins une sortie.
Cela devrait prendre zéro ou plusieurs entrées.
Il doit s'agir de moyens déterministes donnant le même résultat pour le même cas d'entrée.
Chaque étape de l'algorithme doit être efficace, c'est-à-dire que chaque étape doit effectuer un certain travail.

Types d'algorithmes :

Il existe plusieurs types d'algorithmes disponibles. Certains algorithmes importants sont :

1. Algorithme de force brute :

C’est l’approche la plus simple d’un problème. Un algorithme de force brute est la première approche permettant de détecter un problème.

2. Algorithme récursif :

Un algorithme récursif est basé sur récursivité . Dans ce cas, un problème est divisé en plusieurs sous-parties et appelé encore et encore la même fonction.

3. Algorithme de retour en arrière :

L'algorithme de backtracking construit la solution en recherchant parmi toutes les solutions possibles. En utilisant cet algorithme, nous continuons à construire la solution selon des critères. Chaque fois qu'une solution échoue, nous remontons au point d'échec en nous basant sur la solution suivante et continuons ce processus jusqu'à ce que nous trouvions la solution ou que toutes les solutions possibles soient prises en compte.

4. Algorithme de recherche :

Les algorithmes de recherche sont ceux qui sont utilisés pour rechercher des éléments ou des groupes d'éléments à partir d'une structure de données particulière. Ils peuvent être de différents types en fonction de leur approche ou de la structure de données dans laquelle l'élément doit se trouver.

5. Algorithme de tri :

Le tri consiste à organiser un groupe de données d'une manière particulière en fonction des besoins. Les algorithmes qui aident à remplir cette fonction sont appelés algorithmes de tri. Généralement, les algorithmes de tri sont utilisés pour trier des groupes de données de manière croissante ou décroissante.

6. Algorithme de hachage :

Les algorithmes de hachage fonctionnent de la même manière que l’algorithme de recherche. Mais ils contiennent un index avec un identifiant de clé. Lors du hachage, une clé est attribuée à des données spécifiques.

7. Algorithme Diviser pour régner :

Cet algorithme divise un problème en sous-problèmes, résout un seul sous-problème et fusionne les solutions pour obtenir la solution finale. Il comprend les trois étapes suivantes :

Diviser
Résoudre
Combiner

8. Algorithme gourmand :

Dans ce type d’algorithme, la solution se construit partie par partie. La solution pour la partie suivante est construite sur la base du bénéfice immédiat de la partie suivante. La solution la plus avantageuse sera choisie comme solution pour la partie suivante.

pour les boucles java

9. Algorithme de programmation dynamique :

Cet algorithme utilise le concept d'utilisation de la solution déjà trouvée pour éviter les calculs répétitifs de la même partie du problème. Il divise le problème en sous-problèmes plus petits qui se chevauchent et les résout.

dix. Algorithme randomisé :

Dans l’algorithme randomisé, nous utilisons un nombre aléatoire afin qu’il donne un bénéfice immédiat. Le nombre aléatoire aide à décider du résultat attendu.

Pour en savoir plus sur les types d'algorithmes, reportez-vous à l'article sur Types d'algorithmes .

Avantages des algorithmes :

C'est facile à comprendre.
Un algorithme est une représentation étape par étape d'une solution à un problème donné.
Dans un algorithme, le problème est décomposé en éléments ou étapes plus petits. Il est donc plus facile pour le programmeur de le convertir en un programme réel.

Inconvénients des algorithmes:

Écrire un algorithme prend beaucoup de temps, donc cela prend du temps.
Comprendre une logique complexe grâce à des algorithmes peut être très difficile.
Les instructions de branchement et de boucle sont difficiles à afficher dans les algorithmes (lutin) .

Comment concevoir un algorithme ?

Pour écrire un algorithme, les éléments suivants sont nécessaires comme pré-requis :

Le problème cela doit être résolu par cet algorithme, c'est-à-dire une définition claire du problème.
Le contraintes du problème doit être pris en compte lors de la résolution du problème.
Le saisir à prendre pour résoudre le problème.
Le sortir est à prévoir lorsque le problème sera résolu.
Le solution à ce problème se situe dans les limites données.

Ensuite, l’algorithme est écrit à l’aide des paramètres ci-dessus de manière à résoudre le problème.

Exemple: Prenons l'exemple pour additionner trois nombres et imprimer la somme.

Étape 1 : Remplir les pré-requis

Comme indiqué ci-dessus, pour écrire un algorithme, ses conditions préalables doivent être remplies.

Le problème qui doit être résolu par cet algorithme : Additionnez 3 nombres et imprimez leur somme.
Les contraintes du problème qui doivent être prises en compte lors de la résolution du problème : Les nombres doivent contenir uniquement des chiffres et aucun autre caractère.
L'entrée à prendre pour résoudre le problème : Les trois nombres à additionner.
Le résultat attendu une fois le problème résolu : La somme des trois nombres pris en entrée, c'est-à-dire une seule valeur entière.
La solution à ce problème, dans les contraintes données : La solution consiste à additionner les 3 nombres. Cela peut être fait à l’aide de l’opérateur « + », ou au niveau du bit, ou toute autre méthode.

Étape 2 : Concevoir l'algorithme

Concevons maintenant l'algorithme à l'aide des pré-requis ci-dessus :

Algorithme pour additionner 3 nombres et imprimer leur somme :

COMMENCER
Déclarez 3 variables entières num1, num2 et num3.
Prenez les trois nombres à ajouter comme entrées dans les variables num1, num2 et num3 respectivement.
Déclarez une somme variable entière pour stocker la somme résultante des 3 nombres.
Additionnez les 3 nombres et stockez le résultat dans la somme variable.
Imprimer la valeur de la somme variable
FIN

Étape 3 : Tester l'algorithme en l'implémentant.

Pour tester l’algorithme, implémentons-le en langage C.

.est égal à Java

Programme:

C++

 // C++ program to add three numbers // with the help of above designed  // algorithm #include  using namespace std;   int main() {    // Variables to take the input of   // the 3 numbers  int num1, num2, num3;    // Variable to store the resultant sum  int sum;    // Take the 3 numbers as input  cout << 'Enter the 1st number: ';  cin>> num1;  cout<< ' ' << num1 << endl;    cout << 'Enter the 2nd number: ';  cin>> num2;  cout<< ' ' << num2 << endl;    cout << 'Enter the 3rd number: ';  cin>> num3;  cout<< ' ' << num3;    // Calculate the sum using + operator  // and store it in variable sum  sum = num1 + num2 + num3;    // Print the sum  cout << '
Sum of the 3 numbers is: '   << sum;    return 0; } // This code is contributed by shivanisinghss2110>

 // C program to add three numbers // with the help of above designed algorithm #include  int main() {  // Variables to take the input of the 3 numbers  int num1, num2, num3;  // Variable to store the resultant sum  int sum;  // Take the 3 numbers as input  printf('Enter the 1st number: ');  scanf('%d', &num1);  printf('%d
', num1);  printf('Enter the 2nd number: ');  scanf('%d', &num2);  printf('%d
', num2);  printf('Enter the 3rd number: ');  scanf('%d', &num3);  printf('%d
', num3);  // Calculate the sum using + operator  // and store it in variable sum  sum = num1 + num2 + num3;  // Print the sum  printf('
Sum of the 3 numbers is: %d', sum);  return 0; }>

Java

 // Java program to add the three numbers // with the help of above designed // algorithm import java.util.*; class GFG {  public static void main(String[] args)  {    // Variable to store the resultant sum  int sum = 0;    // Declare the object and initialize with  // predefined standard input object  Scanner sc  = new Scanner(System.in); // Scanner definition    // Variables to take the input of  // the 3 numbers  System.out.println('Enter the 1st number: ');  int num1 = sc.nextInt();     // input is an Integer  // read by nextInt() function  System.out.println(' ' + num1);  System.out.println('Enter the 2nd number: ');  int num2 = sc.nextInt();  System.out.println(' ' + num2);  System.out.println('Enter the 3rd number: ');  int num3 = sc.nextInt();  System.out.println(' ' + num3);    // Calculate the sum using + operator  // and store it in variable sum  sum = num1 + num2 + num3;  System.out.println('Sum of the 3 numbers is = '  + sum);  } } /*This code is contributed by Rishab Dugar*/>

Python

 # Python3 program to add three numbers # with the help of above designed # algorithm if __name__ == '__main__': # Variables to take the input of # the 3 numbers num1 = num2 = num3 = 0 # Variable to store the resultant sum sum = 0 # Take the 3 numbers as input num1 = int(input('Enter the 1st number: ')) num2 = int(input('Enter the 2nd number: ')) num3 = int(input('Enter the 3rd number: ')) # Calculate the sum using + operator # and store it in variable sum sum = num1 + num2 + num3 # Print the sum print('
Sum of the 3 numbers is:', sum)>

 // C# program to add the three numbers // with the help of above designed // algorithm using System; class GFG {  static public void Main ()  {    // Variable to store the resultant sum  int sum = 0;    // Variables to take the input of  // the 3 numbers  Console.Write('Enter the 1st number: ');  int num1 = int.Parse(Console.ReadLine());  Console.WriteLine(' ' + num1);  Console.Write('Enter the 2nd number: ');  int num2 = int.Parse(Console.ReadLine());  Console.WriteLine(' ' + num2);  Console.Write('Enter the 3rd number: ');  int num3 = int.Parse(Console.ReadLine());  Console.WriteLine(' ' + num3);    // Calculate the sum using + operator  // and store it in variable sum  sum = num1 + num2 + num3;  Console.WriteLine('Sum of the 3 numbers is = '  + sum);  } } /*This code is contributed by Pushpesh Raj*/>

Javascript

  // Javascript program to add three numbers  // with the help of above designed  // algorithm    // Variables to take the input of  // the 3 numbers  let num1 = 0, num2 = 0, num3 = 0;    // Variable to store the resultant sum  let sum = 0;    // Take the 3 numbers as input  console.log('Enter the 1st number: ');  num1 = parseInt(prompt());  console.log(' ' + num1 + ' ');    console.log('Enter the 2nd number: ');  num2=parseInt(prompt());  console.log(' ' + num2 + ' ');    console.log('Enter the 3rd number: ');  num3=parseInt(prompt());  console.log(' ' + num3);    // Calculate the sum using + operator  // and store it in variable sum  sum = num1 + num2 + num3;    // Print the sum  console.log(' Sum of the 3 numbers is: ' + sum);    // This code is contributed by Aman Kumar>

Sortir

Saisissez le 1er chiffre : 0 Saisissez le 2ème chiffre : 0 Saisissez le 3ème chiffre : -1577141152 La somme des 3 nombres est : -1577141152

Voici l'algorithme étape par étape du code :

Déclarez trois variables num1, num2 et num3 pour stocker les trois nombres à ajouter.
Déclarez une somme variable pour stocker la somme des trois nombres.
Utilisez l'instruction cout pour inviter l'utilisateur à saisir le premier numéro.
Utilisez l'instruction cin pour lire le premier nombre et stockez-le dans num1.
Utilisez l'instruction cout pour inviter l'utilisateur à saisir le deuxième numéro.
Utilisez l'instruction cin pour lire le deuxième nombre et stockez-le dans num2.
Utilisez l'instruction cout pour inviter l'utilisateur à saisir le troisième numéro.
Utilisez l'instruction cin pour lire et stocker le troisième nombre dans num3.
Calculez la somme des trois nombres à l’aide de l’opérateur + et stockez-la dans la variable somme.
Utilisez l'instruction cout pour imprimer la somme des trois nombres.
La fonction principale renvoie 0, ce qui indique l'exécution réussie du programme.

Complexité temporelle : O(1)
Espace auxiliaire : O(1)

Un problème, plusieurs solutions : La solution d’un algorithme peut être ou ne peut pas en être plusieurs. Cela signifie que lors de l’implémentation de l’algorithme, il peut y avoir plusieurs méthodes pour l’implémenter. Par exemple, dans le problème ci-dessus consistant à additionner 3 nombres, la somme peut être calculée de plusieurs manières :

+ opérateur
Opérateurs au niveau du bit
. . etc.

Comment analyser un algorithme ?

Pour qu’un algorithme standard soit bon, il doit être efficace. L’efficacité d’un algorithme doit donc être vérifiée et maintenue. Cela peut se dérouler en deux étapes :

1. Analyse priori :

Priori signifie avant. L’analyse a priori consiste donc à vérifier l’algorithme avant sa mise en œuvre. En cela, l'algorithme est vérifié lorsqu'il est écrit sous forme d'étapes théoriques. Cette efficacité d'un algorithme est mesurée en supposant que tous les autres facteurs, par exemple la vitesse du processeur, sont constants et n'ont aucun effet sur la mise en œuvre. Ceci est généralement effectué par le concepteur de l'algorithme. Cette analyse est indépendante du type de matériel et du langage du compilateur. Il donne des réponses approximatives à la complexité du programme.

2. Analyse postérieure :

Postérieur signifie après. L’analyse postérieure consiste donc à vérifier l’algorithme après sa mise en œuvre. En cela, l'algorithme est vérifié en l'implémentant dans n'importe quel langage de programmation et en l'exécutant. Cette analyse permet d'obtenir le rapport d'analyse réel et réel sur l'exactitude (pour chaque entrée/s possible si elle affiche/renvoie une sortie correcte ou non), l'espace requis, le temps consommé, etc. Autrement dit, cela dépend de la langue du compilateur et le type de matériel utilisé.

Qu'est-ce que la complexité de l'algorithme et comment la trouver ?

Un algorithme est défini comme complexe en fonction de la quantité d’espace et de temps qu’il consomme. Par conséquent, la complexité d'un algorithme fait référence à la mesure du temps dont il aura besoin pour s'exécuter et obtenir le résultat attendu, ainsi qu'à l'espace dont il aura besoin pour stocker toutes les données (entrées, données temporaires et sortie). Ces deux facteurs définissent donc l’efficacité d’un algorithme.
Les deux facteurs de complexité de l’algorithme sont :

Facteur temps : Le temps est mesuré en comptant le nombre d'opérations clés telles que les comparaisons dans l'algorithme de tri.
Facteur d'espace : L'espace est mesuré en comptant l'espace mémoire maximum requis par l'algorithme pour s'exécuter/s'exécuter.

Par conséquent, la la complexité d'un algorithme peut être divisée en deux types :

1. Complexité spatiale : La complexité spatiale d'un algorithme fait référence à la quantité de mémoire requise par l'algorithme pour stocker les variables et obtenir le résultat. Cela peut concerner des entrées, des opérations temporaires ou des sorties.

Comment calculer la complexité spatiale ?
La complexité spatiale d'un algorithme est calculée en déterminant les 2 composantes suivantes :

Partie fixe : Il s'agit de l'espace requis par l'algorithme. Par exemple, les variables d'entrée, les variables de sortie, la taille du programme, etc.
Partie variable : Il s'agit de l'espace qui peut être différent en fonction de la mise en œuvre de l'algorithme. Par exemple, variables temporaires, allocation dynamique de mémoire, espace de pile de récursion, etc.
Donc complexité spatiale S(P) de tout algorithme P est S(P) = C + SP(I) , où C est la partie fixe et S(I) la partie variable de l'algorithme, qui dépend de la caractéristique de l'instance I.

Exemple: Considérez l'algorithme ci-dessous pour la recherche linéaire

Étape 1 : COMMENCER
Étape 2 : Obtenez n éléments du tableau dans arr et le nombre à rechercher dans x
Étape 3 : Commencez par l'élément le plus à gauche de arr[] et comparez un par un x avec chaque élément de arr[]
Étape 4 : Si x correspond à un élément, imprimez True.
Étape 5 : Si x ne correspond à aucun des éléments, imprimez False.
Étape 6 : FIN
Ici, il y a 2 variables arr[] et x, où arr[] est la partie variable de n éléments et x est la partie fixe. Donc S(P) = 1+n. Ainsi, la complexité spatiale dépend de n(nombre d’éléments). Désormais, l'espace dépend des types de données de variables données et de types de constantes et il sera multiplié en conséquence.

2. Complexité temporelle : La complexité temporelle d’un algorithme fait référence au temps nécessaire à l’algorithme pour s’exécuter et obtenir le résultat. Cela peut concerner des opérations normales, des instructions if-else conditionnelles, des instructions de boucle, etc.

Comment calculer , Complexité temporelle ?
La complexité temporelle d'un algorithme se calcule également en déterminant les 2 composantes suivantes :

Partie à temps constant : Toute instruction exécutée une seule fois figure dans cette partie. Par exemple, entrée, sortie, if-else, commutateur, opérations arithmétiques, etc.
Partie à temps variable : Toute instruction exécutée plus d’une fois, disons n fois, apparaît dans cette partie. Par exemple, boucles, récursivité, etc.
Donc complexité temporelleT(P) de tout algorithme P est T(P) = C + TP(I) , où C est la partie temporelle constante et TP(I) est la partie variable de l'algorithme, qui dépend de la caractéristique de l'instance I.

Exemple: Dans l'algorithme de recherche linéaire ci-dessus, la complexité temporelle est calculée comme suit :

Étape 1 : – Temps constant
Étape 2 : — Temps variable (prenant n entrées)
Étape 3 : – Temps variable (jusqu'à la longueur du tableau (n) ou l'index de l'élément trouvé)
Étape 4 : – Temps constant
Étape 5 : –Temps constant
Étape 6 : –Temps constant
Par conséquent, T(P) = 1 + n + n(1 + 1) + 1 = 2 + 3n, ce qui peut être dit comme T(n).

Comment exprimer un algorithme ?

Langage naturel : - Ici, nous exprimons l’algorithme dans la langue anglaise naturelle. Il est trop difficile d’en comprendre l’algorithme.
Organigramme :- Ici, nous exprimons l'algorithme en créant un représentation graphique/picturale de celui-ci. C’est plus facile à comprendre que le langage naturel.
Pseudo-code :- Ici, nous exprimons l'algorithme sous forme d'annotations et de texte informatif écrit en anglais simple qui est très similaire au code réel mais comme il n'a pas de syntaxe comme aucun des langages de programmation, il ne peut pas être compilé ou interprété par l'ordinateur. . C’est la meilleure façon d’exprimer un algorithme car il peut être compris même par un profane ayant des connaissances de niveau scolaire.

TechCodeview

Qu'est-ce que l'algorithme | Introduction aux algorithmes