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 3 avril
2024, avant 9 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 : on peut ne pas réussir et 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 les nouvelles valeurs de la 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, un soustracteur...) 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. On prendra comme valeurs celles données par la fonction de remplisage d'un tableau d'altitude ou un relevé topographique de montagne.
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. Il faut donc disposer de six successeurs pour chaque noeud.
Ou encore, à 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.
La même structure sera utilisée pour toute matrice, dans la suite.
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...).
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
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.
Vous connaissez aux échecs le mouvement et le problème du cheval ? Il s'agit de faire parcourir toutes les cases à un cavalier, en suivant les mouvements normaux du cavalier aux échecs, sans jamais repasser par la même case.
Ici, avec un cheval ivre, tous les trois coups, il rue et saute, dans un mouvement plus long que d'habitude : au lieu d'un mouvement (2,1) il fait alors un mouvement (3,2). Par exemple, à partir de la case A1, le cheval fou peut passer (premier coup) en B3 (ou en C2) puis (deuxième coup) en C5 (ou C1 ou...) puis, de là, en (troisième coup, le saut) F7 (ou en E2...). And so on.
Il s'agit de
? (crible 10) = (2 3 5 7)Le crible est une méthode aisée pour chercher les nombres premiers :
Attention, il faudra gérer la situation des listes vraiment très longues qui ne rentrent pas en mémoire, par exemple si n vaut 1 000 000 000 000 000.
Il faut donc travailler avec des listes chaînées.
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 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.
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é.
Pour cela, on peut 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.
Votre programme devra lire une phrase et tenter d‘en faire l'analyse syntaxique.
Vous commencerez par des phrases simples.
Le programme pourra ensuite analyser les phrases avec des propositions subordonnées...
L'enseignant donnera des phrases pour voir ce que votre programme propose comme analyse.
Écrire en C un programme qui trouve toutes les solutions d'une grille de Boggle.
Les mots authorisés peuvent être stockés dans un fichier texte où chaque ligne contiendra un mot.
Le programme doit prendre en compte le fait qu'au Boggle toutes les lettres sont non accentuées. (à un E peut correspondre l'un des caractères suivants :ÉÈËÊ)
Dans ce jeu, des arbres et des indications sont donnés sur une grille carrée. On pourra voir des exemples sur jeux tentes
Il s'agit de poser des tentes qui doivent respecter les règles suivantes :
Écrire en C un programme qui prend trouve la solution à un tel problème. Pour cela il faudra :
Dans le jeu norinori , des régions sont délimitées sur une grille carrée. Il faut griser des dominos (groupes de deux cases) de façon à ce que :
Écrire en C un programme qui prend trouve la solution à un tel problème. Pour cela il faudra :
Mis à jour le 4/3/2024