Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Université PARIS-SUD - Licence MPI - S1 1 Introduction à l’informatique Introdu

Université PARIS-SUD - Licence MPI - S1 1 Introduction à l’informatique Introduction à l’informatique Chapitre 1: Algorithmes et Programmes Université PARIS-SUD - Licence MPI - S1 2 Algorithmes et Programmes Algorithmes et Programmes Vie d'un programme Algorithme Programmation : le langage Exécution et test des programmes Université PARIS-SUD - Licence MPI - S1 3 Cycle de vie d'un programme (d'un logiciel) Cycle de vie d'un programme (d'un logiciel)  Conception - Modélisation  Analyse du problème  Solution algorithmique langage d'algorithmes  Programmation  Programme langage de « haut niveau »  Compilation – Interprétation  Exécution sur machine langage machine de « bas niveau » assembleur et code machine  Mise au point  Vérification par test pour corriger  Evaluation du coût pour optimiser Université PARIS-SUD - Licence MPI - S1 4 Cycle de vie d'un programme (d'un logiciel) Cycle de vie d'un programme (d'un logiciel) Conception - Modélisation Langage de description d'algorithme simplicité , précision indépendant de la programmation et de la machine Exemple : diagramme , pseudo C, ...  Programmation  Exécution Université PARIS-SUD - Licence MPI - S1 5 Conception - Modélisation  Programmation  Langage de programmation (langages « évolués ») syntaxe contraignante, différents styles d'abstraction indépendant de la machine  Types de langages impératifs : Fortran, Cobol, Pascal, C fonctionnels : Lisp, ML, Caml logiques : Prolog objets : C++, Java  Exécution Cycle de vie d un programme (d un Cycle de vie d un programme (d un logiciel) logiciel) Université PARIS-SUD - Licence MPI - S1 6 Conception - Modélisation Programmation Exécution Langage assembleur dépendant de la machine, du processeur Exemples : Assembleur pour PC (IA-32), PowerPC, MIPS, SPARC, etc. Cycle de vie d un programme (d un Cycle de vie d un programme (d un logiciel) logiciel) Université PARIS-SUD - Licence MPI - S1 7 Conception - Modélisation Analyse du problème Un nombre N est pair si le reste de la division de N par 2 est nul Solution algorithmique 1. calculer le reste R de la division de N par 2 2. si R est égal à 0 alors N est pair 3. sinon N n'est pas pair L'entier N est-il pair ? L'entier N est-il pair ? Université PARIS-SUD - Licence MPI - S1 8 Programmation Programme C main () {// début du programme principal int nombreateste ; printf("Donner un nombre :") ; scanf("%d", & nombreateste) ; if ((nombreateste % 2) == 0) printf("%d est pair \n", nombreateste); else printf("%d n'est pas pair \n", nombreateste); } // fin du programme principal L'entier N est-il pair ? L'entier N est-il pair ? Université PARIS-SUD - Licence MPI - S1 9 L'entier N est-il pair ? L'entier N est-il pair ? Compilation - Codage 9de3bfc0 21000000 a0142000 d2040000 90000000 80a24000 02800009 01000000 …. 808a6001 02800003 01000000 90022001 load N modi 2 jzer P ... halt Assembleur Code machine Université PARIS-SUD - Licence MPI - S1 10 () Recette, règle, mécanisme, procédé, procédure, méthode, (=) Description d'une procédure de calcul par une suite d'étapes de calcul, d'actions (plus ou moins) élémentaires. Un algorithme n'est pas forcément destiné à décrire la solution d'un problème pour la programmation et l'informatique ...  Un algorithme en cuisine s'appelle une recette  Un algorithme en musique s'appelle une partition  Un algorithme en tissage s'appelle un point Algorithme Algorithme Université PARIS-SUD - Licence MPI - S1 11 Peu de mécanismes de base Peu de mécanismes de base Faire A ; Faire B ; Faire C … en séquence a←10 affectation + - * / operations de math {Faire A ; Faire B };{Faire C ; Faire D} groupés Si (…) Alors {…} Sinon Tant que (…) Faire {…} Pour i allant de 0 jusqu’à 100 faire {…i…} f(a, b, c) Fonctions (appel et déclaration) Comment est-ce possible que l’informatique tienne en si peu de mécanismes de base ? Université PARIS-SUD - Licence MPI - S1 12 Variables : codage des données Variables : codage des données Soit n1, n2, n3,…n17 les 17 notes d’un étudiant Soit r le nombre de redoublements (0 si aucun) Soit sma une variable qui vaut vrai si l’étudiant suit des cours d’anglais facultatifs et faux sinon  (n1+2*n2) / 3 sa moyenne de module m1 … Soit lps une liste de poursuite d’étude possible Pour chaque poursuite d’étude considérons les conditions d’admission (m1>12) et le nb max… Soit d le désir de l’étudiant (d=1 il veut faire des math, d=2 de la physique et d=3 de l’info.) Université PARIS-SUD - Licence MPI - S1 13 Infor…Matique Infor…Matique Infor comme information : il y a des données stockées numériquement auxquelles l’ordinateur a accès TRES TRES vite Matique comme Automatique : L’ordinateur traite automatiquement TRES TRES vite et sans jamais se tromper Université PARIS-SUD - Licence MPI - S1 14 Algorithme (historique) Algorithme (historique) Les premières formulations de règles précises pour la résolution de certains types d'équations remontent aux Babyloniens (époque d'Hammurabi, (1800 avant J.C.). Depuis l'antiquité : algorithmes sur les nombres.  Exemple : l'algorithme d'Euclide qui permet de calculer le p.g.c.d. de deux nombres entiers. Le mot algorithme est plus récent, il vient du nom d'un mathématicien perse du IXe siècle: Muhammad ibn Musa al-Khowârizmî. La signification du mot évolue au cours des temps :  pratique de l'algèbre (d'Alembert, XVIIIe siècle)  méthode et notation de toute espèce de calcul  tout procédé de calcul systématique, voire automatique Université PARIS-SUD - Licence MPI - S1 15 Algorithme de la mousse au chocolat Algorithme de la mousse au chocolat (6 p) (6 p) Ingrédients :  250g de chocolat, 125g de beurre, 6 œufs, 50 g de sucre, café Etapes :  Si chocolat a dessert faire fondre le chocolat avec 2 cuillères d'eau Sinon Faire tièdir le chocolat liquide au micro-onde  Ajouter le beurre, laisser refroidir puis ajouter les jaunes  Ajouter le sucre et comme parfum un peu de café  Battre les blancs jusqu’à former une neige uniforme  Ajouter au mélange.  A partir des ingrédients (données en entrée), appliquer la recette (les étapes) va produire une mousse au chocolat (le résultat). L’abus de mousse au chocolat est déconseillé L’abus de mousse au chocolat est déconseillé Université PARIS-SUD - Licence MPI - S1 16 Traitement différé Traitement différé Un programme ne peut pas être écrit au fur et a mesure qu’il est exécuté C’est un humain qui doit écrire le programme (les ordinateurs en sont incapables) C’est un ordinateur qui exécute le programme a raison de plusieurs milliards d’instructions par seconde Nécessité d’écrire un programme sans ambigüité que l’ordinateur puisse exécuter sans intervention humaine Université PARIS-SUD - Licence MPI - S1 17 Interaction Interaction L’ordinateur peut arrêter l’exécution du programme pour demander des précisions a l’utilisateur qui n’est pas le programmeur L’utilisateur peut avoir l’impression que le programme/ordinateur est intelligent mais c’est en fait l’intelligence du programmeur qui est perçue au travers de l’exécution du programme Un humain munit du bon ordinateur/programme peut passer pour plus intelligent aux yeux de ses semblables Université PARIS-SUD - Licence MPI - S1 18 Algorithme : un peu de méthodologie Algorithme : un peu de méthodologie identifier les données fournies / nécessaires (données en entrée)  identifier le résultat (données en sortie)  déterminer les actions ou opérations élémentaires  spécifier l'enchaînement des actions langage d'algorithmes = langage de description des données, des actions et des enchaînements Université PARIS-SUD - Licence MPI - S1 19 Langage de description d'algorithmes Langage de description d'algorithmes Algorithme titre % commentaire Lexique : variables // entrée : variables // sortie : variables // auxiliaire actions : noms des opérations début liste d'instructions fin Université PARIS-SUD - Licence MPI - S1 20 Calculer les intérêts d’un prêt bancaire Calculer les intérêts d’un prêt bancaire  Analyse  ValF = (ValIni * (1+interet/100) )* (1+interet/100)… 30 fois  Interet = 4% si valeur<10000 et 5% si >=10000 Algorithme InteretsBanquairesVariables %Calcul des interets qnnee qpres qnnee Lexique : ValIni entier // Entrée ValF entier //Auxiliaire Action : +, *, /, lire ,ecrire Début Lire ValIni //Demander ValIni a l’utilisateur Faire 30 fois : Si ValF<10000 Alors ValF ← ValF *1.04 Sinon ValF ← ValF *1.05 Ecrire “a la fin des 30 ans vous avez : “, ValF, “ euros” Fin Commentaires Commentaires Université PARIS-SUD - Licence MPI - S1 21 Calculer les intérêts d’un prêt bancaire Calculer les intérêts d’un prêt bancaire Algorithme InteretsBanquairesVariables %Calcul du carré d'un entier Lexique : ValIni entier // Entrée ValF entier //Auxiliaire Action : +, *, /, lire ,ecrire Début Lire ValIni //Demander ValIni a l’utilisateur Faire 30 fois : Si ValF<10000 Alors ValF ← ValF *1.04 Sinon ValF ← ValF *1.05 Ecrire “a la fin des 30 ans vous avez : “, ValF, “ euros” Fin Interactions Interactions Université PARIS-SUD - Licence MPI - S1 22 Pour aller plus loin … Pour aller plus loin … Poursuite de l’analyse Les valeurs intermédiaires permettraient à l’utilisateur de voir qu’au bout de x années il est a 9998,4 euros et uploads/Industriel/ 2-algo.pdf