Remerciez-le!

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

Algorithmique & Structures de données I S U P P O R T D E C O U R S 1 E R E ANN

Algorithmique & Structures de données I S U P P O R T D E C O U R S 1 E R E ANNEE LI C ENC E – TECH NOLOGI ES D E L’I NF ORMA TI Q UE 1 E R E ANNEE PR EPARA TOIR E I NTEGRE 3 E M E ANNEE GENI E I NF OR MATI Q U E – CYC LE I NG ENI EUR Adel DAHMANE adeldahmane.net@gmail.com Hind ELOUEDI h_elouedi@yahoo.fr Walid MELIANI walid.meliani@isetso.rnu.tn Notions abordées LES ELEMENTS DE BASE D'UN ALGORITHME Les structures de données simples Les instructions élémentaires LES STRUCTURES DE CONTROLES Les structures conditionnelles (de choix) Les structures itératives (les boucles) LES STRUCTURES DE DONNEES COMPOSEES Le type Tableau Le type Chaîne de caractère Le type Structure (Enregistrement) LES SOUS PROGRAMMES : LES FONCTIONS ET LES PROCEDURES LA RECURSIVITE LES ALGORITHMES DE RECHERCHE : SEQUENTIELLE ET DICHOTOMIQUE LES ALGORITHMES DE TRI : TRI A BULLES, TRI PAR SELECTION, TRI INSERTION, ... Auteurs : A. DAHMANE, H. ELOUEDI & W. MELIANI | Algorithmique & Structures de données I 2 UVT 2004 Table des matières CHAPITRE 1: LES ELEMENTS DE BASE D'UN ALGORITHME CHAPITRE 2: LES STRUCTURES CONDITIONNELLES CHAPITRE 3: LES STRUCTURES ITERATIVES CHAPITRE 4: STRUCTURES DE DONNEES COMPOSEES Auteurs : A. DAHMANE, H. ELOUEDI & W. MELIANI | Algorithmique & Structures de données I 3 UVT 2004 CHAPITRE 5: LES SOUS PROGRAMMES CHAPITRE 6: LA RECURSIVITE CHAPITRE 7: LES ALGORITHMES DE RECHERCHE Auteurs : A. DAHMANE, H. ELOUEDI & W. MELIANI | Algorithmique & Structures de données I 4 UVT 2004 LES ELEMENTS DE BASE D’UN ALGORITHME CHAPITRE 1 OBJECTIF Construire des algorithmes à structures simples. ELEMENTS DE CONTENU 1) NOTION D’OBJET ALGORITHMIQUE .......................................................................................... 5 1.1. DEFINITION .................................................................................................................................. 5 1.2. CARACTERISATION D’UN OBJET ALGORITHMIQUE............................................................................ 5 2) STRUCTURE GENERALE D’UN ALGORITHME .......................................................................... 6 2.1. PARTIE DECLARATIVE ................................................................................................................... 7 2.2. CORPS DE L’ALGORITHME ............................................................................................................. 8 3) LES STRUCTURES DE DONNEES SIMPLES .............................................................................. 8 3.1. LES TYPES NUMERIQUES .............................................................................................................. 8 3.2. LE TYPE CARACTERE .................................................................................................................... 9 3.3. LE TYPE BOOLEEN OU LOGIQUE .................................................................................................. 10 4) LES INSTRUCTIONS ELEMENTAIRES ...................................................................................... 10 4.1. L’INSTRUCTION D’AFFECTATION .................................................................................................. 10 4.2. L’INSTRUCTION D’ECRITURE ....................................................................................................... 11 4.3. L’INSTRUCTION DE LECTURE ....................................................................................................... 12 FIGURES FIGURE 1 : STRUCTURE GENERALE D’UN ALGORITHME ................................................................................. 6 FIGURE 2 : DEFINITION DE CONSTANTE ....................................................................................................... 7 FIGURE 3 : DEFINITION DE TYPE .................................................................................................................. 7 FIGURE 4 : DEFINITION DE VARIABLE ........................................................................................................... 7 FIGURE 5 : L’INSTRUCTION D’AFFECTATION ............................................................................................... 11 FIGURE 6 : L’INSTRUCTION D’ECRITURE ..................................................................................................... 11 FIGURE 7 : L’INSTRUCTION DE LECTURE .................................................................................................... 12 Auteurs : A. DAHMANE, H. ELOUEDI & W. MELIANI | Algorithmique & Structures de données I 5 Chapitre 1 Eléments de base d'un algorithme UVT 2004 1) NOTION D’OBJET ALGORITHMIQUE 1.1 DEFINITION Pour chaque algorithme, on a besoin de données pour fournir des résultats. Données et résultats sont appelés des objets algorithmiques. On distingue :  Les objets en entrée (saisis ou mémorisés) : ce sont les données fournies à l'algorithme.  Les objets en sortie : ce sont les résultats produits par l'algorithme.  Les objets internes ou intermédiaires (locaux) : ce sont les objets de manœuvre de l'algorithme servant aux manipulations internes (exp : compteurs, objets intermédiaires de stockage). Exemple : On se propose de permuter le contenu de deux objets A et B. Pour ce faire, on aura besoin des objets A et B en entrée et d'un troisième objet intermédiaire C puis on procédera comme suit :  On met le contenu de A dans C.  On met le contenu de B dans A.  On met le contenu de C dans B. Les objets A et B serviront aussi pour objets de sortie. 1.2. CARACTERISATION D’UN OBJET ALGORITHMIQUE Les objets algorithmiques, traités par l’ordinateur, sont stockés dans des cases mémoires dont la gestion est prise en charge par l’ordinateur. En mémoire, les cases sont reconnues à l’aide de leurs adresses, on parle d’adresse mémoire. Pour définir un objet algorithmique, on doit préciser son nom, son sens, son type, son utilisation et sa nature. a) NOM : Il sert à désigner l'objet dans l'algorithme, il est représenté par une chaîne de caractères alphanumériques qui commence obligatoirement par un caractère alphabétique. Dans la mesure du possible, ce nom doit être significatif, on l'appelle aussi identificateur. NB : l'identificateur d'un objet algorithmique ne doit pas contenir le caractère Espace. b) SENS : C'est la signification d'un objet, son rôle, son utilisation dans le problème. Exp : Soit Masse_Corps la masse d'un corps en kilogrammes. c) TYPE : Le type d'un objet caractérise les valeurs que peut prendre cet objet. On distingue les types simples et les types structurés (composés). Un objet de type simple contient une seule information, tandis qu'un objet de type structuré contient une collection d'informations réparties en plusieurs champs, accessibles individuellement ou collectivement. Un objet de type structuré est homogène si toutes ses informations sont de même type et hétérogène dans le cas contraire. Auteurs : A. DAHMANE, H. ELOUEDI & W. MELIANI | Algorithmique & Structures de données I 6 Chapitre 1 Eléments de base d'un algorithme UVT 2004 Exemples :  Type simple : Entier, Réel, Caractère,...  Type structuré homogène : Un tableau d'entiers.  Type structuré hétérogène : Un enregistrement Etudiant contenant : - Le numéro de la carte d'étudiant de type entier. - Le nom et le prénom de type chaîne de caractères. d) UTILISATION : Il s'agit de préciser si un objet est en entrée (E), en sortie (S) ou interne (I). e) NATURE : Il s'agit de préciser si un objet est une constante (Const) ou une variable (Var). Exemple : On se propose de représenter les objets algorithmiques utilisés dans un problème de résolution d'une équation du premier degré à une seule inconnue. Soit l'équation de la forme: ax + b = 0. Pour ce faire, on va dresser le tableau suivant : Nom Sens Type Utilisation Nature a Premier coefficient de l'équation Réel (non nul) E Var b Deuxième coefficient de l'équation Réel E Var x Solution de l'équation Réel S Var 2) STRUCTURE GENERALE D’UN ALGORITHME Un algorithme est une suite finie et ordonnée d’opérations élémentaires (instructions ou actions), écrites dans un langage de programmation abstrait non compréhensible par la machine, et constituant un schéma de calcul ou de résolution informatique d’un problème. Il devrait être exprimé par la suite dans un langage de programmation concret (évolué), traduit en langage machine puis exécuté afin d’aboutir aux résultats effectifs. Figure 1 : Structure générale d’un algorithme -- Auteur : Nom de l’auteur -- Date d’écriture : Date d’écriture de l’algorithme -- Fonction : Ce que doit faire l’algorithme ALGORITHMENom_algorithme DEFCONST Liste des constantes avec leurs valeurs DEFTYPE Liste des types personnalisés (tableau, structure…) DEFVAR Liste des variables avec leurs types DEBUT Instruction 1 Instruction 2 ... Instruction n FIN En-tête Partie Déclarative Corps de l’algorithme Auteurs : A. DAHMANE, H. ELOUEDI & W. MELIANI | Algorithmique & Structures de données I 7 Chapitre 1 Eléments de base d'un algorithme UVT 2004 2.1. PARTIE DECLARATIVE Avant d'utiliser n'importe quel objet algorithmique, il faut le déclarer au niveau de la partie déclarative de l'algorithme. Ces objets peuvent être de deux natures à savoir : constante ou variable. Dans ce qui suit, on va décrire la partie déclarative relative à un algorithme qui est composée de trois parties pas nécessairement toutes présentes : a) DEFINITION DES CONSTANTES : Il s'agit de la première rubrique de la partie déclarative qui sert à définir les constantes utilisées dans l'algorithme. Une constante est une donnée dont la valeur reste fixe durant toute la durée de l’exécution d’un algorithme. Figure 2 : Définition de constante b) DEFINITION DES TYPES : C'est la deuxième rubrique de la partie déclarative qui sert à définir les types non standards (non prédéfinis). Figure 3 : Définition de type c) DEFINITION DES VARIABLES : C'est la troisième rubrique de la partie déclarative qui sert à déclarer les différentes variables utilisées dans l'algorithme. Figure 4 : Définition de variable DefConst identificateur (Type) = valeur Exemple : a (Entier) = 5 b (Réel) = 2.5 DefType Nom_Type = Définition de type Exemple : Tab = Tableau[1..10] de Entier -- Déclaration de type tableau d'entiers Indice = 1..10 -- Déclaration de type intervalle Etudiant =Structure -- Déclaration de type enregistrement NCE : Entier Nom : Chaîne(15) Prénom : Chaîne(15) Fin Structure DefVar identificateur (Type) -- Commentaire Exemples : DefVar x (Entier) -- Dividende. y (Entier) -- Diviseur différent de zéro. z (Réel) -- Quotient. r (Entier) -- Reste de la division. Auteurs : A. DAHMANE, H. ELOUEDI & W. MELIANI | Algorithmique & Structures de données I 8 Chapitre 1 Eléments de base d'un algorithme UVT 2004 2.2. CORPS DE L’ALGORITHME Cette partie de l’algorithme contient l’ensemble des instructions applicables sur l’ensemble des objets algorithmiques déjà déclarés au niveau de la partie précédente (déclarative). Ces instructions se divisent en essentiellement en trois catégories :  Les instructions simples : Entrée de données, sortie de résultats, affectation.  Les structures décisionnelles (conditionnelles uploads/Ingenierie_Lourd/ cours 9 .pdf