Principaux paradigmes algorithmiques

Support de cours principaux paradigmes algorithmiques, tutoriel & guide de travaux pratiques algorithmes en pdf.

Arbres enracinés 

Rappel
Un arbre est un graphe non-orienté acyclique et connexe
Définition
Un arbre enraciné(rooted tree) est un arbre avec un sommet distingué.
Le sommet distingué s’appelle laracine (root) de l’arbre.
Définition
Soit T = (V,E) un arbre enraciné au sommetr, x un sommet de T .
• si {y,x} est une arête deT et y est un ancêtre dex, alors y est le père de x, et x est un fils de y.
• la racine de l’arbre n’a pas de père. si x et y ont le même père, alors ils sont frêres.
• un sommet sans fils est un sommet externe ou feuille (leaf). les autres sommets sont les sommets internes
• le nombre de fils d’un sommet x est le degré dex.
Définition
La profondeur du sommet x est la longueur de la chaine entre la racine et le sommet x.
La hauteur (ou profondeur) de l’arbre est :
Max{prof ondeur(x)} x∈V
Les arbres binaires sont définis récursivement.
Définition
un arbre binaire est une structure sur un ensemble fini de sommets.
Il est :
• soit vide (ne contient pas de sommet)
• soit l’union de 3 ensemble disjoints de sommets :
• un sommet appelé racine
• un arbre binaire : le sous-arbre gauche
• un arbre binaire : le sous-arbre droit
La racine d’un sous-arbre gauche non vide est appelé le fils gauche de la racine de l’arbre.
Définition
Soit a un réel non négatif.
bac est le plus grand entier qui est ≤ a.
dae est le plus petit entier qui est ≥ a.
exemples
bπc = 3
dπe = 4
b5c = d5e = 5
notation
log désigne le logarithme en base 2.
Théorème 1
La profondeur d’un arbre binaire à n sommets est au moins blog nc
Preuve
a. A la profondeur l, il y a au plus 2l sommets dans l’arbre.
Parce que : c’est vrai à la profondeur 0, et si c’est vrai à la profondeur l − 1, à la profondeur l il y a au plus 2 fois autant de sommets, donc au plus 2l.
b. Un arbre binaire de profondeur d a au plus 2d+1 − 1 sommets.
Parce que: on somme les sommets selon leur profondeur. et alors : N ombre de sommets ≤ d 2l = 2d+1 − 1  l=0 log n c
c. Soit d la profondeur de l’arbre. On suppose que d < b , alors P  d ≤ blog nc − 1. Il vient que n ≤ 2blog nc − 1 ≤ 2log n − 1 < n ce qui est une contradiction.
Tri 
Input : Une liste de n entiers (a1,a2, . . . ,an)
Output : Une permutation (a01,a02, . . . ,a0n) de la liste d’entrée telle que a01 ≤ a02 ≤ . . . ≤ a0n ou a01 ≥ a02 ≥ . . . ≥ a0n.
Souvent les entiers sont une partie d’une donnée plus complexe, l’entier est alors la cléde la donnée. Et on triera les données d’après les clés.
La structure de donnée est une listeA à n éléments avecA[i] = ai au début etA[i] = a0i à la fin.
L’opération de base pour les algorithmes de tri est la comparaison :
A[i] : A[j], c’est la seule opération permise sur les clés.
Une autre opération estl’échange: on peut échangerA[i] et A[j], ce que l’on note par A[i] ↔ A[j].
Le résultat est alors le suivant :
k := A[i] A[i] := A[j] A[j] = k
Un algorithme de tri est stable s’il préserve l’ordre de départ des éléments avec la même clé.
Un algorithme de tri se fait sur place s’il utilise seulement un nombre constant de variables auxiliaires.

Tri par selection

idée :
On recherche le minimum de la liste et on le met en première position, et on recommence sur la fin de la liste où l’on a ajouté l’élément qui se trouvait en première place.
Après le k-ième placement, les k plus petits éléments de la liste sont à leur place définitive.
Exemple :
Input : 101 115 30 63 47 20
selection de 20
Placement : 20 115 30 63 47 101
selection de 30
Placement : 20 30 115 63 47 101
selection de 47
Placement : 20 30 47 63 115 101
selection de 63
Placement : 20 30 47 63 115 101
selection de 101
Placement : 20 30 47 63 101 115
output : 20 30 47 63 101 115

Procedure TRI-SELECTION

Input :
A : array [1..n] of integer
var i, j, k : integer
begin
i :=1
while i<n do begin { i-ème placement } j:=i
for k:=i+1 to n do
if A[k]<A[j] then j:=k
A[j]↔A[i] { placement du minimum }
end
end
Complexité
• Nombre de comparaisons en itérationi :
(n − i + 1) − 1 = n − i

Comment me contacter?
sylvain.peyronnet@lrde.epita.fr
Structure du cours
• Complexité et algorithmique : définitions
• Principales méthodes de tri
• Structures de données de bases
• Structures de données avancées
• Principaux paradigmes algorithmiques
Support de cours

………