book
book copied to clipboard
edunumsec2
Issue on page /content/appr/theme/algo2/cours/heuristiques/eleve.html
La solution de l'exercice 2 est fausse. Même en parcourant deux fois ça reste du n^2.
Bonjour @redelmann, merci pour l'issue. J'assigne @biljana-petreska-gyyv, pour voir si elle peut intervenir.
L'exercice est maintenant le 5.3. La réponse donnée est (à mon humble avis) correcte.
Comme l'énoncé est formulé je comprends le programme comme:
for x in xs:
...
for x1 in xs:
for x2 in xs:
...
C'est aussi l'interprétation de la personne qui m'avait signalé le problème.
Ça mériterait d'être un peu plus clair dans le formulation à mon avis si on considère plutôt:
for x1 in xs:
for x2 in xs:
for x3 in xs:
...
Ça me semblait clair, si on comprend que tu parcours le tableau pour chaque paire. Après, s'il y a quelqu’un pour qui c'est pas clair, c'est qu'en effet, ça peut mériter d'être clarifié!
Ha, je vois ! Il faut le comprendre ça comme ?
for x in xs:
parcourir(xs)
for x1 in xs:
for x2 in xs:
parcourir(xs)
def parcourir(xs):
for x in xs:
...
Je le voyais juste comme ça:
for x1 in xs:
for x2 in xs:
for x3 in xs:
ou comme tu viens d'écrire, mais dans la boucle initiale alors.
Quelque chose du style ?
Quelle est la complexité d'un algorithme qui, pour chaque paire d'éléments d'un tableau, effectue une opération qui traverse à nouveau tous les éléments du tableau ?
Moi je l'ai compris comme Romain (2e version).
for x in xs: parcourir(xs) for x1 in xs: for x2 in xs: parcourir(xs) def parcourir(xs): for x in xs: ...
La formulation de Romain est effectivement un peu plus claire, mais l'exercice est aussi simplifié... Du coup je rouvre et laisse @biljana-petreska-gyyv commenter...
merci de vous êtes creusé la tête, j'ai entre temps eu l'idée d'une autre formulation plus claire. mais comme c'est pour l'année 2 ça va attendre...
ça va être un truc dans le genre 3 listes de nombres, peut-on arriver à un autre nombre en prenant un élément de chaque tableau et en faisant la somme.
je cherche toujours s'il y a un exemple d'application dans la vie courante.
merci !
On Wed, Aug 17, 2022 at 4:16 PM mihersch @.***> wrote:
Reopened #63 https://github.com/edunumsec2/book/issues/63.
— Reply to this email directly, view it on GitHub https://github.com/edunumsec2/book/issues/63#event-7206409604, or unsubscribe https://github.com/notifications/unsubscribe-auth/AIHDAGOOYFJS7QPQN66UHYLVZTXGTANCNFSM5RRSUF6A . You are receiving this because you were mentioned.Message ID: @.***>
Amandine cherche à acheter trois bâtons pour former un cadre triangulaire pour un projet d'art visuel. Selon les instructions de l'enseignant, les trois bâtons doivent obligatoirement former un triangle rectangle. Amandine passe au magasin de bricolage et se rends compte qu'il y a beaucoup de longueurs différentes ! Amandine note toutes les longueurs de bâtons disponibles et essaie de trouver une combinaison qui fonctionne à l'aide d'un algorithme...
Décris un algorithme pour trouver une combinaisons de trois longueurs a, b, et c avec pour propriété a^2 + b^2 = c^2 tant donné un tableau des longueurs disponibles. Si une telle combinaison n'existe pas, l'indiquer.
La solution naïve est en O(n^3), et avec une recherche dichotomique O(n^2 * log(n)).
Plus proche de ta question: Trois amis organisent une fête, avec un budget total de N. L'un s'occupe d'organiser les boissons, l'autre la nourriture et le troisième la salle et l'équipement. Chaque ami note dans son propre tableau le prix de diverses options pour la partie sous sa responsabilité. Étant donné les trois listes de prix, décris un algorithme pour trouver trois options (une pour les boissons, une pour la nourriture et une pour l'équipement) qui somment au budget total N.
Même complexité qu'avant.
Ça pourrait se faire en O(n²) avec un hashset qu'on remplirait en parcourant les paires et en y insérant la somme, non?
En pratique, clairement oui. Mais, pour être pédant, en théorie la complexité worst-case de l'appartenance à un hashset c'est O(log(n)) à cause des collisions que tu dois gérer par derrière.
Mais c'est quand même nxn combinaisons xn ça fait toujours n^3 non ?
On Wed, Aug 17, 2022 at 6:17 PM Jean-Philippe Pellet < @.***> wrote:
Ça pourrait se faire en O(n²) avec un hashset qu'on remplirait en parcourant les paires et en y insérant la somme, non?
— Reply to this email directly, view it on GitHub https://github.com/edunumsec2/book/issues/63#issuecomment-1218227577, or unsubscribe https://github.com/notifications/unsubscribe-auth/AIHDAGKC5NM5RZ3WMM4ZOSTVZUFO7ANCNFSM5RRSUF6A . You are receiving this because you were mentioned.Message ID: @.***>
Deux solutions en O(n^2 * log(n)).
def f1(xs1, xs2, xs3):
sort(xs3)
for x1 in xs1:
for x2 in xs2:
x3 = x1 + x2
if binary_search(x3, xs3):
return (x1, x2, x3)
return None
# Ou, avec un set
def f2(xs1, xs2, xs3):
s3 = set(xs3)
for x1 in xs1:
for x2 in xs2:
x3 = x1 + x2
if x3 in s3:
return (x1, x2, x3)
return None
un truc qui m'échappe
x3 = x1 + x3
x3 n'est pas défini, ça plante il me semble
On Thu, Aug 18, 2022 at 8:15 AM Romain Edelmann @.***> wrote:
Deux solutions en O(n^2 * log(n)).
def f1(xs1, xs2, xs3): sort(xs3)
for x1 in xs1: for x2 in xs2: x3 = x1 + x3 if binary_search(x3, xs3): return (x1, x2, x3) return NoneOu, avec un set
def f2(xs1, xs2, xs3): s3 = set(xs3)
for x1 in xs1: for x2 in xs2: x3 = x1 + x3 if x3 in s3: return (x1, x2, x3) return None— Reply to this email directly, view it on GitHub https://github.com/edunumsec2/book/issues/63#issuecomment-1219073676, or unsubscribe https://github.com/notifications/unsubscribe-auth/AIHDAGLLQ6XVCPJU2CGYKJ3VZXHBJANCNFSM5RRSUF6A . You are receiving this because you were mentioned.Message ID: @.***>
je ne vois pas où est stocké le nombre auquel on doit arriver ?
On Thu, Aug 18, 2022 at 9:44 AM Romain Edelmann @.***> wrote:
Oui, j'ai édité, c'était une typo. C'est x2 à la place de x3.
— Reply to this email directly, view it on GitHub https://github.com/edunumsec2/book/issues/63#issuecomment-1219140940, or unsubscribe https://github.com/notifications/unsubscribe-auth/AIHDAGOKE4YJUUHZEGPHAHDVZXSBXANCNFSM5RRSUF6A . You are receiving this because you were mentioned.Message ID: @.***>
Là c'était pour trouver deux nombres qui somment à un troisième. Si tu veux trouver trois nombres qui somment à n, l'idée est la même:
def f2(xs1, xs2, xs3, n):
s3 = set(xs3)
for x1 in xs1:
for x2 in xs2:
x3 = n - (x1 + x2)
if x3 in s3:
return (x1, x2, x3)
return None
Alors un truc qui m'échappe. On est d'accord que
if x3 in s3:
peut prendre n dans le worst-case scenario, si les options ne sont pas triées.
On Thu, Aug 18, 2022 at 1:40 PM Romain Edelmann @.***> wrote:
Amandine cherche à acheter trois bâtons pour former un cadre triangulaire pour un projet d'art visuel. Selon les instructions de l'enseignant, les trois bâtons doivent obligatoirement former un triangle rectangle. Amandine passe au magasin de bricolage et se rends compte qu'il y a beaucoup de longueurs différentes ! Amandine note toutes les longueurs de bâtons disponibles et essaie de trouver une combinaison qui fonctionne à l'aide d'un algorithme...
Décris un algorithme pour trouver une combinaisons de trois longueurs a, b, et c avec pour propriété a^2 + b^2 = c^2 tant donné un tableau des longueurs disponibles. Si une telle combinaison n'existe pas, l'indiquer.
La solution naïve est en O(n^3), et avec une recherche dichotomique O(n^2
- log(n)).
— Reply to this email directly, view it on GitHub https://github.com/edunumsec2/book/issues/63#issuecomment-1218166069, or unsubscribe https://github.com/notifications/unsubscribe-auth/AIHDAGPHP3RZHA3PMP6OALLVZUAM3ANCNFSM5RRSUF6A . You are receiving this because you were mentioned.Message ID: @.***>
Non, comme s3 est un hashset, la plupart du temps, c'est même O(1) (cf. https://wiki.python.org/moin/TimeComplexity#set).
ah ok, alors je ne sais pas si on peut restreindre sur le fait d'utiliser uniquement des listes ? en fait c'est tout con, l'idée était de leur faire "généraliser" le parcours imbriqué, et qu'ils réalisent que c'est long.
@romain pour les prix j'aime bien, j'y avais pensé, mais en général on alloue des budgets séparés. Mais c'est ce qui se rapproche le plus. Ou construire une table de multiplication, ça donnera pas envie à tous
On Thu, Aug 18, 2022 at 2:18 PM Jean-Philippe Pellet < @.***> wrote:
Non, comme s3 est un hashset, la plupart du temps, c'est même O(1).
— Reply to this email directly, view it on GitHub https://github.com/edunumsec2/book/issues/63#issuecomment-1219422258, or unsubscribe https://github.com/notifications/unsubscribe-auth/AIHDAGPAAROKJXEJY4RV5CDVZYS2RANCNFSM5RRSUF6A . You are receiving this because you were mentioned.Message ID: @.***>
Hello! Si j'ose rajouter mon grain de sel... Il me semble que l'énoncé de l'exercice:
"Quelle est la complexité d’un algorithme qui pour chacun de ses éléments doit parcourir le tableau, puis pour chaque combinaison de deux de ses élements doit encore parcourir le tableau ?"
est très (trop?) abstrait pour des gymnasiens. Je serais assez en faveur d'une des deux formulations suggérées par Romain, plus concrètes.
oui oui, c'est prévu de la changer. mais pas trouvé d'attracteur stable pour l'instant
On Mon, Aug 22, 2022 at 1:38 PM ofleveque @.***> wrote:
Hello! Si j'ose rajouter mon grain de sel... Il me semble que l'énoncé de l'exercice:
"Quelle est la complexité d’un algorithme qui pour chacun de ses éléments doit parcourir le tableau, puis pour chaque combinaison de deux de ses élements doit encore parcourir le tableau ?"
est très (trop?) abstrait pour des gymnasiens. Je serais assez en faveur d'une des deux formulations suggérées par Romain, plus concrètes.
— Reply to this email directly, view it on GitHub https://github.com/edunumsec2/book/issues/63#issuecomment-1222233547, or unsubscribe https://github.com/notifications/unsubscribe-auth/AIHDAGIVMJJ6LQ752QYSCTLV2NRCZANCNFSM5RRSUF6A . You are receiving this because you were mentioned.Message ID: @.***>
Comme c'est formulé je le comprends comme:
for x in xs:
...
for x1 in xs:
for x2 in xs:
...
C'est aussi l'interprétation de la personne qui m'avait signalé le problème.
Ça mériterait d'être un peu plus clair à mon avis.
On Wed, Aug 17, 2022, 11:26 Jean-Philippe Pellet @.***> wrote:
Je pense aussi que la réponse est correcte.
— Reply to this email directly, view it on GitHub https://github.com/edunumsec2/book/issues/63#issuecomment-1217750423, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAIMYHWVIDRUKU62TKYVLM3VZSV3DANCNFSM5RRSUF6A . You are receiving this because you were mentioned.Message ID: @.***>