Ressource en auto-formation : Théorie de l’information : modèles, algorithmes, analyse

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 fon...
cours / présentation - Création : 11-02-2010
Par : Brigitte Vallée
Partagez !

Présentation de: Théorie de l’information : modèles, algorithmes, analyse

Informations pratiques sur cette ressource

Langue du document : Français
Type : cours / présentation
Niveau : enseignement supérieur
Langues : Français
Contenu : ensemble de données
Public(s) cible(s) : apprenant, enseignant
Document : Document HTML, Document PDF
Age attendu : 18 ans et +
Difficulté : très difficile
Droits d'auteur : pas libre de droits, gratuit
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)

Description de la ressource en auto-formation

Résumé

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.

  • Granularité : leçon
  • Structure : en réseau

"Domaine(s)" et indice(s) Dewey

  • Information theory (003.54)
  • Systems programming and programs (005.4)

Domaine(s)

Informations pédagogiques

  • Proposition d'utilisation : 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
  • Commentaires pédagogiques : Il s'agit plutôt d'un thème enseignement-recherche qui ne fait pas encore partie des cursus standard en biologie

Intervenants, édition et diffusion

Intervenants

Créateur(s) de la métadonnée : Marie-Hélène Comte;Marie-Hélène
Validateur(s) de la métadonnée : Sylvain Duranton sduranton;Sylvain Duranton

Édition

  • Institut National de Recherche en Informatique et en Automatique

Diffusion

Document(s) annexe(s) - Théorie de l’information : modèles, algorithmes, analyse

Partagez !

AUTEUR(S)

  • Brigitte Vallée
    Université de Caen

DIFFUSION

Cette ressource en auto-formation vous est proposée par :
UNIT - accédez au site internet
Sur les réseaux sociaux :

ÉDITION

Institut National de Recherche en Informatique et en Automatique

EN SAVOIR PLUS

  • Identifiant de la fiche
    http://ori.unit-c.fr/uid/unit-ori-wf-1-3783
  • Identifiant OAI-PMH
    oai:www.unit.eu:unit-ori-wf-1-3783
  • Statut de la fiche
    final
  • Schéma de la métadonnée
  • Entrepôt d'origine
    UNIT
  • Publication
    03-10-2010

Ressources en auto-formation sur les mêmes thèmes

Présentation de la ressource en auto-formation Théorie algorithmique de l'information cours / présentation
05/06/2013
Théorie algorithmique de l'information
Auteur(s) : DELAHAYE Jean-Paul
Description : Qu'est-ce que l'information et comment la mesurer ? qu'est-ce que la complexité et comment la mesurer ? En 2013, les travaux d'application sur la mesure de la complexité continuent car on est encore loin d'avoir tout compris. Les solutions proposées jusqu'à présent sont trop simplifiées ou trop ...
Présentation de la ressource en auto-formation Complexité des données et compression informatique cours / présentation, démonstration
26/09/2011
Complexité des données et compression informatique
Description : S’il est une notion complexe à définir, c’est bien celle de complexité ! La théorie de la complexité de Kolmogorov fait le lien entre complexité et compression des données.