IN101 - cours 05 - 15 octobre 2010

IN 101 - Cours 057 octobre 2011pr´esent´e parMatthieu FiniaszUn probleme concretRecherche de collisionspLe paradoxe des anniversaires dit que 365 ´el`eves sont suffisants(en moyenne) pour avoir une collision d’anniversaire,deux ´el`eves ayant leur anniversaire le mˆeme jour._Comment fait-on pour efficacement trouver ces “paires” d’´el`eves?1Un probleme concretRecherche de collisionspLe paradoxe des anniversaires dit que 365 ´el`eves sont suffisants(en moyenne) pour avoir une collision d’anniversaire,deux ´el`eves ayant leur anniversaire le mˆeme jour._Comment fait-on pour efficacement trouver ces “paires” d’´el`eves?M´ethode simple :on remplit un tableau avec les n dates d’anniversaire,on compare chaque ´el´ement `a tous les autres du tableau2complexit´e enΘ(n )._Peut-on faire mieux?2Un probleme concretRecherche de collisionspLe paradoxe des anniversaires dit que 365 ´el`eves sont suffisants(en moyenne) pour avoir une collision d’anniversaire,deux ´el`eves ayant leur anniversaire le mˆeme jour._Comment fait-on pour efficacement trouver ces “paires” d’´el`eves?M´ethode simple :on remplit un tableau avec les n dates d’anniversaire,on compare chaque ´el´ement `a tous les autres du tableau,2complexit´e enΘ(n )._Peut-on faire mieux? OUI_on trie le tableau,on le parcourt en regarant si 2 voisins sont ´egaux,complexit´e enΘ(nlogn)._3Commenttrier un tableauLe triDescription du problemeOn se donne un tableau de n ´el´ements (des entiers ...