IN101 - cours 05 - 15 octobre 2010

Un probl`eme concretRecherche de collisions√Le paradoxe des anniversaires dit que 365 ´el`eves sont suffisants(en moyenne) pour avoir une collision d’anniversaire,IN 101 - Cours 05deux ´el`eves ayant leur anniversaire le mˆeme jour.7 octobre 2011Comment fait-on pour efficacement trouver ces “paires” d’´el`eves?pr´esent´eparMatthieu FiniaszUn probl`eme concret Un probl`eme concretRecherche de collisions Recherche de collisions√ √Le paradoxe des anniversaires dit que 365 ´el`eves sont suffisants Le paradoxe des anniversaires dit que 365 ´el`eves sont suffisants(en moyenne) pour avoir une collision d’anniversaire, (en moyenne) pour avoir une collision d’anniversaire, deux ´el`eves ayant leur anniversaire le mˆeme jour. deux ´el`eves ayant leur anniversaire le mˆeme jour.Comment fait-on pour efficacement trouver ces “paires” d’´el`eves? Comment fait-on pour efficacement trouver ces “paires” d’´el`eves?M´ethode simple : M´ethode simple :on remplit un tableau avec les n dates d’anniversaire, on remplit un tableau avec les n dates d’anniversaire,on compare chaque ´el´ement `a tous les autres du tableau on compare chaque ´el´ement `a tous les autres du tableau,2 2complexit´eenΘ(n ). complexit´eenΘ(n ). Peut-on faire mieux? Peut-on faire mieux? OUIon trie le tableau,on le parcourt en regarant si 2 voisins sont ´egaux,complexit´eenΘ(nlogn).Le triDescription du probl`emeOn se donne un tableau de n ´el´ements (des entiers par exemple) etune relation ...