Je suis en prépa et je dois faire un projet le long de cette année que je devrais présenter aux concours. Je laisse tomber mon ancien TIPE qui était trop orienté maths : j'ai le choix entre faire un TIPE maths-info ou un TIPE info, et j'ai choisi le second donc je cherche plutôt un TIPE d'informatique pure, avec certes un peu de maths (il y en a toujours) mais dont la complexité soit sur l'aspect informatique. Je ne savais pas vraiment où poster ça mais étant donné que je compte le programmer en C++ (très probablement), je suis venu ici.
Je viens ici pour demander des conseils à des personnes ayant plus de recul que moi sur certains sujets : je n'ai plus le temps de me renseigner en profondeur sur un sujet pour au final me rendre compte qu'il n'y a pas assez pour approfondir ou que le sujet n'est pas vraiment adapté à un TIPE. Parmi les quelques recherches d'idées que j'ai faites, deux émergent :
D'une part, le calcul formel m'intéresse pas mal : l'utilisation d'arbres et le côté choix d'une structure de données adapter pour optimiser le tout, ainsi que des algorithmes qu'il est possible de développer par soi-même avec un peu de réflexion. Ceci dit, je ne me suis pas encore renseigné sur le sujet, donc est-ce faisable sans qu'il y ai une trop grosse part de mathématiques ? Même si à la base il s'agit de 'mathématiques informatisées', mais je parle plutôt des outils nécessaires aux algorithmes. D'autre part, et surtout, ne ferait-ce pas un peu catalogue, une fois le système de représentation des expressions avec des arbres mis en place, de traiter d'une part la factorisation, puis la dérivation, puis les développements limités (exemples arbitraires, je ne me suis encore décidé de rien) etc ?
D'autre part, une idée qui m'est venue en faisant des recherches sur les bases de données, serait de modéliser un système de trams/métros, càd en entrant plusieurs lignes de trams (dont certaines se croisent) avec leurs arrêts, sous la forme de graphes probablement, puis de faire circuler les trams de la manière la plus optimisée possible ? J'ai l'impression que ça sonne un peu creux, même si on pourrait approfondir en faisant une optimisation en temps réel selon des imprévus, en intégrant un système routier ... Bien que ça réponde à un problème réel, j'ai l'impression que ça manque de réfexion, je ne sais pas bien comment expliquer. Une solution serait de définir une liste d'arrêts et de créer plusieurs lignes de trams de manière optimisée, mais ça reviendrait +/- à un problème de plus court chemin (pas entièrement, mais ça reste un sujet trop abordé en TIPE).
Ces deux idées ne sont absolument pas fixées et je suis ouvert à toutes suggestions, j'avais aussi pensé à un apprentissage de la conduite en vue de haut à l'aide d'un algorithme génétique mais pareil ça sonne vide, ou sinon je suis intéressé par tout ce qui touche au programme de MP info (graphes, arbres, structures de données (recherche optimisée), automates, langages, logique...) mais je ne trouve aucune application concrète.
N'ayant pas trop d'idée sur le niveau demandé et la charge de travail disponible (le temps que tu peux consacrer à ce travail), il est assez difficile de te proposer quelque chose de pertinent. Le calcul formel est à mon avis un peu trop bateau surtout en prépa , mais il y a peut être moyen de faire un truc sympa sur un modèle relativement proche: passer d'une expression formulée en langage naturel à une requête sur une base de données, par exemple je dis "je veux les noms des chats noirs", le programme analyse mon expression et forme la requête SELECT name FROM cats WHERE color=black Un autre exemple "Ma chatte est blanche et s'appelle Mirza" sera transformé en INSERT INTO cats(name,gender,color) VALUES('Mirza',female,white).
Une autre idée, beaucoup plus matheuse, serait la démonstration automatique de prédicats en logique du premier ordre, c'est quelque chose qui ne te dépaysera pas beaucoup, la plupart des théorèmes que l'on trouve en mathématique (pour ne pas dire tous) sont exprimés sous la forme de prédicats de la logique du premier ordre (dés que tu vois quelque soit ou il existe, c'est un prédicat du 1er ordre ) . Il y a un problème sous-jacent assez intéressant, c'est le théorème d'incomplétude de Gödel. L'ensemble des prédicats du premier ordre contient des prédicats indémontrables (c'est à dire des prédicats qu'on ne peut ni démontrer, ni réfuter). Là dessus il y a de quoi s'amuser, tu as un wagon d'algorithmique à torcher avec pas mal d'embûches au programme, car un certain nombre de problèmes qui vont se présenter à toi seront naïvement NP-Complets (voir totalement NP-Complets), pas mal de théorie à ingurgiter aussi, en informatique théorique (calculabilité complexité, algorithmique, théorie des graphes...) et aussi en math (théorie des ensembles, logique du 1er ordre, systèmes formels, plus probablement aussi un peu de calcul matriciel, la liste n'est pas exhaustive), par contre je dois te prévenir que ça ne sera pas de la tarte.
Concernant le niveau demandé, disons entre bac+2 et bac+3 en maths et en infos (pas sur une base générale mais le but est d'approfondir sur certaines notions pouvant être hors-programme). Quant au temps, il me reste quelques mois avant les concours, le but serait que je puisse en grande partie le faire en m'y consacrant à fond pendant une semaine de vacances, après rien n'est sûr mais ça dépend du sujet choisi.
Concernant l'analyse d'une expression, je ne vois pas bien l'intérêt algorithmique : ce serait juste un amas de conditions pour transformer chaque mot-clé SQL en un mot français, modulo les sujets / déterminants...
La seconde idée à l'air plus intéressante, je vais me renseigner en espérant qu'il y ai tout de même plus d'infos que de maths. Ceci dit le sujet m'a encore l'air un peu vague, de quelle manière est-il possible d'appliquer ce théorème d'incomplétude de Gödel en informatique ?
Tu ne vas pas appliquer le théorème de Gödel dans ton programme, tu vas plutôt être victime de ses conséquences, le théorème dit en très gros qu'il existe en logiques des prédicats des prédicats qu'on ne peut ni démontrer ni réfuter, ce qui fait que si ton programme essaye de démontrer un tel prédicat il va effectuer des substitutions à l'infini ce qui ne sera pas sans poser quelques problèmes techniques car les ordinateurs apprécient assez peu les programmes nécessitant des ressources infinies. Après je pense que si tu n'as qu'une semaine à y consacrer, ça risque d'être très juste car il y a un paquet de théorie à ingurgiter, pas forcément beaucoup de littérature disponibles (à part peut être dans une Bibliothèque Universitaire bien fournie en ouvrages sur la logique et l'informatique théorique) et le programme à réaliser promet d'être assez complexe au niveau des algorithmes à mettre en place, et de la représentation des données.
Quant au premier sujet que je t'ai proposé, il est plus complexe qu'il n'y parait, tu auras besoin d'une double analyse, analyse syntaxique d'abord pour repérer des mots clés qui vont correspondre à des instructions SQL, à des noms de table, de vue, de colonne et éventuellement à des valeurs de colonnes, puis sémantique ensuite, il faudra établir les liens sémantiques entre les différents mots clé qui auront été trouvés, ça fait aussi pas mal de boulot et si tu n'as qu'une semaine, je pense que ça risque aussi d'être trop juste.
J'ai un peu exagéré, j'ai plus qu'une semaine c'est juste que j'ai pas mal de travail à côté, mais je consacrerai au TIPE le temps qu'il faudra. Le but n'est pas nécessairement qu'il soit abouti ou approfondi au maximum, il faut surtout proposer une réflexion quant aux algorithmes / structures de données choisies et apporter une réelle contribution personnelle.
Concernant Gödel, j'ai en effet du mal à trouver des informations sur des algorithmes qui permettraient de démontrer des théorèmes. Je n'ai aucune connaissance sur le sujet donc je ne sais pas si c'est à ma portée. Mais comme dit, j'ai plus qu'une semaine, il faut surtout que ce ne soit pas trop vaste afin que je n'aye pas à approfondir toutes les branches du sujet (le jury peut poser des questions sur tout ce que j'aurais utilisé dans mon TIPE).
Et pour la seconde idée, je ne vois pas vraiment à quel moment je pourrais utiliser des arbres, graphes ou autres structures de données, ni où réside vraiment le problème. Je ne dis pas que c'est trivial mais pour moi il s'agit d'algorithmes plutôt intuitif avec des conditions traitant les cas possibles avec les différents mot clés. Je ne vois pas d'algorithmes "complexe" (je veux dire dont il faille prouver le fonctionnement / la terminaison ou qui pose un problème quant au calcul ou à l'optimisation de sa complexité).
Enfin concernant le calcul formel, tu trouves vraiment qu'il s'agit d'un sujet faible par rapport à ce dernier ?
Tu peux éventuellement écrire un solveur SMT (ou déjà SAT dans un premier temps), tu te branches sur un parseur SMT-LIB et tu montes le solveur derrière ça. C'est assez rapide d'avoir un truc basique qui sera lent à crever et après, il y a plein de boulot pour optimiser le bousin. Sinon, tu peux écrire un compilateur pour un langage fortement typé (Caml par exemple), il y a largement de quoi s'amuser sur l'inférence de types.
Le premier, c'est plutôt des petits algos biens optimisés, avec des calculs de complexité etc. Le deuxième, pas mal de code mais ça me semble plus éloigné du programme (alors que dans le premier on a des arbres, des expressions logiques ...). C'est bien ça ?
En soit, le deuxième m'intéresse plus mais le premier me semble plus intégré dans l'esprit choix des structures de données, petits algos, correction, complexité etc, bref de l'esprit prépa. Ceci dit, je ne m'y connais pas en compilation : c'est peut-être pareil avec le deuxième ?
Enfin, il s'agirait plus d'interprétation du CamL que de la compilation, étant donné que je ne compte pas faire de l'assembleur, ce serait plutôt de la traduction de CamL vers C++, ainsi que de la correction du code. J'ai peur encore une fois que ça fasse un peu "liste", de traiter cas par cas toutes les expressions possibles en CamL puis de les traduire en C++. Est-ce que ça reste pertinent comme sujet ?
Merci !
Sujet de TIPE
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Posez vos questions ou discutez informatique, sur le Discord NaN | Tuto : Preuve de programmes C