Les algorithmes : structure, organisation, arbres...

Résumé du document

En pratique, l'ordinateur (concret ou virtuel) communique au moins par deux périphériques : un pour entrer les données et un autre pour sortir les résultats. Ceux-ci peuvent devenir les données d'entrée d'un autre algorithme et ainsi de suite, mais pour un nombre fini de fois (...)

Extraits

[...] D´emonstration. Par r´ecurrence sur le nombre de nœuds. Si n = l'arbre se r´eduit sa racine qui est une feuille. Si n = c'est que la racine est l'unique nœud int´erieur et poss`ede donc deux fils qui sont des feuilles. Supposons maintenant la propri´et´e vraie pour tout arbre binaire plein de n nœuds int´erieurs et soit un arbre binaire plein de n + 1 nœuds int´erieurs. Choisissons une de ses feuilles et le nœud dont elle est le successeur. Supprimons les deux fils de ce nœud (lequel devient une feuille) et les deux branches qui vont avec. [...]

[...] Pour plus de pr´ecision, nous renvoyons l'annexe 1. La proc´edure trunc() prend en entr´ee un nombre r´eel (ici le r´esultat de la division de a par et renvoie sa partie enti`ere Revenons sur l'algorithme MAX3 ´etudi´e dans la section pr´ec´edente. Il peut ˆetre impl´ement´e en Pascal comme suit : 2 Dans certaines impl´ ementations, lorsque a et b sont entiers, a/b donne le quotient entier de a par rendant inutile l'appel ` a trunc() Algorithmes de l'Arithm´etique ementaire pyl 13 program max3 ; var a,b,c,m : integer ; function max2(x,y :integer) :integer ; begin var if y then max2 x else max2 y ; end ; begin writeln('Calcul du plus grand de trois entiers') ; writeln(' Entrer trois entiers :') ; readln(a, ; m max(a, ; m max(m, ; writeln('max', a : ',', b : ',', c : '=', m : ; end. [...]

[...] Comment reconnaˆıtre dans la matrice f les feuilles de l'arbre ? c. Montrer que si p est la profondeur de l'arbre, I + f + + f p est la matrice triangulaire inf´erieur t dont toutes les composantes sous la diagonale sont ´egales ` a 1 (i.e. ti,j = 1 si i j et ti,j = 0 dans les autres cas). d. Montrer comment reconstruire, ` a partir de f , la matrice des filiations et la matrice d'adjacence associ´ees a l'arbre. [...]

[...] L'ensemble B des branches peut ˆetre donn´e sous plusieurs formes, en fonction de consid´erations th´eoriques, algorithmiques ou informatiques. Tout d'abord, B peut ˆetre d´ecrit tout simplement en extension (liste exhaustive des ´el´ements de ou en compr´ehension (l'ensemble est d´efini par une propri´et´e caract´eristique) ou de bien d'autres mani`eres. La m´ethode qui nous int´eresse ici fait intervenir la notion de matrice d'adjacence (ou encore d'incidence) b du graphe non orient´e constitu´e par l'arbre. Indexons A i.e. A = as } ; par d´efinition, b est une matrice carr´ee d'ordre s de composantes ai,j (i-i`eme ligne, j-i`eme colonne j d´efinies par 1 si {ai , aj } B ; ai,j = 0 sinon. [...]

[...] Elles correspondent l'´ecriture usuelle pour effectuer des calculs sur les nombres. Elles se construisent r´ecursivement comme suit : un nombre est une expression intrafix´ee ; si α et β sont des expressions intrafix´ees, alors (α + β) et (α β) sont des expressions intrafix´ees. Par exemple, l'expression 2 + + qui utilise les r`egles classiques de parenth´esage, est du type intrafix´ee. Il est commode de visualiser la construction de cette exemple au moyen d'un arbre (enracin´e)2 comme indiqu´e sur la figure 9 : les nœuds de l'arbre sont occup´es par des signes d'op´eration et les feuilles (extr´emit´es de l'arbre) sont occup´ees par des nombres. [...]