Cours d'introduction à l'Intelligence Artificielle

Liste des Projets, 2nd semestre 2006

Les projets se font soit par binômes, soit seul.

Vous pouvez proposer vos propres sujets si ils ont un rapport avec l'IA et les problèmes de satisfaction de contraintes.

Le langage de programmation est libre. Les programmes devront cependant tourner sur les ordinateurs du bocal.

Le projet compte pour 50% de la note finale.

Les projets seront soutenus à l'oral la dernière semaine de cours. Il faudra m'envoyer au moins une version préliminaire du code une semaine avant.

Avec le projet, fournissez un fichier de documentation, par exemple appelé README, qui explique au moins ce que fait le programme et comment l'utiliser. Parlez également des résultats obtenus par votre programme.

La qualité du code, sa lisibilité, la qualité des commentaires, rentrent pour une grande part dans l'évaluation. Je note principalement la partie intelligence artificielle du projet. D'autres aspects comme la qualité de l'interface pourront être appréciés mais sont secondaires.

Voici un texte écrit par Jean Méhat avec des conseils pour bien soigner le code d'un programme, et dont la lecture est conseillée.

Pour tout autre renseignement :


  1. Programme générique de résolution de problèmes cryptarithmétiques (Ali Badlou)

    Il s'agit de généraliser le programme, vu en cours, de résolution du fameux SEND+MORE=MONEY. Le programme cryptarithmétique sera donné au programme sous la forme d'une chaîne de caractères : "SEND+MORE=MONEY", ou bien "BILL+WILLIAM+MONICA=CLINTON", ou encore "USA+USSR=PEACE"... Cette chaîne pourra, par exemple être fournie sur l'entrée standart du programme. Écrire un programme de backtracking avec, si possible, des optimisations telles que la propagation de contraintes et la sélection de la variable la plus contrainte. Essayer aussi de représenter le problème avec une contrainte par colonne, plutôt que une pour toute l'addition.

  2. Coloriage de graphes (2 groupes : Rahmati, Nechache-Chergui)

    Un graphe est fourni au programme, ainsi que le nombre de couleurs autorisées. Le programme doit colorier le graphe de sorte que deux sommets adjacents n'aient pas la même couleur. Par exemple, les données du problème pourraient être :

    4 3
    1-2 1-3 1-4 2-3 3-4
    

    Pour indiquer un graphe à 4 sommets, à colorier avec 3 couleurs, correspondant à :

    Écrire un programme de backtracking le plus efficace possible pour colorier ces graphes.

  3. Un problème d'optimisation sous contrainte : construction d'emplois du temps

    On a un certain nombre de professeurs, un certain nombre de classes, un certain nombre de salles disponibles, un certain nombre de créneaux horaires par jour. On a aussi un certain nombre de cours qui doivent être donnés chaque semaine par un certain professeur à une certaine classe. Trouver le "meilleur" emploi du temps possible, selon des critères tels que :

  4. Arrangements de pentominos

    On dispose de 12 formes appelées pentominos :

           +      +    ++
    +++++  ++++  ++++   +++
    
    +    +++  ++    +   +    ++
    +     +    +   +++  +++   ++
    +++   +    ++   +    +     +
    
    ++   + +
    +++  +++
    

    et on souhaite les arranger dans un carré de taille 8x8, en laissant 4 trous au centre :
    ........
    ........
    ........
    ...  ...
    ...  ...
    ........
    ........
    ........
    

    Résoudre ce problème avec un programme de backtracking. Trouver toutes les solutions.

    On pourra aussi essayer d'arranger les 12 pentominos dans un volume 5x4x3 (en supposant aue les pentominos ont une épaisseur de 1, et qu'on peut les tourner dans n'importe quel sens dans l'espace)

  5. Puzzles de type Nikoli
    Ces puzzles sont un peu semblables au sudoku. Voir la page wikipedia en anglais pour un inventaire ; certains ont aussi des pages en français. Voir aussi Le site web http://www.puzzle.jp/en/.
    1. Kakuro (OUERYEMCHI Abdessamad)

      Écrire un programme de résolution de grilles de Kakuro (lien wikipedie française)).

    2. Hitori (Okiemba Bernard ?)
    3. Picross

      Écrire un programme de résolution de grilles de Picross (lien wikipedie française).

    4. Hashiwokakero
    5. Voir d'autres exemples sur la page wikipedia
  6. Satisfaction d'expressions booléennes (2 groupes: Zaki ; Okiemba Bernard aussi ?)
    Le programme recoit en entrée une expression booléenne sous forme normale conjonctive ; par exemple, l'expresssion (a OU b) ET ((NON b) OU (NON c)) ET (c OU (NON a)) ET ((NON a) OU b OU (NON c)) pourrait être entrée sous la forme :
    a b
    B C
    c A
    A b C
    
    Le programme cherche une solution par backtracking ; dans ce cas, il doit répondre : a=0, b=1, c=0.
  7. Résolution de sudoku en copiant les raisonnements humains
    Le programme recoit en entrée un problème de sudoku, et il cherche à le résoudre en se limitant à aux types de raisonnements qui sont utilisés par des joueurs humains. Pour commencer, remplir des cases quand on est sûr qu'elles ne peuvent contenir qu'une valeur ou quand on est sûr qu'une valeur ne peut aller que dans une case ; des techniques plus compliquées s'appellent "paires nues", "paires cachées", "triplets nus"...