Mathematics">
Algorithmic Part1
Algorithmic Part1
Algorithmic Part1
D’ALGORITHMIQUE
COMPRENDRE LES FONDEMENTS
DE L'ALGORITHMIQUE
Pr. Hanane GRISSETTE
Hanane.grissette@usmba.ac.ma
Filiere: Intelligence artificiellle
OUTLINES
• Informations pratiques
• 25 heures de cours ;
25 heures de travaux dirigés ;
• Évaluation :
2 contrôles + examen final
Part I:
INTRODUCTION À L’ALGORITHMIQUE
ET À LA PROGRAMMATION
• Contenu :
• Définitions et concepts de base en algorithmique.
• Rôles et importance des algorithmes dans l'informatique.
• Notation asymptotique (Big O) et analyse de la complexité.
ALGORITHMIQUE
Steps:
1. Obtenir les coefficients a, b et c.
2. Est a égal à zéro ? Calculer le discriminant (Δ)
3. Δ < 0 ?
4. Δ = 0 ?
5. Pas de solutions réelles (Δ < 0)
6. One Real Root (Δ = 0)
7. Calculer les racines
8. Two Real Roots (Δ > 0) :
9. One Real Double Root (Δ = 0) :
10. End (Fin)
DÉFINITIONS
•Algorithme : procédure de calcul bien définie qui prend en entrée une valeur, ou un ensemble
de valeurs, et qui donne en sortie une valeur, ou un ensemble de valeurs. Un algorithme est donc
une séquence d’étapes de calcul qui transforment l’entrée en sortie.
•Un algorithme prend des données en entrée, exprime un traitement particulier et fournit des
données en sortie.
méthode indépendante de la machine
méthode indépendante du langage de programmation résolution structurée
algorithme = description des étapes de la méthode utilisée
03
Cette polyvalence fait des
algorithmes un outil précieux
pour résoudre un large éventail
de problèmes informatiques.
RECAP
1. Analyse du problème
2. Conception d’une solution algorithmique: (1) choix de la
représentation des données (2) choix de la méthode
utilisée
3. Développement : programmation
choix du langage de programmation choix de la
machine utilisée
4. Tests
Déclaration et syntaxe:
Exemple
Algorithme Bonjour
{il dit juste bonjour mais ... en anglais }
Début
afficher('Hello world !!!’)
ALaLigne
Fin
EXERCICE
UN BON ALGORITHME
Un bon algorithme =
Un algorithme correct : i.e. pour chaque instance en entrée, l’algorithme se termine en
produisant la bonne sortie.
Définition:
Variable : Elle peuvent stocker des chiffres, des nombres, des caractères
des chaîne de caractères..., dont la valeur peut être modifiée au cours
de l’exécution de l’algorithme
Déclaration et syntaxe:
Exemple
Variable A, B : entier
d : réel
Note:
- Une variable locale ne peut s’utiliser que dans la macro ou le programme principal où elle est déclarée.
- Une variable globale se déclare en début de l’algorithme et peut s’utiliser n’importe où.
DANS LA MÉMOIRE
Définition:
Constante : Elle peuvent stocker des chiffres, des nombres, des caractères des chaîne
de caractères..., dont la valeur ne peut être modifiée au cours de l’exécution de
l’algorithme.
Déclaration et syntaxe:
Exemple
Constante A1 : entier
Note:
- Important: Les noms de variables ne doivent pas contenir d’espaces, d’accents, de caractères spéciaux autre que _.
Les minuscules et les majuscules sont aussi différenciées.
AFFECTATION
Définition:
L'instruction d’affectation est l'instruction qui consiste à donner une valeur à une variable.
L'instruction d’affectation s'écrit en indiquant le nom de la variable, suivi de l'opérateur
d'affectation ← et de la nouvelle valeur à donner à la variable. Cette valeur doit respecter
le type de la variable.
Note:
•Pour les variables de type booléen, les valeurs possibles sont vrai et faux.
•Pour les variables de type chaine, les valeurs sont entourées de guillemets “.
ELÉMENTS DE BASE : OPÉRATEURS
Définition:
Un opérateur est un symbole d’opération qui permet d’agir sur des variables ou de
faire des “calculs”
Une opérande est une entité (variable, constante ou expression) utilisée par un opérateur
Une expression est une combinaison d’opérateur(s) et d’opérande(s), elle est évaluée
durant l’exécution de l’algorithme, et possède une valeur (son interprétation) et un type
•Exemples
•prixPromo ← prix * 0,6
• surface ← (base * hauteur)/2
ELÉMENTS DE BASE
Types opérateurs
Un opérateur est unaire (non) ou binaire (+)
Un opérateur est associé à un type et ne peut être utilisé qu’avec des données de ce
type
Opérateur d’affectation
Il permet d’affecter une valeur de l’opérande droit à
une variable (opérande gauche), il est représenté par: ←
Exemple:
nom ← "Venus "
val1 ← val2
val ← val ×2
LES I N S T R U C T I O N S D 'E N T R É E S - S O RT I E S E N
P S EU D O - C O D E
Un algorithme peut avoir des interactions avec l’utilisateur et communiquer avec
lui dans les deux sens, les sorties sont des envois de messages a l'utilisateur, les
entrées sont des informations fournies par l'utilisateur.
Il peut demander à l’utilisateur de saisir une information afin de la stocker dans une
variable et peut afficher un résultat (du texte ou le contenu d’une variable)
INSTRUCTION DE LECTURE
Définition:
L'instruction de lecture permet au système d'interagir avec l’extérieur, elle se note avec le
mot-clé Lire.
Cette instruction permet au système numérique :
• de demander à l’utilisateur de lui fournir une information ;
• de récupérer des données qui proviennent d’un capteur ;
• de recevoir des données qui proviennent d’un réseau.
Exemple
Déclaration et syntaxe: • Lire (age)
• Lire (prix)
• Lire(x, y, A)
Lire(liste de variables)
Note:
- La valeur de cette information est affectée à une variable, dont le nom suit le mot-clé Lire.
- La valeur lue prend le type de la variable à laquelle elle est affectée.
INSTRUCTION D’ÉCRITURE
Définition:
L'instruction d'écriture permet au système d'interagir avec l’extérieur, elle se note avec le mot-
clé Écrire.
Cette instruction permet au système numérique :
• d’afficher une information à destination de l’utilisateur ;
• d’envoyer une commande à un actionneur ;
• d’envoyer des données sur un réseau.
Exemple
Déclaration et syntaxe: • Écrire (“Quel est votre nom ?”)
• Écrire (“Votre prénom est ”, prenom, “.”)
Écrire(liste d'expressions)
Note:
- Après le mot Écrire, on indique ce qui sera transmis. Cela peut être la valeur d'une variable, une chaine ou un
mélange des deux.
RECAP
• Dans le cas où le système est un ordinateur, ce qui sera le cas dans les prochains
exemples, l’information est affichée sur l’écran.
• La valeur écrite doit être de type chaine.
• Plusieurs chaines peuvent être écrites à la suite, en les séparant par des virgules.
• Pour ne pas se tromper sur le rôle de l’instruction lecture et le rôle de
l’instruction écriture, il faut se rappeler que l’algorithme est destiné à être
exécuté par un système numérique. C’est donc le point de vue du système qu’il
faut adopter quand on écrit les instructions.
• Quand le système exécute l’instruction Lire, il récupère ainsi une information.
• Quand le système exécute l'instruction Écrire, il écrit quelque chose à l’écran.
EXERCICE
Enonce:
Écrire un algorithme qui utilise les instructions de lecture et d’écriture. Le
système pour lequel cet algorithme est dédié est un ordinateur. Il demande
à l'utilisateur son prénom et son nom, puis le salue à l'écran.
Solution:
Algorithme : Affichage
variables :
prenom, nom : chaines de caractères
DEBUT
Écrire “Quel est votre prénom?”
Lire prenom
Écrire “Quel est votre nom?”
Lire nom
Écrire “Bonjour ”, prénom,“ ”,nom 30
FIN
EXERCICE
Enonce:
Ecrire un algorithme demande a l'utilisateur de saisir une valeur
numérique, ensuite il affiche la valeur saisie, puis la même valeur
incrémentée de 1.
Solution:
Algorithme : Affichage incrément
variables :
a, b : entier
DEBUT
écrire("Saisissez une valeur numérique")
lire(a)
b a+1
écrire("Vous avez saisi la valeur ", a, ". ")
écrire(a, "+ 1 = ", b) 30
FIN
LES FONCTIONS EN PSEUDO-CODE
Définition:
Une fonction permet de réaliser une tâche complexe, en écrivant un seul mot.
1.Une fonction reçoit aucun, un ou plusieurs arguments, qu’on transmet à la
fonction, et renvoie ensuite un résultat, qui est une valeur.
Déclaration et syntaxe:
Écrire(liste d'expressions)
Note:
EXERCICE
Enonce:
Ecrire un algorithme qui demande à l'utilisateur la longueur et la largeur
d'un rectangle, il calcule l'aire du rectangle, puis il l’écrit sur l'écran.
Solution:
Algorithme : Aire_Rectangle
variables :
longueur, largeur, aire : nombre
DEBUT
Écrire “Quelle est la longueur du rectangle ?”
Lire longueur
Écrire “Quelle est la largeur du rectangle ?”
Lire largeur
aire ← longueur * largeur
Écrire “L'aire du rectangle vaut ”, chaine(aire),“ m2.”
FIN 30
EXERCICE
Enonce:
Ecrire un algorithme qui propose à l’utilisateur de générer un nombre
aléatoire, entre deux bornes choisies par l’utilisateur
Solution:
Algorithme : Affichage incrément
variables :
borneInf, borneSup, nombreAleatoire : nombre
DEBUT
Écrire “Je vais générer un nombre aléatoire entre deux bornes.”
Écrire “Veuillez entrer la borne inférieure.”
Lire borneInf
Écrire “Veuillez entrer la borne supérieure.”
Lire borneSup
nombreAleatoire ← alea(borneInf,borneSup)
Écrire “Le nombre aléatoire est : “,
30
chaine(nombreAleatoire)
FIN
PLUS D’EXERCICES: A VOUS
Définition:
Une fonction personnalisées commence par le mot-clé Fonction, suivi du nom qu’on donne à la
fonction, puis des éventuels arguments de la fonction. Le mot-clé Renvoyer permet de préciser la
valeur que la fonction renvoie. La fonction peut posséder ses propres variables internes.
Exemple
Voici l’écriture d’une fonction qui permet de calculer le cube d’un nombre.
Elle se nomme cube, et prend un seul argument, de type nombre, qu’on
nomme arg. La valeur renvoyée est la variable résultat, de type nombre.
Contenu :
• Types de données fondamentaux (entiers, réels,
caractères).
• Structures de données linéaires (tableaux, listes).
• Structures de données avancées (arbres, graphes).
LES STRUCTURE DE DONNÉES
Définition:
Les structures de données en informatique sont des modèles pour organiser des
données. Elles se divisent en deux types : les types de base comme int et char, et
les types composites comme les tableaux. Ces structures sont essentielles pour
stocker et manipuler efficacement des données.
En Algorithmique:
Les algorithmes sont conçus en fonction de ces structures pour résoudre divers problèmes
informatiques. En résumé, les structures de données sont les fondations sur lesquelles les
algorithmes reposent pour traiter des informations de manière efficace.
LES TYPES DE BASE
Définition:
Les données sont finies : elles ont donc une taille maximale. Par exemple, les tailles
usuelles des variables en C sont les suivantes:
Note:
- ASCII est un système de codage devenu un standard pour transmettre l’information de manière numérique.
ELÉMENTS DE BASE
Entier
C’est le type qui représente des nombres entiers relatifs (int, integer)
Il peut être codé en entier simple sur deux octets ou long sur quatre
octets
Il peut être représenté en décimal (0, - 55…), en hexadécimal (10h,
4Ah…) ou en binaire (% 01001, % 1110)
Réel
Caractère
Il est représenté en code ASCII
Il permet d’avoir une relation d’ordre
Exemple ‘A’ < ‘a’ car en ASCII 65<97 et ‘A’<‘Z’ car en ASCII 65<90
Chaîne de caractère
Elle représente un tableau de caractères
Plusieurs fonctions prédéfinies : Longueur(S) donne la longueur de S
Booléen
Il présente les deux valeurs Vrai et Faux (True and False ou 1 et 0)
ELÉMENTS DE BASE
Constante
Déclaration
Exemple
TYPE STRUCTURÉ
Définition:
Une nouvelle structure regroupant plusieurs variables.
Type structuré = Création d’un nouveau type de
variable = Nom d’un espace en mémoire
Déclaration et syntaxe:
structure date (
entier jour
entier mois
entier annee
)
La structure linéaire enchaîne les actions, les unes après les autres sans
rebouclage ni décision.
S T R U C T U R E S R É P É T I T I V E S : ’’ B O U C L E P O U R ’’