Licence Informatique 1ère Année - Introduction à la Programmation (1) PDF

Licence informatique 1ère année Introduction à la programmation (1) Qu est-ce qu un programme ? un langage ? un algorithme ? Méthodologie en informatique : du problème à la solution. [email protected]...

Licence informatique 1ère année Introduction à la programmation (1) Qu est-ce qu un programme ? un langage ? un algorithme ? Méthodologie en informatique : du problème à la solution. [email protected] Version du 13/09/23 ’ ’  2 Pourquoi vous êtes ici ? Les ordinateurs sont devenus nos « compagnons » au quotidien : – Communiquer / travailler / s organiser / s orienter / s amuser / etc. / etc. – Les utilisateurs ne connaissent que la fonctionnalité qui leur est apportée – Les programmeurs quant à eux : - Savent comment fonctionnent les ordinateurs - Apprennent des langages informatiques et des méthodes - Maîtrisent des outils qui les aident à construire des programmes 10101 1101100110 011101110 ’ ’ ’  3 Qu est-ce qu un programme ? Exemple de programme pour les humains : 1. Left hand out and up 2. Right hand out and up 3. Flip Left hand 4. Flip Right hand 5. Left hand to right shoulder 6. Right hand to left shoulder 7. Left hand to back of head 8. Right hand to back of head 9. Left hand to right hip 10. Right hand to left hip 11. Left hand on left bottom 12. Right hand on right bottom 13. Wiggle 14. Wiggle 15. Jump ’ ’  4 Qu est-ce qu un programme ? Soit le texte ci-dessous : – Combien y a t-il de mots au total et de mots différents ? – Quel mot apparaît le plus souvent et combien de fois ? le clown couru après la voiture et la voiture fonça sur la tente et la tente tomba sur le clown et la voiture Nom du fichier: clown.txt Il y a 23 mots Il y a 11 mots différents Le mot la apparaît 5 fois ’ ’  5 Qu est-ce qu un programme ? Quel mot apparaît le plus souvent (et combien de fois) dans « Notre Dame de Paris » de Victor Hugo ? Nom du fichier: hugo.txt Il y a 176194 mots Il y a 26438 mots différents Le mot de apparaît 8081 fois ’ ’  6 Qu est-ce qu un programme ? Qu est-ce qu un programme ? – C est une séquence d instructions mémorisées dans l ordinateur. – C est un petit morceau de notre intelligence dans l ordinateur. - Nous comprenons quelque chose puis nous le traduisons en langage informatique pour le donner à d autres pour leur faire pro ter de notre expertise. – Cela peut aussi être considéré comme un objet créatif, voire artistique : ’ ’ ’ ’ ’ ’ ’ ’ fi ’ ’  7 Du problème à la solution Données Méthodologie professionnelle en informatique : Problème Méthode Algo Prog Analyse Conception Codage Exécution 1. Analyse : Etudier le problème ➙ Méthode Résultat 2. Conception : Formaliser la solution ➙ Algorithme 3. Codage : Traduire cet algorithme avec un langage ➙ Programme 4. Tests : Exécuter le programme dans différentes situations ➙ Validation  8 Analyse du problème Analyse Conception Codage Exécution Exemple de problème (de maths) : – Soit la fraction 120 quelle est la fraction irréductible qui lui est égale ? 45 Analyse du problème (en termes mathématiques) : – Une fraction est irréductible si son numérateur et son dénominateur sont premiers entre eux, c est-à-dire si leur PGCD est égale à 1. – Corollaire : pour rendre une fraction irréductible, une méthode est de diviser son numérateur et son dénominateur par leur PGCD. – Le problème est donc ramené au calcul du PGCD de deux nombres… ’  9 Conception d un algorithme Analyse Conception Codage Exécution Qu est-ce qu un algorithme ? En informatique, un algorithme est une méthode / procédure de calcul bien dé nie : Qui prend en entrée une valeur ou un ensemble de valeurs Qui produit en sortie une valeur ou un ensemble de valeurs Qui peut produire des effets de bord (action sur un moteur par exemple) Un algorithme doit toujours produire un résultat censé résoudre un problème : Si l algorithme est correct, le résultat résout le problème Si l algorithme est incorrect, le résultat est faux et inutile – Le mot algorithme vient du nom du mathématicien Perse Al-Khawarizmi (780-850) ’ ’ ’ ’ ’ fi  10 Conception d un algorithme Analyse Conception Codage Exécution Un algorithme doit être déterministe : – Son exécution ne doit dépendre que des entrées (sauf si fonction aléatoire) – Il doit toujours se terminer en un temps ni (solution calculable au sens de Turing) On peut concevoir plusieurs algorithmes pour un même problème : – Des bons, des astucieux, des rapides, des lents, des mauvais, des archi-nuls ! – Exemple typique du tri dans un tableau d entiers : 45 12 6 23 71 9 37 10 3 3 6 9 10 12 23 37 45 71 ’ fi ’  11 Conception d un algorithme Analyse Conception Codage Exécution 15 algorithmes de tri numérique très différents pour un même résultat : ’  12 Conception d un algorithme Analyse Conception Codage Exécution Algorithme dû à Euclide (285 av. JC) pour calculer le PGCD de 2 nombres : – Si un des nombres est nul, l autre est le PGCD. – Sinon il faut soustraire le plus petit du plus grand et laisser le plus petit inchangé. – Puis recommencer ainsi de suite avec la nouvelle paire. Véri cation de l algorithme « à la main » sur notre exemple : (120,45)→(75,45)→(30,45)→(30,15)→(15,15)→(0,15) 120 / 15 = 8 120 8 donc = 45 / 15 = 3 45 3 fi ’ ’ ’  13 Ecriture d un programme Analyse Conception Codage Exécution Un programme est un texte écrit avec un langage informatique : – Qui respecte une syntaxe = vocabulaire + grammaire + conventions d écriture – Qui possède une sémantique = signi cation du texte = quel sens le texte véhicule ? Tout langage informatique doit permettre les actions suivantes : – Stocker et retrouver des données Un langage a qui il manquerait une de ces – Comparer des données entre elles possibilités ne serait pas « Turing-Complet » – Effectuer des traitements c.a.d. ne pourrait pas traiter tous les problèmes – Répéter un même traitement calculables au sens de Turing ’ fi ’  14 Ecriture d un programme Analyse Conception Codage Exécution Exemple de programme en langage Python qui implémente l algorithme : ################## ####################### # Calcul du PGCD # # Programme principal # ################## ####################### def calcPgcd (a,b): n1 = int(input("Numérateur: ")) while a > 0 and b > 0: d1 = int(input("Dénominateur: ")) if a > b: a = a - b pgcd = calcPgcd(n1,d1) else: n2 = n1 / pgcd b = b - a d2 = d1 / pgcd if a == 0: return b print("%d/%d = %d/%d" % (n1,d1,n2,d2)) else: return a ’ ’  15 Exécution du programme Analyse Conception Codage Exécution Exécuter les instructions de façon séquentielle à partir de données Le but est évidemment d exécuter le programme sur un ordinateur Mais on peut aussi exécuter le programme « à la main » – On réalise ainsi une simulation de l exécution du programme sans ordinateur – Véri er le programme à partir de plusieurs jeux de données = batterie de tests – Peut s avérer utile de réaliser des tests unitaires pour chaque partie d un programme – La notion de qualité du logiciel devient importante, comme dans toute production fi ’ ’ ’ ’  16 Exécution du programme Analyse Conception Codage Exécution Exécution du programme « à la main » avec 120 et 45 : ################## a b a>0 b>0 a>b a=0 # Calcul du PGCD # ################## 120 45 oui oui oui def calcPgcd (a,b): 75 45 oui oui oui while a > 0 and b > 0: 30 45 oui oui non if a > b: a = a - b 30 15 oui oui oui else: b = b - a 15 15 oui oui non if a == 0: return b 15 0 oui non non else: return a  17 Exécution du programme Analyse Conception Codage Exécution Exécution du programme sur un ordinateur avec 120 et 45 : ####################### # Programme principal # ####################### n1 = int(input("Numérateur: ")) Numérateur: 120 d1 = int(input("Dénominateur: ")) Dénominateur: 45 pgcd = calcPgcd(n1,d1) 120/45 = 8/3 n2 = n1 / pgcd d2 = d1 / pgcd print("%d/%d = %d/%d" % (n1,d1,n2,d2))  18 Peut-on tout calculer ? Que signi e cette question ? – Toute multiplication de nombres entiers se ramène à des additions successives – Toute division de nombres entiers se ramène à des soustractions successives – Toute addition ou soustraction se ramène à des manipulations de cailloux – Toute opération peut-elle se réduire à des manipulations de cailloux ? Problème de la calculabilité : Quel est l ensemble des problèmes ou des calculs exprimables en termes mathématiques, pour lesquelles il existe une succession nie de manipulations de symboles déterminant sans ambiguïté le résultat du problème ou du calcul ? – Alan Turing a établi en 1937 une classe de problèmes répondant à l intuition de ce que l on se fait des fonctions calculables et il démontre que leurs solutions peuvent être toutes calculées de façon automatique ! fi ’ fi ’ ’  19 La machine de Turing Pour démontrer sa thèse, Turing invente une « machine » composée de : – Un ensemble ni d états que l on peut nommer comme on le souhaite – Un ensemble ni de symboles ou idéogrammes plus le symbole « vide » – Un ruban in niment long qui peut se déplacer vers la gauche ou vers la droite – Une tête de lecture-écriture qui peut lire ou écrire un symbole sur le ruban – Un ensemble de règles qui dé ni un « programme » pour effectuer un calcul (état actuel ; symbole lu) ➙ (nouvel état ; symbole à écrire ; déplacement du ruban) Exemple d’une machine à 6 états (0, 1, 2, 3, 4, 5) à 4 symboles (0, 1, +, _ ) et à 12 règles : (0 ; 0) ➙ (0 ; 1 ; gauche) (2 ; _ ) ➙ (0 ; _ ; gauche) (0 ; 1) ➙ (1 ; 0 ; gauche) (3 ; 1) ➙ (3 ; 0 ; gauche) C es 12 règles (0 ; +) ➙ (4 ; _ ; droite) (3 ; 0) ➙ (2 ; 1 ; droite) co n st it ue n t le (1 ; +) ➙ (3 ; + ; gauche) (3 ; _ ) ➙ (2 ; 1 ; droite) prog ramme de la (1 ; x) ➙ (1 ; x ; gauche) (4 ; 1) ➙ (4 ; _ ; droite) m ach ine (2 ; x) ➙ (2 ; x ; droite) (4 ; _ ) ➙ (5 ; _ ; droite) fi fi fi ’ fi ’  20 Exemple de machine de Turing Ses « possibilités » sont équivalentes à celles de nos ordinateurs !!!  21 Et les ordinateurs d aujourd hui ? Une architecture basée sur un microprocesseur et de la mémoire : – Le microprocesseur accède à la mémoire et effectue des calculs – Les calculs ou opérations sont décrits à l aide de programmes – Le microprocesseur sait donc également exécuter des programmes – Les programmes sont décrits à l aide de langages de programmation – Les langages de programmation doivent être Turing-complets Les langages de programmation usuels sont Turing-complets car ils possèdent toutes les caractéristiques nécessaires à la simulation d une machine de Turing universelle : écrire, lire, comparer, compter, etc. La puissance d expression des langages (et donc des ordinateurs) d aujourd hui ne dépasse pas celle d une machine de Turing ! En revanche, la puissance de calcul (nombre d opérations par seconde) des microprocesseurs ainsi que la mémoire ne cessent d augmenter. ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’  22 Qu est-ce qu un langage ? Exemple de grammaire formelle générative : vocabulaire règles de grammaire sémantique le = = la = | les = les = = chat = | chats = souris = = souris = | mange = = = le chat mange la souris phrase grammaticalement correcte ’ ’  23 Qu est-ce qu un langage ? En informatique, un langage de programmation est une notation conventionnelle destinée à produire des programmes informatiques qui implémentent des algorithmes. D'une manière similaire à une langue naturelle, un langage de programmation est composé d'un alphabet, d'un vocabulaire, de règles de grammaire et de signi cations. Vocabulaire et grammaire (extraits) du langage C : case = const | | default | else | float | for if = : | case : int | default : return switch = {}? ; void while = if ( )... | if ( ) else | switch ( ) ’ ’ fi  24 Qu est-ce qu un langage ? Il y a plusieurs familles de langages de programmation (paradigmes) : – Programmation impérative (Assembleur, Fortran, Pascal, C, etc.) - Le programme est constitué d une suite d instructions - Adapté aux architectures des ordinateurs (modèle de Von Neumann) – Programmation fonctionnelle (Lisp, Scheme, Caml, Haskell, etc.) - Le programme est constitué d un ensemble de fonctions - Adapté aux calculs mathématiques ou formels = Lambda Calcul – Programmation orientée objet (Smalltalk, Ada, Java, Ruby, etc.) - Le programme est constitué d un ensemble d objets qui interagissent - Adapté au Génie Logiciel et aux gros projets industriels – Programmation inférentielle (Prolog, Datalog, CLIPS, Jess, etc.) - Le programme est constitué d un ensemble de règles de déduction - Adapté aux problèmes combinatoires et à l Intelligence Arti cielle ’ ’ ’ ’ ’ ’ ’ ’ ’ fi  25 Quelques langages Exemple de langage fonctionnel (Lisp) : – Une fonction qui calcule la factorielle d un nombre n : - Si n > 1 alors factorielle(n) = n * factorielle (n - 1) - Sinon factorielle(n) = 1 – Une fonction qui renverse une liste de mots : - Pour renverser une liste non vide, il suf t d accoler (append … ) : – La liste privée de son premier élément puis renversée : (renverser (cdr liste)) – La liste singleton contenant le premier élément : (list (car liste)) (defun factorielle (n) (if (> n 1) (* n (factorielle (- n 1))) > (factorielle 10) 1)) 3628800 (defun inverser (liste) > (inverser '(LE LISP EST UN LANGAGE)) (if liste (LANGAGE UN EST LISP LE) (append (inverser (cdr liste)) (list (car liste))))) fi ’ ’  26 Quelques langages Exemple de langage orienté objet (Java) : – On dé nit ce qu est un joueur (classe Joueur) qui sait juste envoyer une balle ; – On crée deux objets différents o1 et o2 à partir de la même classe Joueur ; – On envoie à o1 le message envoyerBalle(o2) ; – On laisse o1 réagir à ce message… o2.envoyerBalle(o1) public class Joueur { o1 o2 private String nom; nom = "Pierre" nom = "Paul" public Joueur(String nom) { this.nom = nom; } o1.envoyerBalle(o2) public void envoyerBalle(Joueur unAutreJoueur) { System.out.println("La balle est chez " + nom); Thread.sleep(500); unAutreJoueur.envoyerBalle(this); La balle est chez Pierre } La balle est chez Paul La balle est chez Pierre public static void main (String[] args) { La balle est chez Paul Joueur o1 = new Joueur(« Pierre"); La balle est chez Pierre Joueur o2 = new Joueur(« Paul »); La balle est chez Paul o1.envoyerBalle(o2); }... } fi ’  27 Quelques langages Exemple de langage inférentiel (Prolog) : – On fournit des informations, des règles de déduction et un but à atteindre : a-tue(X,Y,J) :- peut-desirer-tuer(X,Y), possede-arme(X), alibi-pour-le-donne-par(luc, mardi, bernard). pas-alibi-pour(X,J). alibi-pour-le-donne-par(paul, mardi, bernard). alibi-pour-le-donne-par(louis, mardi, luc). pas-alibi-pour(X,J) :- not(alibi-pour-le-donne-par(X,J,_)). alibi-pour-le-donne-par(alain, jeudi, luc). pas-alibi-pour(X,J) :- alibi-pour-le-donne-par(X,J,Y), personnage-douteux(Y). personnage-douteux(alain). peut-desirer-tuer(X,Y) :- a-interet-a-tuer(X,Y). desire-se-venger-de(paul, jean). peut-desirer-tuer(X,Y) :- desire-se-venger-de(X,Y). desire-se-venger-de(luc, jean). a-interet-a-tuer(X,Y) :- est-heritier-de(X,Y). est-heritier-de(bernard, jean). a-interet-a-tuer(X,Y) :- doit-de-largent-a(X,Y). est-heritier-de(jean, louis). a-interet-a-tuer(X,Y) :- a-vu-commettre-un-crime(Y,X). doit-de-largent-a(louis, jean). run :- a-tue(X,jean,mardi), doit-de-largent-a(luc, jean). write('Le coupable est '), write(X). a-vu-commettre-un-crime(jean, alain). possede-arme(luc). possede-arme(louis). possede-arme(alain). > run. Le coupable est Alain  28 Les ordinateurs comprennent-ils tout ces langages ? NON ! ils ne comprennent aucun de ces langages… Mais que comprennent-ils alors ? 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 11 22 10 51 00 00 00 00 11 40 64 79 6C 64 5F 73 74 75 62 5F 62 69 6E 64 65 72 00 51 72 00 90 00 72 10 11 40 5F 70 72 69 6E 74 66 00 90 00 00 00 Ces codes correspondent à des actions élémentaires du microprocesseur : – Aller chercher une valeur en mémoire, – Effectuer une addition entre deux valeurs, C f. mo du le Arch i te c t u re d – Véri er si le résultat est égal à zéro, es – etc. O rdi n ate u rs Il faut donc procéder à des traductions, en simultané ou en amont… fi  29 Langage compilé vs. interprété Interprétation d un script écrit avec un langage interprété : script interpréteur 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 11 22 10 51 6C 00 64 00 5F 00 73 00 74 11 75 40 62 64 5F 79 62 résultat 69 6E 64 65 72 00 51 72 00 90 00 72 10 11 40 5F 70 72 69 6E 74 66 00 90 00 00 00 écrit exécute – Le programmeur écrit le script avec un « langage interprété » – La processeur exécute l interpréteur qui exécute le script à chaque exécution. – L interpréteur interprète le script avec les données du programme. ’ ’ ’  30 Langage compilé vs. interprété Compilation d un code source écrit avec un langage compilé : code source compilateur code exécutable 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 11 22 10 00 00 00 00 00 00 11 22 10 51 6C 00 64 00 5F 00 73 00 74 11 75 40 62 64 5F 79 62 51 6C 00 64 00 5F 00 73 00 74 11 75 40 62 64 5F 79 62 résultat 69 6E 64 65 72 00 51 72 00 69 6E 64 65 72 00 51 72 00 90 00 72 10 11 40 5F 70 72 90 00 72 10 11 40 5F 70 72 69 6E 74 66 00 90 00 00 00 69 6E 74 66 00 90 00 00 00 écrit exécute exécute – Le programmeur écrit le code source avec un « langage compilé » – La processeur exécute le compilateur (exécutable fourni avec le système). – Le code source est la donnée du compilateur. – Le code exécutable est le produit du compilateur. ’  31 Mêêêêêêêh ! Un bidouilleur va se contenter d un programme qui marche… Un informaticien professionnel se soucie également : – De l ef cacité de son code (complexité algorithmique) – De la lisibilité de son code (mise en forme, commentaires) – Du respect de normes et des conventions de codage – D une forme d écologie de la programmation : - Ne pas répéter inutilement un même calcul - Ne pas mémoriser inutilement des données - 80% du temps CPU porte sur 20% du code Par conséquent, lorsqu on vous fait des remarques sur votre code, ne répondez JAMAIS : « oui mais ça marche » ! ! ! Le fait que votre programme « marche » est une condition nécessaire mais non suf sante ! ! ! ’ ’ fi ’ ’ ’ fi  Fin du cours n°1 Nom du cours UMTICE : L1 INFO - Introduc on à la Programma on Clé d’enregistrement : ROBOT2024 ti ti