Cours de mathématiques discrètes

p?{p?@@pq??pqqqp?q@p?qCours de Mathematiques discretes7 novembre 20101 Rappels sur les recurrences1.1 recurrences lineairesDe 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 k2. recurrences lineaires non homogenes a coe cients constants : n;n k 0,u a un 1 n 1::: a u b n ;k n k3. recurrences lineaires a coe cients variables : n;n k 0, u a n u :::n 1 n 1a n u b n ;k n kExemple 1. 1. Nombre de comparaison dans une recherche dichotomique pour un tableau triemde longueur n 2 : t t 1 et t 1.n n 2 1resolution inuitive et demonstration par recurrence : t d m 1 m 1 log n .n 1 22. 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 2hauteur).Resolution par polyn^ ome caracteristique : marche pour les recurrences du typeu aun n 12bu qui a pour polyn^ ome caracteristique x ax b, de racines x et x . Ce qui donnen 2 1 2n n nu lx mx si les deux racines sont distinctes et u l mn x sinon.n n1 2 13. Complexite en temps de l’agorithme recursif des tours de Hano : h 2h 1 eth 1.n n 1 1Le probleme : deplacer des disques de diametres di erents d’une tour de depart a une tourd’arrivee en passant par une tour intermediaire et ceci en un minimum de coups, tout enrespectant les regles suivantes :{ on ne peut deplacer plus d’un disque a la fois,{ on ne peut ...