Support de cours algorithmique logique booléenne, tutoriel & guide de travaux pratiques algorithmes en pdf.

Structure de liste

Definitions
Une liste est une suite nie d’elements notee L = (a0 ; a1; . . .; an 1) ou 2 N est la longueur de la liste L et a0, a1 , . . . , an 1 sont le premier, le deuxieme, . . . , le neme objet de L. Lorsque n = 0 la liste ne contient aucun objet, on dit que c’est une liste vide. Le premier element d’une liste est aussi appele t^ete de la liste, et la sous-liste L0 = (a1 ; . . . ; an 1) est la queue de L.
Exemples
{ Coordonnees d’un point dans le plan : L = (x; y). La longueur de L est 2 ; le premier objet est x (abscisse), c’est un nombre reel ; le deuxieme objet est y (ordonnee), c’est aussi un nombre reel.
{ Polygone dans un plan a n sommets : L = (P1 ; . . .; Pn). Le i eme objet est = (x ; y ), un point repere par ses coordonnees. Par exemple la liste :
iii L = (0; 0); (1; 0); (1; 1); (0; 1) represente un carre. Remarquer que les elements de L sont eux-m^emes des listes.
{ Liste des eleves de la classe : chaque objet represente un eleve sous la forme de son nom (cha^ne de caracteres), son prenom (cha^ne de caracteres) et sa moyenne generale (nombre decimal). L’ordre de rangement dans la liste est par exemple l’ordre alphabetique des noms.
{ Liste des termes d’un polyn^ome : chaque objet ti est un couple (a; e) repre-sentant un mon^ome aXe avec a =6 0. Les exposants sont distincts, et les ter-mes sont classes par ordre croissant des exposants. Par exemple le polyn^ome P = X3 X2 + 2 est represente par la liste L = (2; 0); ( 1; 2); (1; 3) .
Remarque : une liste peut contenir plusieurs fois le m^eme objet a des positions differentes, par exemple un point du plan peut avoir deux coordonnees egales.
Operations usuelles sur les listes
{ Creation et initialisation d’une liste.
{ Parcours d’une liste pour e ectuer un m^eme traitement sur chaque element. Par exemple imprimer l’element.
{ Recherche d’un element particulier dans une liste : cet element est speci e par son indice ou une partie de sa valeur. Par exemple dans la liste des eleves de la classe on peut chercher le troisieme dans l’ordre alphabetique, ou celui dont le nom commence par MARTIN. On peut aussi chercher l’eleve ayant la plus forte moyenne generale. Lorsque plusieurs elements de la liste veri ent le critere de recherche, on peut les chercher tous ou seulement le premier ou le dernier.
{ Insertion d’un nouvel element : en debut, en n ou au milieu d’une liste. Si la liste ne doit pas contenir de repetition alors l’insertion peut ^etre precedee d’une recherche de l’element a inserer pour s’assurer qu’il n’est pas deja present dans la liste.
{ Permutation des elements d’une liste pour respecter un nouvel ordre de classement. Par exemple trier les eleves de la classe par moyenne decrois-sante.
{ Concatenation ou fusion de deux listes L1 et L2 : la concatenation produit une liste L constituee de tous les elements de L1 puis tous les elements de L2 ; la fusion produit une liste L0 constituee de tous les elements de L1 et de L2 classes suivant un certain ordre. Pour la fusion on suppose que L1 et L2 sont deja triees suivant l’ordre choisi.
Representation en memoire
Le langage caml de nit trois structures de donnees permettant de representer des listes.
Representation par un n-uplet
La declaration :
let A = (0,0) and B = (1,0) and C = (1,1) and D = (0,1);; let L = (A,B,C,D);; de nit A, B, C, D comme etant des listes a deux elements entiers et L comme etant une liste de quatre elements couples d’entiers. Les listes de nies de cette maniere sont appelees (( n-uplets )) ou n est la longueur de la liste ; elles sont essentiellement utilisees pour grouper plusieurs objets participant a un m^eme traitement, par exemple les deux coordonnees d’un point dans un programme de dessin. Les elements d’un n-uplet ne sont pas necessairement de m^eme type. L’acces aux elements d’un n-uplet se fait en indiquant leur position :
let (_,_,x,_) = L in …
(( selectionne )) le troisieme element de L et le nomme x pour la suite des calculs.
La longueur d’un n-uplet est de nie implicitement par son ecriture.
Representation par un vecteur
Un vecteur est une liste d’objets de m^eme type ranges (( consecutivement )) en memoire.
let V = [| 1.0; 2.0; 3.0; 4.0 |];; declare une variable V de type vecteur reel dont les elements sont V:(0) = 1:0, V:(1) = 2:0, V:(2) = 3:0 et V:(3) = 4:0. La longueur de V est vect length(V) = 4.
La premiere cellule contient la longueur du vecteur, les cellules suivantes contien-nent les elements places par indice croissant. La longueur d’un vecteur n’est pas modi able mais chaque element peut ^etre modi e (( sur place )), c’est-a-dire sans avoir a construire un nouveau vecteur.
Les vecteurs permettent donc de representer des listes de longueur constante, mais on peut aussi les utiliser pour representer des listes de longueur variable en ne (( remplissant )) que le debut du vecteur et en conservant dans une variable a part le nombre d’elements e ectivement presents.
Representation par une liste cha^nee
Une liste cha^nee est une liste d’objets de m^eme type ranges en memoire de maniere non necessairement consecutive. A chaque element de la liste autre que le dernier est associe un pointeur qui contient l’adresse memoire de l’element suivant ; au dernier element est associe un pointeur special marquant la n de la liste.
Le premier element de la liste est hd L = 3 et la queue de la liste est tl L = [1; 4; 1] (hd et tl sont les contractions de head et tail). Le deuxieme element est donc hd(tl L) = 1, le troisieme hd(tl(tl L)) = 4 et ainsi de suite. Dans un programme caml les pointeurs sont representes par l’operateur :: et les declarations suivantes sont equivalentes :
let L = [ 3; 1; 4; 1 ];;
let L = 3 :: [ 1; 4; 1 ];;
let L = 3 :: 1 :: [ 4; 1 ];;
let L = 3 :: 1 :: 4 :: [ 1 ];;
let L = 3 :: 1 :: 4 :: 1 :: [];;
mais : let M = [ 3; 1 ] :: [ 4; 1 ] est interpretee comme la demande de creation de la liste : [ [ 3; 1 ]; 4; 1 ] ce qui provoque une erreur de typage (liste heterogene).
Parcours d’une liste
Soit L = (a0 ; . . .; an 1) une liste. Parcourir L consiste a (( passer en revue )) chaque element ai pour e ectuer un traitement. Par exemple pour conna^tre la longueur d’une liste cha^nee, on la parcourt en incrementant un compteur a chaque element rencontre. De m^eme le calcul de la somme ou du maximum d’une liste de nombres est une operation de type (( parcours )) de la liste.
(* Applique la fonction traitement aux elements du vecteur v *)
let parcours_vect traitement v =
for i=0 to vect_length(v)-1 do traitement(v.(i)) done
;;
(* idem pour une liste cha^nee *)
let rec parcours_liste traitement l = match l with
|[]->()
a::suite -> traitement(a); parcours_liste traitement suite
;;
Les fonctions parcours_vect et parcours_liste sont implementees dans la bibliotheque standard de caml sous les noms do_vect et do_list.
Recherche d’un element dans une liste
Recherche d’un element par son rang et un entier i on veut conna^tre le i eme element Etant donnes une liste L  de L. Cette situation se presente par exemple lorsque L est une table de valeurs d’une fonction f de nie sur les entiers de [[1; n]] : l’element cherche est alors la valeur f(i).
(* recherche dans un vecteur *)
let cherche_vect v i =
if (i <= 0) or (i > vect_length(v))
then failwith « rang incorrect »
else v.(i-1)
;;
(* recherche dans une liste *)
let rec cherche_liste l i =
if (i <= 0) or (l = []) then failwith « rang incorrect »
else if i = 1 then hd l
else cherche_liste (tl l) (i-1)
;;
Comparaison de ces versions : la version (( vecteur )) s’execute en un temps constant tandis que la version (( liste cha^nee )) necessite un temps d’execution environ proportionnel a i (pour i grand). Une liste cha^nee se comporte comme une bande magnetique, il faut derouler la bande depuis le debut jusqu’a la position desiree. De plus le test de non debordement est e ectue a chaque etape dans le cas d’une liste cha^nee car la longueur de la liste n’est pas connue.
Recherche d’un element par sa valeur
Etant donne une liste L on veut savoir s’il existe un ou plusieurs elements de L veri ant une certaine propriete et eventuellement conna^tre ces elements. Considerons par exemple le travail d’un compilateur analysant un texte source. Il tient a jour la liste des identi cateurs deja declares, et doit acceder a cette liste :
{ lors de la declaration d’un nouvel identi cateur pour determiner s’il n’y a pas double declaration ;
{ lors de la compilation d’une expression faisant intervenir une variable pour veri er que cette variable a ete declaree et determiner son type, sa taille et son adresse en memoire.
Dans cet exemple la propriete a veri er est l’egalite du nom de l’identi cateur avec le nom analyse. En principe l’identi cateur cherche gure au plus une fois dans la liste des identi cateurs declares, mais il peut ^etre present plusieurs fois si le compilateur supporte la notion de portee locale des identi cateurs, auquel cas la recherche doit retourner l’identi cateur le plus recemment declare ayant le nom analyse. On peut supposer que la liste des identi cateurs est organisee de sorte que les declarations les plus recentes gurent en debut de liste, donc la recherche doit s’arr^eter sur le premier element convenant en partant du debut de la liste.
(* Recherche si le vecteur v contient un objet convenant, et *)
(* renvoie le premier objet convenant s’il existe, sinon *)
(* declenche l’exception « non trouve ». *)
(* « convient » est une fonction booleenne disant si un objet *)
(* convient. *)
let cherche_vect convient v =
let i = ref 0 in
while (!i < vect_length(v)) & not(convient(v.(!i))) do
i := !i+1
done;
if !i < vect_length(v) then v.(!i)
else failwith « non trouve »
;;
(* idem pour une liste cha^nee *)
let rec cherche_liste convient l = match l with
| [] -> failwith « non trouve »
| a::suite -> if convient(a) then a
else cherche_liste convient suite
;;
Dans les deux versions on examine successivement tous les elements de L jusqu’a en trouver un convenant. Le temps de recherche est donc proportionnel a la position de l’objet trouve ou a la longueur de la liste si aucun element ne convient. Pour une liste (( aleatoire )) de longueur n le temps de recherche est en moyenne de n=2 appels a convient s’il y a un objet convenant, et le temps d’une recherche infructueuse est toujours de n appels a convient.
Insertion et suppression
Inserer un objet x dans une liste L = (a0 ; . . .; an 1) consiste a construire une nouvelle liste L0 contenant l’objet x et tous les elements de L. Il existe plusieurs types d’insertion :
{ insertion en debut de liste : L0 = (x; a0 ; . . .; an 1) ;
{ insertion en n de liste : L0 = (a0 ; . . .; an 1; x) ;
{ insertion apres le i-eme element : L0 = (a0 ; . . .; ai 1; x; ai; . . .; an 1).
La suppression d’un objet est l’operation inverse. Lorsque l’ordre de classe-ment des elements dans L est sans importance on choisit generalement l’insertion et la suppression en debut ou en n de liste car ces positions sont les plus accessi-bles. Par contre si L est une liste triee et si l’on veut que L0 soit aussi triee, alors il faut chercher dans L deux elements consecutifs encadrant x et l’inserer entre ces elements. La suppression dans une liste triee, quant a elle, ne modi e pas le ca-ractere trie. Par ailleurs si L ne doit pas comporter de repetitions il faut s’assurer que x 2= L avant de proceder a une insertion, en employant l’une des methodes de recherche vues precedemment.
Insertion et suppression a une extremite de la liste
let insere_debut_vect v x =
let n = vect_length(v) in
let w = make_vect (n+1) x in
for i = 0 to n-1 do w.(i+1) <- v.(i) done;
w
;;
let supprime_debut_vect v =
let n = vect_length(v) in
if n = 0 then failwith « vecteur vide »
else if n = 1 then [||]
else begin
let w = make_vect (n-1) v.(1) in
for i = 2 to n-1 do w.(i-1) <- v.(i) done;
w
end
;;
(* insere_fin_vect et supprime_fin_vect sont analogues *)
let insere_debut_liste l x = x :: l;;
let supprime_debut_liste l = match l with
| [] -> failwith « liste vide »
_::suite -> suite
;;
let rec insere_fin_liste l x = match l with
| [] -> [x]
a::suite -> a :: (insere_fin_liste suite x)
;;
let rec supprime_fin_liste l = match l with
| [] -> failwith « liste vide »
| [_] -> []
a::suite -> a :: (supprime_fin_liste suite)
;;
Remarquer que les operations (( en n de liste cha^nee )) imposent de parcourir toute la liste pour acceder au dernier element donc elles ont un temps d’execution environ proportionnel a la longueur de la liste tandis que les operations (( en debut de liste cha^nee )) s’executent en temps constant. En ce qui concerne les vecteurs, l’insertion et la suppression modi ent la longueur du vecteur considere et imposent d’allouer en memoire un nouveau vecteur et d’y recopier la partie utile de l’ancien, donc ont un temps d’execution environ proportionnel a la longueur du vecteur initial. Par contre si l’on utilise un vecteur partiellement rempli alors l’insertion et la suppression peuvent ^etre e ectuees (( sur place )) en temps constant si la position d’insertion ou de suppression est l’extremite (( libre )) du vecteur partiellement rempli.

Chapitre 1 Methodes de programmation
1-1 Description d’un algorithme
1-2 Iteration
1-3 Recursivite
1-4 Diviser pour regner
1-5 Exercices
Chapitre 2 Structure de liste
2-1 Denitions
2-2 Representation en memoire
2-3 Parcours d’une liste
2-4 Recherche d’un element dans une liste
2-5 Insertion et suppression
2-6 Exercices
Chapitre 3 Listes triees
3-1 Insertion dans une liste triee
3-2 Recherche dans une liste triee
3-3 Fusion de listes triees
3-4 Tri d’une liste
3-5 Tri a bulles
3-6 Tri par fusion
3-7 Tri rapide
3-8 Exercices
Chapitre 4 Evaluation d’une formule
4-1 Structure de pile
4-2 Representation lineaire d’une formule
4-3 Evaluation d’une formule postxe
4-4 Exercices
Chapitre 5 Logique booleenne
5-1 Propositions
5-2 Circuits logiques
5-3 Synthese des fonctions booleennes
5-4 Manipulation des formules logiques
5-5 Exercices
Chapitre 6 Complexite des algorithmes
6-1 Generalites
6-2 Equation de recurrence T (n) = aT(n ? 1) + f(n)
6-3 Recurrence diviser pour regner
6-4 Exercices
Chapitre 7 Arbres
7-1 Denitions
7-2 Representation en memoire
7-3 Parcours d’un arbre
7-4 Denombrements sur les arbres binaires
7-5 Exercices
Chapitre 8 Arbres binaires de recherche
8-1 Recherche dans un arbre binaire
8-2 Insertion
8-3 Suppression
8-4 Exercices
Chapitre 9 Manipulation d’expressions formelles
9-1 Introduction
9-2 Representation des formules
9-3 Derivation
9-4 Simplication
9-5 Exercices
Chapitre 10 Langages reguliers
10-1 Denitions
10-2 Operations sur les langages
10-3 Appartenance d’un mot a un langage regulier
10-4 Exercices
Chapitre 11 Automates nis
11-1 Denitions
11-2 Simulation d’un automate ni
11-3 Determinisation d’un automate
11-4 Le theoreme de Kleene
11-5 Stabilite et algorithmes de decision
11-6 Langages non reguliers
11-7 Exercices
Problemes

……….