URI http://ori.unit-c.fr/uid/unit-ori-wf-1-3783 Théorie de l’information : modèles, algorithmes, analyse fre Tout étudiant d’un cours d’algorithmique de base apprend que la complexité moyenne de l’algorithme QuickSort est en O(n log n), celle de QuickSelect est en O(n) et celle de RadixSort est en O(n log n). De tels énoncés ont le mérite d’être simples, mais leur simplicité est trompeuse, car ils sont fondés sur des hypothèses spécifiques à chaque algorithme : pour les deux premiers algorithmes, le coût unitaire est la comparaison entre clés, tandis que, pour le troisième, le coût unitaire est la comparaison entre symboles. Dans cet exposé, l’analyse probabiliste de trois principaux algorithmes est revisité: QuickSort, QuickSelect, et les algorithmes de dictionnaire fondés sur la structure de tri. analyse algorithmique théorie de l'information algorithme de tri algorithme de recherche complexité algorithme analyse probabiliste fuscia LOMv1.0 networked LOMv1.0 2 LOMv1.0 ensemble de données LOMv1.0 final LOMv1.0 author BEGIN:VCARD VERSION:3.0 N:Vallée;Brigitte;;; FN:Brigitte Vallée EMAIL;TYPE=INTERNET:brigitte.vallee@info.unicaen.fr ORG:Université de Caen END:VCARD 2010-02-11 LOMv1.0 publisher BEGIN:VCARD VERSION:3.0 N:Institut National de Recherche en Informatique et en Automatique;;;; FN:Institut National de Recherche en Informatique et en Automatique EMAIL;TYPE=INTERNET: ORG:INRIA END:VCARD 2010-10-03 URI http://ori.unit-c.fr/uid/unit-ori-wf-1-3784 LOMv1.0 validator BEGIN:VCARD VERSION:3.0 N:sduranton;Sylvain Duranton;Sylvain Duranton;;; FN:Sylvain Duranton sduranton;Sylvain Duranton ORG:Mon université URL:http://www.univ.fr UID:sduranton EMAIL;TYPE=INTERNET: END:VCARD LOMv1.0 creator BEGIN:VCARD VERSION:3.0 N:Comte;Marie-Hélène;Marie-Hélène;;; FN:Marie-Hélène Comte;Marie-Hélène EMAIL;TYPE=INTERNET:marie-Hélène.comte@sophia.inria.fr ORG:Inria, Institut National de recherche en informatique et Automatique END:VCARD 2010-01-19 LOMv1.0 LOMFRv1.0 SupLOMFRv1.0 fre text/html application/pdf http://iww.inria.fr/colloquium/fr/brigitte-vallee-theorie-de-linformation-modeles-algorithmes-analyse/ LOMv1.0 lecture LOMv1.0 learner LOMv1.0 teacher LOMv1.0 higher education 18 ans et + LOMv1.0 very difficult On peut conseiller cette ressource comme un "cours de recherche" sur le sujet à utiliser dans le cadre d'un master en informatique 2eme année ou recherche fre LOMv1.0 no LOMv1.0 yes Document libre, dans le cadre de la licence Creative Commons (http://creativecommons.org/licenses/by-nd/2.0/fr/), citation de l'auteur obligatoire et interdiction de désassembler (paternité, pas de modification) LOMv1.0 ispartof URI http://www-sop.inria.fr/colloquium/collection.html Colloquium Jacques Morgenstern : Collection des séminaires Il s'agit plutôt d'un thème enseignement-recherche qui ne fait pas encore partie des cursus standard en biologie LOMv1.0 discipline Classification UNIT 1305 Programmation : Algorithmique, langages, conception objet, programmes LOMv1.0 discipline CDD 22e éd. 003.54 Information theory LOMv1.0 discipline Classification UNIT 1320 Informatique théorique LOMv1.0 discipline DDC 22nd ed 005.4 Systems programming and programs