Cette thèse s’intéresse à la résolution de problèmes d’optimisation combinatoires NP-difficiles en utilisant des méthodes de résolution approchées. Deux domaines d’application sont ciblés ici, d’une ...part la problématique générale du réseau de transport avec une variante portant plus précisément sur la planification des tournées avec une équipe de véhicules, d’autre part le problème de gestion de sessions en mode multicast dans un réseau de télécommunication, abordé ici du point de vue plus général du partitionnement dans un graphe biparti. Ces deux applications sont évidemment d’intérêt, tant du point de vue fondamental pour les méthodes de résolution qui doivent toujours progresser face à de nouveaux challenges, que du point de vue des retombées industrielles potentielles. La résolution de tels problèmes comporte généralement deux phases : dans un premier temps il s’agit de définir un ou plusieurs modèles mathématiques, de les comparer éventuellement pour choisir le plus efficace en fonction des outils de résolution disponibles; dans un deuxième temps il est possible d’utiliser un paradigme de résolution générique, comme par exemple un solveur de programmation linéaire, ou bien de spécialiser un algorithme en y incluant des heuristiques et connaissances spécifiques, afin d’optimiser sa performance. C’est dans cette deuxième démarche que se situe cette thèse, démarche souvent nécessaire lorsque les problèmes abordés deviennent complexes et/ou de grande taille et que l’on souhaite concevoir des algorithmes plus efficaces
This thesis focuses on solving combinatorial optimization problems NP-hard using approximate solving methods. Two practical application areas are targeted here, firstly the general problem of vehicule routing network with a variant specifically with planning tours with a vehicle team, on the other hand the multicast session management problem on a telecommunications network, addressed by the broader perspective of clustering in a bipartite graph. Both applications are obviously of interest both from the fundamental point of view for the resolution methods that must always progress facing new challenges, from the point of view of potential industrial benefits. The resolution of such problems usually has two phases: initially it comes to define one or more mathematical models to compare possibly to choose the most effective according to the available resolution tools; secondly it is possible to use a generic resolution paradigm, such as a linear programming solver, or specialize an algorithm by including specific heuristics and knowledge to optimize its performance. This thesis is in this second approach. This is often necessary when the problems addressed become complex and / or large and that we need to be designing more efficient algorithms
Ces dernières décennies, la spectroscopie moléculaire a bénéficié du progrès des spectromètres, notamment en terme de sélectivité et sensibilité, et de méthodes d'analyse et de calculs de chimie ...quantique toujours plus avancés. Désormais, la spectroscopie rotationnelle s'oriente vers l'analyse de systèmes moléculaires plus complexes caractérisés spectralement par une forte densité de raies. La congestion spectrale des espèces étudiées dans ma thèse s'explique non seulement par de faibles constantes rotationnelles mais aussi par la présence d'états vibrationnels excités à température ambiante, une forte richesse isotopique, un haut degré de splittings dus aux mouvements de grande amplitude ou encore par un paysage conformationnel complexe. Cette thèse illustre ainsi divers scénarii à travers les études du chlorure de thionyle, des nitrotoluènes et des méthoxyphénols. Les spectres rovibrationnels des bandes v2 et v5 des isotopologues du chlorure de thionyle ont été mesurés dans l'infrarouge lointain au synchroton SOLEIL et analysés en utilisant une approche semi-automatique basée sur des algorithmes évolutionnaires. Les isomères du nitrotoluène ont été ciblés pour leur intérêt défense comme traceurs d'explosif (TNT), les spectres de rotation pure ont été mesurés dans les régions micro-ondes en jet moléculaire et millimétrique à température ambiante. Le spectre millimétrique du 3-nitrotoluène était particulièrement faible et congestionné avec des splittings dus à la rotation interne très importants (jusqu'à plusieurs GHz) en raison d'une barrière de rotation très faible ( Vз=6.7659(24)cmˉ ¹). La limite de détection a été estimée et une liste de raies établie. Les spectres millimétriques des 2-nitrotoluène et 4-nitrotoluène ont également été partiellement analysés. Enfin, les méthoxyphénols émis lors de feux de biomasse ont également étudiés comme précurseurs d'aérosols organiques secondaires pour leur détection atmosphérique future. Associée à des calculs de chimie quantique, l'analyse du spectre millimétrique du 3-méthoxyphénol mesuré à température ambiante dans la région millimétrique a permis de déterminer la stabilité relative de quatre conformères.
In recent decades, molecular spectroscopy has benefited from the progress of spectrometers, particularly in terms of selectivity and sensitivity, and from the continuous advancement of the analysis methods and quantum chemistry calculations. Today, rational spectroscopy is moving towards the analysis of more complex molecular systems spectrally characterized by a high density of lines. The spectral congestion of the species studied in this thesis is not only explained by low rotational constants, but also by the presence of vibrational states excited at room temperature, a high isotopic richness, a high degree of line splitting due to large amplitude motions or by a complex conformational landscape. This thesis thus illustrates various scenarios through the studies of thionyl chloride, nitrotoluenes and methoxyphenols. The rovibrational spectra of the v2 and v5 bands of the isotopologues of thionyl chloride were measured in far-infrared at the SOLEIL synchroton and analyzed using a semi-automatic approach based on evolutionary algorithms. The isomers of nitrotoluene have been targeted for military application as explosive taggants (TNT), the pure rotation spectra were measured in the microwave region in molecular jet and in the millimeter-wave region at room temperature. The millimeter-wave spectrum of 3-nitrotoluene was especially weak and congested with very large internal rotation splittings (up to several GHz) due to a very weak rotational barrier (V3=6.7659(24)cmˉ ¹). The detection limit was estimated and a linelist established. The 2-nitrotoluene and 4-nitrotoluene millimeter-wave spectra have been also partially analyzed. Finally, methoxyphenols emitted during biomass fires have also been studied as they are secondary organic aerosol precursors for their future atmospheric detection. Combined with quantum chemistry calculations, the analysis of the millimeter-wave spectrum of the 3-methoxyphenol measured at room temperature permitted the relative stability of four conformers to be determined.
La evolución de la electrónica y la informática ha mostrado que la relación entre estas dos ciencias esta muy ligada. Esta relación no solo es vigente desde la concepción de la arquitectura interna ...de un microprocesador y su repertorio de instrucciones de máquina provistas para que un desarrollador de software construya sus aplicaciones, sino que ha llegado a niveles superiores como es el caso de los circuitos dispositivos PIC(Circuito Integrado Programable), FPGA (Field Programmable Gate Array), GAL (Generic Array Logic), DSP (Procesador Digital de Señales), PLC (Controlador Lógico Programable), PID (Control Proporcional Integral y Derivativo), entre otros.
Algoritmos voraces Solarte Martínez, Guillermo Roberto; Muñoz Guerrero, Luis Eduardo
Scientia et technica,
2007, Volume:
5, Issue:
37
Journal Article
Open access
The voracious algorithms are used essentially for solve optimization problems,
even also they can approximate to a solution for problem considered difficult
computationally, they are algorithms very ...easy to design and implement and of
great efficiency.
Los algoritmos voraces son usados esencialmente para resolver problemas de
optimización, aunque también pueden aproximarse a una solución a problemas
considerados computacionalmente difíciles, Son algoritmos muy fácil de
diseñar e implementar y de gran eficiencia.
PDF
