:
|
Site: |
Cours VB.net |
|
 1.4 |
Les Algorithmes |
 |
 |
A- Pour écrire un programme.
B- Définition de l'algorithme.
C- Principe généraux
Séquences
Notion de variable
Notion de constante
Affectation
Booléens
Choix
Répétition
Logique: ET, OU, NON
Saut
Programmation structurée
Sous programmes, fonctions
Tableaux
Collections
Pile, Queue
Liste chaînée
Notion de Clé
Hachage
Sécurisation
Flag et variables d'état.
D -Code source, exécutable, interprétation, compilation.
D -Quelques algorithmes.
Recherche dans un tableau
Tri de tableau
A - Pour écrire un programme:
Pour écrire un programme, aller du problème à résoudre à un programme exécutable, il faut passer par les phases suivantes:
Analyse du cahier des charges.
Il doit être clair, exhaustif, structuré.
Analyse générale du problème.
Il existe des méthodes pour professionnels (MERISE, JACKSON..), nous utiliserons plutôt l'analyse fonctionnelle: Le problème global est découpé en sous problèmes nommés fonctions. Chaque fonction ne contient plus qu'une partie du problème. Si une fonction est encore trop complexe, on itère le processus par de nouvelles fonctions à un niveau plus bas.
Cela se nomme la 'Conception structurée descendante'. La 'Conception ascendante' existe aussi: en assemblant des fonctions préexistantes, on résout le problème: attention, il faut que les fonctions préexistantes soient cohérentes. (Pour le moment on ne fait pas de programmation objet)
Analyse détaillée.
Chaque fonction est mise en forme, la logique de la fonction est écrite dans un pseudo langage (ou pseudo code) détaillant le fonctionnement de la fonction. Ce pseudo code est universel , il comporte des mots du langage courant ainsi que des mots relatifs aux structures de contrôle retrouvées dans tous les langages de programmation.
Codage.
Traduction du pseudo code dans le langage que vous utilisez.
Test
Car il faut que le programme soit valide.
Exemple simpliste:
Analyse du cahier des charges.
Création d'un programme affichant les tables de multiplication, d'addition, de soustraction.
Analyse générale du problème.
Découpons le programme en diverses fonctions:
Il faut créer une fonction 'Choix de l'opération', une fonction 'Choix de la table', une fonction 'TabledeMultiplication', une fonction 'TabledAddition', une fonction 'Affiche'...
Analyse détaillée.
Détaillons la fonction 'TabledeMultiplication'
Elle devra traiter successivement (pour la table des 7 par exemple)
1X7
2X7
3X7..
Voici l'algorithme en pseudo code.
Début
Pour i allant de 1 à 10
Ecrire (i*7)
Fin Pour
Fin
Codage.
Traduction du pseudo code en Visual Basic, en respectant la syntaxe du VB.
Sub MultiplicationPar7
Dim i As Integer
For i=1 to 10
Call Affiche(i*7)
next i.
End Sub
Test
Ici il suffit de lancer le programme pour voir si il marche bien..
Pour des programmes complexes, il existe d'autres méthodes.
B - Un Algorithme : c'est quoi?
Un problème est traitable par informatique si :
on peut parfaitement définir les données (entrées) et les résultats (sorties),
on peut décomposer le passage de ces données vers ces résultats en une suite d'opérations élémentaires exécutables.
L'algorithme
détaille, en pseudo code, le fonctionnement de ce passage et en décrit la
logique.
|
Étudions cette logique valable pour tous les langages de programmation (ceux qui sont des langages impératifs):
Pour représenter n'importe quel algorithme, il faut disposer des trois possibilités suivantes:
Exemple d'algorithme principalement composé d'une répétition:
Pour i allant de 1 à 10
Ecrire (i*7)
Fin Pour
Voyons cela en détails:
C - Principes généraux :
Le langage algorithmique et son pseudo-code n'est pas vraiment standardisé, chacun l'écrit à sa manière, aussi vous verrez des notations différentes dans les divers cours d'algorithme. Cela n'a pas d'importance car un programme en pseudo-code ne sera jamais exécuté sur une machine.
L'intérêt de d'étude des algorithmes est didactique: elle permet de comprendre la logique d'un programme totalement indépendamment du langage: ce qui suit est valable en C++, Delphi, Java, Visual Basic, Assembleur...
La séquence:Structure séquentielle d'un programme:
Au sein d'un programme, la structure est généralement séquentielle.
Le code est fait d’une succession de lignes (ou instructions) qui seront lues et traitées les unes après les autres.
Instruction 1
Instruction 2
Instruction 3
..
En VB on peut mettre plusieurs instructions sur la même ligne séparées par ":"
Instruction1 : Instruction2
Les variables, leur 'Type':
Elles contiennent les informations les données nécessaires au déroulement du programme (C'est le même sens qu'en mathématique).
Chaque variable a un Nom (identifiant) et un Type. Ce dernier indique la nature de l'information que l'on souhaite mettre dans la variable:
Un type indique:
La nature des valeurs que peut prendre la variable.
Les opérations possibles.
Exemple: un Type 'Entier' (Integer en VB) correspond au valeur entière, positive ou négative, les opérations possibles sont l'addition, la soustraction, la multiplication...
La nature, le type peut être:
Type numérique:
'Entier'(Integer en VB), 'réel'.. (Single en VB) Exemple d'un entier: 123
Type alphanumérique:
'Caractère' (Char en VB) contient 1 caractère. Exemple d'un caractère: "a" (avec des guillemets)
'Chaîne de caractères',(String en VB), contient plusieurs caractères. Exemple: "toto" (avec des guillemets)
Autres Type:
Booléen (Boolean en VB) ne peut contenir que True ou False ('Vrai' ou 'Faux').
Objet. (Object en VB)
Monétaire (Décimal en VB)
Date (Date en VB)
A partir des types précédents on peut créer des types complexes (ou structurés):
Les tableaux (Array).
Les Collections.
Exemple: la variable nommée 'Total' contient un réel dans un programme de comptabilité.
on remarque qu'il ne faut pas confondre 1 qui est une valeur numérique( sans guillemets) et "1" qui est le caractère '1' (avec des guillemets).
Utilisation des variables:
Les variables numériques serviront à faire des calculs:
Les variables alphanumériques, les chaînes de caractères, serviront entre autres à afficher du texte.
Comment afficher les résultats de calcul?
On apprendra à transformer des variables numériques en variables alphanumériques.
Déclaration:
Pour utiliser une variable, il faut qu'elle existe, il faut donc la créer, on dit il faut la déclarer:
Dans un algorithme: Variable A en Numérique 'crée une variable nommée A et de Type Numérique.
En VB: Dim A As Integer 'crée une variable nommée A et de Type Integer.
On peut aussi initialiser une variable c'est à dire définir sa valeur initiale.
On peut utiliser un littéral: c'est une donnée utilisée directement: sa valeur est écrite directement dans le code.
X <- 2 veut dire: donner à la valeur X la valeur 2 ( 2 est une littéral)
En VB: X = 2
Constante:
Comme une variable, une Constante a un Nom (identifiant) et un Type. Elle contient une valeur: un nombre, une chaîne de caractères..
Son contenu ne peut pas être modifié.
Constante A en Numérique =12
En VB: Const A As Integer =12
Ensuite on ne peut pas modifier sa valeur, on ne peut que la lire.
Affectation ( ou Assignation):
C'est une instruction consistant à donner une valeur à une variable.
En langage algorithmique on l'indique par '<-'
X <- 2 veut dire: donner à la valeur X la valeur 2 ( 2 est une littéral)
Z <- X veut dire: donner à la variable Z la valeur de la variable X .
Z <- X+1 veut dire: donner à la variable Z la valeur de la variable X à laquelle on ajoute 1 (Z prendra la valeur 2+1 =3).
Cela revient à évaluer l'expression de droite et à en mettre la valeur dans la variable de gauche.
En VB le signe d'affectation est '=' on écrit donc:
Z=X+1
Attention ce n'est pas le même sens qu'en mathématique.
Exemple Visual Basic: A=B
Attention ce n'est pas une égalité mais une affectation.
L'affectation ne marche que si le type de variable est le même:
Variable A en Numérique
Variable B en Numérique
B<-12
A<-B 'fonction B contient 12, on met 12 dans A
En VB:
Dim A As Integer
Dim B As Integer
B=12
A=B
Si on écrit:
Variable A en Numérique
Variable B en Alphanumérique
B<-'toto'
A<-B 'cela ne fonctionne pas car on tente de mettre le contenue de B qui est alphanumérique dans une variable numérique.
L'affectation sert à effectuer des calculs:
Variable A en Numérique
A<-3+4-2 'L'expression à droite est évaluée et son résultat est affecté à la variable A.
En VB: A= 3+4-2
Ici les + - sont des opérateurs; il y en a d'autres: * (multiplier) / (diviser)....
Les booléens:
On a parfois besoin de savoir si une assertion est vraie ou Fausse.(True ou False)
Pour stocker une information de ce type, on utilise une variable de type booléen. Une variable de ce type ne peut contenir que True ou False.
Le terme booléen vient de "l'algèbre de Boole", cette algèbre ne travaille que sur les valeurs 1 ou 0 (True ou False)
Soit B une variable booléenne:
On peut écrire B<-True (B=True en VB)
On peut aussi tester cette variable:
Si B=False alors
En VB: If B=False Then..
L'expression après Si est évaluée, si elle est vraie 'alors' se produit.
Autre exemple:
Si C=2 alors.. (If C=2 Then ..en VB)
L'expression C=2 est évaluée, si C est effectivement égal à 2, C=2 est évalué et prend la valeur True; dans ce cas le programme se poursuit après Then.
si C est différent de 2, C=2 est évalué et prend la valeur False; dans ce cas le programme ne se poursuit pas après Then.
Les choix: Si..Alors
Le programme doit pouvoir choisir parmi deux ou plusieurs possibilités en fonction d’une condition :
Si Condition Alors
Action 1
Sinon
Action 2
Fin Si
Si Condition est vraie Action 1 est effectuée, sinon Action 2 est effectué.
Parfois il n’y a pas de seconde branche :
Si Condition Alors
Action 1
Fin Si
ou sur une seule ligne:
Si Condition Alors Action 1
Il peut y avoir plusieurs conditions imbriquées :
Si Condition 1 Alors
Si Condition 2 Alors
Action 1
Sinon
Action 2
Fin Si
Sinon
Action 3
Fin Si
Noter bien le retrait des lignes de la seconde condition afin de bien visualiser la logique du programme :
Action 2 est effectuée si la Condition 1 est remplie et la Condition 2 n’est pas remplie.
En VB cela correspond à l’instruction IF THEN
If Condition 1 Then
Action 1
Else
Action 2
End If
Remarque sur les conditions
Une condition contient 2 valeurs et un opérateur:
Si C>2 Alors est correcte.
Si B=3 Alors est correcte.
Si B>2 Et B<7 Alors est correct (If B>2 And B<7 Then en Visual Basic)
Exemple: Trouver le plus grand nombre entre x et y et le mettre dans max
Variable x en Numerique
Variable y en Numerique
Variable max en Numerique
Si x>y Alors
max<-x
Sinon
Max<-y
Fin Si
En VB
Dim x As Integer
Dim y As Integer
DIm max As Integer
if x>y Then
max=x
else
max=y
End if
Les choix: Sélectionner (Décider entre) :
Il est parfois nécessaire d’effectuer un choix parmi plusieurs solutions :
On parle de sélection :
Sélectionner.
Le cas : condition 1
Action 1
Le cas : condition 2
Action 2
..
Les autres cas
FinSélectionner
Si la condition 1 est remplie Action 1 est effectuée puis le programme saute après FinSelectionner.
Si la condition 1 n’est pas remplie, on teste la condition 2..
Si aucune condition n’est remplie on saute à Les autres cas, on effectue Action 4.
On parle parfois de Décider Entre dans certains cours d'algorithme.
En VB cela correspond à
Select Case Valeur
Case condition 1
Action 1
Case condition 2
Action 2
..
Case Else
Action 4
End Select
Si Valeur=Condition 1 Action 1 est effectuée, si Valeur=Condition 2 Action 2 est effectuée...
Les répétitions: Pour...Répéter
Permet de répéter une séquence un nombre de fois déterminé :
Le cas le plus classique est :
Pour I variant de 0 à N Répéter
Action
FinRépéter
I prend la valeur 0, 'Action' est effectuée,
puis I prend la valeur 1, Action est effectuée,
puis I prend la valeur 2..
cela jusqu'à N
La boucle tourne N+1 fois (car ici on commence à 0 )
Cela se nomme une itération.
Intérêts?
Au lieu de faire
Afficher (1*7)
Afficher (2*7)
Afficher (3*7)
Afficher (4*7)
...
on remarque qu'un élément prend successivement la valeur 1, 2, 3, ..
Une boucle peut faire l'itération:
Pour i allant de 1 à 10 Répéter
Affiche (i*7)
Fin répéter
La variable dite 'de boucle' prend bien les valeurs 1 puis 2 puis 3.. ; elle est utilisée dans le corps de la boucle.
Une instruction Sortir permet de sortir prématurément de la boucle.
En VB
For i=0 To N
..
Next i
L'instruction Exit For permet de sortir prématurément de la boucle.
On peut aussi boucler en parcourant tous les éléments d’une collection.
(Une collection est une liste d'objets, liste de taille variable en fonction de ce qu'on ajoute ou enlève.)
Pour Chaque élément de la liste
Action
Fin Pour
En VB :
For each… In
Next
Les répétitions: Tant que :
Permet de faire une boucle sans connaître le nombre d’itérations à l’avance.
Tant Que Condition
Action
Fin Tant Que
L’action qui est dans la boucle doit modifier la condition afin qu’à un moment ‘Tant que’ ne soit pas vérifié et que l’on sorte de la boucle. Sinon la boucle tourne sans fin.
Pour plus cadrer avec la réalité :
Faire tant que condition
Action
Boucler
En VB :
Do while Condition
Action
Loop
Il existe une boucle équivalente :
Répéter
Action
Jusqu’à Condition
En VB :
Do
Action
Loop Until Condition
Une instruction Exit Do permet de sortir prématurément de la boucle.
Logique: ET, OU, NON:
Une condition contient 2 valeurs et un opérateur:
Si C>2 Alors est correcte.
Si B=3 Alors est correcte.
Si 2<B<7 Alors est incorrecte car il y a 2 opérateurs, il faut dans ce cas utiliser plusieurs conditions et des opérateurs logiques:
Si B>2 Et B<7 Alors est correct (If B>2 And B<7 Then en Visual Basic)
La condition est évaluée:
Exemple : Soit l'expression Si C>2 Alors , elle sera évaluée; si C contient 3, C>2 est vérifié donc Vrai.
ET:
On a vu Si B>2 Et B<7 Alors
Il existe aussi:
OU:
Si B>2 Ou B<7 Alors
Et
NON:
Si NON(B>2) Alors est équivalent à Si B<=2 Alors
En VB on utilise les termes AND OR NOT.
En VB: If Not(B>2 Then..
Saut:
Aller à
Permet de 'sauter' vers un label (une étiquette= un endroit du code)
Exemple:
Variable A en Numérique
Variable B en Numérique
Variable C en Numérique
B<-12
A<-B
Aller à Poursuivre
C<-1
Étiquette Poursuivre
A<-A+1
Le programme saute de Aller à Poursuivre à Étiquette Poursuivre, il n'exécute pas C<-1
En VB on utilise GoTo.
monetiquette:
Goto monetiquette
Programmation structurée:
Avant on écrivait:
Variable A en Numérique
Variable B en Numérique
Variable C en Numérique
B<-12
A<-B
Si A=B Aller à Poursuivre1
C<-1
Étiquette Poursuivre1
Si A<>B Aller à Poursuivre2
C<-2
Étiquette Poursuivre2
On faisait des sauts dans tous les sens!! Code illisible, non structuré.
Maintenant on structure et on n'utilise pas de 'Aller à'.
Variable A en Numérique
Variable B en Numérique
Variable C en Numérique
B<-12
A<-B
Si A=B Alors
C<-1
Sinon
C<-2
Fin Si
'Procédure':
On a déjà vu cette notion.
Une procédure est un ensemble d'instructions référencée par un nom et dont l'exécution est provoquée par le simple énoncé de ce nom.
Quand on appelle une procédure, le logiciel ‘saute’ à la procédure, il effectue celle-ci puis revient effectuer ce qui suit l’appel.
En algorithmie, une procédure commence par le mot Proc et se termine par End Proc.
|
Instruction 1 Instruction 2 MaProcédure()3 Instruction 4 Instruction 5
|
 |
Proc MaProcédure Instruction 10 Instruction 11 End Proc |
Le programme effectuera les instructions 1, 2, 3, 10, 11, 4, 5.
Une opération complexe peut être découpée en plusieurs procédures ou sous-programmes plus petits et plus simples qui seront appelés.
Chaque procédure résout un problème.
Si dans un programme il y a des suites
d'instructions qui effectuent la même action, cela plusieurs fois, on peut
créer une procédure contenant la suite d'instructions; elle sera appelée de
plusieurs endroits du programme.
On peut fournir aux procédures des paramètres, ce sont des variables qui seront transmises à la procédure.
Exemple:
Création d'une Procédure 'MaProcédure' recevant 2 paramètres:
Proc MaProcédure(paramètre1, paramètre2)
..
End Proc
Exemple d'appel de la procédure 'Maprocédure' en envoyant 2 paramètres:
MaProcédure(premierparamètre, secondparamètre)
Exemple : si j'écris MaProcédure(2,3)
dans la procédure MaProcédure paramètre1=2 et paramètre2=3.
Il est nécessaire de définir le type des paramètres:
Proc MaProcédure(paramètre1 En Integer, paramètre2 En Integer) indique que la procédure attend 2 entiers.
Il y a 2 manières d’envoyer des paramètres :
Par valeur : (By Val)c’est la valeur, le contenu de la variable qui est envoyé.
Par référence :(By Ref) c’est l’adresse (le lieu physique où se trouve la variable) qui est envoyée. Si la Sub modifie la variable, cette modification sera visible dans la procédure appelante après le retour.
Parfois on a besoin que la procédure appelée retourne une valeur dans ce cas il faut créer une fonction:
Function MaFonction() En Integer 'MaFonction qui retourne un entier
..
Retourne Valeur
End Function
Pour appeler la fonction:
ValeurRetournée = MaFonction()
Donc ValeurRetournée est aussi un entier
Exemple de fonction: créer une fonction qui retourne le plus petit nombre:
Fonction Minimum (x en Numerique, y en Numérique) en numérique
Si x<y Alors
Retourner x
Sinon
Retourner y
Fin Si
Fin Fonction
Pour l'utiliser:
Variable Min en Numerique
Min<-Minimum (5,7) 'Appelle la fonction en donnant les 2 paramètres 5 et 7.
Min contient maintenant 5
Et VB les sous-programmes (ou procédures) sont des Sub(procédures) ou des Function. Pour appeler une procédure on utilise Call NomProcedure() ou NomProcedure()
En Vb
Function Minimum(x As Integer, y As Integer) As Integer
If x<y Then
Return x
Else
Return y
End If
End Function
Pour l'utiliser:
Dim min As Integer
Min= Minimum (5,7)
La fonction résout un problème et plus
précisément à partir de données, calcule et fournit un résultat.
Notion de 'tableau':
Un tableau de variables permet de stocker plusieurs variables de même type sous un même nom de variable, chaque élément étant repéré par un index ou indice.
C'est une suite finie d'éléments.
Soit un tableau A de 4 éléments
|
3 |
|
12 |
|
4 |
|
0 |
Pour accéder à un élément il faut utiliser l'indice de cet élément.
L'élément d'index 0 se nomme A[0] et contient la valeur 3.
On remarque que le premier élément est l'élément d'index 0 (ZERO) en .Net.
L'élément d'index 1 se nomme A[1] et contient la valeur 12.
Quand on crée un tableau, il a un nombre d'éléments bien défini: 4 dans notre exemple d'index 0 à 3.
Pour donner une valeur à un des éléments , on affecte la valeur à l'élément.
A[2] <- 4
Pour lire une valeur dans un tableau et l'affecter à une variable x:
x <- A[2]
Traduction en VB
A(2)=4
x = A(2)
Pour parcourir tous les éléments d'un tableau on utilise une boucle:
Exemple: afficher tous les éléments du tableau tab qui contient n éléments.
début
Pour i allant de 0 à n-1 Répéter
écrire(tab[i])
Fin Répéter
fin
En VB:
For i=0 to n-1
Affiche ( tab(i)) 'routine d'affichage
Next i
Il existe des tableaux multidimensionnels avec plusieurs index:
Voyons les index de chaque élément:
| B(0,0) | B(0,1) | B(0,2) |
| B(1,0) | B(1,1) | B(1,2) |
| B(2,0) | B(2,1) | B(2,2) |
B[1,0] désigne l'élément rouge (ligne 2, colonne 1).
Voyons par exemple, le contenu de chaque élément:
| 3 | 12 | 0 |
| 18 | 4 | 5 |
| 2 | 2 | 8 |
Ici B[1,0] =18
Notion de 'Collection':
Une collection permet de stocker plusieurs variables ou objets, chaque élément étant repéré par un index ou indice.
Soit la collection Col, au départ elle est vide.
J'ajoute des éléments (ou items) à cette collection.
Col.Ajouter ("Toto")
Voici la collection:
|
Toto |
La collection a maintenant 1 élément.
Col.Ajouter("Lulu")
Col.Ajouter("Titi")
|
Toto |
|
Lulu |
|
Titi |
La collection a 3 éléments maintenant.
Col.Retirer(2) enlève l'élément numéro 2
|
Toto |
|
Titi |
La collection n'a plus que 2 éléments maintenant.
On voit que le nombre d'éléments n'est pas connu à l'avance, il varie en fonction des éléments ajoutés (ou retirés)
Un élément est repéré par un indice.
En VB
Col.Add 'Ajoute un élément
Col.Remove 'Enlève une élément
Il existe des collections avec des clés permettant de retrouver la valeur d'un élément rapidement.
Pile et Queue:
Un type pile ( ou stack) est LIFO (Last In, First Out)
Dernier entré, premier sortie.
Ce type de stack (pile) est très utilisé en interne par les programmes informatiques: on stocke dans une stack les adresses de retour des procédures appelées, au retour on récupère l'adresse du dessus.
Push insère un objet en haut de la pile
Pop enlève et retourne un objet en haut de la pile
On peut utiliser une pile dans un programme pour gérer le déplacement de l'utilisateur dans un arbre, les éléments en cours sont stockés par Push, pour remonter en chemin inverse, on Pop.
'Queue' de type FIFO (First In, First Out)
Premier arrivé premier servi.
C'est la queue devant un cinéma, le premier arrivé, prend son billet le premier.
Les éléments stockés dans Queue sont insérés à une extrémité et extrait, supprimés à l'autre.
Le nombre d'élément de la queue est géré automatiquement.
Généralement on à les possibilités suivantes:
DeQueue supprime et retourne l’objet de début de liste
EnQueue ajoute un objet en fin de liste
Peek retourne l’objet de début sans le supprimer
Liste Chaînée:
Une liste chaînée est une liste d'éléments non classée. Dans chaque enregistrement il y a, outre le contenu de l'enregistrement, la localisation, l'adresse, l'index de l'enregistrement précédent et de l'enregistrement suivant.
Ainsi on peut parcourir la liste en allant d'enregistrement en enregistrement. il existe des algorithmes pour ajouter ou supprimer un enregistrement. La liste peut être ouverte ou fermée (le dernier enregistrement bouclant sur le premier).
Notion de Clé:
Quand on classe une série importante de données, on peut utiliser la notion de clé/Valeur (Key/Value).
Ici on utilise comme clé le numéro du département et comme valeur, le nom du département.
Si on a la clé, on peut retrouver la valeur correspondante.
Autre exemple: La clé peut être le nom, prénom.
Notion de Hachage:
Une fonction de hachage est une fonction qui fait subir une succession de traitements à une donnée fournie en entrée pour en produire une empreinte servant à identifier la donnée initiale.
Donnée d'entrée=> Fonction de hachage => Empreinte.
Le résultat d'une fonction de hachage peut être appelé selon le contexte empreinte, somme de contrôle (dans le cas de la CRC), résumé, condensé, condensat ou encore empreinte cryptographique (dans le cadre de la cryptographique). On l'appelait aussi autrefois aussi signature.
Les fonctions de hachage sont utiles en cryptographie où elles sont utilisées pour chiffrer une donnée initiale.
Mot de passe: "GftUi6h77"=> Fonction de hachage => Empreinte: "4587213399545684246847"
C'est l'empreinte qui va être enregistrée. Quant l'utilisateur rentre le mot de passe, on le 'hache" et on compare l'empreinte du mot de passe tapé par l'utilisateur avec l'empreinte enregistrée pour voir si le mot tapé est bon. Ainsi a aucun moment le mot de passe est en clair.
Ces fonctions sont très utilisées pour accéder rapidement à une donnée contenue dans un grande nombre de données.
Ceci grâce aux tables de hachage (ou hash tables en anglais).
Un exemple classique et simpliste de fonction de hachage est la fonction modulo n : Si on dispose d'un grand nombre de données, à mettre dans un tableau de n cases, on pourra ranger l'élément numéro i dans la case i modulo n. Ainsi, pour aller chercher notre donnée, nous n'avons plus besoin de parcourir tous les éléments jusqu'à trouver l'élément i : Il suffit de parcourir les éléments contenus dans la case i modulo n. Si les données initiales étaient réparties uniformément, le temps de recherche en moyenne est divisé par n. En pratique, on utilise des fonctions de hachage bien plus complexes.
Le hachage est un nombre qui permet la localisation des éléments dans une table.
Exemple:
Nous avons une série de noms et adresses, on veut rapidement trouver l'adresse correspondant à un nom sans avoir à faire une boucle qui compare le nom cherché avec chaque élément du tableau pour le trouver.
Pour chaque nom la fonction de hachage, va créer un numéro (empreinte).
On crée des enregistrements indexée par le dit numéro (empreinte), chaque enregistrement contenant l'adresse.
Si maintenant on cherche un nom, on calcul son empreinte, ce qui nous donne l'index de l'enregistrement que l'on trouve rapidement.
Si la fonction de hachage est uniforme, cela veut dire que pour des entrées différentes, il n'y a jamais la même empreinte. Ce qui est la plupart du temps impossible.
Deux noms peuvent donc donner la même empreinte parfois (on parle de collision). Dans ce cas, on range les enregistrements ayant la même empreinte les uns à la suite des autres (sous forme de liste chaînée). Si le premier enregistrement n'est pas le bon, on regarde le suivant.
Erreur d'exécution: Notion de 'Sécurisation' du code:
Des instructions doivent protéger certaines parties du code afin d'éviter d'effectuer des opérations incohérentes.
Si l'utilisateur entre 2 nombres X et Y et qu'une instruction exécute Z<=X/Y , alors que Y=0 ,la division par 0 étant impossible, le logiciel 'plante': Il s'arrête et donne un code d'erreur(du genre 'Erreur division par 0 interdite').
Il s'agit d'une 'Erreur d'exécution'.
En VB on dit que X/Y 'lève une exception'.
Il appartient au programmeur, une fois l'algorithme écrit, de le sécuriser: Des instructions doivent protéger certaines parties du code afin d'éviter d'effectuer des opérations incohérentes.
- On peut donc prévoir l'erreur et ajouter un contrôle avant l'exécution de la ligne :
Si Y est différent de 0 alors on effectue la division.
Si Y<>0 Alors
Z<=X/Y
Sinon
...
Fin Si
En VB:
If Y<> 0 Then
Z= X/Y
End If
- L'autre solution est de mettre en place un système de surveillance de l'exécution du code qui, s'il se produit une erreur, fait poursuivre le code à un endroit ou il sera géré.
Notion de Drapeau ou 'Flag' et de variable d'état:
Un Flag (ou drapeau) est une variable utilisée pour enregistrer un état, la valeur de cet état servant à déclencher ou non des actions. C'est une manière de retenir qu'un évènement s'est produit.
Si le drapeau est abaissé, les voitures roulent..
Exemple: Utiliser un Flag pour sortir d'une boucle:
On utilise flagSortir.
flagSortir=Faux
Tant que flagSortir =Faux
Si on doit sortir de la boucle, on met la valeur de flagSortir à Vrai
Boucler
En VB:
flagSortir=Faux
Do while flagSortir =Vrai
Si on doit sortir de la boucle, on met la valeur de flagSortir à Vrai
Loop
Tant que flagSortir =Faux la boucle tourne.
On peut généraliser cette notion en parlant de variable d'état.
Un variable d'état sert à décrire l'état du programme.
Exemple:
fileIsOpen est une variable indiquant si un fichier est ouvert ou fermé.
D - Interprétation, compilation :
Tout langage doit obligatoirement être traduit en langage machine (le langage du processeur) pour que ce programme soit exécutable.
Le VB.Net est un langage compilé.
Le code source est dans des fichiers '.vb' et l'exécutable un un '.exe'. On verra que dans l'environnement de développement vb présente les avantages d'un langage interprété (exécution pas à pas, modification du source en cours de débogage...) On peut aussi créer une exécutable autonome.
Les choses sont plus complexes car en vb , entre le source et l'exécutable il y a un code 'intermédiaire'.
E - Quelques algorithmes :
Recherche dans un tableau.
Soit un tableau A() de 4 éléments
|
3 |
|
12 |
|
4 |
|
0 |
Je veux parcourir le tableau pour savoir s'il contient le chiffre '4'.
Il faut faire une itération afin de balayer le tableau: la variable dite de boucle ( I ) va prendre successivement les valeurs: 0 ,1 ,2 ,3. (Attention: dans un tableau de 4 éléments, l'index des éléments est 0,1,2,3)
Pour I variant de 0 à 3 Répéter
..
FinRépéter
Dans la boucle il faut tester si la valeur de l'élément du tableau est bien la valeur cherchée.
Pour I variant de 0 à 3 Répéter
Si A(I)= 4 Alors..
FinRépéter
Si on a trouvé la bonne valeur, on met un flag (drapeau) à Vrai.
flagTrouvé<-Faux
Pour I variant de 0 à 3 Répéter
Si A(I)= 4 Alors flagTrouvé<-Vrai
FinRépéter
Ainsi si après la boucle flagTrouvé= Vrai, cela veut dire que le chiffre 4 est dans le tableau.
En VB
flagTrouve=False
For I=0 To 4
If A(I)=4 Then flagTrouve=True
Next I
Si le tableau était trié dans l'ordre croissant des nombres, on pourrait faire notre recherche plus rapidement: