Idée pour un projet fin d'année.

Bonjour,

Septembre prochain je serai en 1ére année master math informatique et je suis à la recherche d’un projet à réaliser ou d’un problème à résoudre pendant 3mois 4 au max, pour mes gouts je suis passionnée par la théorie des graphes, recherche opérationnelle, programmation linéaire et optimisation Pour cela j’ai fait des recherche sur internet j’ai lu quelque article scientifique à propos de la théorie des graphes, puis j’ai contacté un professeur il m’a proposé des axes pour faire une recherche et déduire un bon sujet :

• problème d'ordonnancement, coloration des graphes nombres chromatique.

• Méthodes de la recherche locale.

• programme qui permet de résoudre l'équation d'un problème financier suivante :

1 000,00 = { 80 * [ 1 - ( (1+t) ˉ³ ] / t } + { 1 080,00 * ( 1+t) ˉ⁴ } ( depuis internet).

• le jeu des gendarmes et du voleur sur les graphes.

• une machine de Turing.

• le problème Eternity II.

Que pensez-vous à propos de ces sujets ?

Vous auriez des suggestions de problèmes qui feraient un sujet satisfaisant et original?

Merci.

Salut !

J'étais exactement dans la même situation qu toi l'année dernière quand je cherchais un sujet de TIPE. Ces problèmes me passionnaient (et continuent de me passionner).

le problème Eternity II.

Un problème de combinatoire très intéressant ! Je l'avais finalement choisi comme sujet de TIPE.
Je l'avais résolu avec les algorithmes génétiques (ici un "individu", solution partielle en cours de construction tirée de ma population encours d'évolution) :

J'avais essayé différentes politiques, etc… (courbes ci-dessus)

C'est un problème NP-complet donc peu probable que tu les résolves avec un "bon" algo (à moins d'avoir un coup de chance) mais bien sûr si tu y parviens tu as 1 million de dollars à la clef

Méthodes de la recherche locale.

Elles sont une stratégie de résolution possible de Eternity 2.

Il existe bien d'autres algos, il y a vraiment de quoi s'amuser sur ce problème.

La coloration de graphe, c'est utilisé pour l'affectation des registres lors de la compilation. En sachant que tu as aussi possibilité de réordonner certaines instructions, il y a probablement moyen de faire quelque chose de sympa de ce côté là aussi.

Moi je vote en temps que futur économiste pour l'équation de finance ! C'est quoi exactement le problème associé (si tu sais) ?

Eternity II : Si le projet te plait, vas-y. Mais n'espère pas toucher le moindre centime si tu trouves une solution : le challenge a été lancé en 2007, et il fallait trouver une solution avant fin 2011. Si je suis bien informé.

Mais n'espère pas toucher le moindre centime si tu trouves une solution : le challenge a été lancé en 2007, et il fallait trouver une solution avant fin 2011. Si je suis bien informé.

Je parlais de $P = NP$

Ca va sans dire, mais ça va mieux en le disant.

Bonsoir à tous,

je tiens à vous remercier pour les informations.

Algue-Rythme : ça semble que vous avez proposé un très bon sujet et je vois que vous l'avez entamer .

qu'est vous pouvez dire a propos de la complexité de ce sujet ?

Berdes : pour la coloration des graphes c'est un bon sujet cependant, il faut plus de temps pour entamer le problème du nombre chromatique ,afin de faire du progrès dans le sujet " l'affectation des registres lors de la compilation" en globalité.

Demandred : aucune idées pour le moment j'ai demander du détail et j'attend une réponse.

Merci a vous tous.

Algue-Rythme : ça semble que vous avez proposé un très bon sujet et je vois que vous l'avez entamer . qu'est vous pouvez dire a propos de la complexité de ce sujet ?

Tu peux me tutoyer !

C'est une question un peu vague. L'énoncé du problème est extrêmement simple, il s'agit juste de résoudre un puzzle de $16\times 16 = 256$ pièces.

En revanche le résoudre est actuellement problème très difficile (pour preuve : personne n'y est parvenu). Il existe $4^{256}\times256!=10^{681}$ configurations différentes possibles. Même si les ordinateurs actuels étaient un milliard de milliard de fois plus rapides tu n'aurais presque aucune chance d'y parvenir, même en plusieurs milliards d'années de calcul.

La raison est la suivante : c'est un problème $NP$-complet ce qui signifie qu'on ne connait actuellement pas de meilleur algorithme déterministe que celui qui énumère toutes les possibilités.

Néanmoins ça ne veut pas dire que le problème est insoluble. Avec des méta-heuristiques adaptées au problème tu peux espérer le résoudre. Et il y en a des dizaines ! Fais toi plaisir ! Tu peux les combiner entre-elles, faire varier les paramètres, etc…

Donc le grand intérêt de ce sujet est qu'il a la complexité que tu veux bien lui donner. Si tu veux faire des trucs basiques qui résout des mini-puzzle, sans trop d'efforts ni de sophistication, tu peux !

Ci-dessous un puzzle $4\times 4$ parfaitement résolu (je n'ai résolu un 5x5 qu'une seule fois !) :

Mais si tu y passes le temps nécessaire tu peux développer de nouvelles approches, et utiliser des méthodes très sophistiquées (la pointe de la recherche dans le domaine !) pour espérer faire mieux. Et là tu auras un sujet très riche et très complet, mais ça peut nécessiter énormément de travail.

Salut, voilà une suggestion d'approche si tu veux bosser sur l'équation du problème financier : l'analyse par intervalles représente chaque réel (= pas forcément représentable exactement sur une machine) par un intervalle à bornes flottantes (= représentables exactement sur une machine). En étendant toutes les opérations classiques (+, -, x, /, cos, 1/x, …) aux intervalles, le résultat de mon calcul est un intervalle dont on sait qu'il contient le résultat exact.

Voilà pour le contexte. Le calcul par intervalles permet de faire des trucs trop swags, du genre un algorithme de Newton (qui historiquement permet de trouver une solution d'un équation non-linéaire, pour peu qu'on soit pas trop loin de la racine). Sauf que le Newton sur intervalles amuse pas la galerie : moyennant quelques subtilités, tu peux encadrer toutes les solutions d'une équation non-linéaire avec une précision arbitraire, quelle que soit la valeur de départ dans un intervalle.

Elle est pas belle la vie ?

L'intersection tangente-abscisse de l'algo de Newton original est remplacé par une intersection cône-abscisse… c'est-à-dire un intervalle. Et les racines sont automatiquement séparées

PS : ça permet de faire plein d'autres trucs, évidemment la résolution de systèmes non-linéaires, de l'optimisation globale, de l'intégration numérique, etc. J'ai bossé là-dessus pendant ma thèse, donc si tu as des questions hésite pas.

PS2 : en 1D, tu peux faire des visualisations sympas au cours des itérations, cf Wikipedia.

Bonjour à tous,

Eternity II je vais travailler dessus,j’arrête pas de réfléchir sur des approches pour avoir une solution.

Algue-Rythme : pour avoir un bon bagage avant de commencer la résolution, qu'est ce que vous recommandez ??

Merci

Sauf que le Newton sur intervalles amuse pas la galerie : moyennant quelques subtilités, tu peux encadrer toutes les solutions d'une équation non-linéaire avec une précision arbitraire, quelle que soit la valeur de départ dans un intervalle.

C'est vrai dans $\mathbf{C}$ si ton équation est donnée par un polynôme. Dans les cas plus généraux c'est plus délicat. Dans $\mathbf{R}$ il faut notamment s'assurer de l'existence des racines dans $\mathbf{R}$.

J'ai bossé là-dessus pendant ma thèse, donc si tu as des questions hésite pas.

Ta thèse m'intéresse, mp ?

L'algo de Newton sur intervalles (itératif) fournit automatiquement l'existence et l'unicité des racines simples dans un intervalle donné S'il n'existe pas de racine, l'intervalle est simplement éliminé de la liste des possibilités.

Les algorithmes sur intervalles travaillent sur R^n. Il doit exister des extensions à C, mais je n'ai pas eu l'occasion d'en prendre connaissance.

Holosmos : je t'envoie le lien vers ma thèse en MP

L'algorithme de Newton se fait classiquent dans $\mathbf{C}$. Mais tu dois parler d'une variante.

Il est vrai que si toutes les racines sont accessible, le temps de convergence est lui très variable