Algorithmique

Algorithmique - Techniques fondamentales de programmation - Exemples en Python (nombreux exercices corrigés) - BTS, DUT informatique

Algorithmique : techniques fondamentales de programmation, exemples en Python : nombreux exercices corrigés

By: CREPIN, Ludivine. Editions ENI. ISBN: 978-2-409-04184-6, 978-2-409-04202-7.

https://eds-p-ebscohost-com.bnf.idm.oclc.org/eds/results?sid=0098f5b8-3586-4afe-bc01-42b775ba1cb5@redis&vid=0&sdb=edspub&tid=3000EP&bquery=algorithmique+techniques&bdata=JmRiPWVkc3B1YiZsYW5nPWZyJnR5cGU9NDQmc2VhcmNoTW9kZT1BbmQmc2l0ZT1lZHMtbGl2ZQ==

• L’algorithmique est la base de la programmation, mais aussi de l'intelligence et de l'analyse, de la compréhension, de la résolution de problème dans tous les domaines.

• L’algorithmique est la science qui s’occupe de tous les calculs.

• En arithmétique on distingue 4 opérations fondamentales : l’addition, la soustraction, la multiplication et la division; les autres opérations ne sont que des combinaisons de celles-ci.

• ⇒ Si un calcul vous parait difficile vous pouvez repérer chaque opérations simples qui se trouvent dans le calcul et voir comment chacune de ses opérations sont reliées entre elles : c’est comprendre la succession d’opération, c’est donc retrouver l’algorithme.

• L'algorithme, tout comme la programmation c'est de la création, il faut être créatif. Donc un algorithme ou un programme fait par une personne ne sera pas le même que fait par une autre personne.
  Alors, si chacun a le sien, s'il peut y avoir plusieurs solutions, laquelle est la bonne laquelle choisir ? Quelles sont les critères :
  
  • la rapidité d'exécution,
  • le fait que ça fonctionne dans plusieurs cas d’usage,
  • le fait que si ça tombe en panne le programme à la capacité de se remettre tout seul à fonctionner,
  • le fait qu'il ne prend pas de ressources mémoire
  • le fait qu'il soit lisible, c'est-à-dire que si une autre personne que vous doit faire des modifications, il faut pas que ce soit complètement incompréhensible.

Le principe de base

1. Identifier les informations à manipuler
   1. données initiales
   2. résultats attendus

2. Quel mode de calcul (ou comment) va permettre d’obtenir le résultat à partir d’un paramètre (données initiales)

3. Coût d’exécution du calcul
   1. ressources en mémoire
   2. ressources en temps : le nombre d’opérations de base effectuées par l’ordinateur pour calculer le résultat

Exemple d’algorithme : le sudoku

La résolution des sudokus peut se faire à l'aide d'algorithmes simples. Il faut disposer de deux tableaux : l'un pour les cases du sudoku, l'autre pour noter les chiffres qu'il est possible de placer dans une case donnée de la grille.

Exemple d’algorithme : le fil d’actualité d’un réseau social

L’algorithme de placement dans le fil d’actualité d’un réseau social détermine l’ordre d’affichage des publications. Il analyse les interactions des utilisateurs (likes, commentaires, partages) et donne priorité aux contenus des comptes avec lesquels les utilisateurs interagissent souvent. Il prend en compte le temps de publication pour privilégier les contenus récents. Il évalue également la diversité des types de contenus (photos, vidéos, articles) pour offrir une expérience équilibrée. Enfin, il peut intégrer des paramètres de personnalisation pour ajuster l’affichage en fonction des intérêts spécifiques de chaque utilisateur.

Créer un algorithme avant d’écrire un programme est une étape essentielle dans le processus de développement.

1. Clarification du problème

Un algorithme permet de bien comprendre le problème à résoudre. Il aide à :

• Décomposer le problème en étapes claires et logiques.

• Identifier les données d’entrée et les résultats attendus.

Exemple : Si on veut créer un programme pour calculer la moyenne de notes, l’algorithme aide à comprendre qu’il faut additionner les notes et diviser par le nombre total de notes.

2. Planification

Un algorithme sert de plan détaillé pour le programme. Comme un plan de construction pour un bâtiment, il aide à :

• Organiser les étapes du programme.

• Définir l’ordre des opérations.

Exemple : Planifier comment gérer les erreurs (par exemple, si une note est négative, elle doit être rejetée).

3. Simplification du développement

En créant un algorithme, il devient plus facile d’écrire le code. On sait déjà quelles étapes sont nécessaires, donc :

• Le temps de développement est réduit.

• On peut se concentrer sur la syntaxe du langage de programmation sans se perdre dans la logique.

4. Facilite la détection d’erreurs

L’algorithme aide à repérer les erreurs logiques avant même de passer à l’écriture du code. C’est plus facile de corriger un problème dans un algorithme que dans un programme déjà écrit.

Exemple : Si une boucle risque d’être infinie, on le verra plus facilement dans l’algorithme.

5. Communication et collaboration

Un algorithme est un langage compréhensible par tous, même sans connaître un langage de programmation spécifique. Il permet de :

• Communiquer la logique à d’autres développeurs, collègues ou enseignants.

• Partager le raisonnement et la structure du programme avec les membres d’une équipe.

6. Réutilisabilité et modularité

L’algorithme permet de définir des étapes qui peuvent être réutilisées dans d’autres parties du programme ou dans d’autres projets :

• On peut créer des algorithmes modulaires pour des tâches spécifiques (par exemple, un algorithme de tri).

7. Réduction des coûts

Corriger des erreurs logiques dans un algorithme coûte beaucoup moins cher (en temps et en argent) que de corriger ces mêmes erreurs une fois le programme codé et testé.

En résumé, créer un algorithme avant de coder permet de gagner du temps, d’éviter des erreurs coûteuses, de mieux structurer son projet et d’améliorer la collaboration. C’est une étape indispensable pour réussir un projet informatique, quel que soit le niveau de complexité.

Dans un algorithme il y a des données entrées dans le programme et des données qui sortent du programme. Les données ont permis au programme de faire des choses avec et il nous donne le résultat.

Variable

Type d’une variable

• int / entier - nombre entier : 0 / -5 / 222

• float / reel - nombre flottant : 0,2 / -3.14

• string / chaine- chaîne de caractère : “Bonjour et bienvenue”

• liste ou un tableau : [chat, chien, oiseau, poisson] ou [2, 4, 6, 8, 10] ou [1.3, -3.6, 4]

• bouléen / booleen : elle n’a que 2 valeurs possibles : true (vrai) ou false (faux)
  • par exemple 2 > 7 ⇒ false ou 10 > 7 ⇒ true

• date - date : (2024, 9, 24)

Donc on affecte une valeur à une variable

• pain_nom ← “baguette”

• pain_tarif ← 1.3

Les instructions ou opérations d’entrée-sortie

• LIRE()achat_nombre (saisir)

• ECRIRE() achat_total (afficher)

PROGRAMME Nom_du_programme
CONST //(ici on mettra toutes les variables constantes nécessaires au programme)
	pain_tarif <- 1 : ENTIER
VAR //(ici on mettra toutes les variables nécessaires au programme)
	pain_nom : CHAINE
DEBUT
	ECRIRE (”Saisissez le nom du pain que vous souhaitez acheter”)
	pain_nom <- LIRE()
	ECRIRE (”Vous avez choisi le pain “, pain_nom, ". Tarif : ", pain_nom x pain_tarif," euros")
FIN

PROGRAMME operations
VAR
	a <- 17 : ENTIER
	b <- 2 : ENTIER
	c <- 2.5 : REEL
	resultat : REEL
DEBUT
	resultat <- a + b
	ECRIRE (”L'addition de a et b vaut : ”, resultat)
	resultat <- a - b
	ECRIRE (”La soustraction de a et b vaut : ”, resultat)
	resultat <- a x c
	ECRIRE (”La multiplication de a et c vaut : ”, resultat)
	resultat <- a / c
	ECRIRE (”La division de a par c vaut : ”, resultat)
FIN

PROGRAMME comparaison
VAR
	a <- 17 : ENTIER
	b <- 2 : ENTIER
	resultat : REEL
DEBUT
	resultat <- a = b
	ECRIRE (”a est-il égal à b ? ”, resultat) // FAUX
	resultat <- a ? b // différence
	ECRIRE (”a est-il différent de b ? ”, resultat) // VRAI
	resultat <- a < b
	ECRIRE (”a est-il inférieur à b ? ”, resultat) // FAUX
	resultat <- a > b
	ECRIRE (”a est-il supérieur à b ? ”, resultat) // VRAI
	resultat <- a <= b
	ECRIRE (”a est-il inférieur ou égal à b ? ”, resultat) // FAUX
	resultat <- a >= b
	ECRIRE (”a est-il supérieur ou égal à b ? ”, resultat) // VRAI
FIN

PROGRAMME chaines
VAR
	sujet : CHAINE <- "Le chat"
	verbe : CHAINE <- "ronronne"
	resultat : CHAINE
DEBUT
	//Concaténation
	resultat <- CONCATENER(sujet, verbe)
	ECRIRE (resultat) // Le chatronronne
	resultat <- CONCATENER(sujet," ", verbe)
	ECRIRE (resultat) // Le chat ronronne

	//Extraction
	resultat <- EXTRAIRE(sujet, 5, 3)
	ECRIRE (resultat) //hat
	//Longueur
	resultat <- LONGUEUR(verbe)
	ECRIRE (resultat) //8

FIN

Hello World

D’après vous c’est quoi une condition ?

PROGRAMME Entier_positif 
VAR  
   un_nombre : ENTIER 
DEBUT 
   ECRIRE("Entrez un entier de votre choix") 
   un_nombre <- LIRE() 
   SI un_nombre > 0 
   ALORS 
      ECRIRE("Votre entier est positif")
	 SINON 
      ECRIRE("Votre entier est négatif") 
   FINSI 
FIN 

PROGRAMME Entier_positif 
VAR  
   un_nombre : ENTIER 
DEBUT 
   ECRIRE("Entrez un entier de votre choix") 
   un_nombre <- LIRE() 
   SI un_nombre > 0 
   ALORS 
      ECRIRE("Votre entier est positif")
	SINON 
      SI un_nombre < 0 
      ALORS 
         ECRIRE("Votre entier est négatif") 
      SINON 
         ECRIRE("Votre entier est nul") 
      FINSI 
   FINSI 
FIN 

PROGRAMME Mois_cas_parmi 
VAR 
   mois : ENTIER 
DEBUT 
   ECRIRE("Entrer un chiffre entre 1 et 6 compris") 
   mois <- LIRE() 
   CAS mois PARMI : 
      CAS : 1 
         ECRIRE("Janvier") 
      CAS : 2 
         ECRIRE("Février") 
      CAS : 3 
         ECRIRE("Mars") 
      CAS : 4 
         ECRIRE("Avril") 
      CAS : 5 
         ECRIRE("Mai") 
      PARDEFAUT 
         ECRIRE("Juin") 
   FINCASPARMI 
FIN 

PROGRAMME age_personne
VAR
   age : ENTIER
DEBUT
   ECRIRE("Entrez votre âge :")
   LIRE(age)
   SI age >= 18 ET age <= 30 ALORS
      ECRIRE("Vous avez entre 18 et 30 ans.")
   SINON
      ECRIRE("Vous n'avez pas entre 18 et 30 ans.")
   FINSI
FIN

PROGRAMME age_personne
VAR
   age : ENTIER
DEBUT
   ECRIRE("Entrez votre âge :")
   LIRE(age)
   SI age < 18 OU age > 65 ALORS
      ECRIRE("Vous êtes soit mineur, soit âgé de plus de 65 ans.")
   SINON
      ECRIRE("Vous avez entre 18 et 65 ans.")
   FINSI
FIN

D’après vous c’est quoi une boucle ?

Par exemple quand on a une liste de produit pour calculer le montant à payer on lit le prix de chaque produit et on l’ajoute à la somme.

PROGRAMME deplacement_personnage
VAR
   position, distance_max : ENTIER
DEBUT
   position <- 0        // La position de départ du personnage
   distance_max <- 10    // La position finale que le personnage doit atteindre
   
   ECRIRE("Le personnage commence à avancer...")
   
   TANTQUE position < distance_max FAIRE
      position <- position + 1
      ECRIRE("Le personnage est à la position :", position)
   FINTANTQUE

   ECRIRE("Le personnage a atteint la fin du parcours !")
FIN

PROGRAMME jeu_nombre_mystere
VAR
   nombre_mystere, nombre_saisie : ENTIER
DEBUT
   nombre_mystere <- 7  // Le nombre mystère est 7 (ou on peut utiliser une valeur aléatoire)
   
   ECRIRE("Bienvenue au jeu du nombre mystère !")
   
   REPETER
      ECRIRE("Devinez un nombre entre 1 et 10 :")
      nombre_saisie <- LIRE
      
      SI nombre_saisie < nombre_mystere ALORS
         ECRIRE("C'est plus grand ! Essayez encore.")
      SINON SI nombre_saisie > nombre_mystere ALORS.    // ici on répète une condition pour le cas où le nombre deviné serait égal au nombre mystère
         ECRIRE("C'est plus petit ! Essayez encore.")
      FINSI
   JUSQUA nombre_saisie = nombre_mystere

   ECRIRE("Félicitations ! Vous avez deviné le nombre mystère :", nombre_mystere)
FIN

PROGRAMME Table_multiplication 
   i : ENTIER 
   entree_utilisateur : ENTIER 
DEBUT 
   ECRIRE("Quelle table de multiplication voulez-vous afficher ? 
(entier entre 1 et 10)") 
   entree_utilisateur <- LIRE() 
   POUR i ALLANT de 1 à 10 AU PAS DE 1 
   FAIRE 
      ECRIRE(i," x ", entree_utilisateur," = ", entree_utilisateur x i) 
   FINPOUR 
FIN 

PROGRAMME Tables_multiplication 
   i, j : ENTIER  
DEBUT  
   POUR i ALLANT de 1 à 10 AU PAS DE 1 
   FAIRE 
      ECRIRE("Table de ", i)  
      POUR j ALLANT de 1 à 10 AU PAS DE 1 
      FAIRE 
         ECRIRE(i," x ",j," = ",j x i) 
      FINPOUR 
   FINPOUR 
FIN

La structure permet de regrouper et organiser les informations de manière plus efficace et propre.

Programme qui demande au visiteur ce qu’il veut acheter

PROGRAMME achat_boulangerie
STRUCTURE achat 
DEBUT 
   produit : CHAINE 
   quantite : ENTIER 
FINSTRUCTURE 
VAR 
   mon_achat : achat
DEBUT 
   ECRIRE("Entrez le nom du produit que vous souhaitez acheter") 
   mon_achat.nom <- LIRE() 
   ECRIRE("Entrez la quantité du produit") 
   mon_achat.quantite <- LIRE() 
   ECRIRE("vous avez choisi : ",mon_achat.nom, " avec une quantité de ", mon_achat.quantite) 
FIN 

On peut mettre un tableau dans une structure

STRUCTURE livre 
DEBUT 
   titre : CHAINE 
   editions : TABLEAU[1...5] : CHAINE 
FINSTRUCTURE 

Les fonctions sont le type de sous-programmes le plus utilisé aujourd’hui en informatique. Ce sont des procédures restreintes :

• Les paramètres sont uniquement en entrée.

• Une fonction renvoie toujours une et une seule valeur au programme qui l’appelle.

Interpréteurs :

• https://try.ocamlpro.com/

• https://onecompiler.com/ocaml