Dissertations / Theses: 'Algorithme de flots'

1

Gueth, Frederic. "Observations interférométriques des flots moléculaires L1157 et HH211." Université Joseph Fourier (Grenoble), 1997. http://www.theses.fr/1997GRE10202.

Full text

Abstract:

La formation des etoiles s'accompagne de puissants phenomenes d'ejection de matiere, qui se traduisent par la presence de flots moleculaires bipolaires autour de la plupart des protoetoiles. Cette these etudie la structure interne des flots moleculaires, a l'aide d'observations interferometriques millimetriques realisees a l'interferometre du plateau de bure de l'iram. Les cartes presentees figurent parmi les toutes premieres images de flots moleculaires realisees avec une resolution angulaire aussi elevee (de l'ordre de la seconde d'arc). Deux flots extremement jeunes (environ 10000 ans) et leurs protoetoiles excitatrices sont etudies, a travers l'emission de co et sio. Le flot moleculaire de l 1157 revele deux cavites distinctes, dont les distributions de brillance et les proprietes cinematiques peuvent etre reproduite par un modele de precession. Une forte interaction prend place entre le flot et l'enveloppe entourant la protoetoile. Cette derniere montre de plus une signature d'effondrement gravitationnel. Le flot de hh 211 presente quant a lui une structure remarquable dans laquelle un jet moleculaire rapide emerge de la source centrale et est entoure d'une cavite detectee a plus faible vitesse. La forme de cette derniere correspond parfaitement aux predictions de modeles simples de propagation d'un choc en arc. Plusieurs aspects des observations de l 1157 et hh 211 sont egalement discutes, parmis lesquels les mecanismes de formation des flots moleculaires (la propagation de larges chocs en arc semble etre l'hypothese la plus pertinente) et les processus de formation de la molecule sio dans les flots. Finalement, la deuxieme partie de cette these presente les algorithmes de reconstruction et de deconvolution, adaptes au cas des observations interferometriques de mosaiques, qui ont ete developpes pour permettre les observations decrites precedemment.

APA, Harvard, Vancouver, ISO, and other styles

2

Vernet, Mathilde. "Modèles et algorithmes pour les graphes dynamiques." Thesis, Normandie, 2020. http://www.theses.fr/2020NORMLH12.

Full text

Abstract:

Les problèmes de graphes ont été largement étudiés dans le cas des graphes statiques. Cependant, ces graphes ne permettent pas de prendre en compte la dimension temporelle, qui est souvent une donnée importante pour les situations à modéliser. Les graphes dynamiques viennent combler ces lacunes en permettant de modéliser des évolutions dans le temps. On peut alors s'interroger sur ces mêmes problèmes de graphes dans un contexte dynamique. Cela passe d'abord par la définition du modèle de graphes dynamiques le plus approprié et la modélisation précise du problème sur ces graphes. Lorsque le problème ne peut pas être résolu efficacement en appliquant directement des méthodes connues sur les graphes statiques, il faut alors concevoir un algorithme de résolution spécifique aux graphes dynamiques et l'analyser théoriquement et expérimentalement.En suivant cette démarche, l'objectif de cette thèse est de s'interroger sur l'extension aux graphes dynamiques des problèmes bien connus sur les graphes statiques. Ce travail s'intéresse à plusieurs problèmes de graphes en contexte dynamique en se focalisant sur les aspects algorithmiques et en s'abstrayant des domaines d'applications
Graph problems have been widely studied in the case of static graphs. However, these graphs do not allow a time dimension to be considered, even though time is an important variable for the situations to model. Dynamic graphs make it possible to model evolution over time. This is a reason to wonder about graph problems in a dynamic context. First, it is necessary to define the most appropriate dynamic graphs model and the precise problem on those graphs. When the problem cannot be efficiently solved directly using known static graph methods, an algorithm specific to dynamic graphs must be designed and analyzed theoretically and practically.With that approach, this thesis' objective is to study graph problems' extensions to dynamic graphs. This works deals with several graph problems in a dynamic context by focusing on algorithmic aspects and without considering application domains

APA, Harvard, Vancouver, ISO, and other styles

3

Bouchakour, Mustapha. "Composition de graphes et le polytope des absorbantsUn algorithme de coupes pour le problème du flots a coûts fixes." Rennes 1, 1996. http://www.theses.fr/1996REN10196.

Full text

Abstract:

Cette these est composee de deux parties: la premiere partie porte sur le probleme des absorbants de poids minimum. Nous nous interessons au polytope des solutions de ce probleme. Dans un premier temps, nous decrivons certaines facettes de base et nous discutons de certaines proprietes structurales de ce polytope. Par la suite, nous considerons ce polytope dans les graphes decomposables par des sommets d'articulation. Si g est un graphe qui se decompose en deux graphes g#1 et g#2, alors on montre que le polytope des absorbants dans g peut etre decrit a partir de deux systemes lineaires lies a g#1 et g#2. Ceci donne lieu a une technique permettant de caracteriser le polytope des absorbants dans les classes de graphes qui sont recursivement decomposables. Nous obtenons egalement une procedure de composition de facettes dans ce type de graphes. Nous montrons que le probleme de l'absorbant peut etre aussi decompose. Des applications de cette technique sont discutees pour la classe des cactus. Nous etudions aussi des procedures generales de construction de facettes. Dans la deuxieme partie, nous etudions le probleme du flot quand les couts fixes et des couts variables sont associes aux arcs du graphe. Nous developpons une approche polyedrale pour ce probleme. Nous introduisons des nouvelles contraintes valides pour le polyedre associe, appelees contraintes de coupes. Ces contraintes sont utilisees par la suite dans une methode de coupes pour resoudre des instances du probleme. Les resultats experimentaux montrent que ces contraintes peuvent etre utiles pour la resolution du probleme dans les graphes peu denses

APA, Harvard, Vancouver, ISO, and other styles

4

Beker, Sergio Ariel. "Techniques d'Optimisation pour le Dimensionnement et la Reconfiguration des Réseaux MPLS." Phd thesis, Télécom ParisTech, 2004. http://pastel.archives-ouvertes.fr/pastel-00000689.

Full text

Abstract:

La superposition de topologies virtuelles à la topologie physique d'un réseau est un des principaux mécanismes de l'ingénierie de trafic. Soit un réseau physique d'une certaine topologie et capacité fixées et une matrice de trafic à véhiculer, il s'agit trouver une topologie logique permettant de mapper de manière optimale la matrice de trafic sur le réseau physique. Lors de l'évolution de la matrice de trafic sur des échelles de temps longues, il faudra agir sur le layout. La première contribution concerne la définition de fonctions de coût mieux adaptées à la réalité d'un opérateur, la deuxième contribution concerne la prise en compte du coût de changement du layout. Il s'avère intéressant d'un point de vue opérateur de réduire la complexité du layout, mesurée comme une fonction du nombre de chemins virtuels. Nous avons donc formulé divers problèmes de minimisation de la complexité du layout sous des contraintes de QoS. Il s'agit d'une modélisation réaliste mais qui engendre des modèles difficiles à résoudre. Nous avons développés des heuristiques qui permet de trouver des solutions approchées pour des réseaux de grande taille. Nous avons montré que la complexité des layouts peut être significativement réduite en comparaison avec celle obtenue suite à l'optimisation des fonctions de coût classiques. Le changement du layout implique d'une part un coût d'opération et d'autre part peut engendrer des coupures de service qui affecteront directement le coût d'opération. Nous avons formulé une famille de problèmes prenant en compte le coût de reconfiguration du layout. L'une des heuristiques citées a été adaptée pour analyser ces nouveaux problèmes.

APA, Harvard, Vancouver, ISO, and other styles

5

Bonnotte, Nicolas. "Unidimensional and Evolution Methods for Optimal Transportation." Phd thesis, Université Paris Sud - Paris XI, 2013. http://tel.archives-ouvertes.fr/tel-00946781.

Full text

Abstract:

In dimension one, optimal transportation is rather straightforward. The easiness with which a solution can be obtained in that setting has recently been used to tackle more general situations, each time thanks to the same method. First, disintegrate your problem to go back to the unidimensional case, and apply the available 1D methods to get a first result; then, improve it gradually using some evolution process.This dissertation explores that direction more thoroughly. Looking back at two problems only partially solved this way, I show how this viewpoint in fact allows to go even further.The first of these two problems concerns the computation of Yann Brenier's optimal map. Guillaume Carlier, Alfred Galichon, and Filippo Santambrogio found a new way to obtain it, thanks to an differential equation for which an initial condition is given by the Knothe--Rosenblatt rearrangement. (The latter is precisely defined by a series of unidimensional transformations.) However, they only dealt with discrete target measures; I~generalize their approach to a continuous setting. By differentiation, the Monge--Ampère equation readily gives a PDE satisfied by the Kantorovich potential; but to get a proper initial condition, it is necessary to use the Nash--Moser version of the implicit function theorem.The basics of optimal transport are recalled in the first chapter, and the Nash--Moser theory is exposed in chapter 2. My results are presented in chapter 3, and numerical experiments in chapter 4.The last chapter deals with the IDT algorithm, devised by François Pitié, Anil C. Kokaram, and Rozenn Dahyot. It builds a transport map that seems close enough to the optimal map for most applications. A complete mathematical understanding of the procedure is, however, still lacking. An interpretation as a gradient flow in the space of probability measures is proposed, with the sliced Wasserstein distance as the functional. I also prove the equivalence between the sliced and usual Wasserstein distances.

APA, Harvard, Vancouver, ISO, and other styles

6

Sa, Shibasaki Rui. "Lagrangian Decomposition Methods for Large-Scale Fixed-Charge Capacitated Multicommodity Network Design Problem." Thesis, Université Clermont Auvergne‎ (2017-2020), 2020. http://www.theses.fr/2020CLFAC024.

Full text

Abstract:

Typiquement présent dans les domaines de la logistique et des télécommunications, le problème de synthèse de réseau multi-flot à charge fixe reste difficile, en particulier dans des contextes à grande échelle. Dans ce cas, la capacité à produire des solutions de bonne qualité dans un temps de calcul raisonnable repose sur la disponibilité d'algorithmes efficaces. En ce sens, cette thèse propose des approches lagrangiennes capables de fournir des bornes relativement proches de l'optimal pour des instances de grande taille. L'efficacité des méthodes dépend de l'algorithme appliqué pour résoudre les duals lagrangiens, nous choisissons donc entre deux des solveurs les plus efficaces de la littérature: l'algorithme de Volume et la méthode Bundle, fournissant une comparaison entre eux. Les résultats ont montré que l'algorithme de Volume est plus efficace dans le contexte considéré, étant celui choisi pour le développement du projet de recherche.Une première heuristique lagrangienne a été conçue pour produire des solutions réalisables de bonne qualité pour le problème, obtenant de bien meilleurs résultats que Cplex pour les plus grandes instances. Concernant les limites inférieures, un algorithme Relax-and-Cut a été implémenté intégrant une analyse de sensibilité et une mise à l'échelle des contraintes, ce qui a amélioré les résultats. Les améliorations des bornes inférieures ont atteint 11\%, mais en moyenne, elles sont restées inférieures à 1\%. L'algorithme Relax-and-Cut a ensuite été inclus dans un schéma Branch-and-Cut, pour résoudre des programmes linéaires dans chaque nœud de l'arbre de recherche. De plus, une heuristique Feasibility Pump lagrangienne a été implémentée pour accélérer la recherche de bonnes solutions réalisables. Les résultats obtenus ont montré que le schéma proposé est compétitif avec les meilleurs algorithmes de la littérature et fournit les meilleurs résultats dans des contextes à grande échelle. De plus, une version heuristique de l'algorithme Branch-and-Cut basé sur le Feasibility Pump lagrangien a été testée, fournissant les meilleurs résultats en général, par rapport aux heuristiques de la littérature
Typically present in logistics and telecommunications domains, the Fixed-Charge Multicommodity Capacitated Network Design Problem remains challenging, especially when large-scale contexts are involved. In this particular case, the ability to produce good quality soutions in a reasonable amount of time leans on the availability of efficient algorithms. In that sense, the present thesis proposed Lagrangian approaches that are able to provide relatively sharp bounds for large-scale instances of the problem. The efficiency of the methods depend on the algorithm applied to solve Lagrangian duals, so we choose between two of the most efficient solvers in the literature: the Volume Algorithm and the Bundle Method, providing a comparison between them. The results showed that the Volume Algorithm is more efficient in the present context, being the one kept for further research.A first Lagrangian heuristic was devised to produce good quality feasible solutions for the problem, obtaining far better results than Cplex, for the largests instances. Concerning lower bounds, a Relax-and-Cut algorithm was implemented embbeding sensitivity analysis and constraint scaling, which improved results. The increases in lower bounds attained 11\%, but on average they remained under 1\%.The Relax-and-Cut algorithm was then included in a Branch-and-Cut scheme, to solve linear programs in each node of the search tree. Moreover, a Feasibility Pump heuristic using the Volume Algorithm as solver for linear programs was implemented to accelerate the search for good feasible solutions in large-scale cases. The obtained results showed that the proposed scheme is competitive with the best algorithms in the literature, and provides the best results in large-scale contexts. Moreover, a heuristic version of the Branch-and-Cut algorithm based on the Lagrangian Feasibility Pump was tested, providing the best results in general, when compared to efficient heuristics in the literature

APA, Harvard, Vancouver, ISO, and other styles

7

Soyez-Martin, Claire. "From semigroup theory to vectorization : recognizing regular languages." Electronic Thesis or Diss., Université de Lille (2022-....), 2023. http://www.theses.fr/2023ULILB052.

Full text

Abstract:

L'évaluation efficace des expressions régulières constitue un défi persistant depuis de nombreuses décennies. Au fil du temps, des progrès substantiels ont été réalisés grâce à une variété d'approches, allant de nouveaux et ingénieux algorithmes à des optimisations complexes de bas niveau.Les outils de pointe de ce domaine utilisent ces techniques d'optimisation, et repoussent constamment les limites de leur efficacité. Une avancée notoire réside dans l'intégration de la vectorisation, qui exploite une forme de parallélisme de bas niveau pour traiter l'entrée par blocs, entraînant ainsi d'importantes améliorations de performances. Malgré une recherche approfondie sur la conception d'algorithmes sur mesure pour des tâches particulières, ces solutions manquent souvent de généralisabilité, car la méthodologie sous-jacente à ces algorithmes ne peut pas être appliquée de manière indiscriminée à n'importe quelle expression régulière, ce qui rend difficile son intégration dans les outils existants.Cette thèse présente un cadre théorique permettant de générer des programmes vectorisés particuliers capables d'évaluer les expressions régulières correspondant aux expressions rationnelles appartenant à une classe logique donnée. L'intérêt de ces programmes vectorisés vient de l'utilisation de la théorie algébrique des automates, qui offre certains outils algébriques permettant de traiter les lettres en parallèle. Ces outils permettent également d'analyser les langages réguliers plus finement, offrent accès à des optimisations des programmes vectorisés basées sur les propriétés algébriques de ces langages. Cette thèse apporte des contributions dans deux domaines. D'une part, nous présentons des implémentations et des benchmarks préliminaires, afin d'étudier les possibilités offertes par l'utilisation de l'algèbre et de la vectorisation dans les algorithmes d'évaluation des expressions régulières. D'autre part, nous proposons des algorithmes capables de générer des programmes vectorisés reconnaissant les langages appartenant à deux classes d'expressions rationnelles, la logique du premier ordre et sa restriction aux formules utilisant au plus deux variables
The pursuit of optimizing regular expression validation has been a long-standing challenge,spanning several decades. Over time, substantial progress has been made through a vast range of approaches, spanning from ingenious new algorithms to intricate low-level optimizations.Cutting-edge tools have harnessed these optimization techniques to continually push the boundaries of efficient execution. One notable advancement is the integration of vectorization, a method that leverage low-level parallelism to process data in batches, resulting in significant performance enhancements. While there has been extensive research on designing handmade tailored algorithms for particular languages, these solutions often lack generalizability, as the underlying methodology cannot be applied indiscriminately to any regular expression, which makes it difficult to integrate to existing tools.This thesis provides a theoretical framework in which it is possible to generate vectorized programs for regular expressions corresponding to rational expressions in a given class. To do so, we rely on the algebraic theory of automata, which provides tools to process letters in parallel. These tools also allow for a deeper understanding of the underlying regular language, which gives access to some properties that are useful when producing vectorized algorithms. The contribution of this thesis is twofold. First, it provides implementations and preliminary benchmarks to study the potential efficiency of algorithms using algebra and vectorization. Second, it gives algorithms that construct vectorized programs for languages in specific classes of rational expressions, namely the first order logic and its subset restricted to two variables

APA, Harvard, Vancouver, ISO, and other styles

8

Frery, Jordan. "Ensemble Learning for Extremely Imbalced Data Flows." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSES034.

Full text

Abstract:

L'apprentissage machine est l'étude de la conception d'algorithmes qui apprennent à partir des données d'apprentissage pour réaliser une tâche spécifique. Le modèle résultant est ensuite utilisé pour prédire de nouveaux points de données (invisibles) sans aucune aide extérieure. Ces données peuvent prendre de nombreuses formes telles que des images (matrice de pixels), des signaux (sons,...), des transactions (âge, montant, commerçant,...), des journaux (temps, alertes, ...). Les ensembles de données peuvent être définis pour traiter une tâche spécifique telle que la reconnaissance d'objets, l'identification vocale, la détection d'anomalies, etc. Dans ces tâches, la connaissance des résultats escomptés encourage une approche d'apprentissage supervisé où chaque donnée observée est assignée à une étiquette qui définit ce que devraient être les prédictions du modèle. Par exemple, dans la reconnaissance d'objets, une image pourrait être associée à l'étiquette "voiture" qui suggère que l'algorithme d'apprentissage doit apprendre qu'une voiture est contenue dans cette image, quelque part. Cela contraste avec l'apprentissage non supervisé où la tâche à accomplir n'a pas d'étiquettes explicites. Par exemple, un sujet populaire dans l'apprentissage non supervisé est de découvrir les structures sous-jacentes contenues dans les données visuelles (images) telles que les formes géométriques des objets, les lignes, la profondeur, avant d'apprendre une tâche spécifique. Ce type d'apprentissage est évidemment beaucoup plus difficile car il peut y avoir un nombre infini de concepts à saisir dans les données. Dans cette thèse, nous nous concentrons sur un scénario spécifique du cadre d'apprentissage supervisé : 1) l'étiquette d'intérêt est sous-représentée (p. ex. anomalies) et 2) l'ensemble de données augmente avec le temps à mesure que nous recevons des données d'événements réels (p. ex. transactions par carte de crédit). En fait, ces deux problèmes sont très fréquents dans le domaine industriel dans lequel cette thèse se déroule
Machine learning is the study of designing algorithms that learn from trainingdata to achieve a specific task. The resulting model is then used to predict overnew (unseen) data points without any outside help. This data can be of manyforms such as images (matrix of pixels), signals (sounds,...), transactions (age,amount, merchant,...), logs (time, alerts, ...). Datasets may be defined to addressa specific task such as object recognition, voice identification, anomaly detection,etc. In these tasks, the knowledge of the expected outputs encourages a supervisedlearning approach where every single observed data is assigned to a label thatdefines what the model predictions should be. For example, in object recognition,an image could be associated with the label "car" which suggests that the learningalgorithm has to learn that a car is contained in this picture, somewhere. This is incontrast with unsupervised learning where the task at hand does not have explicitlabels. For example, one popular topic in unsupervised learning is to discoverunderlying structures contained in visual data (images) such as geometric formsof objects, lines, depth, before learning a specific task. This kind of learning isobviously much harder as there might be potentially an infinite number of conceptsto grasp in the data. In this thesis, we focus on a specific scenario of thesupervised learning setting: 1) the label of interest is under represented (e.g.anomalies) and 2) the dataset increases with time as we receive data from real-lifeevents (e.g. credit card transactions). In fact, these settings are very common inthe industrial domain in which this thesis takes place

APA, Harvard, Vancouver, ISO, and other styles

9

Gessese, Alelign Fekade. "Algorithms for Bed Topography Reconstruction in Geophysical Flows." Thesis, University of Canterbury. Mechanical Engineering, 2013. http://hdl.handle.net/10092/8673.

Full text

Abstract:

Bed topography identification in open channel and glacier flows is of paramount importance for the study of the respective flows. In the former, the knowledge of the channel bed topography is required for modelling the hydrodynamics of open channel flows, fluvial hydraulics, flood propagation, and river flow monitoring. Indeed, flow models based on the Shallow Water Approximation require prior information on the channel bed topography to accurately capture the flow features. While in the latter, usable bedrock topographic information is very important for glacier flow modellers to accurately predict the flow characteristics. Experimental techniques to infer the bed topography are usually used but are mostly time consuming, costly, and sometimes not possible due to geographical restrictions. However, the measurement of free surface elevation is relatively easy. Alternative to experimental techniques, it is therefore important to develop fast, easy-to-implement, and cost-effective numerical methods. The inverse of the classical hydrodynamic problem corresponds to the determination of hydraulic parameters from measurable quantities. The forward problem uses model parameters to determine measurable quantities. New one-shot and direct pseudo-analytical and numerical approaches for reconstructing the channel bed topography from known free surface elevation data is developed for one-dimensional shallow water flows. It is shown in this work that instead of treating this inverse problem in the traditional partial differential equation (PDE)-constrained optimization framework, the governing equations of the direct problem can be conveniently rearranged to obtain an explicit PDE for the inverse problem. This leads to a direct solution of the inverse problem which is successfully tested on a range of benchmark problems and experimental data for noisy and noiseless free surface data. It was found that this solution approach creates very little amplification of noise. A numerical technique which uses the measured free surface velocity to infer the channel bed topography is also developed. The one-dimensional shallow water equations along with an empirical relationship between the free surface and the depth averaged velocities are used for the inverse problem analysis. It is shown that after a series of algebraic manipulation and integration, the equation governing the inverse problem simplifies to a simple integral equation. The proposed method is tested on a range of analytical and experimental benchmark test cases and the results confirm that, it is possible to reconstruct the channel bed topography from a known free surface velocity distribution of one-dimensional open channel flows. Following the analysis of the case of one-dimensional shallow water flows, a numerical technique for reconstructing the channel bed topography from known free surface elevation data for steep open channel flows is developed using a modified set of equations for which the zero-inertia shallow water approximation holds. In this context, the shallow water equations are modified by neglecting inertia terms while retaining the effects of the bed slope and friction terms. The governing equations are recast into a single first-order partial differential equation which describes the inverse problem. Interestingly, the analysis shows that the inverse problem does not require the knowledge of the bed roughness. The forward problem is solved using MacCormack’s explicit numerical scheme by considering unsteady modified shallow water equations. However, the inverse problem is solved using the method of characteristics. The results of the inverse and the forward problem are successfully tested against each other. In the framework of full two-dimensional shallow water equations, an easy-to-implement and fast to solve direct numerical technique is developed to solve the inverse problem of shallow open channel flows. The main underlying idea is analogous to the idea implemented for the case of one-dimensional reconstruction. The technique described is a “one-shot technique” in the sense that the solution of the partial differential equation provides the solution to the inverse problem directly. The idea is tested on a set of artificial data obtained by first solving the forward problem. Glaciers are very important as an indicator of future climate change or to trace past climate. They respond quickly compared to the Antarctica and Greenland ice sheets which make them ideal to predict climate changes. Glacier bedrock topography is an important parameter in glacier flow modelling to accurately capture its flow dynamics. Thus, a mathematical technique to infer this parameter from measured free surface data is invaluable. Analogous to the approaches implemented for open channel flows, easy-to-implement direct numerical and analytical algorithms are developed to infer the bedrock topography from the knowledge of the free surface elevation in one space dimension. The numerical and analytical methods are both based on the Shallow Ice Approximation and require the time series of the ablation/accumulation rate distribution. Moreover, the analytical method requires the knowledge of a non-zero glacier thickness at an arbitrary location. Numerical benchmark test cases are used to verify the suitability and applicability of the algorithms.

APA, Harvard, Vancouver, ISO, and other styles

10

Pervaiz, Mehtab M. "Spatio-temporal adaptive algorithm for reacting flows." Thesis, Massachusetts Institute of Technology, 1988. http://hdl.handle.net/1721.1/34994.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Chizat, Lénaïc. "Transport optimal de mesures positives : modèles, méthodes numériques, applications." Thesis, Paris Sciences et Lettres (ComUE), 2017. http://www.theses.fr/2017PSLED063/document.

Full text

Abstract:

L'objet de cette thèse est d'étendre le cadre théorique et les méthodes numériques du transport optimal à des objets plus généraux que des mesures de probabilité. En premier lieu, nous définissons des modèles de transport optimal entre mesures positives suivant deux approches, interpolation et couplage de mesures, dont nous montrons l'équivalence. De ces modèles découle une généralisation des métriques de Wasserstein. Dans une seconde partie, nous développons des méthodes numériques pour résoudre les deux formulations et étudions en particulier une nouvelle famille d'algorithmes de "scaling", s'appliquant à une grande variété de problèmes. La troisième partie contient des illustrations ainsi que l'étude théorique et numérique, d'un flot de gradient de type Hele-Shaw dans l'espace des mesures. Pour les mesures à valeurs matricielles, nous proposons aussi un modèle de transport optimal qui permet un bon arbitrage entre fidélité géométrique et efficacité algorithmique
This thesis generalizes optimal transport beyond the classical "balanced" setting of probability distributions. We define unbalanced optimal transport models between nonnegative measures, based either on the notion of interpolation or the notion of coupling of measures. We show relationships between these approaches. One of the outcomes of this framework is a generalization of the p-Wasserstein metrics. Secondly, we build numerical methods to solve interpolation and coupling-based models. We study, in particular, a new family of scaling algorithms that generalize Sinkhorn's algorithm. The third part deals with applications. It contains a theoretical and numerical study of a Hele-Shaw type gradient flow in the space of nonnegative measures. It also adresses the case of measures taking values in the cone of positive semi-definite matrices, for which we introduce a model that achieves a balance between geometrical accuracy and algorithmic efficiency

APA, Harvard, Vancouver, ISO, and other styles

12

Pullan, Malcolm Craig. "Separated continuous linear programs : theory and algorithms." Thesis, University of Cambridge, 1992. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.260693.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Bourlon, Franck. "Réalisation d'une plate-forme expérimentale pour l'élaboration de pilotages automatiques flous d'une rame de métro en similation à partir de données objectives et subjectives." Valenciennes, 1996. https://ged.uphf.fr/nuxeo/site/esupversions/f8e11027-0073-4089-8f02-5bb1ea3ea18c.

Full text

Abstract:

Depuis les premiers travaux de Zadeh et Mamdani sur la commande floue, celle-ci a été appliquée industriellement dans divers domaines dont celui des transports. En effet, depuis 1987, le métro de Sendai (japon) est piloté automatiquement par un algorithme flou. Aussi, le travail présenté dans ce mémoire, et effectue en collaboration avec la RATP, propose une étude de faisabilité d'une commande floue de rame de métro. Plusieurs aspects de la conduite sont pris en compte dans la commande envisagée, en particulier le confort des passagers et la consommation d'énergie. A cette fin, une plate-forme expérimentale reproduisant le système physique est réalisée. Différentes manipulations sont exécutées par trente-deux sujets accomplissant trois taches (suivi de vitesse de consigne, arrêt et conduite) sur trois interstations, fictives et réelles. A partir des données recueillies, le problème consiste à déterminer les meilleurs sujets, qualifiés d'experts, à la lumières de cinq critères (temps de parcours, suivi de consigne de vitesse, précision d'arrêt, confort, consommation d'énergie) pour chacune des tâches et chacune des interstations. Trois solutions sont proposées: l'une floue et les deux autres multicritères. La synthèse de leurs résultats est ensuite effectuée afin de déterminer les experts. Les données brutes relatives à chaque expert sont ensuite exploitées par l'algorithme d'identification floue de Takagi & Sugeno pour déterminer les différents paramètres de deux types de régulateurs flous : simple et double. Une évaluation des performances de ceux-ci est donnée en comparaison des résultats obtenus avec d'autres approches (classiques et floues). Ce mémoire se conclut sur l'apport de tels régulateurs flous dans la conduite automatique d'une rame et présente les différentes perspectives de cette étude de faisabilité
Since the pioneer works achieved by ZADEH and MAMDANI about fuzzy control, this one has been industrially applied in various domains such as transportation. Besides, since 1987, the Sendai subway (Japan) is automatically driven by a fuzzy control algorithm. Thus, the works set out in this report and carried out in collaboration with RATP, intend to evaluate the feasibility of a subway train fuzzy controller. Many aspects of driving are considered in the controller we intend to design, particulary passengers’comfort and energy saving. For that, an experimental platform reproducing the real system is achieved. Different experiments are performed by thirty-two subjects carrying out three tasks (speed traceability, stopping and driving) over three interstations, fictious and actual. From collected data, the problem consists in determining the best subjects, named experts, in the light of five criteria (running time, target speed traceability, stopping accuracy, comfort, energy consumption) for each task and interstation. Three ways are proposed. The former is a fuzzy method, the latter are multicriteria ones. Their results are then synthesized to determine experts. Then data related to each of the experts are treated via TAKAGI & SUGENO fuzzy identification algorithm to fit the different parameters of two kinds of fuzzy controllers : “single” and “double”. An evaluation of these controllers is given by comparing their results to those obtained through other approaches (classical and fuzzy ones). This report ends by a conclusion about the contribution of such fuzzy controllers in automatic subway train driving and introduces the different prospects of this feasibility study

APA, Harvard, Vancouver, ISO, and other styles

14

Bonnal, Pierre. "Planification possibiliste d'un grand projet industriel s'appuyant sur l'approche de la chaîne critique." Toulouse, INPT, 2002. http://www.theses.fr/2002INPT001H.

Full text

Abstract:

Les planificateurs de projet ont parfois à faire face à de difficiles dilemmes lorsqu'ils ont à choisir un outil de planification approprié à leurs projets : les modèles trop simples sont sources de confusions, ceux plus sophistiqués s'avèrent finalement inutiles à cause de leur piètre réactivité. Les approches de la chaîne critique et de planification floue peuvent constituer un bon compromis. Prises séparément, elles peuvent sembler théoriques, mais lorsqu'utilisées conjointement elles s'avèrent être complémentaires et fournissent un cadre de planification très bien adapté aux grands projets industriels. Après une revue des diverses approches de planification floue, cette thèse propose un environnement de planification multi-niveaux complet, pour la planification de grands projets industriels. Des chercheurs ont récemment mis en évidence que dans un environnement de planification possibiliste, l'identification des activités critiques constituait un problème qui ne pouvait être résolu en un temps de calcul polynomial. Un algorithme est proposé pour fournir une approximation à l'ensemble des activités critiques d'un projet. Les descripteurs linguistiques sont au nombre des fonctionnalités intéressantes que propose la théorie des ensembles flous. Des descripteurs linguistiques temporels de dates et de durées sont aussi proposés pour la quantification des informations au niveau du planning de coordination, et pour la restitution de celle-ci à l'issue de l'exercice de planification. Enfin, une arithmétique floue atténuatrice de l'imprécision est proposée afin que les résultats des calculs soient exploitables.

APA, Harvard, Vancouver, ISO, and other styles

15

Slack, David Christopher. "The development of solution algorithms for compressible flows." Diss., This resource online, 1991. http://scholar.lib.vt.edu/theses/available/etd-07282008-134254/.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Palaniappan, Karthik. "Algorithms for automatic feedback control of aerodynamic flows /." May be available electronically:, 2007. http://proquest.umi.com/login?COPT=REJTPTU1MTUmSU5UPTAmVkVSPTI=&clientId=12498.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Tang, Ping. "Counting algorithm for network arrangements within activity floats." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp01/MQ30035.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Aggarwal, Charu C., Haim Kaplan, and Robert E. 1948 Tarjan. "A Faster Primal Network Simplex Algorithm." Massachusetts Institute of Technology, Operations Research Center, 1996. http://hdl.handle.net/1721.1/5266.

Full text

Abstract:

We present a faster implementation of the polynomial time primal simplex algorithm due to Orlin [23]. His algorithm requires O(nm min{log(nC), m log n}) pivots and O(n2 m ??n{log nC, m log n}) time. The bottleneck operations in his algorithm are performing the relabeling operations on nodes, selecting entering arcs for pivots, and performing the pivots. We show how to speed up these operations so as to yield an algorithm whose running time is O(nm. log n) per scaling phase. We show how to extend the dynamic-tree data-structure in order to implement these algorithms. The extension may possibly have other applications as well.

APA, Harvard, Vancouver, ISO, and other styles

19

Romera, Thomas. "Adéquation algorithme architecture pour flot optique sur GPU embarqué." Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS450.

Full text

Abstract:

Cette thèse porte sur l'optimisation et l'implémentation efficace d'algorithmes d'estimation du mouvement des pixels (flot optique) sur des processeurs graphiques (GPU) embarqués. Deux algorithmes itératifs ont été étudiés : la méthode de Variation Totale - L1 (TV-L1) et la méthode de Horn-Schunck. L’objectif est d’obtenir un traitement temps réel (moins de 40 ms par images) sur des plateformes embarquées à faible consommation énergétique, tout en gardant une résolution image et une qualité d’estimation du flot acceptable pour les applications visées. Différents niveaux de stratégies d'optimisation ont été explorés. Des transformations algorithmiques de haut niveau, telles que la fusion d'opérateurs et le pipeline d'opérateurs, ont été mises en œuvre pour maximiser la réutilisation des données et améliorer la localité spatiale/temporelle. De plus, des optimisations bas niveau spécifiques aux GPU, notamment l'utilisation d'instructions et de nombres vectoriels, ainsi qu'une gestion efficace de l'accès à la mémoire, ont été intégrées. L'impact de la représentation des nombres en virgule flottante (simple précision par rapport à demi-précision) a également été étudié. Les implémentations ont été évaluées sur les plateformes embarquées Nvidia Jetson Xavier, TX2 et Nano en termes de temps d'exécution, de consommation énergétique et de précision du flot optique. Notamment, la méthode TV-L1 présente une complexité et une intensité de calcul plus élevées par rapport à Horn-Schunck. Les versions les plus rapides de ces algorithmes atteignent ainsi un temps de traitement de 0,21 nanosecondes par pixel par itération en demi-précision sur la plate-forme Xavier. Cela représente une réduction du temps d'exécution de 22x par rapport aux versions CPU efficaces et parallèles. De plus, la consommation d'énergie est réduite d'un facteur x5,3. Parmi les cartes testées, la plate-forme embarquée Xavier, à la fois la plus puissante et la plus récente, offre systématiquement les meilleurs résultats en termes de vitesse et d'efficacité énergétique. La fusion d'opérateurs et le pipelining se sont avérés essentiels pour améliorer les performances sur GPU en favorisant la réutilisation des données. Cette réutilisation des données est rendue possible grâce à la mémoire Shared des GPU, une petite mémoire d'accès rapide permettant le partage de données entre les threads du même bloc de threads GPU. Bien que la fusion de plusieurs itérations apporte des gains de performance, elle est limitée par la taille de la mémoire Shared, nécessitant des compromis entre l'utilisation des ressources et la vitesse. L'utilisation de nombres en demi-précision accélère les algorithmes itératifs et permet d'obtenir une meilleure précision du flot optique dans le même laps de temps par rapport aux versions en simple-précision. Les implémentations en demi-précision convergent plus rapidement en raison de l'augmentation du nombre d'itérations réalisables dans un délai donné. Plus précisément, l'utilisation de nombres en demi-précision sur la meilleure architecture GPU accélère l'exécution jusqu'à 2,2x pour TV-L1 et 3,7x pour Horn-Schunck. Ces travaux soulignent l'importance des optimisations spécifiques aux GPU pour les algorithmes de vision par ordinateur, ainsi que l'utilisation et l'étude des nombres à virgule flottante de précision réduite. Ils ouvrent la voie à des améliorations futures grâce à des différentes transformations algorithmiques, à des formats numériques différents et à des architectures matérielles nouvelles. Cette approche peut également être étendue à d'autres familles d'algorithmes itératifs
This thesis focus on the optimization and efficient implementation of pixel motion (optical flow) estimation algorithms on embedded graphics processing units (GPUs). Two iterative algorithms have been studied: the Total Variation - L1 (TV-L1) method and the Horn-Schunck method. The primary objective of this work is to achieve real-time processing, with a target frame processing time of less than 40 milliseconds, on low-power platforms, while maintaining acceptable image resolution and flow estimation quality for the intended applications. Various levels of optimization strategies have been explored. High-level algorithmic transformations, such as operator fusion and operator pipelining, have been implemented to maximize data reuse and enhance spatial/temporal locality. Additionally, GPU-specific low-level optimizations, including the utilization of vector instructions and numbers, as well as efficient memory access management, have been incorporated. The impact of floating-point number representation (single-precision versus half-precision) has also been investigated. The implementations have been assessed on Nvidia's Jetson Xavier, TX2, and Nano embedded platforms in terms of execution time, power consumption, and optical flow accuracy. Notably, the TV-L1 method exhibits higher complexity and computational intensity compared to Horn-Schunck. The fastest versions of these algorithms achieve a processing rate of 0.21 nanoseconds per pixel per iteration in half-precision on the Xavier platform, representing a 22x time reduction over efficient and parallel CPU versions. Furthermore, energy consumption is reduced by a factor of x5.3. Among the tested boards, the Xavier embedded platform, being both the most powerful and the most recent, consistently delivers the best results in terms of speed and energy efficiency. Operator merging and pipelining have proven to be instrumental in improving GPU performance by enhancing data reuse. This data reuse is made possible through GPU Shared memory, which is a small, high-speed memory that enables data sharing among threads within the same GPU thread block. While merging multiple iterations yields performance gains, it is constrained by the size of the Shared memory, necessitating trade-offs between resource utilization and speed. The adoption of half-precision numbers accelerates iterative algorithms and achieves superior optical flow accuracy within the same time frame compared to single-precision counterparts. Half-precision implementations converge more rapidly due to the increased number of iterations possible within a given time window. Specifically, the use of half-precision numbers on the best GPU architecture accelerates execution by up to x2.2 for TV-L1 and x3.7 for Horn-Schunck. This work underscores the significance of both GPU-specific optimizations for computer vision algorithms, along with the use and study of reduced floating point numbers. They pave the way for future enhancements through new algorithmic transformations, alternative numerical formats, and hardware architectures. This approach can potentially be extended to other families of iterative algorithms

APA, Harvard, Vancouver, ISO, and other styles

20

Gaumont, Noé. "Groupes et Communautés dans les flots de liens : des données aux algorithmes." Thesis, Paris 6, 2016. http://www.theses.fr/2016PA066271/document.

Full text

Abstract:

Les interactions sont partout : il peut s'agir de contacts entre individus, d'emails, d'appels téléphoniques, etc. Toutes ces interactions sont définies par deux entités interagissant sur un intervalle de temps: par exemple, deux individus se rencontrant entre 12h et 14h. Nous modélisons ces interactions par des flots de liens qui sont des ensembles de quadruplets (b, e, u, v), où chaque quadruplet représente un lien entre les noeuds u et v existant durant l'intervalle [b,e]. Dans un graphe, une communauté est un sous-ensemble plus densément connecté qu’une référence. Dans le formalisme de flot de liens, les notions même de densité et de référence sont à définir. Nous étudions donc comment étendre la notion de communauté aux flots de liens. Pour ce faire, nous nous appuyons sur des données réel où une structure communautaire est connue. Puis, nous développons une méthode permettant de trouver automatiquement des sous-flots qui sont jugés pertinents. Ces sous-flots, c’est-à-dire des sous-ensembles de liens, sont trouvés grâce à une méthode de détection de communautés appliquée sur une projection du flot sur un graphe statique. Un sous-flot est jugé pertinent s’il est plus dense que les sous-flots qui lui sont proches temporellement et topologiquement. Ainsi nous approfondissons les notions de voisinage et référence dans les flots de liens. Nous appliquons cette méthode sur plusieurs jeux de données d’interactions réelles et obtenons des groupes pertinents qui n’auraient pas pu être détectés par les méthodes existantes. Enfin, nous abordons la génération de flots de liens avec une structure communautaire donnée et à la manière d'évaluer une telle partition
Interactions are everywhere: in the contexts of face-to-face contacts, emails, phone calls, IP traffic, etc. In all of them, an interaction is characterized by two entities and a time interval: for instance, two individuals meet from 1pm to 3pm. We model them as link stream which is a set of quadruplets (b,e,u,v) where each quadruplet means that a link exists between u and v from time b to time e. In graphs, a community is a subset which is more densely connected than a reference. Within the link stream formalism, the notion of density and reference have to be redefined. Therefore, we study how to extend the notion of density for link streams. To this end, we use a real data set where a community structure is known. Then, we develop a method that finds automatically substream which are considered relevant. These substream, defined as subsets of links, are discovered by a classical community detection algorithm applied on the link stream the transformed into a static graph. A substream is considered relevant, if it is denser than the substreams which are close temporally and structurally. Thus, we deepen the notion of neighbourhood and reference in link streams. We apply our method on several real world interaction networks and we find relevant substream which would not have been found by existing methods. Finally, we discuss the generation of link streams having a given community structure and also a proper way to evaluate such community structure

APA, Harvard, Vancouver, ISO, and other styles

21

Gaumont, Noé. "Groupes et Communautés dans les flots de liens : des données aux algorithmes." Electronic Thesis or Diss., Paris 6, 2016. http://www.theses.fr/2016PA066271.

Full text

Abstract:

Les interactions sont partout : il peut s'agir de contacts entre individus, d'emails, d'appels téléphoniques, etc. Toutes ces interactions sont définies par deux entités interagissant sur un intervalle de temps: par exemple, deux individus se rencontrant entre 12h et 14h. Nous modélisons ces interactions par des flots de liens qui sont des ensembles de quadruplets (b, e, u, v), où chaque quadruplet représente un lien entre les noeuds u et v existant durant l'intervalle [b,e]. Dans un graphe, une communauté est un sous-ensemble plus densément connecté qu’une référence. Dans le formalisme de flot de liens, les notions même de densité et de référence sont à définir. Nous étudions donc comment étendre la notion de communauté aux flots de liens. Pour ce faire, nous nous appuyons sur des données réel où une structure communautaire est connue. Puis, nous développons une méthode permettant de trouver automatiquement des sous-flots qui sont jugés pertinents. Ces sous-flots, c’est-à-dire des sous-ensembles de liens, sont trouvés grâce à une méthode de détection de communautés appliquée sur une projection du flot sur un graphe statique. Un sous-flot est jugé pertinent s’il est plus dense que les sous-flots qui lui sont proches temporellement et topologiquement. Ainsi nous approfondissons les notions de voisinage et référence dans les flots de liens. Nous appliquons cette méthode sur plusieurs jeux de données d’interactions réelles et obtenons des groupes pertinents qui n’auraient pas pu être détectés par les méthodes existantes. Enfin, nous abordons la génération de flots de liens avec une structure communautaire donnée et à la manière d'évaluer une telle partition
Interactions are everywhere: in the contexts of face-to-face contacts, emails, phone calls, IP traffic, etc. In all of them, an interaction is characterized by two entities and a time interval: for instance, two individuals meet from 1pm to 3pm. We model them as link stream which is a set of quadruplets (b,e,u,v) where each quadruplet means that a link exists between u and v from time b to time e. In graphs, a community is a subset which is more densely connected than a reference. Within the link stream formalism, the notion of density and reference have to be redefined. Therefore, we study how to extend the notion of density for link streams. To this end, we use a real data set where a community structure is known. Then, we develop a method that finds automatically substream which are considered relevant. These substream, defined as subsets of links, are discovered by a classical community detection algorithm applied on the link stream the transformed into a static graph. A substream is considered relevant, if it is denser than the substreams which are close temporally and structurally. Thus, we deepen the notion of neighbourhood and reference in link streams. We apply our method on several real world interaction networks and we find relevant substream which would not have been found by existing methods. Finally, we discuss the generation of link streams having a given community structure and also a proper way to evaluate such community structure

APA, Harvard, Vancouver, ISO, and other styles

22

Burns, Keaton James. "Flexible spectral algorithms for simulating astrophysical and geophysical flows." Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/119103.

Full text

Abstract:

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Physics, 2018.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 143-147).
Large-scale numerical simulations are key to studying the complex physical systems that surround us. Simulations provide the ability to perform simplified numerical experiments to build our understanding of large-scale processes which cannot be controlled and examined in the laboratory. This dissertation develops a new open-source computational framework, Dedalus, for solving a diverse range of equations used to model such systems and applies the code to the study of stellar and oceanic fluid flows. In the first part, the spectral algorithms used in Dedalus are introduced and the design and development of the code are described. In particular, the code's symbolic equation specification, arbitrary-dimensional parallelization, and sparse spectral discretization systems are detailed. This project provides the scientific community with an easy-to-use tool that can efficiently and accurately simulate many processes arising in geophysical and astrophysical fluid dynamics. In the second part, Dedalus is used to study the turbulent boundary layers that form at the interface between marine-terminating glaciers and the ocean. A simplified model considering the heat transfer from a heated or cooled wall in a stratified fluid is investigated. We find new scaling laws for the turbulent heat transfer from the wall as a function of the imposed thermal forcing, with potential implications for the sensitivity of glacier melting to warming ocean temperatures. In the third part, Dedalus is used to study the stability of the tidal deformations experienced by binary neutron stars as they inspiral. We develop a numerical workflow for determining the weakly nonlinear stability of a tidally forced plane-parallel atmosphere and verify the results using fully nonlinear simulations. This framework may help determine whether tidal instabilities can be observed in gravitational wave signatures of binary neutron stars, which could provide observational constraints on the equation of state of matter above nuclear densities.
by Keaton James Burns.
Ph. D.

APA, Harvard, Vancouver, ISO, and other styles

23

CAVENDISH, SERGIO ALVES. "ELASTIC TIME ALGORITHM FOR VIDEO IN MPEG-2 FLOWS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2005. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=8793@1.

Full text

Abstract:

FUNDO SETORIAL PARA DESENV. TECNOLÓGICO DAS TELECOMUNICAÇÕES
Em apresentações hipermídia, umas das principais tarefas coordenadas pelo orquestrador da apresentação é a sincronização entre os diversos objetos componentes, que pode ser obtida através do ajuste elástico do tempo de exibição dos objetos. Esta técnica pode ser aplicada em tempo de compilação, de forma a manter os relacionamentos de sincronização especificados pelo autor, ou em tempo de apresentação, para prevenir qualquer descasamento temporal causado pelos ambientes de transmissão e de execução. Este trabalho descreve um conjunto de mecanismos para executar o ajuste elástico em fluxos MPEG-2 de Vídeo e de Sistemas, propondo algoritmos para a realização da compressão e expansão do tempo de exibição, do controle da ocupação do buffer do decodificador, da sincronização intermídia e da reconstrução do relógio de referência. Visando seu emprego em tempo de execução, todo o processo de ajuste é realizado diretamente no fluxo MPEG, sem qualquer transcodificação.
In hypermedia presentations, one of the main tasks provided by the orchestrator is the synchronization of all presentation objects, which may be achieved by elastic time adjustment of period of exhibition of the objects, or simply timescale adaptation. This technique can be applied at compilation time, in order to keep track of synchronism relationships specified by authors, or at presentation time, to prevent any temporal mismatch caused by transmission or execution environments. This work presents a set of mechanisms to carry out timescale adaptation in MPEG-2 Systems and Video streams, proposing algorithms to perform compression and expansion of exhibition period, also called playback dilation, rate control, inter-media synchronization and clock reconstruction. In order to be performed at execution time, timescale operations are realized directly in compressed MPEG-2 streams, requiring no transcodification.

APA, Harvard, Vancouver, ISO, and other styles

24

Mansouri, Abdelkhalek. "Generic heuristics on GPU to superpixel segmentation and application to optical flow estimation." Thesis, Bourgogne Franche-Comté, 2020. http://www.theses.fr/2020UBFCA012.

Full text

Abstract:

Déterminer des clusters dans des nuages de points et apparier des graphes sont des tâches primordiales en informatique, analyse de donnée, traitement d’image, généralement modélisées par des problèmes d’optimisation de classe NP-difficile. Avec l’avènement des multiprocesseurs à bas coût, l’accélération des procédures heuristiques pour ces tâches devient possible et nécessaire. Nous proposons des implantations parallèles sur système GPU (graphics processing unit) pour des algorithmes génériques appliqués ici à la segmentation d’image en superpixels et au problème du flot optique. Le but est de fournir des algorithmes génériques basés sur des structures de données décentralisées et aisément adaptables à différents problèmes d’optimisation sur des graphes et plateformes parallèles.Les algorithmes parallèles proposés sur GPU incluent le classique k-means et le calcul de forêt couvrante minimum pour la segmentation en superpixels. Ils incluent également un algorithme de recherche locale parallèle et un algorithme mémétique à base de population de solutions appliqués à l’estimation du flot optique via des appariements de superpixels. Tandis que les opérations sur les données exploitent le GPU, l’algorithme mémétique opère en tant que coalition de processus exécutés en parallèle sur le CPU multi-cœur et requérant des ressources GPU. Les images sont des nuages de points de l’espace euclidien 3D (domaine espace-intensité), et aussi des graphes auxquels sont associés des grilles de processeurs. Les kernels GPU exécutent des transformations en parallèle sous contrôle du CPU qui a un rôle réduit de détection des conditions d’arrêt et de séquencement des transformations.La contribution présentée est composée de deux grandes parties. Dans une première partie, nous présentons des outils pour la segmentation en superpixels. Une implémentation parallèle de l’algorithme des k-means est présentée et appliquée aux données 3D. Elle est basée sur une subdivision cellulaire de l’espace 3D qui permet des recherches de plus proche voisin en parallèle en temps optimal constant pour des distributions bornées. Nous présentons également une application de l’algorithme parallèle de calcul de forêt couvrante de Boruvka à la segmentation superpixel de type ligne de partage-des-eaux (watershed). Dans une deuxième partie, en se basant sur les superpixels générés, des procédures parallèles de mise en correspondance sont dérivées pour l’estimation du flot optique avec prise en compte des discontinuités. Ces méthodes incluent des heuristiques de construction et d’amélioration, telles que le winner-take-all et la recherche locale parallèle, et leur intégration dans une métaheuristique à base de population. Diverses combinaisons d’exécution sont présentées et évaluées en comparaison avec des algorithmes de l’état de l’art performants
Finding clusters in point clouds and matching graphs to graphs are recurrent tasks in computer science domain, data analysis, image processing, that are most often modeled as NP-hard optimization problems. With the development and accessibility of cheap multiprocessors, acceleration of the heuristic procedures for these tasks becomes possible and necessary. We propose parallel implantation on GPU (graphics processing unit) system for some generic algorithms applied here to image superpixel segmentation and image optical flow problem. The aim is to provide generic algorithms based on standard decentralized data structures to be easy to improve and customized on many optimization problems and parallel platforms.The proposed parallel algorithm implementations include classical k-means algorithm and application of minimum spanning forest computation for super-pixel segmentation. They include also a parallel local search procedure, and a population-based memetic algorithm applied to optical flow estimation based on superpixel matching. While data operations fully exploit GPU, the memetic algorithm operates like a coalition of processes executed in parallel on the multi-core CPU and requesting GPU resources. Images are point clouds in 3D Euclidean space (space-gray value domain), and are also graphs to which are assigned processor grids. GPU kernels execute parallel transformations under CPU control whose limited role only consists in stopping criteria evaluation or sequencing transformations.The presented contribution contains two main parts. Firstly, we present tools for superpixel segmentation. A parallel implementation of the k-means algorithm is presented with application to 3D data. It is based on a cellular grid subdivision of 3D space that allows closest point findings in constant optimal time for bounded distributions. We present an application of the parallel Boruvka minimum spanning tree algorithm to compute watershed minimum spanning forest. Secondly, based on the generated superpixels and segmentation, we derive parallel optimization procedures for optical flow estimation with edge aware filtering. The method includes construction and improvement heuristics, as winner-take-all and parallel local search, and their embedding into a population-based metaheuristic framework. The algorithms are presented and evaluated in comparison to state-of-the-art algorithms

APA, Harvard, Vancouver, ISO, and other styles

25

Sheng, Yi Qian. "Modifications to the SIMPLE method for buoyancy-driven flows /." *McMaster only, 1999.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

26

Delaunay, Pascal. "Attaques physiques sur des algorithmes de chiffrement par flot." Versailles-St Quentin en Yvelines, 2011. http://www.theses.fr/2011VERS0006.

Full text

Abstract:

Depuis 1999 et l'article de Paul Kocher, de nombreuses attaques physiques ont été publiées, principalement contre des algorithmes à clé publique et des algorithmes de chiffrement par bloc. Paradoxalement, nous retrouvons peu d'attaques physiques contre les algorithmes de chiffrement par flot, bien qu'ils soient utilisés dans de nombreuses applications. Après un rappel sur les attaques physiques, les registres à décalage à rebouclage linéaire et non-linéaire et les attaques par corrélation, nous proposons trois attaques par corrélation rapides contre des registres à décalage à rebouclage linéaire utilisant des informations issues d'attaques physiques. Nous présentons ensuite deux vulnérabilités dans les registres à décalage à rebouclage non-linéaire qui permettent de retrouver l'état interne du registre. Dans la dernière partie, nous utilisons les deux vulnérabilités précédentes pour proposer deux attaques physiques contre l'algorithme de chiffrement par flot VEST
Since 1999 and Paul Kocher's initial publication, several side-channel attacks have been published. Most of these attacks target public-key cryptosystems and bloc ciphers but only a few of them target stream ciphers, despite being widely used on daily applications. After some remids on side-channel attacks, linear and non-linear feedback shift registers and fast correlation attacks, we propose at first three fast correlation attacks targetting linear feedback shift registers and using side-channel information to improve their accuracy. Next, we present two flaws in non-linear feedback shift registers which allow full recovery of the internal state using well-chosen side-channel attacks. We finally use these vulnerabilities to mount two side-channel attacks against VEST, an eSTREAM candidate, to recover partial information from the internal state

APA, Harvard, Vancouver, ISO, and other styles

27

Croft, Thomas Nicholas. "Unstructured mesh : finite volume algorithms for swirling, turbulent, reacting flows." Thesis, University of Greenwich, 1998. http://gala.gre.ac.uk/6371/.

Full text

Abstract:

The work presented in this thesis develops techniques, employing the Finite Volume discretisation method, which allow the numerical simulation of three dimensional heat transfer and fluid flow problems using unstructured meshes. The method solves and stores all variables at the element centres which lowers storage requirements and generally shortens run times compared with the Control Volume-Finite Element approach. Correction terms are formulated which address two of the main forms of errors caused by mesh skewness. To allow a generic handling of any unstructured mesh the Cartesian components of velocity are solved under all circumstances. This leads to the requirement to adjust the discretisation of the momentum equations when there is significant flow curvature. The changes are presented in this study both when the position of the flow axis is known prior to the simulation and when its position is known only as a result of the simulation, this being the case when there is more than one source of swirling flow. These original features contribute to a Computational Fluid Dynamics code which is capable of solving swirling, turbulent fluid flow and reactive, radiative heat transfer on highly complex geometries. Specifically the techniques are applied to the simulation of processes occurring in the direct smelting of iron. The use of the Finite Volume method makes it relatively easy to employ many techniques and physical models developed for structured codes. The evaluation of the face convective fluxes is effected through the Rhie - Chow interpolation method. The SIMPLE algorithm is used in the pressure - velocity coupling. In the simulation of swirling flows it is shown that both the standard and ReNormalisation Group k-e models fail to accurately predict turbulent effects. An anisotropic hybrid (k-e and mixing length) model is developed which produces excellent numerical results for the flows of interest. The Simple Chemical Reaction Scheme is used to evaluate the transport of the various chemical species. Radiation effects are simulated through the use of the radiosity model. A series of simulation results are presented which show the capabilities of the methods in test cases ranging from simple heat transfer problems through to the simulation of two swirling jets in a three dimensional unstructured mesh.

APA, Harvard, Vancouver, ISO, and other styles

28

Darapuram, Rajasekhar Venkata. "AN INVESTIGATION OF FLUX-SPLITTING ALGORITHMS FOR CHEMICALLY REACTING FLOWS." MSSTATE, 2001. http://sun.library.msstate.edu/ETD-db/theses/available/etd-04102001-104000/.

Full text

Abstract:

This paper presents an investigation of seven different flux splitting algorithms for the discretization of inviscid fluxes, which are the primary source for the non-linear behavior (eg. shocks, contact discontinuities). The aim of the present work is to enhance the accuracy and robustness of CHEM, a three-dimensional flow solver, which is capable of simulating a wide range of flow conditions, including chemical non-equilibrium. Five different test cases cases are considered and thoroughly analyzed. The overall goal is to find a numerical scheme that can meet some stringent specifications of efficiency, accuracy and robustness on the widest possible spectrum of flow conditions.

APA, Harvard, Vancouver, ISO, and other styles

29

Liu, Zhenming. "Probabilistic Algorithms for Information and Technology Flows in the Networks." Thesis, Harvard University, 2012. http://dissertations.umi.com/gsas.harvard:10553.

Full text

Abstract:

This thesis studies several probabilistic algorithms for information and technology ﬂow in the networks. Information ﬂow refers to the circulation of information in social or communication networks for the purpose of disseminating or aggregating knowledge. Technology ﬂow refers to the process in the network in which nodes incrementally adopt a certain type of technological product such as networking protocols. In this thesis, we study the following problems. First, we consider the scenario where information ﬂow acts as media to disseminate messages. The information ﬂow here is considered as a mechanism of replicating a piece of information from one node to another in a network with a goal to “broadcast” the knowledge to everyone. Our studies focus on a broadcasting algorithm called the ﬂooding algorithm. We give a tight characterization on the completion time of the ﬂooding algorithm when we make natural stochastic assumptions on the evolution of the network. Second, we consider the problem that information ﬂow acts as a device to aggregate statistics. We interpret information ﬂow here as artifacts produced by algorithmic procedures that serve as statistical estimators for the networks. The goal is to maintain accurate estimators with minimal information ﬂow overhead. We study these two problems: ﬁrst, we consider the continual count tracking problem in a distributed environment where the input is an aggregate stream originating from \(k\) distinct sites and the updates are allowed to be non-monotonic. We develop an optimal algorithm in communication cost that can continually track the count for a family of stochastic streams. Second, we study the eﬀectiveness of using random walks to estimate the statistical properties of networks. Speciﬁcally, we give the ﬁrst deviation bounds for random walks over ﬁnite state Markov chains based on mixing time properties of the chain. Finally, we study the problem where technology ﬂow acts as a key to unlock innovative technology diﬀusion. Here, the technology ﬂow shall be interpreted as a way to specify the circumstance, in which a node in the network will decide to adopt a new technology. Our studies focus on ﬁnding the most cost eﬀective way to deploy networking protocols such as SecureBGP or IPv6 in the Internet. Our result is a near optimal strategy that leverages the patterns of technology ﬂows to facilitate the new technology deployments.
Engineering and Applied Sciences

APA, Harvard, Vancouver, ISO, and other styles

30

Baudin, Alexis. "Cliques statiques et temporelles : algorithmes d'énumération et de détection de communautés." Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS609.

Full text

Abstract:

Les graphes sont des objets mathématiques qui permettent de modéliser des interactions ou connexions entre entités de types variés. Un graphe peut représenter par exemple un réseau social qui connecte les utilisateurs entre eux, un réseau de transport comme le métro où les stations sont connectées entre elles, ou encore un cerveau avec les milliards de neurones en interaction qu'il contient. Depuis quelques années, la forte dynamicité de ces structures a été mise en évidence, ainsi que l'importance de prendre en compte l'évolution temporelle de ces réseaux pour en comprendre le fonctionnement. Alors que de nombreux concepts et algorithmes ont été développés sur les graphes pour décrire des structures de réseaux statiques, il reste encore beaucoup à faire pour formaliser et développer des algorithmes pertinents pour décrire la dynamique des réseaux réels. Cette thèse vise à mieux comprendre comment sont structurés les graphes massifs qui sont issus du monde réel et à développer des outils pour étendre notre compréhension à des structures évoluant dans le temps. Il a été montré que ces graphes ont des propriétés particulières, qui les distinguent des graphes théoriques ou tirés aléatoirement. Exploiter ces propriétés permet alors de concevoir des algorithmes pour résoudre certains problèmes difficiles beaucoup plus rapidement sur ces instances que dans le cas général. La thèse se focalise sur les cliques, qui sont des groupes d'éléments tous connectés entre eux. Nous étudions l'énumération des cliques dans les graphes statiques et temporels et la détection de communautés qu'elles permettent de mettre en œuvre. Les communautés d'un graphe sont des ensembles de sommets tels qu'au sein d'une communauté, les sommets interagissent fortement entre eux, et peu avec le reste du graphe. Leur étude aide à comprendre les propriétés structurelles et fonctionnelles des réseaux. Nous évaluons nos algorithmes sur des graphes massifs issus du monde réel, ouvrant ainsi de nouvelles perspectives pour comprendre les interactions au sein de ces réseaux. Nous travaillons d'abord sur des graphes, sans tenir compte de la composante temporelle des interactions. Nous commençons par utiliser la méthode de détection de communautés par percolation de cliques, en mettant en évidence ses limites en mémoire, qui empêchent de l'appliquer à des graphes trop massifs. En introduisant un algorithme de résolution approchée du problème, nous dépassons cette limite. Puis, nous améliorons l'énumération des cliques maximales dans le cas des graphes particuliers dits bipartis. Ils correspondent à des interactions entre des groupes de sommets de type différent, par exemple des liens entre des personnes et du contenu consulté, la participation à des événements, etc. Ensuite, nous considérons des interactions qui ont lieu au cours du temps, grâce au formalisme des flots de liens. Nous cherchons à étendre les algorithmes présentés en première partie, pour exploiter leurs avantages dans l'étude des interactions temporelles. Nous fournissons un nouvel algorithme d'énumération des cliques maximales dans les flots de liens, beaucoup plus efficace que l'état de l'art sur des jeux de données massifs. Enfin, nous nous intéressons aux communautés dans les flots de liens par percolation de cliques, en développant une extension de la méthode utilisée sur les graphes. Les résultats montrent une amélioration significative par rapport à l'état de l'art, et nous analysons les communautés obtenues pour fournir des informations pertinentes sur l'organisation des interactions temporelles dans les flots de liens. Mon travail de thèse a permis d’apporter de nouvelles réflexions sur l’étude des réseaux massifs issus du monde réel. Cela montre l'importance d'explorer le potentiel des graphes dans un contexte réel, et pourrait contribuer à l'émergence de solutions novatrices pour les défis complexes de notre société moderne
Graphs are mathematical objects used to model interactions or connections between entities of various types. A graph can represent, for example, a social network that connects users to each other, a transport network like the metro where stations are connected to each other, or a brain with the billions of interacting neurons it contains. In recent years, the dynamic nature of these structures has been highlighted, as well as the importance of taking into account the temporal evolution of these networks to understand their functioning. While many concepts and algorithms have been developed on graphs to describe static network structures, much remains to be done to formalize and develop relevant algorithms to describe the dynamics of real networks. This thesis aims to better understand how massive graphs are structured in the real world, and to develop tools to extend our understanding to structures that evolve over time. It has been shown that these graphs have particular properties, which distinguish them from theoretical or randomly drawn graphs. Exploiting these properties then enables the design of algorithms to solve certain difficult problems much more quickly on these instances than in the general case. My PhD thesis focuses on cliques, which are groups of elements that are all connected to each other. We study the enumeration of cliques in static and temporal graphs and the detection of communities they enable. The communities of a graph are sets of vertices such that, within a community, the vertices interact strongly with each other, and little with the rest of the graph. Their study helps to understand the structural and functional properties of networks. We are evaluating our algorithms on massive real-world graphs, opening up new perspectives for understanding interactions within these networks. We first work on graphs, without taking into account the temporal component of interactions. We begin by using the clique percolation method of community detection, highlighting its limitations in memory, which prevent it from being applied to graphs that are too massive. By introducing an approximate problem-solving algorithm, we overcome this limitation. Next, we improve the enumeration of maximal cliques in the case of bipartite graphs. These correspond to interactions between groups of vertices of different types, e.g. links between people and viewed content, participation in events, etc. Next, we consider interactions that take place over time, using the link stream formalism. We seek to extend the algorithms presented in the first part, to exploit their advantages in the study of temporal interactions. We provide a new algorithm for enumerating maximal cliques in link streams, which is much more efficient than the state-of-the-art on massive datasets. Finally, we focus on communities in link streams by clique percolation, developing an extension of the method used on graphs. The results show a significant improvement over the state of the art, and we analyze the communities obtained to provide relevant information on the organization of temporal interactions in link streams. My PhD work has provided new insights into the study of massive real-world networks. This shows the importance of exploring the potential of graphs in a real-world context, and could contribute to the emergence of innovative solutions for the complex challenges of our modern society

APA, Harvard, Vancouver, ISO, and other styles

31

Navarro, David. "Architecture et Conception de Rétines Silicium CMOS : Application à la mesure du flot optique." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2003. http://tel.archives-ouvertes.fr/tel-00164035.

Full text

Abstract:

Le développement des technologies sub-microniques a permis un regain d'intérêt pour les capteurs d'images CMOS, qui inondent aujourd'hui le marché des capteurs. Les approches conventionnelles pour la conception de machines de vision sont en général basées sur des architectures connectées à une caméra. L'approche proposée dans ce travail consiste à associer, dans un même circuit – une rétine CMOS -, les photocapteurs et des fonctions de pré-traitement de l'image, permettant ainsi de répartir et d'optimiser le traitement. Ces rétines ont des performances en vitesse, en intégration et en consommation meilleures que les solutions classiques (capteurs puis traitements logiciels et/ou matériels). Cette thèse porte plus précisément sur l'intégration d'un algorithme d'estimation du mouvement en transposant le calcul numérique fortement itératif en une structure de calcul électronique. Après avoir réalisé un circuit permettant d'acquérir des connaissances dans le domaine des capteurs d'images CMOS, nous avons conçu un circuit de vision estimant le mouvement. Cette estimation de mouvement est basée sur une méthode robuste de mise en correspondance de blocs de pixels, comprenant une phase de pré-codage des pixels suivi
d'une recherche de ce codage dans une fenêtre de destination potentielle. Cette approche est novatrice car elle propose une rétine CMOS pouvant traiter (électroniquement) des scènes fortement texturées, et à luminosité changeante, en s'appuyant sur une méthode jusqu'alors réservée aux approches numériques (FPGA, DSP) ou logicielles.

APA, Harvard, Vancouver, ISO, and other styles

32

Mejdoub, Mahmoud. "Indexation sémantique des images basée sur les réseaux réguliers de points." Nice, 2010. http://www.theses.fr/2010NICE4046.

Full text

Abstract:

Face au rythme de croissance des volumes des contenus numériques, le développement des méthodes pour l’indexation et la recherche de ces contenus devient une nécessité. Dans cette thèse, nous nous intéressons aux approches de quantification vectorielle produisant des représentations et des structurations automatiques de contenu visuel des images. Pour commencer, nous nous penchons sur le modèle de la description visuelle du contenu afin de fournir une représentation efficace des images. Pour cela, nous utilisons une représentation par sacs de mots visuels basée sur un algorithme de quantification vectorielle flou. Cette représentation permet de décrire localement les images et d’obtenir une représentation plus fine des descripteurs de bas niveau. Les zones locales sélectionnées dans l’image sont aussi bien les zones de variation représentées par les points d’intérêts que les zones homogènes. Le grand nombre de descripteurs locaux qu’on peut obtenir, requiert des outils efficaces pour qu’ils soient exploitables convenablement. Pour cela, nous proposons une nouvelle structure d’indexation : « l’arbre de lattices emboîtés », basée sur la quantification vectorielle par réseau régulier de points. Celui-ci est utilisé aussi bien pour l’accélération de la recherche des k plus proches voisins que pour l’amélioration de la qualité de la classification sémantique des images
With the growth of digital content volumes, the development of methods for index and searching this content becomes a necessity. In this thesis, we are focused on lattice vector quantization approach since its ability to provide an effective automatic structuring of visual feature vectors extracted from the images. The features extraction step is based on local descriptors obtained by the bag of words technique. Local areas selected in the image correspond to both salient points and homogeneous patches. The large number of local descriptors that can be obtained requires effective tools to organize them. For this, we propose a new indexing structure: the “embedded lattices tree” based on lattice vector quantization. The proposed approach is used both to accelerate the k nearest neighbours search and to improve the quality of semantic image classification

APA, Harvard, Vancouver, ISO, and other styles

33

Wu, Yu-Chi. "Direct nonlinear interior point methods for optimal power flows." Diss., Georgia Institute of Technology, 1993. http://hdl.handle.net/1853/15030.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Cinnella, Pasquale. "Flux-split algorithms for flows with non-equilibrium chemistry and thermodynamics." Diss., Virginia Polytechnic Institute and State University, 1989. http://hdl.handle.net/10919/54506.

Full text

Abstract:

New flux-split algorithms are developed for high velocity, high-temperature flow situations, when finite-rate chemistry and non-equilibrium thermodynamics greatly affect the physics of the problem. Two flux-vector-split algorithms, of the Steger-Warming and of the Van Leer type, and one flux-difference-split algorithm of the Roe type are established and utilized for the accurate numerical simulation of flows with dissociation, ionization, and combustion phenomena. Several thermodynamic models are used, including a simplified vibrational non-equilibrium model and an equilibrium model based upon refined statistical mechanics properties. The framework provided is flexible enough to accommodate virtually any chemical model and a wide range of non-equilibrium, multi-temperature thermodynamic models. A theoretical study of the main features of flows with free electrons, for conditions that require the use of two translational temperatures in the thermal model, is developed. Interesting and unexpected results are obtained, because acoustic wave speeds of the symmetric form u±α no longer appear. A simple but powerful asymptotic analysis is developed which allows the establishment of the fundamental gas-dynamic properties of flows with multiple translational temperatures. The new algorithms developed demonstrate their accuracy and robustness for challenging flow problems. The influence of several assumptions on the chemical and thermal behavior of the flows is investigated, and a comparison with results obtained using different numerical approaches, in particular spectral methods, is provided, and proves to be favorable to the present techniques. Other calculations in one and two space dimensions indicate large sensitivities with respect to chemical and thermodynamic modeling. The algorithms developed are of sufficient generality to begin to examine these effects in detail. Preliminary numerical simulations are performed using elementary modeling of transport phenomena.
Ph. D.

APA, Harvard, Vancouver, ISO, and other styles

35

Moradi, Shahab. "A novel scheduling algorithm for video flows in high-rate WPANs." Thesis, University of British Columbia, 2007. http://hdl.handle.net/2429/32111.

Full text

Abstract:

The emerging high-rate wireless personal area network (WPAN) technology is capable of supporting high-speed and high-quality real-time multimedia applications. In particular, video streams are deemed to be a widespread traffic type, and require quality of service (QoS) support. However, in the current IEEE 802.15.3 standard for MAC (media access control) of high-rate WPANs, the implementation details of some key issues such as scheduling and QoS provisioning have not been addressed. Moreover, the hierarchical structure of video streams calls for special measures at the MAC layer in order to improve the QoS. In the first part of this thesis, we propose a frame-decodability aware (FDA) technique to make the scheduling algorithms aware of the hierarchical structure and decoding dependencies in video streams. Simulation results show that the FDA technique can significantly improve the performance of F-SRPT [1] and EDD+SRPT [2] schedulers by up to 61% and 60%, respectively. We also compare two common performance metrics and investigate which one is a more accurate indicator of the QoS given to video streams. In the second part of this thesis, we first propose a mathematical model for the optimal scheduling scheme for video flows in high-rate WPANs. Using this model, we then propose a scheduler that incorporates reinforcement learning (RL). Simulation results show that our proposed scheduler is nearly optimal and performs 42%, 49%, and 53% better than EDD+SRPT [2], PAP [3], and F-SRPT [1] schedulers, respectively.
Applied Science, Faculty of
Electrical and Computer Engineering, Department of
Graduate

APA, Harvard, Vancouver, ISO, and other styles

36

Chisholm, Todd. "Multigrid acceleration of an approximately-factored algorithm for steady aerodynamic flows." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp01/MQ28816.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Loum, Georges L. "Segmentation pyramidale de textures par décomposition en ondelettes." Paris 12, 1996. http://www.theses.fr/1996PA120021.

Full text

Abstract:

Cette these presente une methode de segmentation pyramidale d'images d'aspect texture par decomposition en ondelettes. D'une facon generale, tout processus de segmentation de textures comporte une etape de caracterisation qui precede l'etape de segmentation proprement dite. Notre methode de caracterisation de textures est fondee sur l'interpretation des coefficients de details de la decomposition en ondelettes, comme decrivant les variations locales des niveaux de gris de la texture autour de leur valeur moyenne. Cette interpretation conduit a la definition d'un nouvel attribut, le facteur de forme, qui se calcule sur un nouveau type de voisinage qui possede une structure pyramidale. Pour eprouver la pertinence de ce nouvel attribut, deux algorithmes de classification supervisee de textures sont proposes. Le premier exploite la representation multiresolution de l'analyse par ondelettes pour realiser une caracterisation efficace des textures a plusieurs niveaux de resolution. Le second determine pour chaque texture, un niveau maximal de la decomposition en ondelettes, en definissant un seuil sur les variances des images d'approximation. Ce niveau est utilise pour realiser une preclassification, avant que le processus de classification ne soit conduit a son terme dans chaque classe constituee. Les resultats satisfaisants obtenus par ces deux algorithmes ont valide la methode de caracterisation proposee et demontre la pertinence de l'attribut facteur de forme. La methode de segmentation presentee, tire profit de la forme pyramidale du voisinage sur lequel le facteur de forme est calcule. Cette forme constitue un veritable atout pour un processus de segmentation qui se fonde sur une representation multiresolution des donnees. Elle permet de reduire sensiblement le nombre de pixels de l'image d'attributs representant de zones inter-regions et minimise de ce fait, l'ambiguite sur la localisation precise des frontieres. De plus, les dimensions variables du voisinage pyramidal en fonction du niveau de resolution, suggerent l'elaboration d'un processus de segmentation evoluant suivant une strategie du plus grossier au plus fin: les meilleurs prototypes de chaque classe de texture sont determines a l'aide d'un algorithme qui met en uvre un classificateur flou. Ces prototypes permettent de realiser une segmentation grossiere au niveau de resolution le plus eleve. Cette segmentation primaire est progressivement affinee lors de la descente de la pyramide en dirigeant le processus de segmentation vers les zones de singularites (zones frontalieres ou bruitees). La methode proposee fournit les meilleurs resultats et realise une segmentation sans recouvrement des regions, lorsque la decomposition de l'image est effectuee avec l'ondelette de haar

APA, Harvard, Vancouver, ISO, and other styles

38

Pelanti, Marica. "Wave propagation algorithms for multicomponent compressible flows with applications to volcanic jets /." Thesis, Connect to this title online; UW restricted, 2005. http://hdl.handle.net/1773/6784.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Webb, Marcus David. "Isospectral algorithms, Toeplitz matrices and orthogonal polynomials." Thesis, University of Cambridge, 2017. https://www.repository.cam.ac.uk/handle/1810/264149.

Full text

Abstract:

An isospectral algorithm is one which manipulates a matrix without changing its spectrum. In this thesis we study three interrelated examples of isospectral algorithms, all pertaining to Toeplitz matrices in some fashion, and one directly involving orthogonal polynomials. The first set of algorithms we study come from discretising a continuous isospectral flow designed to converge to a symmetric Toeplitz matrix with prescribed eigenvalues. We analyse constrained, isospectral gradient flow approaches and an isospectral flow studied by Chu in 1993. The second set of algorithms compute the spectral measure of a Jacobi operator, which is the weight function for the associated orthogonal polynomials and can include a singular part. The connection coefficients matrix, which converts between different bases of orthogonal polynomials, is shown to be a useful new tool in the spectral theory of Jacobi operators. When the Jacobi operator is a finite rank perturbation of Toeplitz, here called pert-Toeplitz, the connection coefficients matrix produces an explicit, computable formula for the spectral measure. Generalisation to trace class perturbations is also considered. The third algorithm is the infinite dimensional QL algorithm. In contrast to the finite dimensional case in which the QL and QR algorithms are equivalent, we find that the QL factorisations do not always exist, but that it is possible, at least in the case of pert-Toeplitz Jacobi operators, to implement shifts to generate rapid convergence of the top left entry to an eigenvalue. A fascinating novelty here is that the infinite dimensional matrices are computed in their entirety and stored in tailor made data structures. Lastly, the connection coefficients matrix and the orthogonal transformations computed in the QL iterations can be combined to transform these pert-Toeplitz Jacobi operators isospectrally to a canonical form. This allows us to implement a functional calculus for pert-Toeplitz Jacobi operators.

APA, Harvard, Vancouver, ISO, and other styles

40

Moscu, Mircea. "Inférence distribuée de topologie de graphe à partir de flots de données." Thesis, Université Côte d'Azur, 2020. http://www.theses.fr/2020COAZ4081.

Full text

Abstract:

La deuxième décennie du millénaire actuel peut être résumée en une courte phrase : l'essor des données. Le nombre de sources de données s'est multiplié : du streaming audio-vidéo aux réseaux sociaux et à l'Internet des Objets, en passant par les montres intelligentes, les équipements industriels et les véhicules personnels, pour n'en citer que quelques-unes. Le plus souvent, ces sources forment des réseaux afin d'échanger des informations. En conséquence directe, le domaine du Traitement de Signal sur Graphe a prospéré et a évolué. Son but : traiter et donner un sens à tout le déluge de données environnant. Dans ce contexte, le but principal de cette thèse est de développer des méthodes et des algorithmes capables d'utiliser des flots de données, de manière distribuée, afin d'inférer les réseaux sous-jacents qui relient ces flots. Ensuite, ces topologies de réseau estimées peuvent être utilisées avec des outils développés pour le Traitement de Signal sur Graphe afin de traiter et d'analyser les données supportées par des graphes. Après une brève introduction suivie d'exemples motivants, nous développons et proposons d'abord un algorithme en ligne, distribué et adaptatif pour l'inférence de topologies de graphes pour les flots de données qui sont linéairement dépendants. Une analyse de la méthode s'ensuit, afin d'établir des relations entre les performances et les paramètres nécessaires à l'algorithme. Nous menons ensuite une série d'expériences afin de valider l'analyse et de comparer ses performances avec celles d'une autre méthode proposée dans la littérature. La contribution suivante est un algorithme doté des mêmes capacités en ligne, distribuées et adaptatives, mais adapté à l'inférence de liens entre des données qui interagissent de manière non-linéaire. À ce titre, nous proposons un modèle additif simple mais efficace qui utilise l'usine du noyau reproduisant afin de modéliser lesdites non-linéarités. Les résultats de son analyse sont convaincants, tandis que les expériences menées sur des données biomédicales donnent des réseaux estimés qui présentent un comportement prédit par la littérature médicale. Enfin, une troisième proposition d'algorithme est faite, qui vise à améliorer le modèle non-linéaire en lui permettant d'échapper aux contraintes induites par l'additivité. Ainsi, le nouveau modèle proposé est aussi général que possible, et utilise une manière naturelle et intuitive d'imposer la parcimonie des liens, basée sur le concept de dérivés partiels. Nous analysons également l'algorithme proposé, afin d'établir les conditions de stabilité et les relations entre ses paramètres et ses performances. Une série d'expériences est menée, montrant comment le modèle général est capable de mieux saisir les liens non-linéaires entre les données, tandis que les réseaux estimés se comportent de manière cohérente avec les estimations précédentes
The second decade of the current millennium can be summarized in one short phrase: the advent of data. There has been a surge in the number of data sources: from audio-video streaming, social networks and the Internet of Things, to smartwatches, industrial equipment and personal vehicles, just to name a few. More often than not, these sources form networks in order to exchange information. As a direct consequence, the field of Graph Signal Processing has been thriving and evolving. Its aim: process and make sense of all the surrounding data deluge.In this context, the main goal of this thesis is developing methods and algorithms capable of using data streams, in a distributed fashion, in order to infer the underlying networks that link these streams. Then, these estimated network topologies can be used with tools developed for Graph Signal Processing in order to process and analyze data supported by graphs. After a brief introduction followed by motivating examples, we first develop and propose an online, distributed and adaptive algorithm for graph topology inference for data streams which are linearly dependent. An analysis of the method ensues, in order to establish relations between performance and the input parameters of the algorithm. We then run a set of experiments in order to validate the analysis, as well as compare its performance with that of another proposed method of the literature.The next contribution is in the shape of an algorithm endowed with the same online, distributed and adaptive capacities, but adapted to inferring links between data that interact non-linearly. As such, we propose a simple yet effective additive model which makes use of the reproducing kernel machinery in order to model said nonlinearities. The results if its analysis are convincing, while experiments ran on biomedical data yield estimated networks which exhibit behavior predicted by medical literature.Finally, a third algorithm proposition is made, which aims to improve the nonlinear model by allowing it to escape the constraints induced by additivity. As such, the newly proposed model is as general as possible, and makes use of a natural and intuitive manner of imposing link sparsity, based on the concept of partial derivatives. We analyze this proposed algorithm as well, in order to establish stability conditions and relations between its parameters and its performance. A set of experiments are ran, showcasing how the general model is able to better capture nonlinear links in the data, while the estimated networks behave coherently with previous estimates

APA, Harvard, Vancouver, ISO, and other styles

41

LASAGNA, DAVIDE. "Flow physics and control of trapped vortex cell flows." Doctoral thesis, Politecnico di Torino, 2013. http://hdl.handle.net/11583/2518621.

Full text

Abstract:

The main objective of this work is to investigate on the physics and on the control of the flow in a Trapped Vortex Cell, often referred to as TVC in the following. A TVC is a cavity with a particular geometry, which is optimised to trap a vortical structure. This configuration has recently gained interest has a device to control the flow past thick airfoils, but fundamental research is still required to make this technique effective. Specifically, a first goal of this work is to investigate on the fundamental physics of this flow, by studying the basic elements and the dominant phenomena. In fact, this flow field is the result of the complex interaction of several flows, such as the upstream boundary layer, the shear layer detaching from the cavity leading edge, the vortex core, and the boundary layer developing downstream. A further issue of interest addressed in this work is that related to the role of unsteadiness of the cell flow, and in particular of the shear layer, whose self-sustained oscillations are a common feature of open-cavity flows. The understanding of the driving physical mechanisms of the base flow is required to successfully proceed in developing a control strategy aiming at the control of the flow, because it is necessary to manipulate this flow in order to make the TVC an effective control device. Therefore, a second goal is to study and compare two different control techniques targeting the cavity flow. The first of the two is steady suction of the flow in the cell and has been already applied in past researches, but some additional insight into its effects on the base flow is required. The second proposed control technique is open-loop control with a synthetic jet actuator, a more efficient device whose unsteady action can couple to or drive the relevant mechanisms of the flow. Furthermore, open-loop control studies with a synthetic jet are propaedeutic for closed-loop control of the flow, briefly investigated in the last part of research.

APA, Harvard, Vancouver, ISO, and other styles

42

Sensen, Norbert. "Lower bounds and exact algorithms for the graph partitioning problem using multicommodity flows." [S.l. : s.n.], 2003. http://deposit.ddb.de/cgi-bin/dokserv?idn=971568243.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Kasten, Jens [Verfasser]. "Lagrangian feature extraction in two-dimensional unsteady flows : concepts and algorithms / Jens Kasten." Berlin : Freie Universität Berlin, 2012. http://d-nb.info/102749885X/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Krol, Jakub. "Applications of modal decomposition algorithms to dynamic estimation and reconstruction of fluid flows." Thesis, Imperial College London, 2017. http://hdl.handle.net/10044/1/60590.

Full text

Abstract:

In this thesis, modal decomposition algorithms are utilised to construct reduced-order models of the fluid flows with applications to estimator design and extraction of the dynamical information from the irregularly sampled data. A particular implementation of such algorithms, the Optimal Mode Decomposition (OMD), is used to construct the estimator frameworks for bluff body flows, more specifically past a circular cylinder and bullet-shaped object. Estimator design is motivated by feedback flow control applications in which online knowledge of the system is paramount. Reduced order models are constructed and combined with stochastic estimation techniques using Moving Horizon Estimation (MHE) algorithm to achieve accurate representations of primary oscillatory and transient features of the cylinder flow across all of its dynamically distinct regimes. The designed estimator is subsequently extended to turbulent flow past a three-dimensional axisymmetric bluff body by introducing rotation-dependent framework. This is able to approximate the main oscillatory features of the flow despite the dynamical complexity of the system. Furthermore, an extension to the OMD algorithm is introduced, referred to as the is-OMD algorithm, which allows modal decomposition techniques to be applied to vector-valued signal, such as an ensemble of PIV snapshots, sampled at random time instances. A mapping between underlying time-resolved snapshots and known measurements is defined and data is projected onto a low-order subspace. Subsequently, dynamical characteristics, such as frequencies and growth rates, are approximated by iteratively solving two optimisation sub-problems: consecutively updating a reduced-order dynamical model, then subsequently approximating the 'missing' data at intermediate snapshots between the known values. The methodology is demonstrated on three dynamical systems: a synthetic sinusoid, the cylinder wake at Re = 60 and turbulent flow past an axisymmetric bullet-shaped body. In all cases the algorithm is shown to correctly identify the characteristic frequencies and oscillatory structures present in the flow from downsampled data ensemble.

APA, Harvard, Vancouver, ISO, and other styles

45

Donnot, Benjamin. "Deep learning methods for predicting flows in power grids : novel architectures and algorithms." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS060/document.

Full text

Abstract:

Cette thèse porte sur les problèmes de sécurité sur le réseau électrique français exploité par RTE, le Gestionnaire de Réseau de Transport (GRT). Les progrès en matière d'énergie durable, d'efficacité du marché de l'électricité ou de nouveaux modes de consommation poussent les GRT à exploiter le réseau plus près de ses limites de sécurité. Pour ce faire, il est essentiel de rendre le réseau plus "intelligent". Pour s'attaquer à ce problème, ce travail explore les avantages des réseaux neuronaux artificiels. Nous proposons de nouveaux algorithmes et architectures d'apprentissage profond pour aider les opérateurs humains (dispatcheurs) à prendre des décisions que nous appelons " guided dropout ". Ceci permet de prévoir les flux électriques consécutifs à une modification volontaire ou accidentelle du réseau. Pour se faire, les données continues (productions et consommations) sont introduites de manière standard, via une couche d'entrée au réseau neuronal, tandis que les données discrètes (topologies du réseau électrique) sont encodées directement dans l'architecture réseau neuronal. L’architecture est modifiée dynamiquement en fonction de la topologie du réseau électrique en activant ou désactivant des unités cachées. Le principal avantage de cette technique réside dans sa capacité à prédire les flux même pour des topologies de réseau inédites. Le "guided dropout" atteint une précision élevée (jusqu'à 99% de précision pour les prévisions de débit) tout en allant 300 fois plus vite que des simulateurs de grille physiques basés sur les lois de Kirchoff, même pour des topologies jamais vues, sans connaissance détaillée de la structure de la grille. Nous avons également montré que le "guided dropout" peut être utilisé pour classer par ordre de gravité des évènements pouvant survenir. Dans cette application, nous avons démontré que notre algorithme permet d'obtenir le même risque que les politiques actuellement mises en œuvre tout en n'exigeant que 2 % du budget informatique. Le classement reste pertinent, même pour des cas de réseau jamais vus auparavant, et peut être utilisé pour avoir une estimation globale de la sécurité globale du réseau électrique
This thesis addresses problems of security in the French grid operated by RTE, the French ``Transmission System Operator'' (TSO). Progress in sustainable energy, electricity market efficiency, or novel consumption patterns push TSO's to operate the grid closer to its security limits. To this end, it is essential to make the grid ``smarter''. To tackle this issue, this work explores the benefits of artificial neural networks. We propose novel deep learning algorithms and architectures to assist the decisions of human operators (TSO dispatchers) that we called “guided dropout”. This allows the predictions on power flows following of a grid willful or accidental modification. This is tackled by separating the different inputs: continuous data (productions and consumptions) are introduced in a standard way, via a neural network input layer while discrete data (grid topologies) are encoded directly in the neural network architecture. This architecture is dynamically modified based on the power grid topology by switching on or off the activation of hidden units. The main advantage of this technique lies in its ability to predict the flows even for previously unseen grid topologies. The "guided dropout" achieves a high accuracy (up to 99% of precision for flow predictions) with a 300 times speedup compared to physical grid simulators based on Kirchoff's laws even for unseen contingencies, without detailed knowledge of the grid structure. We also showed that guided dropout can be used to rank contingencies that might occur in the order of severity. In this application, we demonstrated that our algorithm obtains the same risk as currently implemented policies while requiring only 2% of today's computational budget. The ranking remains relevant even handling grid cases never seen before, and can be used to have an overall estimation of the global security of the power grid

APA, Harvard, Vancouver, ISO, and other styles

46

Uygur, Ahmet Bilge. "A Non-iterative Pressure Based Algorithm For The Computation Of Reacting Radiating Flows." Phd thesis, METU, 2007. http://etd.lib.metu.edu.tr/upload/12608274/index.pdf.

Full text

Abstract:

A non-iterative pressure based algorithm which consists of splitting the solution of momentum energy and species equations into a sequence of predictor-corrector stages was developed for the simulation of transient reacting radiating flows. A semi-discrete approach called the Method of Lines (MOL) which enables implicit time-integration at all splitting stages was used for the solution of conservation equations. The solution of elliptic pressure equation for the determination of pressure field was performed by a multi-grid solver (MUDPACK package). Radiation calculations were carried out by coupling previously developed gray and non-gray radiation models with the algorithm. A first order (global) reaction mechanism was employed to account for the chemistry. The predictions of the algorithm for the following test cases: i) non-isothermal turbulent pipe flow and ii) laminar methane-air diffusion flame
were benchmarked against experimental data and numerical solutions available in the literature and the capability of the code to predict transient solutions was demonstrated on these test cases. Favorable agreements were obtained for both test cases. The effect of radiation and non-gray treatment of the radiative properties were investigated on the second test case. It was found that incorporation of radiation has significant effect on Temeprature and velocity fields but its effect is limited in species predictions. Executions with both radiation models revealed that the non-gray radiation model considered in the present study produces similar results with the gray model at a considerably higher computational cost. The algorithm developed was found to be an efficient and versatile tool for the timedependent simulation of different flow scenarios constitutes the initial steps towards the computation of transient turbulent combustion.

APA, Harvard, Vancouver, ISO, and other styles

47

Kannan, Hariharan. "TCP-Carson a loss-event based adaptive AIMD algorithm for long-lived flows." Link to electronic thesis, 2002. http://www.wpi.edu/Pubs/ETD/Available/etd-0513102-135155.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Brayman, Vladimir. "Hierarchical distributed algorithm for optimization of flows and prices in logistics distribution networks /." Thesis, Connect to this title online; UW restricted, 2003. http://hdl.handle.net/1773/5876.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Ehounou, Joseph. "Algorithmes de graphes pour la découverte de la topologie d'un réseau énergétique par la connaissance de ses flots." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLV056/document.

Full text

Abstract:

Dans les réseaux énergétiques, la connaissance des équipements, leurs emplacements et leursfonctions sont les prérequis à l’exploitation de l’infrastucture. En effet, tout opérateur disposed’une carte appelée schéma synoptique indiquant les connexions entre les équipements. À partirde cette carte, sont prises des décisions pour un fonctionnement optimal du réseau.Ce schéma synoptique peut être érronné parce que des opérations de maintenance sur le réseaun’auraient pas été retranscrites ou mal saisies. Et cela peut entrainer des coûts supplémentairesd’exploitation du réseau énergetique.Nous considérons le réseau électrique d’un Datacenter. Ce réseau est composé d’une topologiephysique modélisée par un DAG sans circuit et de mesures électriques sur ces arcs. La particularitéde ce réseau est que les mesures contiennent des erreurs et cette topologie est inconnue c’est-à-direles arcs sont connus mais les extrémités des arcs sont inconnues. Dans le cas où ces mesuressont correctes alors la corrélation des arcs induit la matrice d’adjacence du line-graphe du graphenon-orienté sous-jacent de notre DAG. Un line-graphe est un graphe dans lequel chaque sommet etson voisinage peuvent être partitionnés par une ou deux cliques et que chaque arête est couvertepar une clique. Cependant, avec la présence des erreurs de mesures, nous avons un graphe avecdes arêtes en plus ou en moins qui n’est pas nécessairement un line-graphe. Si ce graphe est unline-graphe alors il n’est pas le line-graphe de notre DAG. Notre problème est de découvrir cettetopologie en se basant sur ces mesures électriques.Nous débutons par une étude bibliographique des corrélations de mesures possibles afin dedéterminer celle qui est pertinente pour notre problème. Ensuite nous proposons deux algorithmespour résoudre ce problème. Le premier algorithme est l’algorithme de couverture et il déterminel’ensemble des cliques qui couvre chaque sommet de notre graphe. Le second algorithme estl’algorithme de correction. Il ajoute ou supprime des arêtes au voisinage d’un sommet non couvertde telle sorte que son voisinage soit partitionné en une ou deux cliques. Enfin, nous évaluons lesperformances de nos algorithmes en vérifiant le nombre d’arêtes corrigées et la capacité à retournerle graphe le plus proche du line-graphe de notre DAG
In energy network, the knowledge of equipments, their locations and their functions are theimportant information for the distributor service operator. In fact, each operator has a networkplan often named synoptic schema. That schema shows the interconnexion between equipments inthe network. From this schema, some management decisions have taken for ensuring an optimalperformance of a network.Sometimes, a synoptic schema has some mistakes because the maintenance operations, such aschanged the connexion between equipments or replaced equipments, have not been updated orhave been written with errors. And these mistakes increase exploitation cost in the energy network.We consider an electric network of a datacenter. This network consists of physical topologymodelised by a DAG without circuit and measurements are on the edges of a DAG. The mainpoint of the network is that measurements are some mistakes and the topology is unknown i.ewe know edges but the nodes of edges are unknown. When measurements are correct then thecorrelations between pairwise edges provide the adjacency matrix of the linegraph of undirectedgraph of the DAG. A linegraph is a graph in which each node and the neighbor are partitionnedby one or deux cliques. However, with the mistakes in measurements, the obtained graph is nota linegraph because it contains more or less edges. If the obtained graph is a linegraph then it isa linegraph of the other DAG. Our problem is to discovery the topology of the DAG with somemistakes in measurements.We start by the state of art in the measurement correlations in order to choose the good methodfor our problem. Then, we propose two algorithms to resolve our problem. The first algorithmis the cover algorithm and it returns the set of cliques in the graph. The second algorithm is acorrection algorithm which adds or deletes edges in the graph for getting a nearest linegraph ofthe DAG. In the last, we evaluate the performances of the algorithms by checking the number ofedges corrected and the ability to return a nearest linegraph of the DAG

APA, Harvard, Vancouver, ISO, and other styles

50

Hiesböcková, Tereza. "Předpovídání povodňových průtoků v měrných profilech Borovnice - Dalečín." Master's thesis, Vysoké učení technické v Brně. Fakulta stavební, 2012. http://www.nusl.cz/ntk/nusl-225458.

Full text

Abstract:

Aim of a work is construction of forecasting models for prediction of flood flows of measuring profile Borovnice – Dalečín on the river Svratka. As a tool for issuing predictions will be used classic hydrological forecasting models, and models based on artificial intelligence methods. Predictive model will be consisting from summer flood flows for the years 1997-2007. In the end of the work will chosen a better method for issuing forecasts

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Algorithme de flots'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles