Aperçu des sections

  • Généralités

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

    Dossier: 1 Devoir: 1

  • Déplacements dans le plan.

    Dans cette partie, nous allons nous intéresser au fameux problème du voyageur de commerce. On considère un plan avec un nuage de points, définis par leurs coordonnées. L'objectif du voyageur de commerce est de visiter tous les points du parcours et de revenir au point de départ, en parcourant la plus petite distance.


    Dossier: 1 Devoir: 1

  • Dungeon crawling

    L'énoncé de cet exercice est issu de la BattleDev 2019, et a pour objectif d'implémenter l'algorithme attendu au cours de cet événement.

    Vous êtes un.e explorat.eur.rice, et vous vous trouvez au milieu d'un long couloir. Dans ce couloir, vous pouvez trouver:

    • des pièces d'or ('o'). Quand vous trouvez une pièce d'or, vous pouvez la ramasser, et accroître votre butin de 1.
    • des portes magiques ('*'). Ces portes obstruent totalement le couloir, et il est impossible de traverser une porte sans l'activer. À chaque fois que vous traversez une porte magique, le butin que vous transportez double.

    À l'entrée du couloir, vous avez trouvé un plan du couloir, et vous disposez d'une connaissance complète du contenu de celui-ci. Ce plan du couloir a l'aspect d'une chaîne de caractères, comportant des 'o' et des '*' correspondant aux éléments précédents, ainsi qu'un 'X' qui est votre position initiale.

    Vous êtes infatigable, et peu importe la distance à parcourir, vous voulez maximisez votre butin avant de quitter le couloir. Une telle opportunité ne se représentera sans doute pas de sitôt.

    Dans la suite de l'exercice, vous devez écrire des méthodes qui retournent la séquence de 'o' et de '*' que vous rencontrez dans l'ordre où vous les rencontrez. selon l'algorithme établi.

  • Le sac à dos

    Dossier: 1

  • Max 3-SAT

    L'objectif de ces deux séances est de travailler sur des formules 3-SAT, via le problème MAX 3-SAT:

    https://en.wikipedia.org/wiki/MAX-3SAT

    Vocabulaire:

    • Variables: les variables qui composent une formule sont des variables booléennes, pouvant prendre pour valeur vrai ou faux.
    • Littéraux: un littéral est constitué d'une variable ou de sa négation.
    • Clause: une clause est une disjonction de littéraux (un ou logique). Dans 3 SAT, on ne s'occupe que de clauses composées de exactement 3 littéraux.
    • Formule (sous forme normale conjonctive): une formule est une conjonction de clauses.  Dans le problème présent, on peut simplement la voir comme un ensemble de clauses.
    Un exemple de formule pourrait être:

    Le problème

    Le problème Max 3-SAT se décrit ainsi:
    Entrée:
    une formule 3-SAT. Ou encore, simplement un ensemble de 3-clauses.
    Sortie:
    Le nombre maximum de clause pouvant être satisfaite dans la formule.
    On peut aussi fournir un certificat, c'est à dire une affectation des variables qui valide ce nombre de clauses.

    Dossier: 1 Zone texte et média: 1

  • BattleDev-2020

    Nous allons maintenant nous intéresser à l'exercice clé de la battledev d'hier soir, le problème de la brochette.

    Ici, il s'agissait comme souvent à ce stade de la compétition de trouver un algorithme de programmation dynamique.


    Fichier: 1