Classement optimal d'une liste chaînée
bonjour
j'ai un probleme d'un algrorithme parallelle le voila
Soit une liste chaînée chaînée L contenant n objets. L'algorithme EREW de classement
par sauts de pointeurs vu en cours est e cace mais non optimal.
Donner un algorithme ClassementListe(L) optimal, de complexité en temps T(n) =
O(log(n)) et utilisant O(n/ log(n)) processeurs comme suit.
i) Réduire la liste L à une liste L0 de taille O(n/ log(n)).
1
ii) Utiliser l'algorithme habituel de classement sur la liste réduite L0, puis récupérer
les objets ôtés lors de l'initialisation et calculer leur rang. Quel est le travail
obtenu ? En déduire que ClassementListe(L) est bien optimal.
iii) Quelles hypothèses faut-il formuler sur les entrées de ClassementListe(L) pour oépré
merci de répondre a mon msg au plus vite posible
j'ai un probleme d'un algrorithme parallelle le voila
Soit une liste chaînée chaînée L contenant n objets. L'algorithme EREW de classement
par sauts de pointeurs vu en cours est e cace mais non optimal.
Donner un algorithme ClassementListe(L) optimal, de complexité en temps T(n) =
O(log(n)) et utilisant O(n/ log(n)) processeurs comme suit.
i) Réduire la liste L à une liste L0 de taille O(n/ log(n)).
1
ii) Utiliser l'algorithme habituel de classement sur la liste réduite L0, puis récupérer
les objets ôtés lors de l'initialisation et calculer leur rang. Quel est le travail
obtenu ? En déduire que ClassementListe(L) est bien optimal.
iii) Quelles hypothèses faut-il formuler sur les entrées de ClassementListe(L) pour oépré
merci de répondre a mon msg au plus vite posible
A voir également:
- Classement optimal d'une liste chaînée
- Liste déroulante excel - Guide
- Liste déroulante en cascade - Guide
- Liste code ascii - Guide
- Site dangereux liste - Guide
- Logiciel de classement de photos gratuit - Guide
1 réponse
Grosso modo tu dois faire ce qui existe actuellement dans les std::set de la STL (cf C++) c'est à dire une structure d'arbre binaire, ou à chaque noeud de l'arbre tu évalues si l'élément à insérer (ou auquel accéder) est plus petit ou plus grand. Ainsi tu divises par deux la zone de recherche à chaque noeud de l'arbre ce qui correspond à du O(log(n)).
http://brassens.upmf-grenoble.fr/IMSS/dciss/Enseignements/PSR/Prog/Java/CoursJava/arbresRougeNoir.htm
Bonne chance
http://brassens.upmf-grenoble.fr/IMSS/dciss/Enseignements/PSR/Prog/Java/CoursJava/arbresRougeNoir.htm
Bonne chance
