Séance N1 Algorithmique & Programmation PDF

Algorithmique & Programmation Pr. JIBOUNI AYOUB [email protected] Année universitaire 2024-2025  Algorithmique & Programmation Objectifs 1. Approfondir les compétences en algorithmique 2. Définir la structure d’un programme et élaborer un u...

Algorithmique & Programmation Pr. JIBOUNI AYOUB [email protected] Année universitaire 2024-2025  Algorithmique & Programmation Objectifs 1. Approfondir les compétences en algorithmique 2. Définir la structure d’un programme et élaborer un utilitaire Compétences visées 1. Concevoir et mettre en œuvre un algorithme 2. Mettre en œuvre un traitement numérique de données expérimentales. 2 PLAN Définitions et concepts de base d’algorithmique Langage algorithmique Langage de programmation 3  Définitions et concepts Définition de l’informatique INFORMATIQUE ? INFORMATION AUTOMATIQUE Science de l’information Art d’entraîner automatiquement des actions Traitement automatique de l’information ORDINATEUR 4  Définitions et concepts Définition du traitement Traitement: l’ensemble des opérations effectuées sur les données afin de modifier leurs états. 2x – 3y = 1  Exemple : (*-2) -2x -12y = -4 2x-3y-2x-12y=1-4 2x – 3y = 1 -15y=-3 x + 6y = 2 y = 3/15 = 1/5 Traitement 5  Définitions et concepts Définition d’un ordinateur Machine qui permet de traiter de l’information : Mémoriser des informations, un réservoir des données est obligatoire (unité de mémorisation). D’effectuer des traitements (calcul), alors elles doivent posséder une unité de calcul. D’accepter des données, et afficher des résultats (unités d’entrées / sorties) Données à l’état Résultats brut ENTREE TRAITEMENT SORTIE Par ordinateur 6  Définitions et concepts Système informatique Un système informatique est une combinaison indépendante de matériels (HARDWARE) et programmes (SOFTWARE). Système informatique = Hardware + Software 7  Définitions et concepts Système informatique Les éléments d’un système informatique sont : Applications Langages (Python, VBA, Java,C/C++, Fortran,etc.) Système d’exploitation (DOS,Windows, Unix, etc.) Matériel Unité centrale (Processeur ou CPU, Mémoire centrale, Disque dur, Cartes spécialisées Périphériques (écran, clavier, souris, Modem, imprimante,…) 8  Définitions et concepts Langages informatiques  Un langage informatique est un outil permettant de donner des ordres (instructions) à la machine  A chaque instruction correspond une action du processeur  Intérêt : écrire des programmes (suite consécutive d’instructions) destinés à effectuer une tache donnée  Exemple: un programme de gestion de comptes bancaires  Contrainte : être compréhensible par la machine 9  Définitions et concepts Langage machine  Les appareils informatisés, dont les ordinateurs, ne comprennent que les 0 et l. C'est ce qu'on appelle le binaire ou bien langage machine.  Pourtant, les ordinateurs font de nombreuses choses. Cependant, pour qu'ils fassent toutes ses choses, il faut des personnes pour leur dire ce qu’ils doivent faire : les programmeurs, alias les développeurs.  Pour dire à un ordinateur ce qu'il doit faire, il faut lui parler. Et il faut le faire dans un langage qu'il comprenne. Cependant, parler avec des 0 et des 1 s'avère difficile. 10  Définitions et concepts Langages de programmation  C’est pour cela qu'on a inventé des langages de programmation, plus proches du langage humain, lesquels permettent de dire plus facilement à un ordinateur ce qu'il doit faire. Ces langages sont appelés langages de programmation.  Exemple de langages de programmation :  C, C++, Java, Python, Visual Basic, PHP…Etc.  C'est le concept de programme qui fait le lien entre l’algorithme conçu par l’humain et le langage machine. 11  Définitions et concepts Langages de programmation  Pour que l'ordinateur fasse quelque chose de ce qu'on lui dit avec le langage de programmation choisit : il faut que ce langage soit traduit en un ensemble de 0 et de 1 compréhensible par un ordinateur, c'est-à-dire traduit en langage machine.  Ce travail est réalisé par un compilateur ou interpréteur. Code source en Interpréteur Résultat langage évolué ou Code Compilateur Exécuteur Résultat objet 12  Définitions et concepts Langages de programmation Schéma de résolution informatique d’un problème Problème Analyse Modèle a résoudre Programme Traduction Algorithme 13  Définitions et concepts Algorithmique Pourquoi un « Algorithme » ?  Objectif : demander à la machine qu’elle effectue un travail à notre place. Bien que nous ? & Mieux que nous?  Problème : expliquer à la machine comment elle doit s'y prendre. Mais... comment le lui dire ? & Comment le lui apprendre ?  Besoins:  savoir expliquer et formaliser son problème  concevoir et écrire des algorithmes (séquence d’instructions qui décrit comment résoudre un problème particulier). 14  Définitions et concepts Algorithmique Définition d’un algorithme  Le mot algorithme (‫ )خوارزمية‬vient du nom de son auteur qui est le mathématicien Al-Khwârizmî (en arabe : ‫)الخوارزمي‬  L’algorithmique est un terme d’origine arabe, comme l’algèbre.  Un algorithme est l'énoncé dans un langage descriptif bien défini d'une suite d'opérations permettant de répondre aux problèmes, Il s'agit de fournir la solution à un problème. On parle généralement d'analyse pour décrire le processus par lequel le problème est formalisé. Un algorithme doit donc être : Lisible, de haute niveau, précis, concis, et structuré. 15  Définitions et concepts Algorithmique Représentation d’un algorithme  Exemples d'algorithmes mis en œuvre «naturellement» tous les jours : Recette de cuisine Tri de nombres par ordre croissant  Historiquement, deux façons pour représenter un algorithme :  L’organigramme: représentation graphique avec des symboles (carrés, losanges, etc.)  offre une vue d’ensemble de l’algorithme  représentation quasiment abandonnée aujourd’hui  Le pseudo-code: représentation textuelle avec une série de conventions ressemblant à un langage de programmation  plus pratique pour écrire un algorithme  représentation largement utilisée 16  Définitions et concepts Algorithmique Exemple: Organigramme correspondant à la résolution d’un problème (validation d'un semestre) Début : Calcul du semestre Moyennes oui M1 >= 8 et M2 >= 8 Moyenne oui générale>= Semestre Non 12 validé Semestre non Non validé Non Compensation oui par le semestre précèdent Compensation Semestre impossible validé par Fin compensation 17  Définitions et concepts Algorithmique Structure d’un algorithme (1) Algorithme Nom Algorithme (2) Variables {Déclarations: réservation d'espace mémoire} (3) début {Préparation du traitement} {Calculs} {Présentation des résultats} Fin 18  Définitions et concepts Algorithmique Structure d’un algorithme Exemple: écrire un algorithme qui affiche « BONJOUR » ? Algorithme Affichage Variables Début ecrire( ‘ BONJOUR ‘ ) ; Fin 19 Partie I - Notions et instructions de base -Algorithmique- 20  Algorithmique Définition Pourquoi apprendre l’algorithmique pour apprendre à programmer ? En quoi a-t- on besoin d’un langage spécial, distinct des langages de programmation compréhensibles par les ordinateurs ?  Parce que l’algorithmique exprime les instructions résolvant un problème donné indépendamment des particularités de tel ou tel langage.  Apprendre l’algorithmique, c’est apprendre à manier la structure logique d’un programme informatique. Cette dimension est présente quelle que soit le langage de programmation, plus précisément : Apprendre l’algorithmique de manière séparée, c’est donc sérier les difficultés pour mieux les vaincre. 21  Algorithmique Notion de variable  Dans les langages de programmation une variable sert à stocker la valeur d’une donnée  Une variable désigne en fait un emplacement mémoire dont le contenu peut changer au cours d’un programme (d’où le nom variable)  Règle : Les variables doivent être déclarées avant d’être utilisées, elle doivent être caractérisées par :  un nom (Identificateur)  un type (entier, réel, caractère, chaîne de caractères, …) 22  Algorithmique Choix des identificateurs  Le choix des noms de variables est soumis à quelques règles qui varient selon le langage, mais en général: – Un nom doit commencer par une lettre alphabétique exemple valide: A1 exemple invalide: 1A – Doit être constitué uniquement de lettres, de chiffres et du soulignement (éviter les caractères de ponctuation et les espaces) valides: ESTD24, ESTD_24 invalides: ESTD 24, ESTD-24, ESTD;24 – Doit être différent des mots réservés du langage (par exemple : int, float, else, switch, case, default, for, main, return, …)  La longueur du nom doit être inférieure à la taille maximale spécifiée par le langage utilisé 23  Algorithmique Choix des identificateurs  Conseil: pour la lisibilité du code choisir des noms significatifs qui décrivent les données manipulées exemples: TotalVentes2004, Prix_TTC, Prix_HT  Remarque : en pseudo-code algorithmique, on va respecter les règles citées, même si on est libre dans la syntaxe 24  Algorithmique Types de variables Type Description Il s'agit d'un type qui a uniquement deux valeurs possibles : 0/1, vrai/ Booléen faux, oui/non ou, généralement, en anglais true ou false. De manière simple, ce sont tous les nombres, positifs ou négatifs, sans Entier chiffre après la virgule. Ce sont tous les nombres, positifs ou négatifs, avec ou sans chiffres Réel après la virgule. Le type "chaîne de caractères" ou plus simplement "chaîne", est une Chaîne succession de caractères. Autres Date, heure, tableau, tableau associatif…etc 25  Algorithmique Déclaration des variables  Rappel: toute variable utilisée dans un programme doit avoir fait l’objet d’une déclaration préalable  En pseudo-code, on va adopter la forme suivante pour la déclaration de variables Variables liste d'identificateurs : type  Exemple: Variables i, j,k : entier prix, salaire : réel is_running: booléen nom, prenom: chaîne de caractères  Remarque: pour le type numérique on va se limiter aux entiers et réels sans considérer les sous types 26  Algorithmique Instruction d’affectation  L’affectation consiste à attribuer une valeur à une variable (ça consiste en fait à remplir où à modifier le contenu d'une zone mémoire)  En pseudo-code, l'affectation se note avec le signe ← Var← e : attribue la valeur de e à la variable Var – e peut être une valeur, une autre variable ou une expression – Var et e doivent être de même type ou de types compatibles – L’affectation ne modifie que ce qui est à gauche de la flèche Ex valides: – i ←1 j ←i k ←i+j – x ←10.3 is_running ←FAUX module← "Algo" – ch2 ←ch1 x ←4 x ←j j ←x Ex non valides: i ←10.3 is_running ← " Algo" 27  Algorithmique Instruction d’affectation Exemple1 : déclaration et affectation de variable  Ecrire l’algorithme permettant de – Déclarer une variable a de type entier – Affecter une valeur 12 à cette variable – Modifier la valeur de a à 7 NB: un algorithme s'exécute de manière séquentielle, c'est-à-dire ligne après ligne (instruction après instruction). Si une variable est modifiée, sa modification prend effet dès la ligne suivante ! 28  Algorithmique Instruction d’affectation Exemple1 : Solution Solution Explication Algorithme Exemple 1 1. On déclare une variable a de Variables type entier. a : entier 2. On affecte la valeur 12 à la Début variable a. a ← 12 3. On modifie la valeur de la a←7 variable a. Fin 29  Algorithmique Instruction d’affectation Exemple2 : type chaines de caractères  Ecrire l’algorithme permettant de: – Déclarer deux variables a et b de type chaine de caractère – Affecter la valeur "hello" à la variable a – Affecter la valeur "world" à la variable b 30  Algorithmique Instruction d’affectation Exemple2 : Solution Algorithme Exemple 2 Variables a,b : chaine Début a ← "hello" b ← "world" Fin Exemple 3 :Ecrire un algorithme permettant d’échanger les valeurs de deux variables A et B de type entier 31