Cette thèse est en majeure partie dédiée au calcul rapide de remontée p-adique par des algorithmes détendus. Dans une première partie, nous présentons le cadre général des algorithmes détendus et de leur application au calcul de p-adiques récursifs. Pour appliquer ce cadre à la remontée p-adique de divers systèmes d'équations, il reste à transformer ces équations implicites en équations récursives. Ainsi, la seconde partie traite des systèmes d'équations linéaires, éventuellement différentiels. La remontée de résolutions de systèmes polynomiaux se trouve en troisième partie. Dans tous les cas, les nouveaux algorithmes détendus sont comparés, en théorie comme en pratique, aux algorithmes existants. En quatrième partie, nous étudions l'algèbre de décomposition universelle d'un polynôme. Nous développons un algorithme rapide pour calculer une représentation adéquate de cette algèbre et l'utilisons pour manipuler efficacement les éléments de l'algèbre. Finalement, nous montrons en annexe que la recherche d'invariants fondamentaux d'algèbres d'invariants sous un groupe fini peut se faire directement modulo p, facilitant ainsi leur calcul.

Ce travail présente l'étude de deux types de problèmes d'ordonnancement. Le premier concerne la résolution centralisée et exacte d'un problème à une machine, le second, la résolution distribuée et coopérative d'un problème job shop où chaque machine est assimilée à un acteur possédant sa propre autonomie décisionnelle. Pour ces deux problèmes, des conditions de dominance sont utilisées, dans le premier cas, dans le but de limiter la complexité algorithmique liée à la recherche de solutions admissibles ou optimales, dans le deuxième cas, pour accroître la capacité de chaque acteur à résister aux incertitudes liées aux fluctuations de son environnement. Dans un premier temps, un théorème proposé dans les années quatre-vingt est rappelé, qui, considérant le problème à une machine, permet de caractériser un ensemble de solutions dominantes. Sur la base de ce théorème, nous proposons ensuite de nouvelles conditions analytiques et numériques de dominance permettant de restreindre encore davantage l'ensemble des solutions dominantes. En exploitant ces résultats, des formulations mathématiques originales et efficaces sont présentées, sous forme de programmes linéaires en nombres entiers, pour la modélisation et la résolution du problème à une machine en s'intéressant tour à tour au critère de minimisation du plus grand retard algébrique, puis à celui de minimisation du nombre de travaux en retard. Dans un deuxième temps, nous étudions le problème d'ordonnancement job shop dans un environnement multi-acteur, chaque acteur gérant l'activité d'une machine. Tenant compte de l'autonomie de décision et des objectifs propres de chacun, l'ordonnancement est envisagé sous la forme d'une fonction distribuée où la solution globale résulte d'une coopération entre les différents acteurs, cette solution pouvant évoluer dans le temps au fur-et-à-mesure des prises de décision locales. Ainsi, chaque acteur construisant localement sa propre organisation et n' n'ayant qu'une connaissance part ielle et incertaine de l'organisation des autres, nous proposons que les organisations locales soient construites de façon robuste. Pour cela nous montrons comment, à l'aide des résultats de dominance, maintenir au niveau de chaque acteur un ensemble dominant de solutions ayant une performance au pire bornée. Une nouvelle approche d'ordonnancement est ensuite proposée où les acteurs négocient deux à deux, de façon distribuée, de façon à converger progressivement vers des décisions assurant un compromis satisfaisant entre l'optimisation des objectifs locaux et des objectifs globaux.

La vélocimétrie Doppler par ultrasons pulsés permet d'obtenir, le profil de vitesses d'un écoulement de fluide. L'estimation de la vitesse est réalisée, pour chaque volume de mesure, à partir du signal Doppler, obtenu à partir du signal rétrodiffusé démodulé et échantillonné, dont la fréquence est proportionnelle à la vitesse des particules. On démontre, dans le cas d'un transducteur plan et circulaire, pour un écoulement homogène et uniforme dans le volume de mesure, que la densité spectrale de puissance (DSP) de ce signal peut être modélisée par une gaussienne. Un algorithme de suppression du bruit blanc, basée sur l'identification paramétrique de la DSP est proposée et validée. Elle consiste à identifier, en temps réel, les différentes composantes de la DSP du signal Doppler en utilisant la méthode de Levenberg-Marquardt avec un modèle général gaussien. Le bruit blanc identifié est soustrait à la densité afin de permettre un calcul de moment non-biaisé par celui-ci. Le signal Doppler étant échantillonné par nature, il est soumis au théorème de Shannon qui impose une vitesse maximale mesurable nommée vitesse de Nyquist. Celle-ci est directement proportionnelle à la fréquence de répétition des trains d'ondes (PRF pour Pulse Repetition Frequency). La profondeur d'exploration est également liée au PRF. Ceci impose la principale limite de cette méthode, à savoir la relation inverse liant la profondeur d'exploration et la vitesse maximale mesurable. Une méthode permettant des mesures de vitesses au-delà de la limite de Nyquist est proposée. Elle se base sur l'utilisation de plusieurs fréquences de répétition des trains d'ondes. Le repliement différent pour chaque PRF permet l'apport d'information nécessaire à la résolution de l'ambiguïté sur les vitesses. Un algorithme original de reconstruction spectrale est proposé. Il permet de recombiner les DSP repliés obtenus pour chaque PRF afin de reproduire la DSP du signal Doppler.

Au cours de ces dernières années, le problème de la recherche de requêtes fréquentes dans les bases de données est un problème qui a suscité de nombreuses recherches. En effet, beaucoup de motifs intéressants comme les règles d'association, des dépendances fonction- nelles exactes ou approximatives, des dépendances fonctionnelles conditionnelles exactes ou approximatives peuvent être découverts simplement, contrairement au méthodes clas- siques qui requièrent plusieurs transformations de la base pour extraire de tels motifs. Cependant, le problème de la recherche de requêtes fréquentes dans les bases de données relationnelles est un problème difficile car, d'une part l'espace de recherche est très grand (puisque égal à l'ensemble de toutes les requêtes pouvant être posées sur une base de données), et d'autre part, savoir si deux requêtes sont équivalentes (donc engendrant les calculs de support redondants) est un problème NP-Complet. Dans cette thèse, nous portons notre attention sur les requêtes de type Projection- Selection-Jointure (PSJ), et nous supposons que la base de données est définie selon un schéma étoile. Sous ces hypothèses, nous définissons une relation de pré-ordre (≤) entre les requêtes et nous montrons que : 1. La mesure de support est anti-monotone par rapport à ≤, et 2. En définissant, q ≡ q′ si et seulement si q ≤ q′ et q′ ≤ q, alors toutes les requêtes d'une même classe d'équivalence ont même support. Les principales contributions de cette thèse sont, d'une part d'étudier formellement les propriétés du pré-ordre et de la relation d'équivalence ci-dessus, et d'autre part, de pro- poser un algorithme par niveau de type Apriori pour rechercher l'ensemble des requêtes fréquentes d'une base de données définie sur un schéma étoile. De plus, cet algorithme a été implémenté et les expérimentations que nous avons réalisées montrent que, selon notre approche, le temps de calcul des requêtes fréquentes dans une base de données définie sur un schéma étoile reste acceptable, y compris dans le cas de grandes tables de faits.

Les systèmes de planification dosimétrique utilisent pour calculer le dépôt de dose dans l'être humain d'une part une description des tissus basée sur l'imagerie scanographique et d'autre part une description de l'interaction du faisceau reposant sur une équivalence eau des tissus, à laquelle peut s'ajouter un facteur de diffusion. Du fait du type de rayonnement et de l'énergie utilisés en scanographie, les nombres CT doivent être convertis en facteurs d'équivalence eau avant d'être utilisés par le système de planification.<br />Une détermination par simulation GEANT4 du facteur d'équivalence eau en fonction des nombres CT est proposée. Les facteurs de 77 tissus humains ont été déterminés pour un faisceau de protons de 135 MeV et de 12C de 290 MeV/A et comparés à ceux rapportés dans la littérature. Aux erreurs de détermination (<1.5%) s'ajoutent les incertitudes liées à l'acquisition des nombres CT, ces dernières pouvant atteindre 2%.<br />Les facteurs d'équivalence eau ont ensuite été utilisés pour convertir les courbes d'énergie déposée obtenues dans un tissu à celles obtenues dans l'eau et inversement. Ces courbes d'énergie déposée recalées ont été comparées aux courbes d'énergie déposée issues de la simulation. Pour les deux faisceaux, un accord en position inférieur à 0.5 mm est atteint. Des différences selon les tissus apparaissent au niveau de l'énergie maximale déposée. Elles peuvent atteindre 3% pour les tissus osseux et le faisceau de protons et varient entre 1.5% et 3.5% pour le faisceau de 12C, quel que soit le tissu. Une amélioration significative des recalages de l'énergie déposée en deux dimensions est obtenue en introduisant un facteur supplémentaire permettant de corriger de la diffusion.

Étant donne un mélange de plusieurs signaux sources, par exemple un morceau et plusieurs instruments, ou un entretien radiophonique et plusieurs interlocuteurs, la séparation de source mono-canal consiste a' estimer chacun des signaux sources a' partir d'un enregistrement avec un seul microphone. Puisqu'il y a moins de capteurs que de sources, il y a a priori une infinité de solutions sans rapport avec les sources originales. Il faut alors trouver quelle information supplémentaire permet de rendre le problème bien pose. Au cours des dix dernières années, la factorisation en matrices positives (NMF) est devenue un composant majeurs des systèmes de séparation de sources. En langage profane, la NMF permet de d'écrire un ensemble de signaux audio a ́ partir de combinaisons d' éléments sonores simples (les atomes), formant un dictionnaire. Les systèmes de séparation de sources reposent alors sur la capacité a trouver des atomes qui puissent être assignes de fa con univoque 'a chaque source sonore. En d'autres termes, ils doivent être interprétables. Nous proposons dans cette thèse trois contributions principales aux méthodes d'apprentissage de dictionnaire. La première est un critère de parcimonie par groupes adapte a la NMF lorsque la mesure de distorsion choisie est la divergence d'Itakura-Saito. Dans la plupart des signaux de musique on peut trouver de longs intervalles ou' seulement une source est active (des soli). Le critère de parcimonie par groupe que nous proposons permet de trouver automatiquement de tels segments et d'apprendre un dictionnaire adapte a chaque source. Ces dictionnaires permettent ensuite d'effectuer la tache de séparation dans les intervalles ou' les sources sont mélangées. Ces deux taches d'identification et de séparation sont effectuées simultanément en une seule passe de l'algorithme que nous proposons. Notre deuxième contribution est un algorithme en ligne pour apprendre le dictionnaire a grande échelle, sur des signaux de plusieurs heures, ce qui était impossible auparavant. L'espace mémoire requis par une NMF estimée en ligne est constant alors qu'il croit linéairement avec la taille des signaux fournis dans la version standard, ce qui est impraticable pour des signaux de plus d'une heure. Notre troisième contribution touche a' l'interaction avec l'utilisateur. Pour des signaux courts, l'apprentissage aveugle est particulièrement difficile, et l'apport d'information spécifique au signal traite est indispensable. Notre contribution est similaire à l'inpainting et permet de prendre en compte des annotations temps-fréquence. Elle repose sur l'observation que la quasi-totalite du spectro- gramme peut être divise en régions spécifiquement assignées a' chaque source. Nous d'éecrivons une extension de NMF pour prendre en compte cette information et discutons la possibilité d'inférer cette information automatiquement avec des outils d'apprentissage statistique simples.

Introduction et objectif : La prescription des traitements en radiothérapie est basée sur l'analyse de la répartition de dose calculée par le TPS. Un changement d'algorithme de calcul doit être précédé d'une analyse dosimétrique complète, afin que les impacts cliniques soient maitrisés. Nous présentons une méthodologie de mise en œuvre d'un nouveau TPS. Matériel et méthodologie : Nous avons utilisé 5 algorithmes de calcul de dose. Nous avons comparé 6 plans de traitement avec des configurations identiques : patient, énergie, balistique. Nous avons comparé 12 localisations tumorales : 5 poumons, 1 œsophage, 1 sein, 3 ORL, 1 encéphales et 1 prostate. Le principe de méthodologie est basé sur deux critères d'analyse : 1.Critère d'analyse dosimétrique : nous avons classé les outils d'analyse en 3 catégories : analyse liée à la dose de traitement, analyse liée à la distribution de dose et analyse liée à la répartition de la dose 2.Critère d'analyse statistique : nous avons considéré que nous avons 5 séries de mesure liée à 5 algorithmes. Nous avons considéré les valeurs dosimétriques calculées par l'ancien algorithme comme valeurs de référence. Le test de comparaison statistique utilisé était un Wilcoxon pour série apparié avec un seuil de signification de 5% et un intervalle de confiance à 95%. Résultats et discussion : Nous avons trouvé des écarts pour tous les paramètres comparés dans cette étude. Ces écarts dépendent de la localisation de la tumeur et de l'algorithme de calcul. La maîtrise statistique des résultats nous permet, d'une part de diagnostiquer et interpréter les écarts dosimétriques observés et d'autre part, de déterminer si les écarts sont significatifs. Conclusion : Nous proposons une méthodologie qui permet de quantifier d'éventuels écarts dosimétriques lors d'un changement d'algorithme. L'analyse statistique permet de s'assurer que les résultats sont significatifs.

Cette étude a pour objectif le développement d'un instrument de mesure du taux de présence local d'un écoulement eau - air par tomographie à rayons X. Après une analyse bibliographique exhaustive, les algorithmes de reconstruction retenus sont comparés afin de sélectionner le plus efficace. Afin d'améliorer la précision de reconstruction au voisinage des parois, plusieurs améliorations de cet algorithme sont rajoutées et testées. En parallèle, un dispositif expérimental a été mis au point et ses paramètres d'acquisition ont été optimisés. L'ensemble chaîne de mesure et algorithme de reconstruction est ensuite mis en oeuvre sur des mesures en géométrie parallèle de fantômes et d'écoulements eau-air homogènes, non homogènes et autour de faisceaux de tubes carrés et cylindriques. Ces mesures sont réalisées avec deux schémas d'échantillonnage : régulier et entrelacé. La comparaison des cartes de taux de présence local tomographiques avec les cartes obtenues par une sonde optique permet de valider la méthode développée. Enfin, l'extension de la méthode à la géométrie en éventail (fan-beam) est étudiée.

Cette thèse a pour objet de développer de nouveaux algorithmes pour les groupes de tresses. Un problème important en théorie mathématique des tresses est d'améliorer les algorithmes existants pour résoudre le problème de conjugaison. Nous résolvons complètement ce problème dans le cas du groupe des tresses à quatre brins, en exhibant un algorithme de complexité cubique en terme de la longueur des entrées. La démonstration s'appuie sur deux aspects fondamentaux des groupes de tresses : la structure de groupe de Garside et la structure de groupe de difféotopie. Comme résultat préliminaire, nous développons un algorithme de complexité quadratique capable de classifier les tresses à quatre brins selon leur type de Nielsen-Thurston. Plus généralement, nous étudions ce problème de classification pour un nombre arbitraire de brins. Nous donnons une adaptation des résultats connus de Benardete-Gutiérrez-Nitecki au cadre de la structure de Garside duale. Enfin, à l'aide d'un résultat profond (et non constructif) de Masur-Minsky, nous prouvons l'existence d'un algorithme de complexité polynômiale pour décider le type de Nielsen-Thurston d'une tresse avec un nombre de brins arbitraire.

La tomographie consiste à reconstruire un objet nD à partir de projections (n-1)D. Cette discipline soulève plusieurs questions auxquelles la recherche essaie d'apporter des réponses. On s'intéresse dans cette thèse à trois aspects de cette problématique : 1) la reconstruction de l'image 2D à partir de projections dans un cadre rarement étudié qui est celui des sources ponctuelles ; 2) l'unicité de cette reconstruction ; 3) l'estimation d'informations concernant un objet sans passer par l'étape de reconstitution de son image. Afin d'aborder le problème de reconstruction pour la classe des ensembles convexes, nous définissons une nouvelle classe d'ensembles ayant des propriétés de convexité qu'on appelle convexité par quadrants pour des sources ponctuelles. Après une étude de cette nouvelle classe d'ensembles, nous montrons qu'elle présente des liens forts avec la classe des ensembles convexes. Nous proposons alors un algorithme de reconstruction d'ensemblesconvexes par quadrants qui, si l'unicité de la reconstruction est garantie, permet de reconstruire des ensembles convexes en un temps polynomial. Nous montrons que si une conjecture, que nous avons proposée, est vraie, les conditions de l'unicité pour les ensembles convexes par quadrants sont les mêmes que celles pour les ensembles convexes. Concernant le troisième aspect étudié dans cette thèse, nous proposons une méthode qui permet d'estimer, à partir d'une seule projection, la surface d'un ensemble 2D. Concernant l'estimation du périmètre d'un ensemble 2D, en considérant les projections par une deuxième source d'un ensemble convexe, nous obtenons deux bornes inférieures et une borne supérieure pour le périmètre de l'objet projeté.