Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Issue on page /content/appr/theme/algo2/cours/heuristiques/eleve.html #63

Open
redelmann opened this issue Mar 24, 2022 · 28 comments
Open

Issue on page /content/appr/theme/algo2/cours/heuristiques/eleve.html #63

redelmann opened this issue Mar 24, 2022 · 28 comments
Assignees
@biljana-petreska-gyyv

Comments

@redelmann
Copy link
Collaborator

La solution de l'exercice 2 est fausse. Même en parcourant deux fois ça reste du n^2.
@elliotvaucher
Copy link
Collaborator

Bonjour @redelmann, merci pour l'issue. J'assigne @biljana-petreska-gyyv, pour voir si elle peut intervenir.

@mihersch
Copy link
Contributor

L'exercice est maintenant le 5.3. La réponse donnée est (à mon humble avis) correcte.

@jppellet
Copy link
Contributor

Je pense aussi que la réponse est correcte.

@redelmann
Copy link
Collaborator Author

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:
            ...

@jppellet
Copy link
Contributor

Ç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é!

@redelmann
Copy link
Collaborator Author

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:
        ...

@jppellet
Copy link
Contributor

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.

@redelmann
Copy link
Collaborator Author

Ha oui, alors je l'avais vraiment pas compris comme ça.

@redelmann
Copy link
Collaborator Author

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 ?

@jppellet
Copy link
Contributor

Mieux, à mon avis!

@mihersch
Copy link
Contributor

mihersch commented Aug 17, 2022 •
edited
Loading

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...

@mihersch mihersch reopened this Aug 17, 2022
@biljana-petreska-gyyv
Copy link
Contributor

biljana-petreska-gyyv commented Aug 17, 2022 via email

@redelmann
Copy link
Collaborator Author

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)).

@redelmann
Copy link
Collaborator Author

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.

@jppellet
Copy link
Contributor

Ç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?

@redelmann
Copy link
Collaborator Author

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.

@biljana-petreska-gyyv
Copy link
Contributor

biljana-petreska-gyyv commented Aug 17, 2022 via email

@redelmann
Copy link
Collaborator Author

redelmann commented Aug 18, 2022 •
edited
Loading

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

@biljana-petreska-gyyv
Copy link
Contributor

biljana-petreska-gyyv commented Aug 18, 2022 via email

@redelmann
Copy link
Collaborator Author

Oui, j'ai édité, c'était une typo. C'est x2 à la place de x3.

@biljana-petreska-gyyv
Copy link
Contributor

biljana-petreska-gyyv commented Aug 18, 2022 via email

@redelmann
Copy link
Collaborator Author

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

@biljana-petreska-gyyv
Copy link
Contributor

biljana-petreska-gyyv commented Aug 18, 2022 via email

@jppellet
Copy link
Contributor

jppellet commented Aug 18, 2022 •
edited
Loading

Non, comme s3 est un hashset, la plupart du temps, c'est même O(1) (cf. https://wiki.python.org/moin/TimeComplexity#set).

@biljana-petreska-gyyv
Copy link
Contributor

biljana-petreska-gyyv commented Aug 18, 2022 via email

@ofleveque
Copy link
Contributor

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.

@biljana-petreska-gyyv
Copy link
Contributor

biljana-petreska-gyyv commented Aug 22, 2022 via email

@redelmann
Copy link
Collaborator Author

redelmann commented Oct 11, 2022 via email

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@biljana-petreska-gyyv biljana-petreska-gyyv

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
6 participants
@jppellet @redelmann @mihersch @biljana-petreska-gyyv @ofleveque @elliotvaucher