Aperçu des sections

  • Un peu de complexité expérimentale.

    Dans cette première partie, nous allons expérimenter la question de la complexité algorithmique avec un exemple très élégant, le problème de l'élément majoritaire.

    input: Vous partez avec une urne, dans laquelle sont des bulletins nominatifs, chacun avec un nom. Vous ne savez a priori rien sur le nombre de noms, ni sur le nombre initial de bulletins, à part qu'il y en a beaucoup. Concrètement, l'urne est un itérateur java.

    output: si un candidat a obtenu strictement plus de la moitié des voies, son nom. Sinon, null.

    La question porte bien entendu sur l'efficacité de votre méthode...

    • Icône Dossier
      ballot Dossier

      Voici une base pour générer des bulletins de vote. Celle-ci est faite pour mettre à l'épreuve tous les aspects de votre code.

    • Icône Devoir
      version naive Devoir
      Remettre un travail

      La première approche s'appuie sur le vécu. Généralement, dans une urne, il n'y a pas des dizaines de bulletins différents.

      Nous allons donc

      • Collecter les noms des candidats mentionnés sur les bulletins dans un tableau ou dans une ArrayList
      • Collecter le nombre de bulletins correspondant dans une autre.

      Faites une classe FindMajority avec une méthode naiveResolution() qui applique cette stratégie, en vous appuyant sur le fichier inclu.

    • Icône Devoir
      Approche diviser pour régner Devoir

      La deuxième méthode que nous allons voir est une méthode dite "diviser pour régner" (divide and conquer). Elle s'appuie sur le constat suivant:

      S'il existe un candidat qui détient la majorité des bulletins sur l'urne toute entière, alors nécessairement, ce même candidat est majoritaire sur la première moitié de l'urne ou il est majoritaire sur la deuxième moitié.

      On peut maintenant proposer un algorithme récursif, en s'appuyant sur le principe suivant.

      • Dans une urne à une seule voix, le candidat majoritaire est le seul candidat exprimé.
      • Dans une urne plus grande, on trouve le candidat1 majoritaire dans la première moitié (éventuellement personne, i.e. null), le candidat2 majoritaire sur la deuxième moitié, et
        • si candidat1 = candidat2, il est majoritaire (même si les deux sont null, d'ailleurs!).
        • sinon, on compte les bulletins de candidat1, pour voir s'il est majoritaire, et à défaut, on procède de même pour candidat2.

      Vous n'avez plus qu'à ajouter une méthode solveDivide(ArrayList<String> box, int start, int end) qui cherche un élément majoritaire dans la section [debut, end[ du tableau.

      Non disponible à moins que : L’activité version naive soit marquée comme achevée
    • Icône Devoir
      Méthode maline Devoir
      Non disponible à moins que : L’activité Approche diviser pour régner soit marquée comme achevée

    • Vous pouvez maintenant voir ce qui se passe avec le premier algorithme en utilisant une HashMap.

      D'un point de vue théorique, qu'est-ce qui justifie toutes ces différentes complexité obtenues?

      Non disponible à moins que : L’activité Méthode maline groupe soit marquée comme achevée