Remerciez-le!

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

26/11/2011 1 Chapitre 1: Notion d’algorithme et d’algorithmique. Université du

26/11/2011 1 Chapitre 1: Notion d’algorithme et d’algorithmique. Université du 20 Août 1955 Année universitaire: 2011/2012 Master1: Ingénierie des systèmes distribués Chapitre 2: Complexité des algorithmes :Bases théoriques. Chapitre3: Récursivité et paradigme: diviser pour régner. Chapitre 4: Etude d’algorithmes de tri-Recherche. Chapitre 5: Algorithmes des graphes-Arbres. Chapitre 6: Programmation dynamique. Chapitre 7: Algorithmes gloutons. Chapitre 8: Classification d’algorithmes: P , NP , NP-complets. Chapitre 9: Algorithmes d’exploration: Heuristique et méta-heuristique. L’algorithmique sert comme point de départ à l’analyse des problèmes et à la recherche de solutions formalisées dans un pseudo langage ou langage algorithmique. Dans un cours d’introduction à l’algorithmique on retrouve généralement les notions suivantes: - Les variables et les types, - les expressions, - les schémas algorithmiques simple, conditionnel et itératif, - les structures de données. A partir de ces connaissances nous allons essayer d’introduire l’algorithmique avancée. Algorithmique Avancée: Présentation du cours 2 26/11/2011 2 En algorithmique simple, il s’agit de trouver des solutions à des problèmes de base en utilisant des structures de données prédéfinies, telles que les tableaux et les enregistrements. En algorithmique avancée, il s’agit de définir un modèle mathématique de données et des opération de base sur ce modèle mathématique. Le couple (modèle mathématique, opérations)est appelé Type de Données Abstrait. Objectifs Concevoir un ”bon” algorithme -c.à.d. correct et efficace - pour résoudre un problème. Algorithmique Avancée: Présentation du cours 3 -Existe-il un algorithme pour résoudre le problème? Connaitre quelques Notions de Calculabilité et de décidabilité. - Est-ce un problème classique? Connaitre et savoir reconnaitre des grands classiques Tris, méthodes de sélection, recherche, algorithmique des graphes …… - Comment concevoir un algorithme? Schémas d’algorithmes Diviser pour régner Programmation Dynamique Algorithmes gloutons - L’algorithme est-il efficace? Savoir analyser la complexité d’algorithmes. - Si le problème est dur, comment l’appréhender? Connaitre quelques techniques d’ Algorithmique Avancée. Algorithmique Avancée: Présentation du cours 4 26/11/2011 3 Qu’est-ce que l’algorithmique ? Définition 1 (Algorithme): Une suite finie d’opérations élémentaires constituant un schéma de calcul ou de résolution d’un problème. Définition 2 (Algorithmique): Un ensemble de règles et des techniques qui sont impliquées dans la définition et la conception d’algorithmes, c’est à dire de processus systématiques de résolution d’un problème par des étapes élémentaires. Objectifs 1. Trouver une méthode de résolution (exacte ou approchée) du problème. 2. Trouver une méthode efficace. =>Savoir résoudre un problème est une chose, le résoudre efficacement en est une autre, ou encore montrer qu' ’il est correcte …!! Chapitre 1: Notion d’algorithme et d’algorithmique 5 Un algorithme doit se terminer sur toutes les données possibles du problème et doit fournir une solution correcte dans chaque cas. Une bonne connaissance de l’algorithmique permet d’écrire des programmes exacts. Pour un problème donné, il existe bien souvent plusieurs algorithmes. Y a-t-il un intérêt à choisir ? et si oui comment choisir ? Il existe des problèmes pour lesquels on a des algorithmes, mais qui restent comme «!informatiquement non résolus!». C’est parce que les temps d’exécution sont vite exorbitants. On cherche alors des solutions pour abaisser ces temps de calcul. Chapitre 1: Notion d’algorithme et d’algorithmique 6 26/11/2011 4 Faire la conception détaillée dans un langage algorithmique, indépendant des langages de programmation, et compréhensible par des informaticiens qui ne sont pas des développeurs ; préparer la phase de test. Chapitre 1: Notion d’algorithme et d’algorithmique 7 •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épond au problème pour lequel il a été conçu? Chapitre 1: Notion d’algorithme et d’algorithmique 8 26/11/2011 5 Evaluation du coût d’exécution d’un algorithme en terme de - Temps (Complexité temporelle) - Espace mémoire (Complexité spatiale) Le coût d’exécution dépend de: - La machine sur laquelle s’exécute l’algorithme - la taille des données traitées - La traduction de l’algorithme en langage exécutable par la machine Chapitre 1: Notion d’algorithme et d’algorithmique 9 Paradigme (Schémas d’algorithmes, Algorithmic design patterns) Une méthode générique qui s'applique dans plusieurs situations algorithmiques. Une approche permettant la résolution de problèmes Diviser pour régner Programmation dynamique Algorithmes gloutons ………. Chapitre 1: Notion d’algorithme et d’algorithmique 10 26/11/2011 6 Supposez que les ordinateurs soient infiniment rapides et que leurs mémoires soient gratuites Question Faudrait-il encore étudier l’algorithmique? Réponse OUI, pour montrer que la solution: - Ne boucle pas indéfiniment - se termine avec la bonne réponse Chapitre 1: Notion d’algorithme et d’algorithmique 11 Chapitre 1: Notion d’algorithme et d’algorithmique -Rappels- 12 26/11/2011 7 Données Calcul variables instructions structures conditions tableaux boucles …… …… l’algorithmique c’est : le choix d’un algorithme le choix d’une structure de données Chapitre 1: Notion d’algorithme et d’algorithmique 13 Chapitre 1: Notion d’algorithme et d’algorithmique 14 26/11/2011 8 Déclaration des constantes Syntaxe : Constante NomConstante : [Type] = Valeur Exemples : Constante Pi : Reel = 3.141559 Constante NombreLettres : Entier = 10 Déclaration des variables Syntaxe : Variable NomVariable : [Type] Exemples : Variable Rayon : Reel Variable Compteur : Entier Variable Lettre : Caractere Chapitre 1: Notion d’algorithme et d’algorithmique 15 • Les procédures et fonctions peuvent nécessiter éventuellement un ou plusieurs paramètres d’entrée ou de sortie. • Un paramètre d’entrée est la référence à une variable manipulée par la procédure ou la fonction. •Un paramètre de sortie est une valeur renvoyée par une fonction. •Une fonction ou une procédure peut elle- même appeler une ou plusieurs fonctions et procédures. Chapitre 1: Notion d’algorithme et d’algorithmique 16 26/11/2011 9 Fonction NomFonction (NomEntrée1 : [Type], NomEntrée2 : [Type],…) : [TypeDuRésultat] Constante ~ déclaration des constantes locales ~ Variable ~ déclaration des variables locales ~ Début ~ description des actions effectuées par la fonction ~ Fin Chapitre 1: Notion d’algorithme et d’algorithmique Variable NomFonction (NomEntrée1, NomEntrée2…) 17 Fonction Moyenne (Note1 : Reel, Note2 : Reel) : Reel Variable Intermediaire : Reel Début Intermediaire Note1 + Note2 Intermediaire Intermediaire / 2 Moyenne Intermediaire Fin Chapitre 1: Notion d’algorithme et d’algorithmique Afficher (Moyenne(10.5,15)) ou NouvelleNote Moyenne (10,5.5) 18 26/11/2011 10 Une affectation consiste à attribuer une valeur à une variable. La syntaxe générale est la suivante : NomVariable Expression « Expression » peut être: · une constante (Ex : surface 40) · une autre variable (Ex : B A) · le résultat d’une fonction (Ex : resultat racine (nombre)) · un calcul portant sur ces différents éléments. (Ex: a b * Carre (c)+d) Chapitre 1: Notion d’algorithme et d’algorithmique 19 Les opérateurs permettent d’élaborer une expression en vue d’effectuer un calcul ou une comparaison. L’usage des parenthèses est vivement conseillé dans le cas d’expressions complexes. Chapitre 1: Notion d’algorithme et d’algorithmique 20 26/11/2011 11 Les structures algorithmiques sont réparties en 3 catégories : - Structures linéaire d'opérations; - Structures alternatives (ou conditionnelles) ou de choix : en fonction d'une condition, le programme exécute des opérations différentes; - Structures itératives ou répétitives: sous contrôle d'une condition, une séquence d'opérations est exécutée répétitivement. Chapitre 1: Notion d’algorithme et d’algorithmique 21 Les actions successives sont mentionnées les unes après les autres. Syntaxe Action1 Action2 ... ActionN Exemple : Calcul d’un produit de 2 nombres Variable a,b,p : réel Début Saisir (a) Saisir (b) p a * b Afficher (p) Fin 22 Chapitre 1: Notion d’algorithme et d’algorithmique 26/11/2011 12 Structure SI ... ALORS ... Une condition est testée pour déterminer si l’action ou le groupe d’actions suivant doit être exécuté. Syntaxe Si Condition Alors Actions FinSi Chapitre 1: Notion d’algorithme et d’algorithmique 23 Structure SI ... ALORS ...SINON ... Une condition est testée pour déterminer quelle action ou quel groupe d’actions doit être exécuté. Syntaxe Si Condition Alors Actions Sinon Actions2 FinSi Chapitre 1: Notion d’algorithme et d’algorithmique 24 26/11/2011 13 Structure REPETER ... JUSQUA ... Une action ou un groupe d’actions est exécuté répétitivement jusqu'à ce qu’une condition soit vérifiée. Syntaxe Répéter Actions Jusqu’a Condition Chapitre 1: Notion d’algorithme et d’algorithmique 25 Structure REPETER ... JUSQUA ... Exemple exécution répétitive d’un programme Variables a,b,p : réel c : caractère Début Répéter Afficher (‘Saisir le nombre a ‘) Saisir (a) Afficher (‘Saisir le nombre b ‘) Saisir (b) p a * b afficher (p) afficher (‘encore un calcul ? Non touche N ; Oui autre touche’) saisir (c) Jusqu'à c = ‘N’ Fin Chapitre 1: Notion d’algorithme et d’algorithmique 26 26/11/2011 14 Structure POUR Indice DE .. A .. FAIRE .. Une action ou un groupe d’actions est exécuté répétitivement un certain nombre de fois : le nombre dépend des valeurs initiale et finale données à la variable « Indice uploads/Management/ master1-ingenierie-des-systemes-distribues.pdf