La sructure de données

Résumé du document

Cours d'Informatique consacré à la structure de données. L'objectif est l'implantation des données dans les réseaux d'ordinateurs pour les manipuler (calcul), les échanger, les modifier, les stocker de manière temporaire ou persistante.

Extraits

[...] Tri en ordre croissant (principe, la plus grosse bulle qui remonte en premier le plus gros élément ) Complexité maximale Tmax(h) étape 1 : permut Permutation=opération fondamentale Etape permutation : Etape 2 : permut Etape k : permut Etape n-1 : 1 permut 1 permutation : permutation : trié Etape permutation : n-1 n-k k=1 = n-1 i=1 i = n n trié θ(n2) //Tri théoriquement plus optimal Etape 3 aucune permutation = Fin S=1+2+3 + S = 1 + Fin 2S=n(n+1) 2 Complexité théorique du tri ? Le tri en ordre : c'est en général la sélection d'une permutation parmi n ! [...]

[...] Temps d'accès de déplacement du disque (accès aux secteurs). Mémoire de Masse tr/mn 60s tr x ( Règle de 3 x 60 / = 3ms ) Temps moyen = 3ms 4 ms 4 STRUCTURE DE DONNEES Processeur Registres Mémoire centrale Mémorisation des données pour calcul Transfert pour mot Disque ms Mémorisation pour sauvegarde persistante Transfert par bloc Mémoire cache Capacité en Calcul Accès direct coût de l'octet faible Temps cycle ns Capacité Go 1 MB = 1024 kb 1 GB = 1024 MB Temps cycle [...]

[...] On cherche la place de pivot entre les indices 1 et k Et on décale donc la partie t(place de 1 rang Vers la fin, et on met le pivot à sa place. Donc à la fin de l'étape k On a : T(1 qui sera trié en ordre 14 STRUCTURE DE DONNEES t : tableau d'entiers Etape 2 trié pas de décalage Etape décalages pivot à insérer Etape décalage Algorithme du tri à bulle t : tableau d'entiers permut : booleen vrai si permutation effectuée etape : entier 1 n d'étape etape 1 permut true Tant que permut et etape t(index+1) alors Permuter(t(index),t(index+1)) permut vrai Finsi Finpour Fin Tant que n-1 fois max 15 n-1 n.etapes etape 1 STRUCTURE DE DONNEES Public class trieuse { Public static void permuter (int[ ] collection, int index1, int index2) { int tempo = collection [index1] ; collection [index1] = collection [index2] ; collection [index2] = tempo ; } public static void trier (int [ ] { . [...]

[...] log(e)) log(n ~ n log(n)+ 1 (log(n)-n log(e)+ 1 log(2π) log(n ~ n log(n)- log(e).n+ 1 log((n)+c log(n ~ θ(n log(n)) = θ(n log(n)) donc le meilleur des tris ne peut pas être meilleur que : Complexité temporelle théorique optimale Tri par insertion Comme pour le tri il y a n-1 étapes étapes : de l'étape 2 à l'étape n A l'étape on considère que les k-1 premiers éléments sont triés. Donc on a T(1 qui est trié en ordre. Ensuite, on va insérer à sa place, l'élément pivot qui est dans la partie triée. [...]

[...] Facteur limitant : L'organisation et les possibilités du matériel Les moyens : Les capacités du matériel (connaître les possibilités et les limites) Structuration des programmes Structuration des données Conception Choix + Algorithmes Performances(comparaison des performances) (dépendent des structures de données) Démarche : Etudier le besoin en termes d'opérations à effectuer (sur les données) Ajouter des éléments (dans une collection) Retirer des éléments Modifier des éléments Taux de ‘rotation' Fréquence Taux de ‘mise à jour' ? Fréquence Profil de fréquence ? Rechercher des éléments Consulter des éléments Taux de consultations ? [...]