Remerciez-le!

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

12/03/2013 1 M AP @ U N I C E . F R COURS ALGORITHMIQUE ET PROGRAMMATION INFORM

12/03/2013 1 M AP @ U N I C E . F R COURS ALGORITHMIQUE ET PROGRAMMATION INFORMATIQUE DUT INFORMATIQUE S1 Marie-Agnès peraldi-frati Mâitre de conférences en informatique UNS/IUT de Nice côte d’azur 1 MAP - UNS RÉFÉRENCES • Algorithmes D.E Knuth CSLI Publications 2011 • Introductipon a la science informatique G. Dowek Ed RPA 2010 • Eléments pour une histoire de l’informatique, D.E Knuth CSLI Publications 2011 • Cours et exercices corrigés d’algorithmique- J. Julliand Ed Vuibert Fev 2010 • Algorthmique méthodes et modèles , P Lignelet Ed Masson 1988 • Cours algorithme Cécile Balkanski, Nelly Bensimon, Gérard Ligozat IUT Orsay 2 MAP - UNS 12/03/2013 2 OBJECTIF DU COURS API • Notions de base en algorithmique • Types de données et lien avec la machine • Notion de sous-programmes et lien avec la compilation • Qualité • nommage des variables, assertions, documentation …, • pré et post conditions • Structures algorithmiques fondamentales: . • Implantation des algorithmes dans un langage de programmation. • Introduction au test unitaire, boîte noire, • Algorithmes fondamentaux de recherche recherche d’un élément, parcours, tri, … • Avoir une première notion des performances des algorithmes utilisés 3 MAP - UNS NOTION DE BASE EN ALGORITHMIQUE MAP - UNS 4 12/03/2013 3 CONCEPTS IMPORTANTS EN INFORMATIQUE • Algorithme : mot dérivé du nom du mathématicien al_Khwarizmi qui a vécu au 9ème siécle, était membre d’un académie des sciences à Bagdad . • Un algorithme prend des données en entrée, exprime un traitement particulier et fournit des données en sortie. • Programme : série d’instructions pouvant s’exécuter en séquence, ou en parallèle (parallélisme matériel) qui réalise (implémente) un algorithme 5 MAP - UNS POURQUOI UN COURS D’ "ALGO" ? •Pour obtenir de la «machine» qu’elle effectue un travail à notre place •Problème: expliquer à la «machine» comment elle doit s'y prendre • Besoins : • savoir expliciter son raisonnement • savoir formaliser son raisonnement • concevoir (et écrire) des algorithmes: • séquence d’instructions qui décrit comment résoudre un problème particulier 6 MAP - UNS 12/03/2013 4 ALGORITHME • Savoir expliquer comment faire un travail sans la moindre ambiguïté • langage simple : des instructions (pas élémentaires) • suite finie d'actions à entreprendre en respectant une chronologie imposée •L’écriture algorithmique : un travail de programmation à visée universelle • un algorithme ne dépend pas du langage dans lequel il est implanté, • ni de la machine qui exécutera le programme correspondant. 7 MAP - UNS EXEMPLE D’ALGORITHMES • Recette de cuisine • Notice de montage de meuble en kit • Mathématiques : problème 3n+1: élémentaire mais redoutable • si n est pair, on le divise par 2 ; • si n est impair, on le multiplie par 3 et on ajoute 1. • Est-il vrai que l’on finira tôt ou tard par tomber sur 1 ? 8 MAP - UNS 12/03/2013 5 LES PROBLÈMES FONDAMENTAUX EN ALGORITHMIQUE • Complexité • En combien de temps un algorithme va -t-il atteindre le résultat escompté? • De quel espace a-t-il besoin? • Calculabilité: • Existe-t-il des tâches pour lesquelles il n'existe aucun algorithme ? • Etant donnée une tâche, peut-on dire s'il existe un algorithme qui la résolve ? • Correction • Peut-on être sûr qu'un algorithme réponde au problème pour lequel il a été conçu ? 9 MAP - UNS EXEMPLE DE LANGAGE ALGORITHMIQUE 10 MAP - UNS 12/03/2013 6 ETAPES D’UN ALGORITHME • Préparation du traitement • données nécessaires à la résolution du problème • Traitement • résolution pas à pas, • après décomposition en sous-problèmes si nécessaire • Edition des résultats • impression à l’écran, • dans un fichier, etc. 11 MAP - UNS LANGAGE ALGORITHMIQUE Algorithme NomAlgorithme { ceci est un commentaire} Début ... Actions Fin • Il faut avoir une écriture rigoureuse • Il faut avoir une écriture soignée : respecter l’indentation • Il est nécessaire de commenter les algorithmes • Il existe plusieurs solutions algorithmiques à un problème posé • X Il faut rechercher l’efficacité de ce que l’on écrit Algorithme Bonjour {il dit juste bonjour mais … en anglais ! Début afficher('Hello world !!!') ALaLigne Fin 12 MAP - UNS 12/03/2013 7 DÉCLARATION DES DONNÉES • Variable <nom de donnée>: type • Instruction permettant de réserver de l’espace mémoire pour stocker des données • Dépendant du type des données : entiers, réels, caractères, etc.) • Exemples : • Variables val, unNombre: entiers nom, prénom : chaînes de caractères 13 MAP - UNS DÉCLARATION DES DONNÉES • Constante <nom de donnée>: type ←valeur ou expression • Instruction permettant de réserver de l’espace mémoire pour stocker une constante dont la valeur ne varie pas. • Exemples : • Constante MAX : entier ←10 DEUXFOISMAX : entier ←MAX x 2 14 MAP - UNS 12/03/2013 8 LECTURE ÉCRITURE DE DONNÉES • Saisir<nom de donnée, …> • Afficher<nom de donnée, …> • Fonction : Instructions permettant • de placer en mémoire les informations fournies par l'utilisateur. • De visualiser des données placées en mémoire • Exemples: Saisir(unNombre) Afficher (« le nom est « , nom, »et le prénom est » , prénom ) Saisir(val) 15 MAP - UNS PHASE D’ANALYSE • Consiste à extraire de l’énoncé du problème des éléments de modélisation • Technique : Distinguer en soulignant de différentes couleurs quelles sont • Quel est le but du programme (traitement à réaliser) • Données en entrée du problème : • Où vont se situer les résultats en sortie 16 MAP - UNS 12/03/2013 9 EXEMPLE D’ÉNONCÉ D’UN PROBLÈME • On souhaite calculer et afficher , à partir d’un prix hors taxe saisi, la TVA ainsi que le prix TTC • Le montant TTC dépend de : • Du prix HT • Du taux de TVA de 20,6 17 MAP - UNS EXEMPLE D’ÉNONCÉ D’UN PROBLÈME • On souhaite calculer et afficher , à partir d’un prix hors taxe saisi, la TVA ainsi que le prix TTC • Le montant TTC dépend de : • Du prix HT • Du taux de TVA de 20,6 Traitement à réaliser 18 MAP - UNS 12/03/2013 10 EXEMPLE D’ÉNONCÉ D’UN PROBLÈME • On souhaite calculer et afficher , à partir d’un prix hors taxe saisi, la TVA ainsi que le prix TTC • Le montant TTC dépend de : • Du prix HT • Du taux de TVA de 20,6 Données en entrée 19 MAP - UNS EXEMPLE D’ÉNONCÉ D’UN PROBLÈME • On souhaite calculer et afficher , à partir d’un prix hors taxe saisi, la TVA ainsi que le prix TTC • Le montant TTC dépend de : • Du prix HT • Du taux de TVA de 20,6 Données en sortie 20 MAP - UNS 12/03/2013 11 ALGORITHME TVA Algorithme CalculTVA {Saisit un prix HT et affiche le prix TTC correspondant} Constantes (TVA : réel) ←20.6 (Titre : chaîne) ←"Résultat" Variables prixHT : réel Variable prixTTC, montantTVA : réels {déclarations} Début {préparation du traitement} afficher("Donnez-moi le prix hors taxe :") saisir(prixHT) prixTTC ←prixHT* (1+TVA/100) {calcul du prix TTC} montantTVA ← prixTTC- prixHT afficher(Titre) {présentation du résultat} afficher(prixHT, «euros H.T. + TVA ",TVA, « devient » ,prixTTC, «eurosT.T.C.") Fin 21 Code peu efficace MAP - UNS INSTRUCTIONS SÉQUENTIELLES RÉSULTAT D’UN ALGORITHME Constante (SEUIL : réel) ←13.25 Variables valA, valB: réels compteur : entier mot , tom : chaînes valA←0.56 valB←valA valA←valA×(10.5 + SEUIL) compteur ←1 compteur ←compteur + 10 mot ←" Bonjour " tom ←"Au revoir ! " Quelles sont les différentes valeurs des variables ? 22 MAP - UNS 12/03/2013 12 SIMULATION D’UN ALGORITHME Algorithme CaDoitEchanger? {Cet algorithme .........................................} Variables valA, valB: réels {déclarations} Début {préparation du traitement} Afficher ("Donnez-moi deux valeurs :") Saisir (valA, valB) Afficher ("Vous m'avez donné ", valA, " et ", valB) {traitement mystère} valA←valB valB←valA {présentation du résultat} Afficher("Maintenant , mes données sont : ", valA, " et ", valB) Fin Que fait cet algorithme ? Pas ce qui est prévu ! 23 MAP - UNS CE QU’IL MANQUE • Déclarer une variable supplémentaire Variables valA, valB, valTemp: entiers • Utiliser cette variable pour stocker provisoirement une des valeurs Saisir(valA, valB) valTemp←valA valA←valB valB←valTemp 24 MAP - UNS 12/03/2013 13 STRUCTURE ALTERNATIVE « SI … ALORS … SINON … FSI » (1) • Exemple : Algorithme SimpleOuDouble {Cet algorithme saisit une valeur entière et affiche son double si cette donnée est inférieure à un seuil donné.) constante (SEUIL : entier) ←10 Variable val : entier début Afficher("Donnez-moi un entier : ") { saisie de la valeur entière} Saisir(val) si val < SEUIL { comparaison avec le seuil} alors Afficher ("Voici son double :" , val ×2) sinon Afficher ("Voici la valeur inchangée :" , val) fsi fin 25 MAP - UNS STRUCTURE ALTERNATIVE « SI … ALORS … SINON … FSI » (2) • Ou instruction conditionnelle si <expression logique> alors instructions [sinon instructions] fsi • Si l’expression logique (la condition) prend la valeur vrai, le premier bloc d’instructions est exécuté; • si elle prend la valeur faux, le second bloc est exécuté (s’il est présent, sinon, rien). 26 MAP - UNS 12/03/2013 uploads/Science et Technologie/ c1-2-apistructuresalgorithmiquesdebase 1 .pdf