Discussion :

[melissa17]

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

[Flodelarab]

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

[melissa17]

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.

[Flodelarab]

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.

[melissa17]

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

[anapurna]

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