Jean-Jacques BOURDIN
Les projets encore "libres" :
Projets 20198
17
18
19
20
21
29
Les projets sont à faire par groupe de deux (2) personnes. La part de
chacun devra être auto-évaluée dans le rapport.
Le rapport et le programme seront envoyés en format
électronique (mail) avant le lundi 16/12/19 9h.
Le rapport et le programme seront rendus en version papier
le lundi 16/12/19 à 15h.
Les étudiants qui choisiront de rendre leur projet en avance, le mardi 10/12/19 avant 18h (version électronique et version papier) auront un bonus de 2 points.
Pour les étudiants qui veulent rendre leur projet en avance, c'est-à-dire le 10/12/19 avant 18h, il est possible que l'accès à l'Université soit très limité, voire impossible (pas de métro...).
Dans ce cas, la version électronique suffira pour l'instant, la version papier devant être rendue avant le lundi 16/12 à 15h.
Il n'est pas sûr que les transports fonctionnent correctement le lundi 16/12, si vous ne voyez pas comment venir ni faire porter votre document par un collègue, vous pouvez l'envoyer par la poste avant l'heure dite. L'adresse serait alors JJ Bourdin Dept Informatique, 2 rue de la Liberté 93526 Saint-Denis.
Le mardi 17/12/19 devrait être une journée de mobilisation, c'est-à-dire que, vraisemblablement, notre université sera fermée toute la journée. Dans ce cas nous devrons renoncer aux présentations des projets.
Le rapport contiendra des explications sur les procédures mises en oeuvre, le mode d'emploi, le listing du programme et des traces d'utilisation.La présentation publique des travaux aura lieu le 17/12/19, de 9 à 11h puis en salle de TP de 14 à 18h.
Si certains ont des problèmes avec leur sujet ou leur binôme, qu'ils n'hésitent pas à poser des questions avant le 9/12/2019 !
Il vous est conseillé d'envoyer au moins une version intermédaire de votre travail de façon à éviter, en particulier, les hors sujet.
Il faut sur, une image, trouver automatiquement toutes les "taches de
couleur". L'image est
donnée comme un grand tableau avec un octet par couleur par "pixel"
(trois couleurs, R, G et B). C'est donc une vaste matrice de (XMAX x
YMAX x 3) octets.
Trouver les taches consiste à trouver et numéroter les zones connexes
ayant la même couleur.
Une bonne méthode consisterait à commencer par trouver tous les pixels
connexes ayant une certaine couleur, ils forment une tache.
Puis à réitérer ce processus pour tous les pixels.
On a alors toutes les taches, si elles ont été listées, il est
maintenant facile de leur appliquer un traitement.
Un traitement pourrait être de délimiter en noir les taches de
couleur.
Enfin, une tache peut être une zone dont les pixels ont à peu
près la même couleur. On définira cette approximation et on
fera la délimitation de ces zones comme précédemment.
On considérera qu'une fenêtre est, dans une image, un carré de
taille n x n dans lequel on fait des calculs (et, peut-être, des
modifications). La fenêtre de travail passe ensuite au carré
suivant. Le fenêtrage est donc une partition de l'image (tout pixel
appartient à une et une seule fenêtre).
Il va falloir d'abord commencer par mettre en place un codage HSV de
l'image, pixel après pixel.
Puis traiter l'image par petites fenêtres.
Les contrastes sont les différences entre la couleur d'un pixel et la
couleur de ses voisins.
Répérer les pixels ayant le plus fort contraste consiste donc à
parcourir l'image en mémorisant ces pixels dont la couleur est très
éloignée de celles de ses voisins.
Mettre en place une fonction qui retourne l'ensemble des pixels de
fort contraste.
Ces pixels peuvent être connexes et dans ce cas, composent une
forme.
Mettre en place une fonction qui prend l'ensemble défini ci-dessus et
trouve les alignements de pixels dans cette liste.
Des lignes adjacentes peuvent composer des formes.
Mettre en place une fonction qui, à partir des lignes trouvées,
compose et reconnaît des objets par leur forme.
En dande dessinée classique, comme dans les vitraux, les taches de
couleur sont uniformes et les formes sont séparées par un trait noir
bien visible. Il s'agit dans ce projet de répérer ces formes, ces
"régions" de couleur. L'image sera représentée comme un ensemble de
contours (c'est-à-dire de listes de points) formant une région
associée à une couleur.
Ce format sera utilisé pour sauvegarder l'image.
Ce format sera alors repris pour afficher une image ainsi
sauvegardée.
On s'intéressera notamment au ratio de compression,
(taille du fichier
obtenu) / (taille du fichier
bmp initial).
Un pixel a huit voisins (1 : est, 2 : nord-est, 3 : nord, 4 :
nord-ouest, 5 : ouest,
6 : sud-ouest, 7 : sud, 8 : sud-est). Son voisinage est l'ensemble de ces huit
voisins plus lui-même.
Modifiez l'image pour que chaque pixel
prenne la valeur de la moyenne, puis de la moyenne pondérée (un grand
poids pour lui-même) de son voisinage.
Modifiez l'image pour accentuer le contraste : pour chaque pixel
on cherche, dans son voisinage, le pixel dont les couleurs sont les
plus éloignées des siennes. On augmente alors d'un tiers ce
contraste.
Attention, dans tout le programme, à éviter les effets de bord (cas du pixel p1
augmenté à cause de son contraste avec p2 et de p2 diminué à cause de
son contraste avec le nouveau p1).
On pourra enfin chercher et améliorer les contrastes de "teinte" en
mode HSV.
On va parcourir une image "fenêtre" par "fenêtre" (par exemple par groupes
disjoints de 3x3 ou 4x4 pixels). Dans ce voisinage, on peut classer les
pixels par "contraste" :
le "contraste" d'un pixel est le plus grand des écarts de
couleurs par rapport à ses voisins.
Il est alors possible de déplacer les couleurs des pixels de la
fenêtre en plaçant, par exemple les pixels les plus contrastés au
centre et les autres de façon régulière vers la périphérie de la
"fenêtre". Le sens inverse doit être essayé également.
D'autres dispositions sont possibles et il faudra voir ce qui
fonctionne le mieux, ce qui donne les effets les plus intéressants.
Le contraste peut aussi être basé sur la "chaleur" des couleurs,
par exemple, un bleu ou un vert est considéré comme froid, un rouge
comme chaud. Faire tourner les mêmes fonctions avec cette nouvelle
définition de contraste.
Il s'agit ici de fabriquer des grilles de sudoku. Les règles sont simples :
NB : enlever des valeurs à une grille pleine et vérifier que la grille respecte les règles a déjà été tenté avec insuccès.
Mettre en place un jeu de robots programmables.
Sur une aire de jeu avec des obstacles, des butins et des aires de
retour, des robots peuvent se déplacer, se combattre, ramasser du
butin.
Une fois qu'elle est en place, on écrira des programmes comme l'addition de deux entiers, la soustraction, le décalage... et on vérifiera que la machine fait bien le travail.
L'enseignant donnera une ou des programmes écrits pour une machine de Turing et vérifiera que votre programme les interprète correctement et réalise les opérations.
Le morpion consiste à aligner 5 points et en faire un segment. Le
morpion solitaire se joue à partir d'une figure initiale, il faut, à
chaque coup, ajouter un point qui permette de tracer un nouveau
segment. Attention, les segments sont indépendants et deux segments
ont au plus un point commun.
Votre but est de fabriquer un programme qui fait une liste des coups
possibles et teste ces coups de façon à obtenir le plus grand nombre
possibles de coups successifs.
Votre programme doit atteindre le record actuel de
178 coups. S'il n'atteint pas 100 coups, il pourra être
considéré comme vraiment mauvais (note inférieure à 8).
Attention, dans la suite, une fois que la structure quadtree est en place, on ne réutilise pas l'image.
C'est un jeu dans lequel on contrôle des cases et où on contruit des
tours sur un damier.
À chaque tour de jeu, un joueur construit ou élève une tour.
Puis
le programme vérifie les contrôles et détruit, éventuellement en
cascade, les tours incontrôlées.
Une tour de n étages donne n contrôles sur sa case et sur les 4 cases
voisines.
Si une tour est construite sur une case contrôlée par l'adversaire,
elle est détruite. Exemple :
Tour1 Joueur 1 (+) ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | +1 | | | | | ----------------------------------------- | | | +1 | T1 | +1 | | | | ----------------------------------------- | | | | +1 | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- Tour1 Joueur 2 (-) ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | -1 | | | | ----------------------------------------- | | | | 0 | T2 | -1 | | | ----------------------------------------- | | | +1 | T1 | 0 | | | | ----------------------------------------- | | | | +1 | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- Tour2 Joueur 1 (+) ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | -1 | | | | ----------------------------------------- | | | | 0 | T2 | -1 | | | ----------------------------------------- | | | +1 | T1 | T1 | +1 | | | ----------------------------------------- | | | | +1 | +1 | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- Tour2 Joueur 2 (-) ----------------------------------------- | | | | -1 | | | | | ----------------------------------------- | | | -1 | T2 | -2 | | | | ----------------------------------------- | | | | -1 | T2 | -1 | | | ----------------------------------------- | | | +1 | T1 | T1 | +1 | | | ----------------------------------------- | | | | +1 | +1 | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- Tour3 Joueur 1 (+) ----------------------------------------- | | | | -1 | | | | | ----------------------------------------- | | | -1 | T2 | -1 | +1 | | | ----------------------------------------- | | | | 0 | +2 | T1 | | | ----------------------------------------- | | | +1 | T1 | T1 | +2 | | | ----------------------------------------- | | | | +1 | +1 | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- En effet, la tour a été détruite car son contrôle (-1) sur la case ne dominait pas le contrôle (+2) du joueur J1. Tour3 Joueur 2 (-) ----------------------------------------- | | | | -1 | | | | | ----------------------------------------- | | | -1 | T2 | -1 | +1 | | | ----------------------------------------- | | | -1 | T2 | +1 | T1 | +1 | | ----------------------------------------- | | | +1 | T1 | T1 | +2 | | | ----------------------------------------- | | | | +1 | +1 | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- Tour4 Joueur 1 (+) Il ajoute un étage à une de ses tours : ----------------------------------------- | | | | -1 | | | | | ----------------------------------------- | | | -1 | T2 | -1 | +2 | | | ----------------------------------------- | | | -1 | T2 | +2 | TT1| +2 | | ----------------------------------------- | | | +1 | T1 | T1 | +3 | | | ----------------------------------------- | | | | +1 | +1 | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | | | | | ----------------------------------------- | | | | | | | | | -----------------------------------------Il s'agit ici de choisir un bon mode de représentaiton du jeu et des systèmes de contrôles, pas de faire un "truc joli". Puis de s'en servir pour que l'ordinateur gère le jeu.
Soit un programme écrit en Scheme. Il s'agit de lire le
fichier et de l'analyser sous la forme d'un graphe. Chaque fonction
sera un noeud du graphe et les liens seront les appels de fonction. On
pourra ainsi analyser le programme, par exemple savoir si une fonction
n'est jamais appelée ou si une fonction n'est pas dans le sous-graphe
connexe d'une fonction donnée, si une fonction est récursive, récursive
terminale, etc.
Attention, en Scheme, il n'y a pas de fonction "main" et donc la
structure de graphe n'a pas de racine.
Attention à la gestion de programmes sur plusieurs fichiers !
Comment gérer les variables globales dans cette analyse ?
Soit un programme écrit en Prolog. Il s'agit de lire le
fichier et de l'analyser sous la forme d'un graphe. Chaque prédicat
sera un noeud du graphe et les liens seront les appels à d'autres prédicats. On
pourra ainsi analyser le programme, par exemple savoir si une partie
n'est jamais appelée ou si un prédicat n'est pas dans le sous-graphe
connexe d'un prédicat donné, si un prédicat est récursif, récursif
terminal, etc.
Il faudra être en mesure de travailler sur les problèmes de
redondance, les détecter, les corriger si nécessaire.
Comment faire pour que votre programme détecte également les
contradictions dans la base de données qu'est le programme ?
Soit un programme écrit en C++. Il s'agit de lire le(s)
fichier(s) et de l'analyser sous la forme d'un graphe. Chaque méthode
sera un noeud du graphe et les liens seront les appels de fonctions ou méthodes. On
pourra ainsi analyser le programme, par exemple savoir si une fonction
n'est jamais appelée ou si une fonction n'est pas dans le sous-graphe
connexe de la fonction main, savoir si une fonction est récursive,
récursive terminale, etc.
Détaillez la structure de données retenue.
Faites la lecture d'un fichier et son entrée dans la structure.
Faites l'analyse du graphe et du programme.
Comment gérer les
pseudo-fonctions ?
On peut compléter ce programme en travaillant sur le corps de chaque fonction
et analysant les boucles et autres actions spéciales.
Soit un programme écrit en Python. Il s'agit de lire le(s)
fichier(s) et de l'(les) analyser sous la forme d'un graphe. Chaque fonction
sera un noeud du graphe et les liens seront les appels de fonctions ou méthodes. On
pourra ainsi analyser le programme, par exemple savoir si une fonction
n'est jamais appelée. En Python, qu'est-ce qui fait le rôle de la
fonction main ?
Il faudra aussi déterminer si une fonction est récursive,
récursive terminale, etc.
Détaillez la structure de données retenue.
Faites la lecture d'un fichier et son entrée dans la structure.
Faites l'analyse du graphe et du programme.
On peut compléter ce programme en travaillant sur le corps de chaque fonction
et analysant les boucles et autres actions spéciales.
Soit un programme écrit en Java. Il s'agit de lire le(s)
fichier(s) et de l'analyser sous la forme d'un graphe. Chaque méthode
sera un noeud du graphe et les liens seront les appels de fonctions ou méthodes. On
pourra ainsi analyser le programme, par exemple savoir si une fonction
n'est jamais appelée ou si une fonction n'est pas dans le sous-graphe
connexe de la fonction main, savoir si une fonction est récursive,
récursive terminale, etc.
Détaillez la structure de données retenue.
Faites la lecture d'un fichier et son entrée dans la structure.
Faites l'analyse du graphe et du programme.
On peut compléter ce programme en travaillant sur le corps de chaque fonction
et analysant les boucles et autres actions spéciales.
Comment tenir compte du dénivelé ? Vous remarquerez qu'un
dénivelé faible ne pose pas de problème alors qu'un dénivelé très
important (par exemple une pente supérieure à 30%) n'est en général
pas franchissable.
Faites le programme !
Un problème de logique peut être donné sous la forme d'une série de
phrases, comme par exemple :
On considere cinq maisons, toutes de couleurs differentes (rouge,
bleu, jaune, blanc, vert), dans lesquelles logent cinq professionnels
(peintre, sculpteur, diplomate, docteur et violoniste) de nationalite
differente (anglaise, espagnole, japonaise, norvegienne et italienne)
ayant chacun une boisson favorite (the, jus de fruits, cafe, lait et
vin) et des animaux favoris (chien, escargots, renard, cheval et
chat).
On dispose des faits suivants :
Il s'agit de trouver le possesseur du chat et le buveur de vin.
Votre travail est d'écrire un programme qui prend en entrée des
propositions comme celles-ci et calcule la solution.
Votre programme devra donc s'adapter à des problèmes différents
mais dont la formalisation sera possible.
Le problème du voyageur de commerce est représenté par un graphe complet dont les n noeuds représentent les villes (n >= 30). Résoudre le problème, c'est trouver le plus court chemin que doit prendre le voyageur pour visiter toutes les villes et revenir à son point de départ.
Les arcs sont pondérés par les distances dij entre ces villes et par une autre pondération TRij(t) qui représente la trace de phéromone laissée par les fourmis.
On appelle génération une succession de n-1 étapes où chaque fourmi aura visité les n villes. Initialement, on placera deux fourmis par ville. On initialise TRij(0) de manière aléatoire entre 0 et 1 ou bien par le réel n/L avec L longueur de visite des n villes en prenant toujours le plus proche voisin.
Chaque fourmi k possède une liste "tabou" TLk des villes déjà visitées et se meut aléatoirement suivant la probabilité qu'il passe du noeud i à j. Cette probabilité est proportionnelle à TRij / dij^7 (plus il y a de phéromones, et plus la distance est courte, et plus la fourmi a de chance de prendre ce chemin).
Pour chaque ville i et chaque fourmi k présente en i, si TLk(t) n'est pas complète, on choisit la ville j aléatoirement parmi celles de plus forte probabilité, j est empilé dans TLk(t) pour former TLk(t+1), et la fourmi k passe en j.
Les phéromones sont mises à jour selon :
TRij(t+1) = TRij(t)/2 + 100 * (nbre de fourmis passant de i à j)
Après n-1 étapes, (une génération), la meilleure liste Tabou (plus petite distance cumulée) est mémorisée et une autre génération est reconduite.
On pourra ensuite essayer de changer le nombre de fourmis et les valeurs numériques. Testez différentes configurations pour voir lesquelles sont les plus intéressantes.
On peut trouver un certain nombre de problèmes de Go en ligne mais il
est plus difficile de trouver des problèmes d'hexago. Hexago est un
jeu de go, basé sur exactement les mêmes principes, mais sur un
maillage hexagonal (à grille en nid d'abeille). Chaque pierre a donc
six voisins potentiels. Il
s'agit ici de mettre en place un système de résolution de
problèmes. La taille maximale du goban est fixée TMAX et, dans un
premier temps, ne pourra pas dépasser 6 x 6.
Pour résoudre ce problème il convient d'écrire quelques fonctions :
| 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 3 |Vous 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 3 |Il faut écrire un programme qui puisse :
(define (som n)
(if (= n 0) 0
(+ n (som (- n 1)))))
on voudra obtenir, par exemple :
int som (int n) {
if (n == 0)
return 0;
return n + som (n - 1);
}
Pour les fonctions les plus simples, c'est assez facile, pour
puissance ou les récursivités terminales, votre programme doit être
bien conçu.
Le problème se complique lorsque deux fonctions sont liées (exemple des fonctions chapeau liées aux récursivités terminales).
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).
Mis à jour le 26/11/2019 (mise à jour des projets libres)