Cours Algorithme PDF : la base de la programmation

Dans ce cours algorithme, nous présentons différentes notions d’algorithme afin de donner envie aux débutants. La maîtrise de l’algorithme est indispensable pour le métier de la programmation.

Cours Algorithme PDF : Initiation et présentation de quelques notions de bases

Dans cette partie nous allons voir des notions variées, un peu en « Vrac » pour vous donner envie et vous encourager à lire le cours.

Cours algorithme : un sous-prgramme ?

Un sous-programme est une partie du programme qui porte

une donné spécifique et qui peut être appelé par ce nom,

selon les besoins, pour exécuter une tâche bien déterminée.

Lorsque les problèmes se révèlent complexes et longs, on

peut utiliser plusieurs sous-programmes différents. Un sous-

programme peut appeler à son tour un sous-sous-programme qui

lui aussi peut appeler un sous-sous-sous-programme et ainsi de

suite.

En programmation, on distingue deux types de sous-

programmes :

Les fonctions qui renvoient des valeurs résultats et qui

peuvent faire partie d’une expression;

– Les procédures qui ne renvoient pas directement des valeurs

résultats et qui ne peuvent pas faire partie d’une expression,

mais qui sont appelées pour réaliser des taches précises.

Objectifs des sous-programmes: rappelons que la méthodologie utilisée à fin de résoudre des problèmes algorithmiquement était de les décomposer en sous problèmes moins compliqués : méthode descendante.
Une des solutions utilisées pour réaliser cela est les sous- programmes.
Les problèmes les plus élémentaires seront représentés par des sous-programmes. 

Algorithme de tri

Trier : c’est ordonner un ensemble d’éléments, c’est-à-dire, les
ranger en ordre croissant ou décroissant :
Tri croissant: si l’élément d’indice I est inférieur ou égal à
l’élément d’indice I + 1,
Tri décroissant: si l’élément d’indice I est supérieur ou
égal à l’élément d’indice I + 1,
Le but du tri est de faciliter l’utilisation d’un ensemble de
données, par exemple pour un algorithme de recherche, fusion
…etc.

TRI INTERNE – TRI EXTERNE.
Un tri interne s’effectue sur des données présentes en mémoire centrale. L’accès aux informations ne prend que peu de temps. Pour évaluer le temps de calcul, on ne considère que le nombre de combinaisons et de permutations. 

TABLEAUX A DEUX DIMENSIONS.

Définition.

Le type de base d’un tableau à une dimension est quelconque, il peut être en particulier de type tableau. On parlera alors d’un tableau de tableau. Ce dernier peut se déclarer de la manière suivante:

Var

T:tableau [T1] de tableau [T3] de T2;

Où:

T : la variable tableau à deux dimensions,

T1: type indice de la première dimension(lignes),

T3:type indice de la deuxième dimension (colonnes),

T2:type de base des éléments du tableau.

Pour simplifier, cette déclaration peut se faire de la manière suivante:

Var

T:tableau [T1,T3] de T2;

Exemple 5:

Var

T:tableau [1..3,1..4] d’entiers;

T sera donc une variable tableau à deux dimensions de 3 lignes et 4 colonnes.

Cours Algorithme : NOTION DE RECURSIVITE

On a vu dans le chapitre précédent qu’un sous-programme peut appeler un autre sous-programme.
Lorsqu’un sous-programme s’appelle lui même, on parle alors d’appel récursif.
La récursivité est donc la capacité d’une procédure ou fonction à s’appeler elle-même. Elle permet de résoudre
beaucoup de problèmes contenant des itérations complexes.
Lorsqu’un algorithme s’appelle lui-même, on parle de récursivité simple ou directe. Mais la récursivité peut être
cachée: lorsqu’un algorithme A appelle un algorithme B et que B appelle ensuite A, on parle alors de récursivité croisée ou indirecte.
Lorsqu’un algorithme s’appelle lui même, il est nécessaire que l’enchaînement des appels successifs connaisse une fin. La suite des actions à exécuter doit être finie : tout algorithme récursif doit contenir une condition qui assure la fin du nombre d’appels. 

Exemple d’algorithmes

Algorithme Tri_Décroissant;

Var

T : tableau[1..100] de réels;

N,ij :entiers;

Aux :réel;

Début

SiN=0 alors

Ecrire(‘le tableau est vide)

Sinon

Pouri<-1àN-1 Faire

Pourj < i+1àN Faire

Si T[i] <T[j] Alors

1

←             Tj];

    Aux;

FinSi

FinPourj

FinPour i

FinSi

Fin

Algorithme Somme_deux_tableau;

Algorithme modification

Algorithme suppression d’un élément d’un tableau

Cet algorithme permet de supprimer, après confirmation, un élément connaissant sa position dans le tableau.

Algorithme Fusion_quelconque

Dans cet algorithme, on va copier les éléments d’un tableau T1 dans un tableau T et à leur suite, on copie ceux d’un autre tableau T2.

On note M : le nombre de cases remplies dans le tableau T2.

Var

T1,T2,T : tableau[1..100] de réels;

N,M,i :entiers;

Si(N=0)et(M=0)alors

Début  Ecrire(‘Les deux tableaux sont vides’)

Sinon

Pouri<-1àN Faire

T1[]

T[]←

Finpour i

Pouri←-1àM Faire

T[N+i] <T2[];

Finpour i

FinSi

Fin

Algorithme :fusion de deux tableaux ordonnés

Dans ce cas les deux tableaux T1 et T2 sont déjà triés par ordre croissant ou décroissant. Le résultat de la fusion doit être un tableau T trié dans le même ordre.
Nous allons utiliser un compteur par tableau i, j, k. On va balayer les deux tableaux T1 et T2 en comparant leurs éléments, le plus petit (ou grand) va prendre sa place dans le tableaux T, puis on avance dans le tableau correspondant et dans le tableau T. Une fois qu’on a épuisé les éléments d’un tableau (T1 ou T2), on recopie le reste des éléments de l’autre tableau dans T.
Dans cet algorithme, on va fusionner deux tableaux triés par ordre croissant.

Var

T1,T2,T3 :  tableau[1..100] de réels;

        N,M,i,j,k,h           :entiers;

Début

Si (N=0) et (M=0) alors

Ecrire(‘Les deux tableaux sont vides’)

Sinon

1;

1;

k         1;

Tantque (i<=N)et(j<= M) Faire

Si T1[i]>T2[j] alors

Sinon

T[k]          T2[0]; j<j  +1;

T[k]<-T1[]; i←-i+1;

FinSi

k<-k+1;

FinTantque

(*on a atteint soit N: la fin du tableau T1 ou M: la fin du tableauT2. Dans le premier cas, il faut compléter par le reste des éléments de T2 qui est (N+M-(k-1)) éléments.Dans le deuxième cas, il faut compléter par le reste des éléments de T1 qui est (N+M-(k-1)) éléments*)

Si i < N alors (*dans ce cas obligatoirement J>M*)

Pour h< iàN Faire

T[k]<T1[h];

k<-k+1;

FinPour h

Sinon (*dans ce cas obligatoirement i>N et j<M*)

Pour h < jà M Faire

T[k]<       T2[h];

k<-k+1;

FinPour h

FinSl

FinSi