Rémi Nollet et Jean-Jacques BOURDIN
Les projets doivent
être réalisés par binômes (C'est-à-dire par groupe de DEUX
étudiants).
Les projets devront être rendus le 8 avril 2021, avant 14 heures (heure de Paris)
Tout jour de retard entamé coûte deux points sur la note (sur vingt).
Il faut fournir :
Les énoncés sont accompagnés d'un indice de difficulté de 0 à 3 étoiles (*). Les projets les plus difficiles sont ceux pour lesquels l'écart-type est le plus important : il est probable de ne pas réussir et d'avoir une très mauvaise note, il est possible d'obtenir une excellente note. Les projets les plus faciles devraient ne pas présenter de difficulté mais il est quasi-impossible d'avoir une très bonne note.
Écrire en C un programme capable d'exécuter du scheme standard. Les programmes scheme peuvent être :
Ce grand mathématicien et informaticien anglais nous a offert un modèle d'ordinateur,
la "machine de Turing". Écrire en C un interprête de machines de
Turing.
Il faut donc que votre programme, écrit en C, lise un programme écrit sous la forme d'une table de transactions. Il lit ensuite une "bande" (sous la forme d'un vecteur de 0 et de 1). Puis il exécute le programme et produit la nouvelle bande.
Dans un premier temps la bande peut être gérée comme un vecteur de taille fixe.
Il faut aussi développer quelques programmes simples en code de Turing (un comparateur 4 bits, un additionneur...) et vérifier que votre machine les interprête correctement.
L'enseignant produira lui-même un programme simple en code de Turing, il faudra qu'il soit correctement interprété.Soit un terrain discret, donné par un tableau d'altitude de ses points. Le marcheur choisit deux points, un point de départ et un point d'arrivée. Il faut trouver un itinéraire entre ces deux points.
1) Essayer la ligne droite et calculer le dénivelé positif et le dénivelé négatif (i.e. le total des montées à faire et le total des descentes).
2) Essayer des variations autour de la ligne droite pour réduire le dénivelé positif.
3) Chercher un chemin réaliste, voire, chercher le meilleur chemin (par exemple le chemin qui minimise le dénivelé positif de tous les chemins possibles).
À défaut de trouver le meilleur chemin, chercher une méthode qui permette de trouver un chemin acceptable, au moins.
Un labyrinthe peut être vu comme une structure de graphe, c'est-à-dire que, pour chaque position, on connait un pointeur sur les positions disponibles à partir de là. Dans un labyrinthe 3D à salles cubiques, il y a au maximum 6 voisins pour chaque salle. À partir de chaque salle, il faut disposer d'une liste de salles atteignables directement.
Définir le labyrinthe de la façon la plus simple possible.
Programmer un algorithme qui trouve une façon de sortir du
labyrinthe quelle que soit la salle dans laquelle on se trouve.
Programmer une méthode permettant de trouver la façon la plus courte de sortir du labyrinthe quelle que soit la salle dans laquelle on se trouve.
Nous donnons ici un exemple de labyrinthe simple, mais il est possible
de faire plus retort.
Exemple
Chaque salle est donnée avec U (up) si on peut monter, D (down) si on
peut descendre et les quatre (eventuellement) murs.
|
|
||
| ----------------| | | | | | | | | | | | --------- | | | | | | | | | U | | | | | | | | | ---- | | | | | | | | | | | | | | | ------------- | | | | | | | |-------------------| | | | U U | | | |-------------------| |
|-------------------| | | | | | U | | | | | | | | -------- | | | | | D | | | | | | | ----| | | | | | | | | | | ------------ | | | | | | | | U | | | | | |---| ----- ----| | | | | D U | D | | | | --------------------- | |
|-------------------| | | | | D | U | | | | | | | | | | | | | |-------| | | | | | | | | | | | | ------------| | | | | | | | U D | | | | | | ----| --------| | | | | U | D | | | | --------------------- |
|-------------------| | | | D | | | | ------------- | | | | | | | | | | | | ------------| | | | | | | | | | | | | | ----- | | | | | | | | | | | D | | | | | | | |-------| |---| | | | | | | U D | U | U | | | | | |-------------------| |
|-------------------| | | | | | | | ------------- | | | | | | | | | | | | | --------| | | | | | | | | | | | | | | | | | | |---| | | | | | | | | | | | | | | | | | | ----| | | | | | | | | D | D | D | | | | | | | |---------------| | |
Dans beaucoup de calculs, une matrice est un grand tableau quasiment
vide. Au lieu de mémoriser la totalité du tableau, il convient
de ne remplir que les cases non nulles. On peut alors les mémoriser
sous la forme d'un triplet : < x, y, valeur >. De telles cases
sont liées entre elles par des pointeurs. Vous fabriquerez donc une
liste des cases non nulles de la matrice.
Cela s'étend bien sûr à
une autre matrice et à leur addition, leur multiplication... et à la
résolution d'une équation linéaire.
Mettre en place
une telle structure puis les opérations élémentaires entre deux ou
trois matrices.
Voici un exemple de système à résoudre :
( 5 0 2 0 1 0 0 0) ( a) ( 5) ( 0 3 0 2 0 0 0 0) ( b) ( 1) ( 2 0 3 0 2 0 0 0) ( c) ( 3) ( 0 2 0 3 0 2 0 0) ( d) ( 3) ( 0 0 2 0 3 0 2 0) x ( e) = ( 2) ( 0 0 0 2 0 3 0 2) ( f) ( 2) ( 0 0 0 0 2 0 3 0) ( g) ( 1) ( 0 0 0 1 0 2 0 3) ( h) ( 0)Vous pouvez, bien sûr le résoudre "à la main", mais les déterminants et les méthodes génériques sont vraiment utiles :-)
Vous pouvez obtenir une bonne infinité d'autres exemples auprès de votre enseignant (essayez tous les nombres possibles pour toutes les tailles possibles de matrice...).
Dans beaucoup de calculs, une matrice est un grand tableau quasiment
vide. Au lieu de mémoriser la totalité du tableau, il convient alors
de ne remplir que les cases non nulles. On peut alors les mémoriser
sous la forme d'une vecteur de lignes. Par exemple une ligne pour
chaque y. Puis dans chaque ligne se trouvent une série de paires :
< x, valeur >. Cette série de paires est, par nature, un
vecteur. Son nombre d'éléments est variable et devra être donné
pour chaque ligne.
Dans cette version, il n'y a plus de case non nulle.
Cela s'étend bien sûr à
une autre matrice et à leur addition, leur multiplication... et à la
résolution d'une équation linéaire.
Mettre en place
une telle structure puis les opérations élémentaires entre deux ou
trois matrices.
Voici un exemple de système à résoudre :
( 5 0 2 0 1 0 0 0) ( a) ( 5) ( 0 3 0 2 0 0 0 0) ( b) ( 2) ( 2 0 3 0 2 0 0 0) ( c) ( 1) ( 0 2 0 3 0 2 0 0) ( d) ( 2) ( 0 0 2 0 3 0 2 0) x ( e) = (- 2) ( 0 0 0 2 0 3 0 2) ( f) ( 0) ( 0 0 0 0 2 0 3 0) ( g) (- 1) ( 0 0 0 1 0 2 0 3) ( h) (- 1)Vous pouvez, bien sûr le résoudre "à la main", mais les déterminants et les méthodes génériques sont vraiment utiles :-)
Vous pouvez obtenir une bonne infinité d'autres exemples auprès de votre enseignant (essayez tous les nombres possibles pour toutes les tailles possibles de matrice...).
Le principe de ce jeu est simple : relier ses deux côtés opposés d'un plateau à maillage carré avec une chaîne ininterrompue de ponts. Les ponts sont à poser entre deux piles de la même couleur distantes d'un saut de cavalier des échecs.
On ne peut pas poser un pont qui croiserait un autre pont.
À chaque tour de jeu chaque joueur doit :
Créer un programme qui
Si vous avez le temps, vous pouvez aussi faire une présentation du jeu autrement que par des printf.
Ce jeu se joue sur un damier à deux joueurs. Il y a un pion blanc positionné au départ au centre du damier. A chaque tour chaque joueur peut soit positionner un pion noir sur le damier, soit deplacer le pion blanc. Le pion blanc se déplace comme un pion qui "mange un autre pion aux dames". Le but du jeu est d'emmener le pion blanc sur un des bords du damier (Nord pour le premier joueur et Sud pour le second).
On trouvera un bon résumé des règles sur ce site
Créer un programme qui
On mettra en place différentes
configurations de plateaux (comme par exemple un anneau de rayon 10 et
d'épaisseur 6).
Créez un programme qui
Soit une image en noir et blanc. Le stockage "quadtree" consiste à conserver un arbre de valeurs. Trois valeurs sont possibles : 0 (noir), 1 (blanc), 2 (ni noir, ni blanc). Dans le cas "gris", l'image est divisée en quatre quarts et chacun a une valeur, etc. On doit,
Comme première image de départ on prendra un rectangle, divisé selon
la diagonale principale, partie inférieure noire et partie supérieure
blanche.
Comme seconde image on prendra un L, d'épaisseur 20, de longueur et de
hauteur 100, placé à 50 pixels du coin inférieur gauche d'une image de
200 pixels de côté. Le L est en noir, le reste de l'image en blanc.
Soit un espace formé de cases cubiques (voxels) toutes de même taille. Il s'agit de calculer la trajectoire d'un rayon lumineux dans cet espace. On donnera ce rayon par les coordonnées de deux de ses points.
Puis calculer les voxels appartenant à un plan, puis à une sphère, puis à une surface complexe.
Il faudra enfin calculer l'intersection entre un rayon lumineux et une surface préalablement définie.
Soit un graphe, dont deux noeuds (D et A) sont particuliers et deux
joueurs, le lieur et le casseur. À chaque tour
de jeu, le casseur casse une arête entre deux noeuds. À chaque tour de
jeu, le lieur rend incassable une arête (non cassée) entre deux
noeuds. Si, à un moment du jeu, il n'y a plus aucun moyen d'aller de D
à A, le casseur a gagné. Si, à un moment donné, il existe un chemin
incassable reliant D à A, le lieur a gagné.
L'implémentation du ou des graphes devra être faite sous la forme soit de listes chaînées soit de tableaux d'arêtes et de brins (voir votre enseignant).
Jouer au morpion, c'est facile, vous avez tous fait cela.
On joue sur une grande grille régulière, par exemple une feuille A4
avec quadrillage 5 mm. Le joueur dessine des croix en cherchant à
en aligner des groupes de cinq.
La situation initiale consiste à prendre une page et à dessiner un
certain nombre de croix initiales. Puis, à chaque coup, le joueur doit
faire un nouvel alignement de
cinq croix. Un alignement est donc formé de quatre segments. Un
segment ne peut être utilisé qu'une fois.
Vous devez écrire un programme qui joue seul au morpion solitaire et tente de trouver le plus grand nombre possible de coups consécutifs.
Jusqu'à combien de croix suplémentaires ira votre programme ? 150 ? ****
* *
* *
**** ****
* *
* *
**** ****
* *
* *
****
Un premier coup pourrait être :
1----
* *
* *
**** ****
* *
* *
**** ****
* *
* *
****
À quoi peut succéder :
1---+
* |
* |
**** |***
* 2 *
* *
**** ****
* *
* *
****
puis :
1----+
* |
* |
**** 3+---
* 2 *
* *
**** ****
* *
* *
****
And so on...
Il arrive que les carrefours soient saturés. Dans ce cas il faut
réussir à débloquer la situation. Le principe du jeu est simple :
des véhicules sont bloqués à un carrefour, ils ne peuvent que avancer
ou reculer d'une case (plusieurs fois si nécessaire). L'un de ces
véhicules doit traverser.
Exemple de situation initiale
--------------------------- | EE DDDD | | EE DDDD | | EE BBBBBBBB| | EE BBBBBBBB| |VVVV CC S |VVVV CC S | FF CC| | FF CC| | FF AAAAAAAA| | FF AAAAAAAA| ---------------------------Notons que les véhicules V, D, B et A avancent horizontalement, les autres verticalement.
--------------------------- | EE DDDD | | EE DDDD | | EE BBBBBBBB| | EE BBBBBBBB| |VVVV CC S |VVVV CC S | IIIIIIIIIII CC| |GG HH IIIIIIIIIII CC| |GG HH FF AAAAAAAA| |GG HH FF AAAAAAAA| ---------------------------Il faut que le véhicule V sorte par la sortie S. Que devons-nous faire ?
Votre programme doit pouvoir lire une position initiale et trouver la suite de mouvements à faire pour résoudre le problème. La position initiale doit pouvoir être donnée dans un fichier.
Soit un échiquier de taille nxn, un dromadaire occupant la case (i,j)
peut se déplacer vers la case (i+di, j+dj) où di et dj appartiennent à
{ -3, -1, 1, 3} et di*dj à {-3, +3}.
On commencera bien sûr par n petit, par exemple 3x3.
Le problème est de placer le plus possible de dromadaires en vérifiant
qu'ils ne peuvent pas se prendre les uns les autres.
Combien de dromadaires peut-on mettre sur un échiquier 2x2 ?
Combien de dromadaires peut-on mettre sur un échiquier 3x3 ?
Combien de dromadaires peut-on mettre sur un échiquier 4x4 ?
Combien de dromadaires peut-on mettre sur un échiquier nxn ?
Il faudra bien sûr que votre programme propose un positionnement de
tous ces dromadaires.
? (crible 10) = (2 3 5 7)Le crible est une méthode aisée pour chercher les nombres premiers :
Il faudra aussi faire attention de tester Eratosthène avant, éventuellement, de tester d'autres méthodes.
Le taquin est un jeu dans lequel on déplace des pièces carrées jusqu'à les mettre toutes à leur place réservée. Une adaptation de ce jeu consiste à disposer de pièces de taille variée (par exemple des pièces de taille 1 x 1 et des pièces de taille 1 x 2) et des les amener à leur position.
Exemple :
ici, un numéro signifie une pièce et un numéro
répété est celui d'une pièce plus grande. Un vide signifie la case vide.
Situation initiale
--------------- | 7 1 3 3 | | 7 4 4 5 | | 8 10 9 | |11 2 12 6 | ---------------
--------------- | 1 2 3 3 | | 4 4 5 6 | | 7 8 9 10 | | 7 11 12 | ---------------Écrire un programme qui prend une situation initiale, une situation à obtenir et propose les mouvements pour y aboutir.
Principe du jeu : sur un plateau carré, deux joueurs
s'affrontent. Chacun joue à tour de rôle. Jouer consiste à construire
une tour sur une case. Un joueur peut jouer jusqu'à trois fois sur la
même case de façon à obtenir une tour de hauteur 3.
Toute tour posée
donne une domination sur les cases adjacentes (y compris sur la case
où elle est posée). Si la tour est de hauteur n elle donne un
contrôle de valeur n.
Quand une tour d'un joueur est sur une case dominée majoritairement
par l'autre joueur, elle est dominée et s'écroule.
Exemple :
-------------------------
| | | | | | |
6 | | | | | | |
| | | | | | |
-------------------------
| | | | | | |
5 | | | | | | |
| | | | | | |
-------------------------
| | | | | | |
4 | | a1| b1| | | |
| | | | | | |
-------------------------
| | | | | | |
3 | | | | | | |
| | | | | | |
-------------------------
| | | | | | |
2 | | | | | | |
| | | | | | |
-------------------------
| | | | | | |
1 | | | | | | |
| | | | | | |
-------------------------
1 2 3 4 5 6
Sur la case (2,4), le joueur a a posé une tour. Elle donne une case de
contrôle sur les cases voisines (2,3),(2,4),(2,5),(1,4),(3,4). Quand b
pose sa tour sur la case (3,4), il obtient un contrôle sur les cases
(3,3),(3,4),(3,5),(2,4),(4,4). Donc les contrôles sont annulés
(+1 -1 = 0) sur les cases (2,4) et (3,4). Ces deux
cases-là sont "neutres" en ce moment. Les tours qui s'y trouvent sont
en danger. Si a veut gagner, il lui suffit de jouer, par exemple,
(4,4). Dans ce cas, il prend un contrôle de plus sur la case (3,4) qui
est majoritairement dominée par a et donc la tour de b s'écroule.Soit une grille de nombres croisés, exemple :
a b c --------- 1 | | 2 | * | 3 | | ---------1) suite de chiffres consécutifs
Écrire un programme qui résout ce genre de problèmes.
Dans un premier
temps on limitera le nombre de définitions (carré, palindrome) et la
taille de la grille.
Dans un second temps on ajoutera des styles de définitions ("le carré
de la somme des chiffres est un palindrome") et la taille de la grille
sera étendue (5x5 puis 6x6).
Soit une grille d'anagrammes (c'est-à-dire de mots croisés dont on
connaît non pas une définition mais la liste des lettres). On suppose
l'existence d'un dictionnaire (qu'il faudra, en partie,
construire ou récupérer). Écrire un programme qui trouve la solution de ces
anagrammes.
Dans un premier temps le dictionnaire sera limité et la taille de
la grille aussi. Dans un second temps ces éléments pourront grandir
jusqu'à être en mesure de résoudre les anagrammes des journaux
spécialisés.
Il serait bon d'utiliser un fichier pour gérer le dictionnaire.
Le jeu du 7-0 est assez simple. Chaque joueur (au moins deux joueurs, dont au moins un joueur joué par votre programme) dispose d'une cagnotte, à 0 au départ du jeu. Le but est d'être le joueur dont la cagnotte est la plus grande à la fin d'un tour où une au moins des cagnottes des joueurs a dépassé 200.
Un tour de jeu se passe ainsi, chaque joueur joue successivement.
À son tour le joueur lance deux dés à six faces et fait leur
somme. Il obtient un total partiel et peut choisir de relancer
pour augmenter son total partiel. À un moment où à un autre, il décide
de ne pas relancer et de mettre le total partiel dans la cagnotte,
c'est alors au joueur suivant.
À chaque lancé de dés, si le total est 7, le total partiel est
remis à 0 et le joueur a fini son tour.
Exemple de début de partie
X joue et fait 4, il rejoue et fait 8 (total partiel 12), il rejoue et
fait 11 (total partiel 23), satisfait, il s'arrête et sa cagnotte
passe à 23.
Y joue et fait 12, il rejoue et fait 11, il rejoue et fait 2, il
rejoue et fait 6, il rejoue et fait 10, à ce moment son total partiel
est 41, il décide de monter à deux fois le résultat de son adversaire
et rejoue. Il fait 7, sa cagnotte reste à 0 et c'est au joueur
suivant.
Si un individu est placé en face d'une série d'immeubles, il peut voir
le plus proche, P. Mais il peut voir aussi un immeuble P' si P' est
plus loin que P mais plus haut que P. De même pour P'' et les
suivants.
On veut fabriquer un paté d'immeubles. Les immeubles ont une hauteur,
donnée par un X ci-dessous. Les valeurs indiquées sur les bords sont
les nombres d'immeubles visibles de ce point. Par exemple si vous
êtes en bas et le plus à droite possible, que vous regardez vers le
haut, vous devez voir 3 immeubles, ce qui veut dire que un seul des
immeubles sera caché par les autres.
Dernières règles, dans chaque ligne et chaque colonne il y a un seul
immeuble d'une hauteur donnée et un problème a une solution
unique.
La taille du quartier est variable, l'exemple ci-dessous est de
taille 4 mais une taille 5, ou 6, ou plus doit être traitée.
1 2 3 2 1 X X X X 4 4 X X X X 1 2 X X X X 2 2 X X X X 2 2 1 2 3Vous devez maintenant trouver la hauteur de chacun des immeubles. Il est assez facile de trouver la solution :
1 2 3 2 1 4 3 2 1 4 4 1 2 3 4 1 2 2 1 4 3 2 2 3 4 1 2 2 2 1 2 3Il faut écrire un programme qui puisse
En français, il est parfois complexe de faire l'analyse
d'une phrase, même quand il n'y a pas d'ambiguïté. Il est
possible de procéder par étapes : associer les mots à
des catégories (noms, verbes, articles, adjectifs,...),
puis, en fonction de la forme de la phrase, déterminer quel
est le groupe nominal, quels sont les qualificatifs,
etc.
Le programme pourra ensuite analyser les phrases avec des
propositions subordonnées...
L'enseignant pourra donner des phrases et voir ce que votre
programme propose comme analyse.
Soit une série de n lettres, trouver tous les mots qui
existent et sont composés de ces n lettres.
Écrivez également une fonction qui calcule le nombre de points
rapportés par un mot au scrabble.
Profitez-en pour écrire une fonction qui permet de vous aider à jouer
au scrabble, c'est-à-dire qui, dans une certaine situation, propose
les mots qui rapportent le plus de points.
On peut à partir de là, mettre en place un solveur de problèmes de scrabble : on donne un problème et le programme trouve tous les scrabbles qu'on peut faire dans cette situation. (On trouvera de tels problèmes sur de vieux numéros de Jeux et Stratégie trouvables sur le web)
La dernière étape, facultative, consistera à écrire un programme qui joue contre vous en faisant à chaque tour de jeu, le plus grand total possible.NB. On se limitera à la version française du jeu.
Mis à jour le 2/3/2021