Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Candidat au Club
    Femme Profil pro
    Lycéen
    Inscrit en
    novembre 2018
    Messages
    9
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 19
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : novembre 2018
    Messages : 9
    Points : 3
    Points
    3

    Par défaut Implémentation d'un arbre binaire

    Bonjour à tous, je vient de commencer un stage d'étude en algorithme et mon professeur ma conseiller de faire se sujet pour comprendre un peu près tout le programme que je doit étudier.
    Je suis nouvelle sur le site et je sais bien que c'est très mal vu de poser un problème sans apporter aucune réponse mais je ne comprend pas trop comment m'y prendre.

    Cela porte sur la récurrence, la complexité et les arbres binaire.
    Je met le sujet en pièces jointes si quelqu'un veux m'aider (je lui promettrai en retour de travailler tres dur ) sinon merci d'avance

    Nom : 0001.jpg
Affichages : 134
Taille : 1,06 MoNom : 0002.jpg
Affichages : 131
Taille : 1,05 MoNom : 0003.jpg
Affichages : 122
Taille : 894,7 KoNom : 0004.jpg
Affichages : 120
Taille : 1,23 MoNom : 0005.jpg
Affichages : 110
Taille : 287,6 Ko

  2. #2
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 332
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 332
    Points : 7 869
    Points
    7 869

    Par défaut

    Bonjour

    je lui promettrai en retour de travailler tres dur
    Le problème de poster un énoncé entier avec toutes les questions et sans commentaires, c'est que ça dénonce l'internaute qui n'a strictement rien fait.


    As-tu compris les choses suivantes ?
    V est l'ensemble des tâches, donc des sommets.
    E est l'ensemble des arêtes.
    Sigma (minuscule) σ est la fonction qui indique le processeur choisi pour une tâche.
    "C" est le temps forfaitaire à ajouter si les tâches ne sont pas en même temps.

    La première question demande simplement de faire un cas concret en te donnant l'arbre, les tâches, les temps, les processeurs alloués et les temps de communication.
    Concrètement, on commence par la tâche 0 à la date 0 sur le processeur A.

    À toi
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  3. #3
    Candidat au Club
    Femme Profil pro
    Lycéen
    Inscrit en
    novembre 2018
    Messages
    9
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 19
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : novembre 2018
    Messages : 9
    Points : 3
    Points
    3

    Par défaut

    Citation Envoyé par Flodelarab Voir le message
    As-tu compris les choses suivantes ?
    V est l'ensemble des tâches, donc des sommets.
    E est l'ensemble des arêtes.
    Sigma (minuscule) σ est la fonction qui indique le processeur choisi pour une tâche.
    "C" est le temps forfaitaire à ajouter si les tâches ne sont pas en même temps.

    La première question demande simplement de faire un cas concret en te donnant l'arbre, les tâches, les temps, les processeurs alloués et les temps de communication.
    Concrètement, on commence par la tâche 0 à la date 0 sur le processeur A.
    Bonsoir, merci beaucoup pour ta réponse. Pour les sommet et les arrêtes je comprend mais pour la question 1 je comprend pas trop le sigma et l'allocation des taches. (ce que cela représente en gros)

    J’essaie en même temps de regarder le cours sur les graphes parce qu'on a pas encore fait tout ça en cours mais en même j'aimerai bien m'avancer sur le cours en comprenant tout ça.

  4. #4
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 332
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 332
    Points : 7 869
    Points
    7 869

    Par défaut

    J'ai une mauvaise nouvelle : Les processeurs sont mono-tâche. (du moins, les cœurs des processeurs)

    En multiplexant les tâches, on fait croire qu'on fait plusieurs choses en même temps.
    Mais en fait, non. L'ordinateur ne réfléchit réellement qu'à une chose. Puis il passe à la suite.

    Donc il faut dire quel cœur réfléchit à quel problème.
    σ(u) = A veut dire que la tâche u est exécutée par le processeur A.
    Simplement.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  5. #5
    Candidat au Club
    Femme Profil pro
    Lycéen
    Inscrit en
    novembre 2018
    Messages
    9
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 19
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : novembre 2018
    Messages : 9
    Points : 3
    Points
    3

    Par défaut

    Mais comment trouver la valeur d'une durée minimale à partir de sigma à un certain sommet de V ?

  6. #6
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 747
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 747
    Points : 4 435
    Points
    4 435

    Par défaut

    salut

    la question que tu doit te poser : une durée c'est quoi ?
    la réponse a cette question toutes simple : une accumulation de temps
    en conclusion il faut que tu parcours ton arbre afin de trouver la somme mini des durées a un certain sommet v
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  7. #7
    Candidat au Club
    Femme Profil pro
    Lycéen
    Inscrit en
    novembre 2018
    Messages
    9
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 19
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : novembre 2018
    Messages : 9
    Points : 3
    Points
    3

    Par défaut

    Donc par exemple en prenant l'arbre de l'énoncé, et en prenant par exemple le sommet 1. La distance minimal est soit tA(1) + tA(4) ou tA(1)+tA(5) ?

  8. #8
    Candidat au Club
    Femme Profil pro
    Lycéen
    Inscrit en
    novembre 2018
    Messages
    9
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 19
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : novembre 2018
    Messages : 9
    Points : 3
    Points
    3

    Par défaut



    Se que j'ai dit est faux je crois mais je crois aussi avoir compris.
    Donc pour la question 1 :

    delta(0) = 2
    delta(1) = tA(0) + tA(1)
    delta(3) = tA(0) + tB(3)
    delta(4) = tA(0) + tA(1) + tB(4)
    delta(5) = tA(0) + tA(1) + tB(5)
    delta(7) = tA(0) + tB(3) + tB(7)

    etc ...

  9. #9
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 747
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 747
    Points : 4 435
    Points
    4 435

    Par défaut

    salut

    tu donne la réponse dans ta propre question qu'elle est la distance minimale pour les éléments de TA entre tA(0) + tA(1) + tA(4) | tA(0) +tA(1)+tA(5)
    resultat c'est ... as toi de trouver et de dire pourquoi

    remarque que tu peut l'exprimer ainsi
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
     tA(0) +Min((tA(1)+Min(tA(4),tA(5))) , (tA(3)+Min(tA(7),tA(6),tA(2))) )

    PS : Ce n'est pas un arbre binaire mais NAire car un noeud peut avoir N enfants
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  10. #10
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 332
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 332
    Points : 7 869
    Points
    7 869

    Par défaut

    Pourquoi les temps de communications ont sauté ? Ils comptent pour le delta.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  11. #11
    Candidat au Club
    Femme Profil pro
    Lycéen
    Inscrit en
    novembre 2018
    Messages
    9
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 19
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : novembre 2018
    Messages : 9
    Points : 3
    Points
    3

    Par défaut

    Citation Envoyé par anapurna Voir le message
    salut

    tu donne la réponse dans ta propre question qu'elle est la distance minimale pour les éléments de TA entre tA(0) + tA(1) + tA(4) | tA(0) +tA(1)+tA(5)
    resultat c'est ... as toi de trouver et de dire pourquoi

    remarque que tu peut l'exprimer ainsi
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
     tA(0) +Min((tA(1)+Min(tA(4),tA(5))) , (tA(3)+Min(tA(7),tA(6),tA(2))) )
    Non je crois que se que j'ai mis est faux car par exemple pour le sommet 4, dans l'énoncé sigma(4) est attribuer au processeur B donc on utilisera le temp tB plutot. (je pense )

    Citation Envoyé par Flodelarab Voir le message
    Pourquoi les temps de communications ont sauté ? Ils comptent pour le delta.

    Ok donc il faudrait à chaque fois ajouter pour par exemple delta(4) = tA(0) + tA(1) + tB(4) +cAB[(1,4)] ( pour 0 et 1 on nous dit que cAA = 0) ??

    pour l'induction je ne comprend pas comment il faut s'y prendre par contre

  12. #12
    Membre éprouvé
    Profil pro
    Inscrit en
    avril 2004
    Messages
    723
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations forums :
    Inscription : avril 2004
    Messages : 723
    Points : 1 051
    Points
    1 051

    Par défaut

    Est-ce que je rêve ou s'agit-il d'une façon formidablement compliquée de poser un problème plutôt simple ( trouver le temps minimum, avec autant de processeurs qu'on veut ) ?
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  13. #13
    Candidat au Club
    Femme Profil pro
    Lycéen
    Inscrit en
    novembre 2018
    Messages
    9
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 19
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : novembre 2018
    Messages : 9
    Points : 3
    Points
    3

    Par défaut

    je reviens avec du nouveau
    Pour l'instant je reste bloqué pour la Question 1.3 mais j'ai sauter cette question en attente de trouver une réponse.

    Question 2.1:

    Je comprend pas trop comment faire pour mettre l'arbre dans un tableau en python donc j'ai besoin d'aide là-dessus.
    Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    tA=[2,3,3,4,10,3,20,5]
    tB=[3,10,1,2,2,15,5,1]
    cAB=[1,4,2,3,3,3,2]
    cBA=[4,3,4,2,4,3,3]

    Question 2.2:

    Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    def duree(u,Sigmau,tA,tB):
         if Sigmau==1:
             return tA[u]
         else: 
              return tB[u]

    La complexité est en theta de 1 (je crois que la justification c'est qu'il faut dire que il y a une comparaison)

    Question 2.3:


    Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    def Val Com(u,v,Sigmau,Sigmav,cAB,BA):
         if Sigmau == Sigmav:
             return 0
         elif Sigmau ==1:
             return 1
         else:
             return cBA
    ici on a que 2 comparaison donc normalement c'est une complexité en theta de 2.

    Question 2.4:

    Pour cette question j'ai besoin du tableau de l'arbre mais je ne sais pas comment l’écrire.
    Mais je pense qu'il faudrait faire une boucle for ou while.

  14. #14
    Candidat au Club
    Femme Profil pro
    Lycéen
    Inscrit en
    novembre 2018
    Messages
    9
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 19
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : novembre 2018
    Messages : 9
    Points : 3
    Points
    3

    Par défaut

    Bonsoir tout le monde, je post mes différent code réponse pour les question des exercices, j'aimerai savoir si il y'a des erreurs et également qu'on m'aide pour les induction de la question 1.3 de l'exercice 1 et la question 2 de l'exercice 2 s'il vous plait car je n'y arrive pas


    Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    307
    308
    309
    310
    311
    312
    313
    314
    315
    316
    317
    318
    319
    320
    321
    322
    323
    324
    325
    326
    327
    328
    329
    330
    331
    332
    333
    334
    335
    336
    337
    338
    339
    340
    341
    342
    343
    344
    345
    346
    347
    348
    #Arbre : List[int]
    Arbre = [0,0,3,0,1,1,3,3]
    #tA : List[int]
    tA = [2,3,3,4,10,3,20,5]
     
    #tB : List[int]
    tB = [3,10,1,2,2,15,5,1]
     
    #cAB : List[int]
    cAB = [0,1,2,4,2,3,3,3]
     
    #cBA : List[int]
    cBA = [0,4,3,3,4,2,3,4]
     
    #Sigma : List[int]
    Sigma = [1, 1, 0, 0, 0, 1, 0, 0]
     
     
     
     
    def duree(u, Sigmau, tA, tB):
        """ list[]**2 * int**2 -> int
        renvoie tA[u] si Sigmau = 1, tB[u] sinon. """
     
        #les comparaisons ont ete faites pour verifier que u est bien un noeud de l'arbre,
        #et que sigma est un booleen 0 ou 1 sinon on demande de rentrer de valeurs valides
     
        if (Sigmau == 1 and (u<len(tA))): 
            return tA[u]
        elif (Sigmau == 0 and (u<len(tB))):
            return tB[u]
        else:
            print("Entrez des valeurs valides, svp.")
     
     
     
     
    def valCom(u, v, Sigmau, Sigmav, cAB, cBA):
        """ liste[]**2 * int**4 -> int
        renvoie 0 si Sigmau et Sigmav égaux, 1 si Sigmau = 1,
        cBA((u,v)) sinon."""
     
        # -||- les comparaisons ont ete faites pour verifier que u est bien un noeudde l'arbre,
        #et que sigma est un booleen 0 ou 1 sinon on demande de rentrer de valeurs valides
     
        if (Sigmau == Sigmav):
            return 0
        elif (Sigmau == 1 and (v<len(cAB))):
            return cAB[v]
        elif (Sigmau == 0 and (v<len(cBA))):
            return cBA[v]
        else:
            print("Entrez des valeurs valides, svp")
     
     
     
    def succ(u, Arbre):
        """ Arbre*int -> list[]
        renvoie la liste des successeurs de u dans l'arbre ABT Arbre."""
     
        #j : int
        j = 1 
     
        #list_succ: list 
        list_succ = []
     
        while (j < len(Arbre)):
        #a partir de Arbre[1] car la racine Arbre[0] n'a pas de successeurs et on risque de boucler a l'infini
            if Arbre[j] == u:
                list_succ.append(j)
            j = j+1
     
        return list_succ
     
     
     
    def CalculDelta(Arbre,tA,tB,cAB,cBA,Sigma,u):
        """list[]**5 * int -> int
        renvoie delta(u) pour une allocation sigma."""
     
        #tab_u, succ_u, succ_u,bis : list[]
     
        tab_u = duree(u,Sigma[u],tA,tB)
        succ_u =succ(u,Arbre)
        succ_u_bis = []
     
        #i, j, val, val_finale : int
        i, j, val, val_finale = 0, 0, 0, 0
     
     
        if (succ_u == []):
                return tab_u
     
     
     
        else: 
                while( i<len(succ_u) ):
     
                        val = valCom(u, succ_u[i], Sigma[u],Sigma[succ_u[i]], cAB, cBA)
                        j  = CalculDelta(Arbre, tA, tB, cAB, cBA, Sigma, succ_u[i]) + val
                        succ_u_bis.append(j)
     
                        i = i + 1
     
     
                val_finale = max(succ_u_bis)
                val_finale += tab_u 
     
     
                return val_finale
     
     
     
     
    #la fonction decompose_base_2 decompose tout entier j en base 2 et envoie le resulat
    #sous la forme d'un tableau, elle est faite pour etre utilitee dans CalculSigmaOptimum
     
    def decompose_base_2(Arbre,j):
        """ int*list[] -> list[]
        renvoie un tableau des chiffres de la decomp de j en base 2. """
     
        #i : int
        i=0
     
        #tab : list[]
        tab = []
     
        #n : int
        n = len(Arbre) 
     
        while(n):
            i = j%2
            j = j//2
            tab.append(i)
            n = n -1
     
        #je fais le mirroir de mon tableau de valeurs vu qu'elles ont ete stockee dans
        #l'ordre inverse, cette etape n'est pas necessaire mais nous sert a voir la bonne 
        #representation binaise de j
     
        i=0
        j=0
        temp = 0  
        while(i<len(tab)):
            j = len(tab) - 1
            temp = tab[i]
            tab[i] = tab[j-i]
            tab[j-i] = temp
            i = i + 1
     
        return tab
     
     
     
     
    def CalculSigmaOptimum(Arbre, tA, tB, cAB, cBA):
        """ list[]**5 -> int
        renvoie l'allocation de duree minimale. """
     
        #n : int
        n = len(Arbre)
     
        #alpha : int
        alpha = 2**n   
     
        #j, j_minimum : int
        j, j_minimum = 0, 0
     
     
        #tab_Sigma, resultats, allocations : list[] 
        tab_Sigma, resultats, allocations = [], [], []
     
     
        #je cherche la representation de tout le nombre < alpha en binaire
        #pour ensuite les stocker dans un tableau d'allocations 
        while( j<alpha ):
            tab_base_2 = decompose_base_2(Arbre,j)
            tab_Sigma.append(tab_base_2)
            j = j + 1  
     
     
        #je cherchce la valeur minimale en stockant d'abord toutes les valeurs
        #pour les allocations possibles, la fonction renvoie ensuite SIgma pour
        #laquelle resultat est minimal.
        for Sigma in tab_Sigma:  
            resultat = CalculDelta(Arbre, tA, tB, cAB, cBA, Sigma, 0)
            resultats.append(resultat)
            allocations.append(Sigma) 
     
        minimum = min(resultats)
        j_minimum = resultats.index(minimum)
     
        return allocations[j_minimum]
     
     
     
     
     
    dA = tA[:]
    dB = tB[:]
     
     
    def CalculBorneInf(Arbre, tA, tB, cAB, cBA, dA, dB, u):
        """List[int]**7 * int ->
        calcule dA et dB de u. """
     
        #liste_succ, tab1, tab2: List[int]
        liste_succ, tab1, tab2 = [], [], []
        liste_succ = succ(u, Arbre)
     
     
        #succsseur : int
        successeur = 0
     
     
        if ( len(liste_succ)>0 ):
            for successeur in liste_succ:
                CalculBorneInf(Arbre, tA, tB, cAB, cBA, dA, dB,successeur)
     
     
            for successeur in liste_succ:
                tab1.append(min(dA[successeur],dB[successeur] + cAB[successeur]))
                tab2.append(min(dB[successeur], cBA[successeur] + dA[successeur]))
     
            dA[u] += max(tab1)
            dB[u] += max(tab2)
     
        #return print("dA(",u,")=",dA[u],", dB(",u,")=",dB[u])
            return [dA, dB] 
     
     
     
     
    def CalculSigmaOptimum2(Arbre, tA, tB, cAB, cBA, DeltaA, DeltaB, Sigma, u):
        """List[int] ** 5 * int ** 4 ->
        calcule et renvoie une allocation sigma pour laquelle la duree est minimale. """
     
        #liste_succ: List[]
        liste_succ = [] 
        liste_succ = succ(u, Arbre)
     
        #successeur : int
        successeur = 0
     
     
        if (u == 0 and dA[0] <= dB[0]):
            Sigma[0] = 1
     
        elif (u == 0): 
            Sigma[0] = 0
     
        else:
     
            if (Sigma[Arbre[u]] == 1):
                if ( dA[u] < (dB[u] + cAB[u]) ):
                    Sigma[u] = 1
                else:
                    Sigma[u] = 0
     
            elif (Sigma[Arbre[u]] == 0):
                if (dB[u] < (dA[u] + cAB[u]) ):
                    Sigma[u] = 0
                else:
                    Sigma[u] = 1
     
        for successeur in liste_succ:
            CalculSigmaOptimum2(Arbre, tA, tB, cAB, cBA, DeltaA, DeltaB, Sigma, successeur)
     
        return Sigma
     
     
    def CalculArbreComplet(hauteur):
        """ int -> Arbre
        renvoie une arbre binaire complet. """
     
        #Complet : list[]
        Complet = []
     
        #nb_noeuds : int
        nb_noeuds = 0
        nb_noeuds = 2^(hauteur - 1) + 1 
     
        #Complet[0] : taille de l'arbre
        Complet.append(nb_noeuds)
     
        #i : int
        i = 0
     
        seed(10)
     
        while(i < nb_noeuds): 
     
            noeud = randint(0,1000)
     
            if noeud not in Complet:
                Complet.append(noeud)
                i = i+1 
     
     
        return Complet 
     
     
    def InstanceAleatoire(n, M):
        """int**2 -> list[]*
        renvoie toutes les valeurs numerique d'une instance de n taches."""
     
        # i : int
        i = 0
     
        # val : int
        val = 0
     
        # M = 50 pour les experimentations
     
        #tA, tB: list[int]
        tA, tB = [], []
     
        #cAB, cBA : list[int]
        cAB, cBA = [], []
     
        i=0
        while (i < n):
            val = randint( 1, M)
            if val not in tA:
                tA.append(val)
                i = i+1
     
        i=0
        while (i < n):
            val = randint( 1, M)
            if val not in tB:
                tB.append(val)
                i = i+1
     
        i=0
        while (i < n):
            val = randint( 1, M)
            if val not in cAB:
                cAB.append(val)
                i = i+1
        i=0
        while (i < n):
            val = randint( 1, M)
            if val not in cBA:
                cBA.append(val)
                i = i+1
     
        return print("tA =" ,tA, "\ntB =" ,tB, "\ncAB =" ,cAB, "\ncBA =" ,cBA, "\n")

Discussions similaires

  1. [Turbo Pascal] Implémentation d'un arbre binaire
    Par cm-punk dans le forum Turbo Pascal
    Réponses: 0
    Dernier message: 25/04/2014, 22h18
  2. [Turbo Pascal] Implémentation d'un arbre binaire de recherche
    Par Ema1714 dans le forum Turbo Pascal
    Réponses: 1
    Dernier message: 11/05/2013, 08h59
  3. Implémentation arbres binaires
    Par Arthur17 dans le forum C
    Réponses: 5
    Dernier message: 03/05/2011, 23h00
  4. Erreur implémentation d'arbre binaire de recherche.
    Par Pallas. dans le forum Débuter
    Réponses: 2
    Dernier message: 24/03/2011, 20h27
  5. Réponses: 2
    Dernier message: 13/02/2010, 17h45

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo