Cours de mathématiques discrètes

Informations

• Publié par: Obbi
• Nombre de lectures: 21
• Langue: Français

Extrait

p
?

{
p
?


@


@


p



q





?

?


p
q


q






q

p

?








q
@
p
?
q

Cours de Mathematiques discretes
7 novembre 2010
1 Rappels sur les recurrences
1.1 recurrences lineaires
De nition 1. 1. recurrences lineaires homogenes a coe cients constants : n;n k 0,
u a u ::: a u ;n 1 n 1 k n k
2. recurrences lineaires non homogenes a coe cients constants : n;n k 0,u a un 1 n 1
::: a u b n ;k n k
3. recurrences lineaires a coe cients variables : n;n k 0, u a n u :::n 1 n 1
a n u b n ;k n k
Exemple 1. 1. Nombre de comparaison dans une recherche dichotomique pour un tableau trie
mde longueur n 2 : t t 1 et t 1.n n 2 1
resolution inuitive et demonstration par recurrence : t d m 1 m 1 log n .n 1 2
2. La suite de Fibonacci f f f et f f 1 et g g g 1 (cf. AVL etn n 1 n 2 2 1 n n 1 n 2
hauteur).
Resolution par polyn^ ome caracteristique : marche pour les recurrences du typeu aun n 1
2bu qui a pour polyn^ ome caracteristique x ax b, de racines x et x . Ce qui donnen 2 1 2
n n nu lx mx si les deux racines sont distinctes et u l mn x sinon.n n1 2 1
3. Complexite en temps de l’agorithme recursif des tours de Hano : h 2h 1 eth 1.n n 1 1
Le probleme : deplacer des disques de diametres di erents d’une tour de depart a une tour
d’arrivee en passant par une tour intermediaire et ceci en un minimum de coups, tout en
respectant les regles suivantes :
{ on ne peut deplacer plus d’un disque a la fois,
{ on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un empla-
cement vide.
On suppose que cette derniere regle est egalement respectee dans la con guration de depart.
L’algorithme :
Hanoi(nombre, A, B, I)
si nombre > 0 alors
Hanoi(nombre - 1, A, I, B);
Deplacer un disque de A vers B; - 1, I, B, A);
finSi
(a) resolution intuitive et par recurrence
(b) R par series generatrices.
4. Complexite la pire du quicksort en nombre de comparaisons : p p n 1 et p 1.n n 1 2
L’algorithme : La methode consiste a placer un element du tableau (appele pivot) a sa place
de nitive, en permutant tous les elements de telle sorte que tous ceux qui lui sont inferieurs
soient a sa gauche et que tous ceux qui lui sont superieurs soient a sa droite. Cette operation
1







?








?





q

p
q
q

p


p
q

p


?
?

q
q
p


p
q
q
q
q
p
q

q
?


q


p
?


q

p





?



q

p






?
q

p
p



?







p



p

p
q
p

?
p



s’appelle le partitionnement. Pour chacun des sous-tableaux, on de nit un nouveau pivot et
on repete l’operation de partitionnement. Ce processus est repete recursivement, jusqu’ a ce
que l’ensemble des elements soit trie.
n 1
n n 1
{ resolution par sommation : p i .n
2
i 1
{ resolution par la methode du polyn^ ome caracteristique : si u a u ::: a un 1 n 1 k n k
l
b n P n avec P n polyn^ ome en n.i i i
i 1
Ici l 1, b 1 et et P n n 1.1 1
5. Complexite en moyenne du quicksort en nombre de comparaisons : supposons que le choix du
pivot se porte de fa con aleatoire sur chacun des elements du tableau de taille n ; alors le cout^
n 1
1moyen en nombre de comparaisons c est : c c c n 1 et c c 0.n n i n 1 i 1 0n
i 0
(a) Le terme generique c peut s’ecrire :n
n 1
2
c c n 1n i
n
i 0
n 2
2 2
c c n 1n 1 i
n n
i 0
n 2
2 n 1 2 n 1
c c n 2 n 2 n 1n 1 i 1
n n n 1 n
i 0
n 1 n 1Le terme entre parentheses est exactement c , doncc c 2 , soitdn 1 n n 1 nn n
n
1 1cc n 1 2 2 2 2n d . Alorsd 2n 1 nn 1 n n 1 n n 1 n 1 n n 1 i 1 i i 1
i 1
n
1
2 H 1 . H est le nombre harmonique au rang n et H log n .n 1 n n
i i 1
i 2
n
1
Comme est negligeable devant H , on a que c 2 n 1 log n 1 .n 1 n
i i 1
i 2
(b) Resolution egalement avec les series generatrices.
1.2 recurrences non lineaires
n 1
Exemple 2. Nombre d’arbres binaires a n noeuds : b b b et b 1, b 1.n k n 1 k 0 1
k 0
Resolution par series generatrices.
2 Enumeration et classes combinatoires
2.1 Enum
Enumerer, c’est determiner le nombre de con gurations combinatoires decrites par un ensemble
ni de regles. On souhaite les compter en fonction de leur(s) taille(s).
De nition 2. On appelle atome d’une con guration combinatoire, un element de cette con gu-
ration de taille 1.
Exemple 3. Nombre d’ecritures binaires :
{ si la taille est la longueur du mot binaire : 1; 2; 4; .
2|q
p
q
|q
q
|
p
|

p
|q
p
?


P

?
rr
|

@
|
?
|


?


|
q
|
u
?
t
|q
q
?
|
p
p
P
|
|
p
?
|
p

|
p
|
|
q

ss



rr
P
ss
|
rr
q
|
|
p
p
?
|
q
q
ss
|
?
P

|
?
?
?


|
p
|


|

?
|
{ si les tailles sont la longueur et le nombre de 1 : 1; 1; 1; 1; 2; 1;
{ si les sont la et le nombre de passage de 0 a 1 : 1; 2; 3; 1;
Un atome est ici un chi re du mot binaire.
Exemple 4.
2.2 Classes combinatoires
Une classe combinatoire est un ensemble ni ou denombrable d’objets de nis par une taille tel
que :
{ la taille soit un entier positif ou nul ;
{ l’ensemble des elements d’une taille donnee n est ni.
A une classe combinatoire A correspond une suite d’enumeration c ;c ;::: , avec c le nombre0 1 i
d’objets deA de taille i.
Exemple 5. Les nombres binaires comptes suivant leur longueur forment une classe combinatoire.
lA une longueur l donnee correspond un ensemble ni de nombres binaires (de taille 2 ).
Notations 1. SoitA un ensemble denombrable.
{ soit a A, on note a la taille de l’element a deA.
{ A A , ouA est l’ensemble des elements deA de taille n.n n
n N
{ On note A; : une classe combinatoire avec : :A N, tel qu’ a tout entier n N correspond
par la fonction inverse de : un ensemble ni d’elements de A. S’il n’y a pas d’ambiguit e, on
noteA pour A; : .
Exemple 6. { La classe A; : des arbres binaires comptes suivant leur nombre n de noeuds
1 2nest une classe combinatoire : A C (preuve par recurrence ou SG).n n 1 n 1 n
{ La classe A; : des permutations comptees suivant leur longueur n est une classe combina-
toire : A n! (preuve par recurrence).n
De nition 3. Deux classes combinatoires A; : et B; : sont dites isomorphes, et on le noteA B
A B, si et seulement si leur suite d’enumeration des objets par taille est la m^eme.
Remarque 1. A B A etB sont en bijection, ie. il existe une fonction f :A B bijective.
nExemple 7. Soit A; : la classe des nombres binaires comptes suivant leur longueur : A 2A n
et soit B; : la classe des parties des ensembles 1;:::;n , comptes suivant n. AlorsA B etB
f : A B
a b :::b b En 1 0
ou i 0;i E si et seulement si b 1.i
3 Series generatrices
3.1 Series formelles a une variable a valeurs dans C
De nition 4. Une serie formelle f a une indeterminee z sur C, est une expression formelle du
itype : f z a z , ou les a , appeles coe cients de f, sont a valeurs dans C. On note C zi i
i 0
l’ensemble des series formelles a valeur dansC. Le coe cient a def est appele le terme constant.0
Remarque 2. Si tous les a sont nuls sauf un nombre ni de a , alors f est un polyn^ ome.i i
i iSoientf etg deux series formelles deC z ,f z a z etg z b z . On munitC zi i
i 0 i 0
de :
3




8
q

?
p

q
p
q

p
p
p

8
p
q


p
?
q

?
?

q
?
p
p
?
q
q
q
p
q
?
q
q
p
p




P

?


?
?

?

?
?






p

p
?
q

?
?
?
?
?

?
q

p
q
q
q
p
p
P
p
?
p

p
q
P
p
p
P
rr
?


?
q

p



q
p
p
?


q

p


?
q

p
?


q
?
p
?
?
q

q
q
q
p
q
q
?
p

ss
p
rr
p
P
?
p
P
@

q
p
q
?
p
P
ss

q
p

q
?

rr
p
?
p<