Le dernier partiel aura lieu le 7/1/2020 à 9h en amphi A2.
Il n'est pas certains que tous puissent se rendre à l'Université
à cette date. Pour ceux qui pourront venir, pas de problème. Pour
les autres une seconde tentative de dernier
partiel aura lieu le 14/1/2020, à 9h en amphi A2.
La remise des projets sous format électronique est maintenue pour
le lundi 6/1/2020 à 9h (mail).
Par contre, la version papier peut, en cas d'incapacité à se
rendre à l'Université, être faite par courrier adressé
à :
JJ Bourdin, Dept Informatique, 2 rue de la Liberté, 93526
Saint-Denis.
Projets encore libres : 1 4 5 7 9 10 11 12 13 14 15 16 23 25 27
Conditions
Le choix des sujets de projets sera fait par binôme.
Les projets devront être rendus sous un format électronique le
lundi 6 janvier 9hh00 (Paris Time) et sous format papier le
même jour à 14h dernier délai.
(tout jour de retard entamé
entraîne
une pénalité de 2 points).
Le projet rendu comprendra :
- un listing du programme,
- un commentaire (avec descriptif des fonctions écrites et des
choix de programmation faits),
- un jeu d'essai,
- un mode d'emploi
Liste des projets encore libres :
1 4 5 7 9 10 11 12 14 15 16 23 25 27
- Interprête Lisp :***
Il s'agit créer en Lisp un interprète Lisp (c'est-à-dire un ensemble
de fonctions permettant de définir de nouvelles fonctions, de les
tester et de les utiliser). Par exemple, une fonction est, dans ce cas,
une liste de deux termes : une liste de paramètres et une liste
"programme". Il faudra bien sûr gérer une liste "environnement global"
contenant les associations (nom, objet).
L'utilisateur pourra, après avoir lancé votre fonction, entrer une
nouvelle liste fonction puis s'en servir.
Des fonctions
d'analyses des fonctions ainsi créées peuvent être ajoutées au projet.
-
Sudoku : **
Vous connaissez le Sudoku. Il s'agit de mettre en place un programme
qui donne la solution d'un problème. On notera par 0 les cases vides.
Il y a une liste de 81 cases. Le travail peut suivre la
séquence suivante :
- Faire une fonction qui prend deux paramètres, x et y, et donne
le numéro de la case, parmi les 81 cases.
- Faire une fonction qui prend deux paramètres, x et y, et donne
la valeur présente dans cette case.
- Faire une fonction qui prend trois paramètres, x et y, d'une part,
la valeur v d'autre part, et renvoie "#t" si on a le droit de poser
v sur cette case et "#f" sinon.
- Faire une fonction qui crée la liste des valeurs possibles pour
une case vide donnée.
- Faire une fonction qui prend une grille (une problème ) et la remplit complétement.
- Adapter ce programme à des jeux de tailles 16x16 (nombres écrits
en hexadécimal).
-
Sokoban : *
Mettre en place un programme qui propose des solutions à des problèmes
(niveaux) de Sokoban. Le programme proposera de préférence la
meilleure solution possible (minimisant le nombre mouvements à
effectuer).
-
Dérivation de fonctions : ***
Soit une fonction numérique. Cette fonction peut être dérivée, on peut
donc construire une fonction qui est sa dérivée. À vous de construire
la fonction "derive" qui dérive toute fonction numérique. Il faut
aussi que le résultat obtenu puisse être, à nouveau, multiplié,
additionné, appliqué ou même dérivé.
Il faut bien sûr que la fonction construite puisse être utilisée,
qu'on puisse, par exemple, calculer la valeur de la dérivée de la
fonction carré en x=2.
Il faut commencer par écrire une fonction qui prend le corps d'une
fonction (une liste) et donne la liste correspondant à la dérivée de
cette expression.
On considérera dans un premier temps uniquement des fonctions à une
seule variable, x.
Faites d'abord la dérivée des fonctions
simples avant de faire des fonctions plus complexes.
-
Forme polonaise inverse *
Une expression lisp est écrite dans la forme préfixée, opérateur puis
opérandes. Mais ceci impose de gérer des parenthèses pour que les
paramètres puissent être séparés et les opérations compléxifiées. Il
est plus simple de travailler en notation postfixée, dans ce cas, un
opérateur n'est écrit que lorsque tous ces opérandes sont déjà
donnés. Par exemple, si (+ (* 3 2) 5) vous paraît clair, 3 2 * 5 +
l'est tout autant.
Fabriquer une calculatrice polonaise inverse en Lisp. Il devra être
possible de faire des calculs même complexes, de mémoriser des valeurs
(et de les rechercher si besoin), voire, même, de créer des fonctions
qui seront donc écrites en post-fixé.
On pourra continuer jusqu'à fabriquer un interprête pseudo-lisp
post fixé.
- Grand Fibonacci : **
Pour calculer la suite de Fibonacci sur de très grands nombres il faut
pouvoir calculer de très grands nombres, c'est-à-dire des nombres
qui sont des listes de chiffres. Il faut pouvoir faire l'addition,
la multiplication et même la division par 2 de tels nombres. À
partir de là, mettre en place une fonction de Fibonacci qui permette
d'obtenir de grandes valeurs comme la 1000 ième, ou la 100 000 ième, valeur
de la suite.
- Polynômes : ***
Un polynôme
est une liste de monômes. On peut le dériver, ou
l'intégrer, l'appliquer à une valeur, en additionner, soustraire,
multiplier ou diviser deux... Il faut pouvoir enchaîner les calculs,
mémoriser les polynômes produits...
- Analyseur grammatical :***
Il faut pouvoir analyser une phrase française.
? (analyse '(Je fais souvent ce reve etrange et penetrant d une femme
inconnue))
verbe : fais (faire)
sujet : Je (premiere personne singulier)
complement : ce reve etrange et penetrant d une femme inconnue
adverbe : souvent
|
Il est conseillé de mettre le résultat de l'analyse dans une liste
(dite "liste grammaticale") avec comme premier terme le verbe, ou la
liste groupe verbe, comme second terme le sujet, sous forme de liste,
sans doute, etc.
En particulier, il faut que l'analyseur décide où est le groupe verbal,
le groupe sujet, les propositions subordonnées relatives... La phrase
sera codée sous la forme d'une liste de mots.
Un dictionnaire partiel
de mots pourra être
classé par catégories (noms, verbes...) mais il faudra traiter les
cas, nombreux, de polysémie.
Une bonne méthode serait de commencer par transformer la phrase (liste
de mots) en phrase organisée (liste de listes de mots).
- Correction grammaticale :***
Vous utiliserez les travaux du groupe précédent pour détecter les
fautes de grammaire dans un texte (présenté sous la forme d'une
liste grammaticale).
Votre programme pourra proposer des corrections.
- Analyseur grammatical anglais : ***
Il faut pouvoir analyser une phrase anglaise.
En particulier, il faut que l'analyseur décide où est le groupe verbal,
le groupe sujet, les propositions subordonnées relatives... La phrase
sera codée sous la forme d'une liste de mots.
Un dictionnaire partiel
de mots pourra être
classé par catégories (noms, verbes...) mais il faudra traiter les
cas, nombreux, de polysémie.
Une bonne méthode serait de commencer par transformer la phrase (liste
de mots) en phrase organisée (liste de listes de mots).
- Traducteur français-anglais : * à **
Il faut ici prendre en données une phrase française sous la forme
d'une liste grammaticale et en donner, sous la même forme, une
traduction anglaise. Si vous ne donniez pas une forme
grammaticale mais une liste simple, votre traduction ne serait que
du mot-à-mot sans intérêt.
- Accord du participe passé :**
Il s'agit de créer une série de fonctions qui, dans une phrase, trouvent
les participes passés et les accordent en fonction des règles en vigueur
en français.
- Go : **
Vous devez générer une fonction LISP qui analyse une
situation de Go, par exemple élimine les groupes morts. Il est aussi
possible de positionner un "problème" de Go (vie et mort d'un groupe,
prise...) sur un Goban réduit. Faites ces fonctions et aidez-nous à
résoudre des problèmes élémentaires.
Voici deux situations "simples" et une situation moins
immédiate. Que doit jouer 1 pour tuer 2 ?
Votre programme devra donc prendre une telle liste et "trouver la solution".
- Cubes : ***
Des cubes sont
posés sur une table, ou les uns sur les autres.
L'utilisateur définit une situation de départ et une situation
d'arrivée... et votre programme lui donne la liste des mouvements à
effectuer pour arriver à cette situation. On ne peut déplacer les cubes
que un à un (pas en pile). Attention, on ne dispose que de trois
positions au sol (dans l'exemple ci-dessous l'une est occupée par B).
Exemple
Départ: |
A sur B, C sur A, B sur Sol |
Arrivée : |
A sur Sol, C sur A, B sur Sol |
Mouvements : |
Poser C sur Sol ; Poser A sur Sol ; Poser C sur A |
- Rubiks hypercube : ***
Dans un espace à, par exemple, 4 dimensions, un cube est un objet
à 8 faces. Il est possible de mettre en place des rotations le
long de chacune de ces faces.
- Imaginez un Rubiks hyper cube d'un espace à 4 dimensions. Dans
un premier temps il y aura 3x3 cases par face.
- Mettez en place la possibilité de jouer avec un tel objet.
- Faites une fonction qui "mélange" l'hypercube.
- Faites une fonction qui résout l'hypercube, c'est-à-dire qui
décrit toutes les rotations à effectuer.
- Toutes les fractales : ***
Faire un programme qui prend une grammaire et construit la
fonction fractale correspondante.
Affichez la fractale obtenur.
- Suites : *
Soit la suite suivante:
| u(0)=8 |
| si u(i) est pair |
u(i+1)=(3 * u(i))/2 |
| si u(i) est de la forme 4*n+1 |
u(i+1)=3*n + 1 |
| si u(i) est de la forme 4*n-1 |
u(i+1)=3*n - 1 |
Notons quelques valeurs de la suite :
u(0)= 8 (nombre pair) donc u(1)=12 (pair) dont u(2)=18 (pair) donc
u(3)=27 (impair, de la forme 4*7 - 1) donc u(4)=20 (pair) u(5)=30
(pair)
u(6)=45 (de la forme 4*11+1) u(7)=32... et ainsi de suite. Notons que
sur toutes les valeurs rencontrées, on n'est jamais passé deux fois
sur la même.
Dire, à propos de cette suite, si il existe deux valeurs différentes j
et k telles que :
u(j) = u(k)
On pourra suivre les étape suivantes :
- faire une fonction qui pour un élément de la liste, u(i), donne le
suivant, u(i+1). Notez que la valeur de i n'a aucune importance ici.
- Faire une fonction qui pour un n donné calcule u(n).
- Faire une fonction qui construit la liste de toutes les valeurs de
la suite.
- Faire une fonction qui, pour valeur x vérifie si elle appartient à
une liste et, si c'est le cas, renvoie le rang de l'élément (1 si
c'est le premier, 2 si c'est le deuxième...).
- Faire une fonction qui utilise les précédentes et satisfait à l'énoncé.
- Jeu du 7-0 : *
Il s'agit de programmer le jeu du 7-0. Dans ce jeu des joueurs se
succèdent pour jouer. A joue : il lance deux dés et les
additionne. Si l'addition vaut 7, ça fait 0 et il passe la
main. Sinon, il choisit, soit de conserver ce total, et il passe la
main, soit de continuer, il rejoue et obtient donc un total
partiel. Il peut ainsi jouer
une fois, deux fois, trois fois, dix fois peut-être. Mais dès qu'il
fait un 7, son total partiel est ramené à 0 et il passe la main.
Le vainqueur est le joueur qui a le plus de point à la fin du premier
tour de jeu où un joueur a obtenu 200. Exemple de début de partie :
| Joueurs : Total | dés successifs | Totaux
partiels | Total conservé |
| Ahmed :
0 | (3,2)(1,1)(6,6)(6,1) | 5,7,19,0 | 0 |
| Bob :
0 | (5,1)(2,2)(4,5)(1,1) | 6,10,19,21 | 21 |
| Claire :
0 | (6,5)(4,4)(5,4)(3,5) | 11,19,28,36 | 36 |
Exemple de second tour :
| Joueurs : total | dés successifs | Totaux
partiels | Total conservé |
| Ahmed : 0 | (6,5)(1,1)(3,5) | 11,13,21 | 21 |
| Bob : 21 | (2,2)(4,4)(4,2) | 4,12,18 | 39 |
| Claire : 36 | (5,1)(4,2) | 6,12 | 48 |
Faire un programme grâce auquel on puisse jouer à ce jeu contre l'ordinateur.
- Mastermind : ***
Vous connaissez le mastermind, où un joueur cache une combinaison de
valeurs et un autre essaie de la trouver à partir de la seule
indication du nombre du valeurs présentes et du nombre de valeurs
bien placées dans sa tentative.
Jouer contre l'ordinateur au mastermind est un programme assez
simple.
Faire jouer l'ordinateur, qui va donc chercher la solution, est plus
intéressant. Surtout si on essaie de minimiser le nombre de coups
à jouer. C'est le programme que vous devez écrire.
- Morpion : **
Soit une matrice de grande taille (100x100). Deux joueurs jouent en
posant des 1 ou des 2 dans des cases vides.
Première variante, le vainqueur est celui qui a, le premier, réussi à
aligner 5 de ses
valeurs.
Seconde variante, le vainqueur est celui qui, à l'issue d'un nombre de
coups prédéterminé, a le plus d'alignement de 5 de ses
valeurs (alignements disjoints).
Dans tous les cas il faut pouvoir jouer contre la machine.
Écrivez le programme !
- Morpion solitaire : **
Soit une matrice de grande taille (100x100). Un certaine nombre de
croix sont déjà posées. Il faut poser une croix qui finisse un
alignement de 5 croix. Et encore, et encore.
On peut se référer à
wikipédia pour en savoir plus.
Votre but est de faire un programme qui trouve une succession de coups
permettant d'approcher les 170 coups consécutifs.
- Problème du trafic : *
Le jeu "trafic" est un jeu très simple des véhicules sont
bloqués à un carrefour et ne peuvent que avancer ou reculer (pas
tourner). Une seule case est libre. Un véhicule doit pouvoir traverser
le carrefour.
Trouver une bonne présentation du problème.
Mettre en place une méthode de résolution du problème.
- Problème du chameau : *
Vous connaissez aux échecs le mouvement et le
problème du cheval ? Hé bien, ce n'est pas celui-là que je vous
propose, mais celui du chameau. Il s'agit pour un chameau de parcourir
l'échiquier, en passant par chaque case, une fois et une seule. Le
mouvement du chameau donne le mal de mer car il s'agit d'un mouvement
alterné composé d'un pas de côté (une case parmi les quatre voisines)
suivi d'un quasi-pas de cheval (trois dans une direction et une dans l'autre
axe). Par exemple, à partir de la case A1, le chameau peut passer
(premier coup) en A2 (ou en B1) puis (deuxième coup) en B5 (ou C4
ou...) puis, de là, en (troisième coup) C5. And so on.
Le problème du chameau consiste à trouver une solution pour
faire passer le chameau, une fois et une seule, sur toutes les cases
de l'échiquier.
Vous devez programmer une fonction qui résoud le problème du chameau.
- Jeu du taquin :**
On veut faire jouer la machine au taqui avec une position initiale donnée. Exemple
On veut obtenir ceci :
'(( 1 2 3 4)
( 5 6 7 8)
( 9 10 11 12)
(13 14 15 ))
on a ceci comme situation de départ :
'(( 1 2 3 4)
( 5 6 7)
( 9 10 11 8)
(13 14 15 12))
Comment arriver à la situation-résultat ?
Si on a comme situation de départ :
'((11 3 8 1)
( 5 4 13 7)
(12 15 10 2)
(14 9 6))
quels mouvements sont à faire pour résoudre le problème ?
C'est, évidemment, au programme de trouver les solutions !
- Récursivité terminale : . *
Écrire un programme qui prend en argument une liste correspondant à
une fonction et renvoie #t s'il s'agit d'une récursivité terminale
et #f sinon.
Attention, il peut y avoir des pièges...
- Fonctions récursives : . ***
C'est fatigant. On écrit cent fois la même fonction, c'est juste la
formule générale qui change :
U(n+1) = U(n) +n
U(0) = 0
donne un programme
U(n+1) = U(n) * n
U(0) = 1
en donne un autre très proche.
U(n+1) = U(n) +U(n-1)
U(0) = 1
U(1) = 1
en donne un troisième, quasi identique.
Comment faire pour donner une "formule" et faire calculer la fonction par Lisp ?
- Récursivité terminale automatique : ***
En vous inspirant des travaux de vos camarades du projet précédent,
travailler sur une fonction qui prend en argument le corps d'une
fonction récursive (sous forme de liste) et qui renvoie la même en récursivité
terminale. Attention, ce projet n'est pas facile.
- Méta-programmation : ***
Nous avons écrit des séries de fonctions souvent identitiques,
numériques ou sur les listes.
Nous avons appris en en remplacer quelques unes par l'application
d'une fonction à une liste, voir de deux fonctions à une
liste.
Vous devez maintenant faire une, ou des fonctions, permettant de
générer automatiquement les fonctions demandées dans les premiers
exercices du cours. Les fonctions obtenues serons conservées sous
la forme de listes et pourront être utilisées après une évaluation
de la liste.
Fait le 3/1/2020 à 16h