Résumé Algorithmique PDF

RÉSUMÉ ALGORITHMIQUE Made by : Reviewed by : Ibrahim Bouaicha Prof Manar Abourezq *The slides in this document are taken from Prof Aboureq’s Algorithmics course.  Language de programmation Langages de programmation de bas niv...

RÉSUMÉ ALGORITHMIQUE Made by : Reviewed by : Ibrahim Bouaicha Prof Manar Abourezq *The slides in this document are taken from Prof Aboureq’s Algorithmics course.  Language de programmation Langages de programmation de bas niveau : Langage machine : (code machine), c’est un ensemble d’instructions et de données codées en binaire (des bits de 0 ou 1) interprété par le processeur exécutant le programme. Langage assembleur : ( langage d’assemblage), il représente le langage machine sous une forme lisible par l’humain. Langages de programmation de haut niveau : Nécessitent une traduction vers le langage machine par un o Compilateur : programme traduisant l’ensemble des instructions demandées dans un langage de bas niveau : Un langage compilé permet d’exécuter le programme directement sur l’ordinateur (plus rapide)  o Interpréteur : programme exécutant pas à pas les instructions demandées) Un langage interprété permet la portabilité, i.e. obtenir un code source qui fonctionne sur tout ordinateur (moin rapide)  Algorigramme Example : Pseudo-code Un programme n’est pas purement séquentiel ➔ nécessité d’avoir des structures de contrôle : 10. Les structures alternatives (tests) 2. Les structures itératives (boucles)  Les structures alternatives (test) Écrire un algorithme qui demande à l’utilisateur de saisir deux nombres puis qui retourne le signe (positif, négatif ou nul) de leur produit (sans calculer ce dernier) Example : Écrire un algorithme qui demande à l’utilisateur de saisir son âge puis qui retourne la catégorie à laquelle il appartient  Les structures itératives (boucles) Écrire un algorithme qui demande à l’utilisateur de saisir un nombre entier n puis qui affiche la somme de tous les entiers jusqu’à n (1 + 2 + … + n) Écrire un algorithme qui demande à l’utilisateur de saisir dix nombres positifs puis qui retourne le nombre le plus grand et sa position : Écrire un algorithme qui demande de saisir des nombres positifs puis qui retourne le nombre le plus grand Le nombre des nombres à saisir n’est pas connu à l’avance La saisie s’arrête quand l’utilisateur saisit le nombre −1  Tableau statique Séquence de données de même type, chacune référencée par un nombre appelé indice (ou index) Désigné par : Son nom Le type de ses éléments Sa taille (i.e. le nombre de ses éléments) Demander à l’utilisateur de saisir 10 nombres réels : Écrire un algorithme qui demande à l’utilisateur de saisir 20 notes et lui affiche leur moyenne : Écrire un algorithme qui demande à l’utilisateur de saisir 20 notes et lui affiche leur moyenne, la note minimale et la note maximale :  Tableau dynamique Séquence de données de même type, chacune référencée par un nombre appelé indice (ou index), dont la taille est variable et peut changer lors de l’exécution. Écrire un algorithme qui demande à l’utilisateur de saisir des notes et lui affiche leur moyenne, la note minimale et la note maximale. Écrire un algorithme qui demande à l’utilisateur de remplir deux tableaux et qui affiche le tableau contenant le produit des éléments des deux.  Tableau à 2 dimensions Séquence de données de même type, chacune référencée par deux indices (matrice). Désigné par : Son nom Le type de ses éléments Sa taille n x m Écrire un algorithme qui cherche, dans un tableau d’entiers de 10 x 10, le nombre minimal et le nombre maximal. Écrire un algorithme qui demande à l’utilisateur de remplir une matrice de 10 x 10 et vérifie si elle est symétrique ou non.  Recherche dans un tableau Recherche de la valeur val dans le tableau tab[N] : Recherche de la valeur val dans le tableau tab[N] :  Tri dans un tableau Exemple du tri par sélection du tableau tab[N] : Exemple du tri à bulles du tableau tab[N]  Procédure Principale Le corps de l’algorithme est appelé procédure principale. Les instructions qu’on regroupe pour effectuer un traitement particulier sont appelées sous-procédures ou fonctions. o On fait appel à ces sous-procédures ou fonctions à partir de la procédure principale. Example de l’appel d’une sous-procédure :  Sous-procédure Une sous-procédure est un ensemble d’instructions décrivant une action simple ou complexe, elle est définie par : Son nom Ses arguments (ou paramètres) Example :  Passage des arguments Quelles sont les caractéristiques d’une variable ? o Son nom (n) o Sa valeur o Son adresse Qu’est-ce qu’une adresse ? o C’est l’adresse de la case mémoire où la variable est stockée o Notation : &n Qu’est-ce qu’un pointeur ? o C’est une variable qu’on déclare pour stocker la valeur de l’adresse d’une autre variable o Déclaration d’un pointeur : VAR ptr : entier* ptr  &n o Si on affiche ptr, le programme va donner l’adresse de n Comment afficher la valeur d’une variable en utilisant son pointeur ? o En utilisant la déréférence, let me explain : ▪ Soit ptr le pointeur qui porte l’adresse de n ▪ La valeur de ptr est &n, évidemment ! ▪ L’opérateur de déréférence, noter *ptr, donne la valeur stockée dans l’adresse &n, i.e. la valeur de n (Dans un ordinateur les adresses sont toujours en notation hexadécimal) ALGORITHME best_algo VAR n : entier VAR ptr : * entier DEBUT n  10 ptr  &n Afficher(n) // la valeur de n Afficher(&n) // l’adresse de n Afficher(ptr) // la valeur de ptr (i.e. l’adresse de n) Afficher(*ptr) // La valeur de n (déréférence) FIN Output : 10 // The value of n 0x7ffe5367e044 // The address of n 0x7ffe5367e044 // The value of ptr (address of n) 10 // Dereferenced value of ptr (value of n)  Passage par valeur Output : Le programme va afficher 2 Explication : arg est déclaré à l’intérieur de la procédure, donc une case mémoire a été réservé pour cette variable La valeur de n est copiée dans la case mémoire de arg Explication (v2) i.e. en donne la valeur de n a arg, arg se triple n reste inchangeable  Passage par adresse La procédure prend comme argument l’adresse de la variable, et change la valeur stockée dans cette adresse : La valeur de l’argument est une adresse On prend la valeur stockée dans cette adresse, par déréférence (*arg) On triple cette valeur, sans la copier En remarque que la procédure n’a pas besoin d’une nouvelle case mémoire puisque le résultat est stocké dans l’adresse de la variable n  Fonctions Une fonction est une sous-procédure particulière qui retourne un résultat à la procédure principale (ou le programme appelant). Elle est définie par : Son nom Ses arguments (ou paramètres d’entrée) Son type de retour Syntaxe de déclaration : Syntaxe d’appel : Écrire une fonction qui permet de calculer la valeur absolue d’un réel. Écrire une fonction qui permet de vérifier si un tableau est trié avec un ordre croissant ou non trié. Fonctions prédéfinies  Protée des variables La portée d’une variable est l’ensemble des sous-programmes (sous-procédures et fonctions) où elle est connue et peut donc être utilisée. Une variable peut être : Locale o Elle est déclarée au sein d’un sous-programme o Ne peut être utilisée que dans ce sous-programme Globale o Elle est déclarée au sein de la procédure principale o Accessible par toute sous-procédure ou fonction appelée par la procédure o Une sous-procédure ou fonction peut déclarer une variable globale :