OODOC RECHERCHE & PUBLICATION DE DOCUMENTS

    Votre panier

    Accéder

    10

    Informatique
    publié le 06/07/2012

    1,80 €

    Recherche, tri, table

    Document de 10 pages au format WORD

    RÉSUMÉ

    Cours d'Algorithmique dispensé en 1ère année de DUT Informatique sur la recherche, le tri et les tables de données.

    EXTRAIT

    [...]
    Nous avons vu dans ce chapitre que pour gérer des données par exemples des clients on pouvait se servir d'une structure de type clients et ranger ces derniers dans une table ou un tableau.

    Il est important à ce niveau de faire quelques remarques

    - Si on fait des recherches fréquentes il est intéressant de trier les données de façon à pouvoir y accéder rapidement par dichotomie.
    - Par contre, si l'on ajoute souvent des données, il est nécessaire de bien insérer de façon à maintenir le tableau trié (-> implique décalage, très lourd si il y a beaucoup de données)
    - Pour un tableau non trié, insertion très rapide. A l'inverse la recherche devient fastidieuse.
    -> Il faut donc trouver une solution pour pouvoir trier et rechercher rapidement.

    [...] Le rangement dispersé est un rangement où la fonction d'adressage est directement calculée.
    Le hachage a la particularité de permettre un temps de recherche constant, c'est-à-dire indépendant du nombre de données.

    Ex : on veut gérer une table de personnes indexées par leur prénom. A chaque prénom on associe un entier h(i) de 0 à 12 en procédant comme suit :
    - Attribuer aux lettres leur rang dans l'alphabet (A -> 1, B -> 2 etc.)
    - Ajouter les valeurs des rangs pour chaque lettre du nom
    - Ajouter au nombre obtenu le nombre de lettre de i
    - Prendre le reste de la division de ce nombre par 13

    On obtient :
    h(« serge ») = ((19+5+18+7+5)+5)mod 13=7
    h(« odile »)=11
    h(« anne »)=12
    h(« luc »)=0
    h(« basile »)=2

    On peut placer les prénoms dans un tableau en utilisant comme position la valeur de h(i). Le problème est que si l'on veut insérer Paule, on constate que h(« paule »)=2. On dit qu'il y a collision primaire entre paule et basile. Toute la difficulté du hachage consiste à trouver une fonction de hachage. Etant quasi impossible de trouver une fonction parfaite, il va donc falloir prendre en compte les collisions et le gérer (...)

    PLAN

    I) Recherche

    A. Recherche séquentielle améliorée
    B. Recherche dichotomique

    II) Insertion

    III) Trier des tableaux

    A. Le tri ordinaire
    B. Le tri à bulle
    C. Le tri par insertion

    IV) Trier des tableaux de structure

    V) Les tables de données

    A. Définition formelle
    B. Accès direct
    C. Accès indirect

    VI) Le problème de la gestion de grandes masses de données

    A. Le rangement dispersé ou hachage
    1. Les fonctions de hachage
    2. Résolution des collisions
    B. Tables de données avec clés multiples

    Conclusion

    10

    Informatique publié le 06/07/2012

    1,80 €

    Recommandations

    • Instruction qualité : fiche de tri ou retouche

      1,80 €

      1

      Management de la qualité publié le 29/10/2008

      Descriptif

      Instruction qualité : surveillance et mesurage : fiche de tri ou retouche.

    • Le tri : définition et principe

      5,40 €

      27

      Ecologie/Environ. publié le 10/07/2007

      Descriptif

      Pour valoriser les déchets, il est nécessaire de ne plus les collecter en mélange. Pour pouvoir être recyclés ceux-ci doivent en effet avoir été préalablement triés. Le tri des déchets doit s'effectuer partout et tout le temps. Du bon respect des consignes ...

    Partenaire de la rubrique Informatique

    Trouver-pas-cher.com : Votre équipement informatique pas cher, votre petit électroménager pas cher et votre installation TV pas chère, tout cela est enfin possible ! Retrouvez les meilleurs prix High-Tech sur le comparateur de prix Trouver-pas-cher.

    Du même auteur

    Voir toutes les publications de cet auteur

    Nouveautés en Informatique

    Aller à la catégorie

    • Evolutions in the music industry. Case study an analysis of Spotify

      5,40 €

      7

      Informatique publié le 26/04/2013

      Descriptif

      Since 2000, the increasing popularity of Internet was one of the main reasons of CD music sales which have been decreasing from 700 million sales in 2000, to less than 200 million for the year 2012. This decrease can also explain the recent collapse of HMV. The...

    • Enseignement : guide d'utilisation de Google Documents

      3,60 €

      26

      Informatique publié le 15/10/2012

      Descriptif

      Guide d'utilisation de Google Documents dans le cadre de l'enseignement. Extrait: Google Documents est une suite bureautique en ligne. Grâce à ce service, il est possible de travailler avec d'autres personnes...

    • Guide d'utilisation du site.tv

      3,60 €

      24

      Informatique publié le 15/10/2012

      Descriptif

      Guide d'utilisation du site.tv et compétences c2i2e mobilisées. Extrait: Le site.tv est une « vidéothèque destinée aux enseignants, aux documentalistes et aux élèves....

    Les plus consultées

    • Rapport de Projet sur la torréfaction

      9,00 €

      48

      Informatique publié le 28/08/2007

      Descriptif

      « La torréfaction consiste à chauffer à très hautes températures, sans ajouts de produits chimiques ou toxiques, une matière afin d'en améliorer les propriétés. Elle est réalisée...

    • Exemple de charte informatique

      1,80 €

      5

      Informatique publié le 31/08/2006

      Descriptif

      Exemple de charte informatique applicable dans toute entreprise pour donner un cadre à l'utilisation du matériel informatique. Vous y trouverez : confidentialité, micro-ordinateurs et serveurs, courrier électronique, utilisation...

    • Modèle de contrat de conception d'un site Web

      3,60 €

      9

      Informatique publié le 18/09/2006

      Descriptif

      Exemple de contrat juridique, relatif à la conception d'un site Web. Le document se compose de 28 articles : l'objet, le délai de fourniture des services, le prix, la facturation, les conditions de paiement, les informations apportées par le client, l'exécution ...

    Accès membre

    Auteur du document

    Jérémy

    Votre panier

    Derniers vus

    Publier vos documents

     

    Charte qualité

    déplier