Affichage des articles dont le libellé est informatique. Afficher tous les articles
Affichage des articles dont le libellé est informatique. Afficher tous les articles
Les algorithmes de tri
Chapitre 6
Les algorithmes de tri
Dans ce chapitre on présente quelques algorithmes utiles, qui permettent d'ordonner les éléments d'un tableau dans un ordre croissant ou décroissant. L'ordre est par défaut croissant.
Un vecteur est dit trié si V[i] <= V[i+1], quel que soit i Є [1..n-1]
1. Tri par sélection
1-a) Principe
Utiliser un vecteur VT (vecteur trié) comme vecteur résultat. Celui ci contiendra les éléments du vecteur initial dans l'ordre croissant.
Le principe est de :
0- Chercher le plus grand élément dans le vecteur initial V
1- Sélectionner le plus petit élément dans V
2- Le mettre dans son ordre dans le vecteur VT
3- Le remplacer par le plus grand élément dans le vecteur initial (pour qu'il ne sera plus le minimum)
4- Si le nombre d'éléments dans le vecteur résultat n'est pas identique à celui dans le vecteur initial Retourner à l'étape 1 Sinon on s'arrête.
1-b) Exemple
Soit le vecteur V contenant 4 éléments.
V VT
Schéma de l'algorithme
Au départ 10 15 -1 7 10 15 15 7 -1 10 15 15 15 -1 7 15 15 15 15 -1 7 10 Phase 4 15 15 15 15 -1 7 10 15
ALGORITHME TRI_SELECTION
CONST Bi = 1
Bs = 10
VAR V, VT : Tableau[Bi..Bs] de réel
N, i, j, indmin : entier
MIN, MAX : réel
DEBUT
{Chargement du vecteur V}
…
{Recherche du maximum}
MAX¬V[1]
Pour i de 2 à N
FAIRE
Si MAX < V[i] Alors
MAX¬V[i]
FINSI
FINFAIRE
POUR i de 1 à N-1 FAIRE
{Recherche du minimum}
MIN ¬ V[1]
indmin ¬ 1
Pour j de 2 à N faire
Si MIN > V[j] ALORS
MIN¬V[j]
Indmin ¬ j
Fin si
Fin Faire
{Mettre le minimum trouvé à sa place dans le vecteur résultat}
VT[i] ¬ MIN
V[indmin] ¬ MAX
Fin Faire
VT[N] ¬ MAX
FIN
Peut-on améliorer cet algorithme ?
2. Algorithme de tri par sélection et permutation
Il s'agit ici d'éviter la construction d'un second vecteur et d'utiliser un seul vecteur initial qui sera trié.
Supposons traités n-i (1 <= i < N) éléments du vecteur.
V[1..i] non traité V[i+1..N] Trié
1 i N
On peut considérer le vecteur V comme la concaténation de deux sous-vecteurs : le sous-vecteur V[1..i] dont les éléments n'ont pas encore été triés, et le sous vecteur V[i+1..N] dont les éléments sont triés. D'autre part tous les éléments du sous-vecteur V[1..i] sont inférieurs ou égaux à l'élément V[i+1].
On a donc :
V[1..i] non traité, V[1..i] <= V[i+1], V[i+1..N] Trié
On a deux cas :
· I = 1
(V[1] non traité, V[1]<= V[2], V[2..N] trié) donc V[1..N] trié
L'algorithme est terminé.
· I > 1
Pour augmenter le sous-vecteur V[i+1..n] d'un élément, il suffit de chercher le plus grand élément contenu dans le sous-vecteur V[1..i] et de placer cet élément en position i.
Schéma de l'algorithme
ALGORITHME SLECTION_PERMUTATION
CONST Bi = 1
Bs = 10
VAR V : Tableau[Bi..Bs] d'entier
N, i, j : entier
DEBUT
{Chargement du vecteur V}
…
Pour i de N à 2 Faire
{Recherche de l'indice du maximum dans V[1..i]}
indmax ¬ 1
Pour j de 2 à i
FAIRE
Si V[indmax] < V[j] Alors
indmax ¬ i
FIN SI
FIN FAIRE
{Mettre le maximum relatif trouvé à sa place}
Si indmax <> i Alors
Aux ¬ V[indmax]
V[indmax] ¬ V[i]
V[i] ¬ Aux
Fin Si
Fin Faire
3. Tri par la méthode des bulles
Même principe que le précédent.
Après avoir traité n-i (1 <= i < N) éléments du vecteur.
V[1..i] non traité V[i+1..N] Trié
1 i N
On peut donc considérer le vecteur V comme la concaténation de deux sous-vecteurs : le sous-vecteur V[1..i] dont les éléments n'ont pas encore été triés, et le sous vecteur V[i+1..N] dont les éléments sont triés. D'autre part tous les éléments du sous-vecteur V[1..i] sont inférieurs ou égaux à l'élément V[i+1].
On a donc :
V[1..i] non traité, V[1..i] <= V[i+1], V[i+1..N] Trié
On a deux cas :
· I = 1
(V[1] non traité, V[1]<= V[2], V[2..N] trié) donc V[1..N] trié
L'algorithme est terminé.
· I > 1
Pour augmenter le sous-vecteur V[i+1..n] d'un élément, il suffit de chercher le plus grand élément contenu dans le sous-vecteur V[1..i] et de placer cet élément en position i.
On parcourt le sous-vecteur V[1..i] de gauche à droite et, chaque fois qu'il y a deux éléments consécutifs qui ne sont pas dans l'ordre, on les permute. Cette opération permet d'obtenir en fin du iième parcours le plus grand élément placé en position i, et les éléments après cette position sont ordonnés.
Schéma de l'algorithme
ALGORITHME TRI_BULLE1
CONST N= 10
VAR V : tableau[1..N] de réel
N, i, j : entier
AUX : réel
DEBUT
{Chargement du vecteur}
…
POUR i de N à 2 pas –1 FAIRE
POUR j de 1 à i FAIRE
SI V[j]>V[j+1] ALORS
AUX ¬ V[j]
V[j] ¬ V[j+1]
V[j+1] ¬ AUX
FIN SI
FIN FAIRE
FIN FAIRE
FIN
Application
Exécuter à la main cet algorithme avec les vecteurs suivants :
2 2 -1 3 0 1 Que remarquez-vous ?
1 -1 2 5 13 15
3. Schéma de l'algorithme à bulle optimisé
ALGORITHME TRI_BULLE1
CONST N= 10
VAR V : tableau[1..N] de réel
N, i, j : entier
AUX : réel
DEBUT
{Chargement du vecteur}
…
i ¬ N
atonpermuté ¬ vrai
TANT QUE (atonpermuté) FAIRE
j¬1
atonpermuté ¬ faux
TANT QUE (j < i) FAIRE
DEBUT
SI (V[J+1] < V[j]) ALORS
AUX¬V[J+1]
V[J+1] ¬V[J]
V[J] ¬ AUX
FIN SI
atonpermuté¬vrai
FIN
j¬j+1
FIN
i¬i-1
FIN
FIN
POUR i de N à 2 pas –1 FAIRE
POUR j de 1 à i FAIRE
SI V[j]>V[j+1] ALORS
AUX ¬ V[j]
V[j] ¬ V[j+1]
V[j+1] ¬ AUX
FIN SI
FIN FAIRE
FIN FAIRE
FIN
![V[1..i] non traité](https://www.technologuepro.com/informatique/chap6_algorithme_fichiers/image001.gif){kind=small}
![V[i+1..N] Trié](https://www.technologuepro.com/informatique/chap6_algorithme_fichiers/image002.gif){kind=small}
Traitement des Tableaux
Chapitre 5
Traitement des Tableaux
Rappel
Pourquoi les tableaux ?
1) Calculer la moyenne de 30 élèves
2) Effectuer leur classement
* Réponse
pour i de 1 à 30
faire
Ecrire (" Donner la moyenne de l'étudiant N°",i)
Lire (moyenne)
Fin faire
* Conclusion : On ne peut pas effectuer le classement
Pourquoi ? Parce qu'on ne garde pas les moyennes précédentes et la variable moyenne contient uniquement la dernière valeur.
Utilisation des tableaux
Intérêt Gain de temps, rétrécissement du volume de l'algorithme et possibilité de réutilisation de toutes les valeurs ultérieurement dans l'algorithme.
Il est plus convenable, alors, de définir un espace mémoire qu'on appelle MOY qui sera divisé en 30 parties équitables, indicées de 1 à 30.
MOY
On définit un tableau de 30 cases à une seule dimension qu'on appelle VECTEUR.
Contenu 15 12 5 10 4 50 …. Indice 1 2 3 4 5 6 7 8 9 10 11 12 13
ALGORITHME MOYENNE
CONST Bi=1
Bs=30
VAR T : Tableau [bi..bs] de réel
i : entier
1.1.1. Les vecteurs
Un vecteur est une partie de mémoire contenant n zones variables référencées par le même nom de variable pour accéder à un élément particulier de ce vecteur.
On indice le nom de variable. L'indice peut être une constante, une variable ou une expression arithmétique.
MOY[i]
indice d'un élément du vecteur
variable qui indique le nom du vecteur
MOY[i] : représente l'élément du vecteur MOY occupant le rang " i ".
L'indice peut être :
ATTENTION
- Une constante : MOY[5]
- Une variable : MOY[i]
- Une expression : MOY[i*2]
Avant d'utiliser un tableau, il faut déclarer sa taille pour que le système réserve la place en mémoire, nécessaire pour stocker tous les éléments de ce tableau.
Les éléments d'un même tableau doivent être de même type.
1.2. Rappel de Déclaration d'un vecteur
Dans la partie CONST, on peut définir la taille du tableau. Ensuite, on peut déclarer le nombre d'éléments à saisir dans le tableau.
Remarque : Le nombre d'éléments à saisir ne doit pas dépasser la taille du tableau pour ne pas déborder sa capacité.
On appelle dimension d'un vecteur le nombre d'éléments qui constituent ce vecteur.
1.3.Chargement d'un Vecteur
Le chargement d'un vecteur consiste à saisir les données des éléments du vecteur. (remplir des cases successives du tableau). On doit utiliser une boucle qui permet de saisir à chaque entrée dans la boucle la iième case.
ALGORITHME Vecteur
CONST N = 30
VAR
MOY : Tableau[1..N] de réels
Début
{ chargement du tableau }
Pour i de 1 à N
Faire
Ecrire (" donner la moyenne de l'étudiant N° " , i )
Lire ( MOY [i])
Fin Faire
{ fin chargement }
{Calcul de la somme des moyennes}
SMOY ← 0
Pour i de 1 à N
Faire
SMOY ← SMOY+MOY[i]
Fin Faire
SMOY ← SMOY / 30
Ecrire (" la moyenne du groupe est ", SMOY )
{ calcul de la différence entre la moyenne de groupe et celle de l'étudiant }
Pour i de 1 à N
Faire
Ecrire (" la différence de la moyenne du groupe et celle de l'étudiant ",i , " est= ", SMOY-MOY[i])
Fin Faire
Fin
$ On peut écrire les deux premières boucle en une seule. Simplifier alors cet algorithme.
Remarque
La taille d'un tableau est fixe et ne peut être donc changée dans un programme : il en résulte deux défauts :
Application
- Si on limite trop la taille d'un tableau on risque le dépassement de capacité.
- La place mémoire réservée est insuffisante pour recevoir toutes les données.
1) Charger un vecteur de 10 éléments par les 10 premiers entiers naturels positifs.
2) Charger un vecteur de 10 éléments par les 10 premiers multiples de 7.
1-a) Recherche dans un vecteur
Recherche séquentielle
On peut chercher le nombre d'apparition d'un élément dans un vecteur, sa ou bien ses positions. Pour cela, on doit parcourir tout le vecteur élément par élément et le comparer avec la valeur de l'élément à chercher.
Applications
1. Chercher la position de la première occurrence d'un élément e dans un vecteur V contenant N éléments. (On suppose que le vecteur est définit)
2. Chercher le nombre d'apparition d'un élément e dans un vecteur V contenant N éléments, ainsi que les positions des occurrences de cet élément.
Réponse 1
i ← 1
Trouv ← vrai
Tant que ((i <= N) et (Trouv = vrai))
Faire
Si V[i] = e Alors
Trouv ← Faux
Sinon
i ← i +1
Fin Si
Fin Faire
Si (Trouv = vrai) Alors
Ecrire(e, "se trouve à la position" , i)
Sinon
Ecrire(e, "ne se trouve pas dans V")
Fin Si
Recherche dichotomique
Ce type de recherche s'effectue dans un tableau ordonné.
Principe
1. On divise le tableau en deux parties sensiblement égales,
2. On compare la valeur à chercher avec l'élément du milieu,
3. Si elles ne sont pas égales, on s'intéresse uniquement la partie contenant les éléments voulus et on délaisse l'autre partie.
4. On recommence ces 3 étapes jusqu'à avoir un seul élément à comparer.
Application
On suppose qu'on dispose d'un vecteur V de N éléments. On veut chercher la valeur Val.
ALGORITHME DICHOTHOMIE
...
Inf ← 1
Sup ← N
Trouv ← vrai
Tant que ((Inf <= Sup) et (Trouv = vrai))
Faire
Mil ← (Inf+Sup)DIV 2
Si (V[Mil] = Val) Alors
Trouv ← faux
Sinon
Si (V[Mil] < Val) Alors
Inf ← Mil + 1
Sinon
Sup ← Mil -1
Fin Si
Fin Si
Fin Faire
Si (Trouv = faux) Alors
Ecrire(Val, "existe à la position" , Mil)
Sinon
Ecrire(Val, "n'existe pas dans V)
Fin Si
1.4.2. Les matrices
Les matrices sont les tableaux à deux dimensions.
L'élément d'indice [i,j] est celui du croisement de la ligne i avec la colonne j
4 COLONNES 1 2 3 4 5 1 2 5 3 6 2 4 -5 -1 3 3 7 -6 -3 0 4 5 -2 2 2 5 8 4 10 -9
M[3,2] est -6
Les structures repetitives
Chapitre 4
Les structures repetitives
1.1. Introduction
Dans les problèmes quotidiens, on ne traite pas uniquement des séquences d'actions, sous ou sans conditions, mais il peut être fréquent d'être obligé d'exécuter un traitement (séquence d'actions), plusieurs fois. En effet, pour saisir les N notes d'un étudiant et calculer sa moyenne, on est amené à saisir N variables, puis faire la somme et ensuite diviser la somme par N. Cette solution nécessite la réservation de l'espace par la déclaration des variables, et une série de séquences d'écriture/lecture. Ce problème est résolu à l'aide des structures répétitives. Celles ci permettent de donner un ordre de répétition d'une action ou d'une séquence d'actions une ou plusieurs fois.
1.2. La boucle POUR
Cette structure exprime la répétition d'un traitement un nombre de fois.
Syntaxe
POUR Vc DE Vi A Vf [PAS Vp] FAIRE
<Traitement>
FINFAIRE
Où Vc est une variable entière, qui compte le nombre de répétition du <Traitement>,
Vi la valeur initiale à laquelle Vc est initialisé,
Vf la valeur finale à laquelle se termine Vc,
Vp la valeur du pas, c'est la valeur qu'on rajoute à Vc à chaque fin de traitement.
Remarque
1. La boucle POUR est utilisée lorsqu'on connaît le nombre de répétition du <Traitement> d'avance.
2. La valeur du pas peut être positive ou négative et par conséquent, il faut; au départ de la boucle; que Vi <= Vf ou Vi >= Vf selon la positivité ou la négativité de cette valeur.
3. La valeur du pas est égale à 1 par défaut.
Les étapes d'exécution de la boucle POUR
1) Initialisation de Vc par la valeur de Vi (comme si on avait Vc¬Vi)
2) Test si Vi dépasse (±) Vf (du côté supérieur ou inférieur, selon la positivité ou la négativité du pas). Si oui, alors la boucle s'arrête et l'exécution se poursuit après le FINFAIRE Sinon,
· Exécution du <Traitement>,
· Incrémentation ou décrémentation de Vc par la valeur du pas,
· Retour à l'étape 2.
Application
Ecrire l'algorithme qui permet de saisir les moyennes des N étudiants de la classe Informatique et de calculer la moyenne générale de la classe.
Résolution
Sans les boucles, on est obligé de déclarer N variables, et d'écrire N actions LIRE.
LIRE(note)
S¬ S + MOY
LIRE(MOY)
S¬ S + MOY
…..
LIRE(MOY)
S¬ S + MOY
La boucle POUR donne l'ordre à la machine d'itérer les deux actions N fois.
Donc le compteur varie de 1 jusqu'à N avec un pas de 1.
ALGORITHME MOYENNE
VAR i, N : entier
MOY, MC : réel
DEBUT
ECRIRE("Donner le nombre d'étudiants")
LIRE(N)
SI (N > 0) ALORS
S ¬ 0 {Initialisation de S}
POUR i DE 1 A N FAIRE {Le pas égale 1 par défaut}
ECRIRE("Donner la moyenne de l'étudiant n°", i)
LIRE(MOY)
S ¬ S + MOY {on rajoute la moyenne du iième étudiant à la somme}
FIN FAIRE
MC ¬ S / N
ECRIRE("La moyenne de la classe est : ", MC)
SINON
ECRIRE("Erreur dans le nombre d'étudiants")
FINSI
FIN
Remarque Juste Avant le FIN FAIRE, le changement de la valeur de i se fait automatiquement.
Application 1
Ecrire l'algorithme qui permet d'afficher tous les nombres pairs qui existent entre 1 et 10.
1ière solution
POUR i de 2 à 10 pas 2 Faire
ECRIRE(i)
FINFAIRE
2ième solution
POUR i de 2 à 10 Faire
SI (i mod 2 = 0) ALORS
ECRIRE(i)
FINSI
FINFAIRE
3ième solution
POUR i de 1 à 5 Faire
ECRIRE(2*i)
FINFAIRE
Application 2
Ecrire l'algorithme qui permet d'afficher tous les nombres impairs entre 50 et 100 dans l'ordre décroissant.
POUR i de 99 à 50 PAS (-2) FAIRE
ECRIRE(i)
FIN FAIRE
La valeur finale peut être 50 ou 51 car le test de sortie est i < Vf (49 < 50 ou à 51)
1.3. La boucle Répéter … Jusqu'à
Syntaxe
Répéter
<Traitement>
Jusqu'à (condition d'arrêt)
Cet ordre d'itération permet de répéter le <Traitement> une ou plusieurs fois et de s'arrêter sur une condition. En effet, lorsque la condition est vérifiée, la boucle s'arrête, si non elle ré-exécute le <Traitement>.
Remarques
1. Dans cette boucle, le traitement est exécuté au moins une fois avant l'évaluation de la condition d'arrêt.
2. Il doit y avoir une action dans le <Traitement> qui modifie la valeur de la condition.
Les étapes d'exécution de la boucle Répéter
1) Exécution du <Traitement>
2) Test de la valeur de la <condition d'arrêt>
Si elle est vérifiée Alors la boucle s'arrête
Sinon Retour à l'étape 1.
Application
Ecrire un algorithme qui saisit un nombre pair et qui détermine combien de fois il est divisible par 2. Exemple 8 est divisible 3 fois par 2 (2*2*2).
ALGORITHME PAIR-NBDIV2
VAR N, N2 : entier
DEBUT
{Saisie d'un entier qui doit être pair}
Répéter
ECRIRE("Donner un entier pair")
LIRE(N)
Jusqu'à (N MOD 2 = 0) {condition pour que N soit pair}
{Détermination du nombre de division par 2}
N2 ¬ 0
NB ¬ N
Répéter
NB ¬ NB div 2
N2 ¬ N2 +1
Jusqu'à (NB MOD 2 <> 0) {On s'arrête lorsque NB n'est plus divisible par 2}
ECRIRE(N, "est divisible par 2", N2,"fois")
FIN
1.4. La boucle TANT QUE
Syntaxe
TANT QUE (condition d'exécution)
FAIRE
<Traitement>
FIN FAIRE
Cet ordre d'itération permet de répéter le <Traitement> zéro ou plusieurs fois et de s'arrêter lorsque la condition d'exécution n'est plus vérifiée. En effet, lorsque la condition d'exécution est vérifiée, le <Traitement> est exécuté, si non elle s'arrête.
Les étapes d'exécution de la boucle Répéter
1) Test de la valeur de la <condition d'exécution>
2) Si elle est vérifiée Alors
Exécution du <Traitement>
Retour à l'étape 1.
Sinon Arrêt de la boucle.
Remarques
1. Dans cette boucle, le traitement peut ne pas être exécuté aucune fois, c'est lorsque la condition d'exécution est à faux dés le départ.
2. Les paramètres de la condition doivent être initialisés par lecture ou par affectation avant la boucle.
3. Il doit y avoir une action dans le <Traitement> qui modifie la valeur de la condition.
Application
Ecrire un algorithme qui saisit un nombre pair et qui détermine combien de fois il est divisible par 2. Exemple 8 est divisible 3 fois par 2 (2*2*2).
ALGORITHME PAIR-NBDIV2
VAR N, N2 : entier
DEBUT
{Saisie d'un entier qui doit être pair}
Répéter
ECRIRE("Donner un entier pair")
LIRE(N)
Jusqu'à (N MOD 2 = 0) {condition pour que N soit pair}
{Détermination du nombre de division par 2}
N2 ¬ 0
NB ¬ N
TANT QUE (NB MOD 2 = 0)
FAIRE
NB ¬ NB div 2
N2 ¬ N2 +1
FIN FAIRE {On s'arrête lorsque NB n'est plus divisible par 2}
ECRIRE(N, "est divisible par 2", N2,"fois")
FIN
Ä La condition d'arrêt avec la boucle Répéter est l'inverse de la condition d'exécution de la boucle TANTQUE.
Remarque
Le Traitement d'une boucle peut contenir lui aussi une autre boucle. On l'appelle dans ce cas des boucles imbriquées.
Les structures Conditionnelles
Chapitre 3
Les structures Conditionnelles
1.1.Introduction
Souvent les problèmes nécessitent l'étude de plusieurs situations qui ne peuvent pas être traitées par les séquences d'actions simples. Puisqu'on a plusieurs situations, et qu'avant l'exécution, on ne sait pas à quel cas de figure on aura à exécuter, dans l'algorithme on doit prévoir tous les cas possibles.
Ce sont les structures conditionnelles qui le permettent, en se basant sur ce qu'on appelle prédicat ou condition.
1.2. Notion de PREDICAT
Un prédicat est un énoncé ou proposition qui peut être vrai ou faux selon ce qu'on est entrain de parler.
En mathématiques, c'est une expression contenant une ou plusieurs variables et qui est susceptible de devenir une proposition vraie ou fausse selon les valeurs attribuées à ces variables.
Exemple :
(10 < 15) est un prédicat vrai
(10 < 3) est un prédicat faux
1.3. Evaluation d'une expression logique
Une condition est une expression de type logique. Ils lui correspondent deux valeurs possibles VRAI et FAUX qu'on note par V ou F.
Considérons deux variables logiques A et B. Voyons quels sont les opérateurs logiques et leurs ordres de priorités.
1-a) Notons que
Les opérateurs logiques sont :
- (A = faux) <=> non A
- (A = vrai) <=> A
- La négation : "non"
- L'intersection : "et"
- L'union : "ou"
1-b) Notation et Ordre de priorité des opérateurs logiques
1. non : ¬
2. et : ^
3. ou : v
1-c)
1-d) Tableaux d'évaluations
La négation d'une condition
L'intersection de deux conditions
L'union de deux conditions
Vrai Vrai Faux Faux Faux Faux
Théorème de DE MORGAN
A ou B Vrai Faux Vrai Vrai Vrai Faux Vrai Faux
- ¬(A ^ B) ↔ ¬A v ¬B
- ¬(A v B) ↔ ¬A ^ ¬B
1.4. La structure conditionnelle SI
Syntaxe
SI <Condition> ALORS
<suite d’action(s)-1>
[SINON
<suite d’actions(s)-2>]
FINSI
Format Organigramme
·
La <condition> est un prédicat, qui peut être vrai ou faux, selon les valeurs des paramètres la constituant.
· Si la condition est vérifiée (sa valeur est vrai), c'est la <suite d'actions-1> qui sera exécutée. Ensuite, le système passe à l'exécution juste après le FINSI.· Dans le cas contraire, lorsque la condition n'est pas vérifiée (valeur de la condition est faux), c'est la <suite d'actions-2> qui s'exécute, en cas où celle ci existe (facultative). Si elle n'existe pas, le système passe directement à l'instruction qui suit le FINSI.· Les suites d'actions 1 et 2, peuvent être des actions simples ou même des structures conditionnelles.1-e) Exemple 1
Lire un nombre réel, et dire s'il est positif ou strictement négatif.
ALGORITHME POS-NEG
VAR A : réel
DEBUT
ECRIRE("Donner un nombre ")
LIRE(A)
SI (A < 0) ALORS
ECRIRE(A, " est négatif ")
SINON
ECRIRE(A, " est positif ")
FINSI
FIN
Autrement :
ALGORITHME POS-NEG-1
VAR A : réel
B : logique
DEBUT
ECRIRE("Donner un nombre ")
LIRE(A)
B ¬ (A < 0)
SI (B) ALORS
ECRIRE(A, " est négatif ")
SINON
ECRIRE(A, " est positif ")
FINSI
FIN
Dans cet exemple, on a déterminé uniquement les cas de positivité ou de négativité, et on n'a pas déterminé le cas où A est nulle.
ALGORITHME POS-NEG-NUL
VAR A : réel
DEBUT
ECRIRE("Donner un nombre ")
LIRE(A)
SI (A < 0) ALORS
ECRIRE(A, " est négatif ")
SINON {A >= 0}
SI (A > 0)ALORS
ECRIRE(A, " est positif ")
SINON {A = 0}
ECRIRE (A, "est nulle")
FINSI
FINSI
FIN
1-f) Exemples
1) Ecrire l'algorithme qui permet de déterminer si un entier lu est pair ou impair.
2) Ecrire l'algorithme qui permet de saisir deux nombres A et B et de déterminer si la valeur de A est supérieure, inférieure ou égale à B.
1.5. La structure conditionnelle SELON
Cette structure conditionnelle est appelée aussi à choix multiple ou sélective car elle sélectionne entre plusieurs choix à la fois, et non entre deux choix alternatifs (le cas de la structure SI).
Syntaxe
SELON (sélecteur) FAIRE
Cas <liste de valeurs-1> : <suite d'action (s)-1>
[Cas <liste de valeur-2> : <suite d'action (s)-2>
………. ]
[SINON : <suite d'action (s)-n> ]
FINSELON
Le sélecteur peut être une variable de type scalaire ou une expression arithmétique ou logique.
La structure SELON évalue le "sélecteur", passe à comparer celui ci respectivement avec les valeurs dans les listes. En cas d'égalité avec une valeur, les actions correspondantes, qui sont devant cette valeur seront exécutées.
Devant "Cas", il peut y avoir une seule valeur, une suite de valeurs séparées par des virgules et/ou un intervalle de valeurs.
Après avoir traiter la suite d'actions correspondante, l'exécution se poursuit après le FINSELON.
Remarque
1. Le sélecteur doit avoir le même type que les valeurs devant les cas.
2. Le type de ces valeurs ne doit être, ni réel ni chaîne de caractères.
1-g) Exemple
Ecrire l'algorithme qui permet de saisir un numéro de couleur de l'arc-en-ciel et d'afficher la couleur correspondante : 1: rouge, 2 : orangé, 3 : jaune, 4 : vert, 5 : bleu, 6 : indigo et 7 : violet.
LES ACTIONS ALGORITHMIQUES SIMPLES
Chapitre 2
LES ACTIONS ALGORITHMIQUES SIMPLES
Objectif du cours : Comprendre les actions algorithmiques simples et connaître leurs syntaxes
Éléments de contenu du cours:
- Concepts de base
- La saisie de données
- L'affichage
- L'affectation
- L'évaluation d'une expression arithmétique
1.1. 0. Concepts de base
Dans tout ce qui suit, pour présenter les syntaxes, on suit les règles suivantes :
· Ce qui est entre les crochets est optionnel.
· La suite des points de suspensions "…" veut dire que ce qui précède peut se répéter plusieurs fois.
· Le symbole " | " veut dire : " ou bien ".
· Les mots en majuscule sont des mots réservés.
· Ce qui est entre accolades est un commentaire, pour la lisibilité des algorithmes.
1.2.1. L'affichage : ECRIRE
Cette action permet de communiquer un résultat ou un message sur écran ou sur imprimante pour l'utilisateur.
Syntaxe
ECRIRE(paramètre1 [[,paramètre2]…])
Paramètre = variable | expression | constante
Constante = nombre | message
1-a) Exemples
ECRIRE(" La valeur de 3*2 est égale à ", 3*2)
message expression
ECRIRE(" La moyenne est = ", MOY)
Variable
1.3. 2. La saisie des données : LIRE
L'ordre LIRE permet à l'ordinateur d'acquérir des données à partir de l'utilisateur, dans des cases mémoire bien définies (qui sont les variables déclarées).
Rappel
Les variables sont des cases mémoire, supposées contenir un type de données, nommées par le nom de variable.
Syntaxe
LIRE(variable1 [[, variable2] …])
Remarques :
1. La saisie se fait uniquement dans des variables. Ce sont les cases (cellules) qui pourront accueillir les données correspondantes.2. La donnée à introduire doit être de même type que la variable réceptrice.1.4. 3. Les expressions arithmétiques
Parmi les opérateurs, on distingue les fonctions et les opérateurs.
Les fonctions
· La fonction DIV permet de donner le résultat de la division entière d'un nombre par un autre. 7 DIV 2 = 3
· La fonction MOD (se lit Modulo), permet de donner le reste de la division entière d'un entier par un autre. 7 MOD 2 = 1
· La fonction ** ou ^ permet d'élever un nombre à la puissance d'un autre. 2**3 ®8
Les opérateurs
· Sont le "+", "-", "/", "*" et le "-" un aire.
Ordre de priorité
Les opérateurs suivants sont ordonnés du plus prioritaire au moins prioritaire dans l'évaluation d'une expression arithmétique.
1- Les parenthèses
2- "- " un aire
3- Les fonctions
4- Les opérateurs de multiplication " * " et de division " / "
5- Les opérateurs d'addition " + " et de soustraction " - "
Remarque
Si l'ordre entre les opérateurs dans une expression est le même, on évalue l'expression de gauche à droite.
Exemples3**2+4 = 9+4=13
3**(2+4)=3**6 car les parenthèses sont plus prioritaires
17 MOD 10 DIV 3=(17MOD10)DIV3=7DIV3=2
1.5. 4. L'affectation
C'est l'action de charger une valeur dans une variable. Cette valeur peut elle-même être une variable, le résultat d'une expression arithmétique ou logique ou une constante.
Syntaxe
Variable1 ¬ variable2 | expression | constante
A ¬ B se lit " A reçoit B "
Le résultat de cette action est de mettre le contenu de la variable B dans la variable A. Si B était une expression, elle aurait été évaluée, ensuite sa valeur est transférée dans la variable réceptrice (à notre gauche).
Remarque
L'affectation ne vide pas la variable émettrice (à notre droite) de sa valeur. Par contre, le contenu de la variable réceptrice est écrasé Supposons qu'on ait deux récipients A et B où A contient un liquide coloré en jaune et B contient un liquide rouge.
Peut-on échanger les contenus de A et de B (c.-à-d. mettre le liquide rouge dans A et le liquide jaune dans B).
Résultat
Cette opération n'est possible que si on utilise un troisième récipient qu'on appelle récipient auxiliaire.
Avec des variables réelles, cette opération d'échange de contenu se fait entre cases mémoires qui représentent les conteneurs (récipients).
Problème : Echanger les valeurs de 2 variables numériques.
Principe : pour éviter de perdre l'une des 2 valeurs initiales (A et B), on utilise une 3ième variable pour préserver la valeur initiale de la première variable modifiée.
Remarques ImportantesExemple
- Toute variable utilisée dans un algorithme doit être déclarée au début de l'algorithme, une fois et une seule.
- L'affectation de valeur à une variable peut être effectuée autant de fois que l'on veut au cours d'un algorithme. La valeur de la variable sera alors modifiée à chaque affectation.
- Lorsqu'une variable apparaît en partie droite d'une action d'affectation, c'est que l'on suppose qu'elle contient obligatoirement une valeur. Cette valeur devra lui avoir été affectée auparavant (par initialisation ou saisie), sinon l'on dira que la valeur est indéfinie, et le résultat de l'affectation ne sera pas défini.
- La variable réceptrice d'une affectation doit être de même type que de la valeur à affecter ou de type compatible. Le type est dit compatible s'il est inclus dans le type de la variable réceptrice. Exemple : REEL ¬ ENTIER est possible mais pas l'inverse.
Ecrire l'algorithme qui permet de calculer le discriminant D (delta) d'une équation du second degré.
INTRODUCTION A L'ALGORITHME
Chapitre 1
INTRODUCTION A L'ALGORITHME
Objectif :Ce cours d'informatique Introduction à l'algorithme à pour objectif de faire connaître le but du cours d'algorithmique
Éléments de contenu :
- Qu'est ce qu'une application informatique ?
- Comment arriver d'un problème réel à un programme pouvant être exécuté par ordinateur
- Liens entre ALGORITHMIQUE et STRUCTURES DE DONNEES
Intérêt de l'algorithmique
Informatiser une application, facturation de la consommation d'eau, par exemple, c'est faire réaliser par ordinateur, une tâche qui était réalisée par l'Homme.
Pour faire exécuter une tâche par ordinateur, il faut tout d'abord, détailler suffisamment les étapes de résolution du problème, pour qu'elle soit exécutable par l'homme. Ensuite, transférer la résolution en une suite d'étapes si élémentaire et simple à exécuter, pouvant être codée en un programme dans un langage compréhensible par ordinateur.
Toute suite d'étapes si élémentaire et simple à exécuter s'appelle un ALGORITHME.
Un programme c'est un algorithme codé dans un langage compréhensible par ordinateur à l'aide d'un compilateur (traducteur).
Définitions
L'algorithme est le résultat d'une démarche logique de résolution d'un problème pour la mise en œuvre pratique sur ordinateur et afin d'obtenir des résultats concrets il faut passer par l'intermédiaire d'un langage de propagation.
Un algorithme décrit une succession d'opérations qui, si elles sont fidèlement exécutées, produiront le résultat désiré.
Un algorithme est une suite d'actions que devra effectuer un automate pour arriver en un temps fini, à un résultat déterminé à partir d'une situation donnée. La suite d'opérations sera composée d'actions élémentaires appelées instructions.
1-a) Qu'est ce que l'Algorithmique ?
C'est la logique d'écrire des algorithmes. Pour pouvoir écrire des algorithmes, il faut connaître la résolution manuelle du problème, connaître les capacités de l'ordinateur en terme d'actions élémentaires qu'il peut assurer et la logique d'exécution des instructions.
Les étapes de résolution d'un problème
1. Comprendre l'énoncé du problème
2. Décomposer le problème en sous-problèmes plus simple à résoudre
3. Associer à chaque sous problème, une spécification :
4. Elaboration d'un algorithme.
- Les données nécessaires
- Les données résultantes
- La démarche à suivre pour arriver au résultat en partant d'un ensemble de données.
Structure d'un algorithme
ALGORITHME nom_de_l'algorithme
CONST {Définition des constantes}
TYPE {Définition de types}
VAR {Déclaration de variables}
DEBUT
{Suite d'instructions}
FIN
1-b) Rappel des notions de :
· Constante,
· Type,
· Variable.
1-c) Exemple 1
ALGORITHME afficher
DEBUT
Ecrire("La valeur de 3*5 est ", 3*5)
FIN
Cet algorithme permet d'afficher sur l'écran la phrase suivante :
La valeur de 3*5 est 15
Exemple 2
On veut écrire l'algorithme qui permet de saisir 3 notes d'un étudiant dans trois matières, étant donnés les coefficients respectifs 2, 3 et 1.
Résolution
A partir de l'énoncé du problème, nous recherchons la solution par une démarche en 2 phases.
Pour notre problème, nous connaissons les coefficients et la formule de calcul (åNi*Ci / åCi), nous avons besoins des notes de chaque matière dans l'ordre, et enfin nous pouvons communiquer le résultat à l'utilisateur.
- On doit comprendre comment le résoudre manuellement,
- Définir ce qu'on a besoin comme données, quelles est la démarche à suivre (formules de calcul) pour arriver aux résultats.
ALGORITHME MOYENNE
CONST C1=2
C2=3
C3=1
VAR
N1, N2, N3 : REEL
MOY : REEL
DEBUT
{Affichage message : Invitation de l'utilisateur à introduire des données}
ECRIRE(" Donner trois valeurs réelles "){Saisie des notes}
LIRE(N1, N2, N3){Calcul de la moyenne}
MOY¬ (N1*C1+N2*C2+N3*C3) / le du résultat sur l'écran}ECRIRE(" La moyenne est = ", MOY)FIN
Remarque : Le texte entre les accolades est purement explicatif, il sert à rendre l'algorithme plus lisible.
LES SYSTÈMES D'EXPLOITATION
Ce cours est une introduction aux systèmes d’exploitation. Il est destiné aux étudiants du deuxième niveau option Informatique Industrielle au sein des Instituts supérieurs des études technologiques.
Objectif général :
Comprendre le rôle et le principe de fonctionnement des systèmes d’exploitation et maîtriser les fonctionnalités de gestion des mécanismes de base (fichier, processus, mémoire et périphériques).
Prérequis :
Architecture des ordinateurs, Algorithmique et Programmation procédurale
Objectif général :
Comprendre le rôle et le principe de fonctionnement des systèmes d’exploitation et maîtriser les fonctionnalités de gestion des mécanismes de base (fichier, processus, mémoire et périphériques).
Prérequis :
Architecture des ordinateurs, Algorithmique et Programmation procédurale
PROGRAMMATION ORIENTÉE OBJETS (POO)
Ce cours est conçu comme une introduction aux paradigmes de la programmation orientée objet (POO) . Ilprésente les notions de base de cette technologie : type abstrait de données, classe, objet, héritage simple etmultiple, objet complexe.Mécanisme d’abstraction, surcharge, généricité, polymorphisme. Les conceptsseront illustrés avec le langage JAVA.
Niveaux cibles: Étudiants du niveau 3, toutes filières (Réseaux Informatique, Informatique de gestion, informatique industrielle)
Inscription à :
Articles (Atom)
