Time-delayed actions appear as an essential component of numerous systems especially in evolution processes, natural phenomena, and particular technical applications and are associated with the existence of a memory. Under common conditions, external forces or state dependent parameters modify the length of the delay with time. Consequently, an altered dynamical behavior emerges, whose characterization is compulsory for a deeper understanding of these processes. In this thesis, the well-investigated class of time-homogeneous finite-state Markov processes is utilized to establish a variation of memory length by combining a first-order Markov chain with a memoryless Markov chain of order zero. The fluctuations induce a non-stationary process, which is accomplished for two special cases: a periodic and a random selection of the available Markov chains. For both cases, the Kolmogorov-Sinai entropy as a characteristic property is deduced analytically and compared to numerical approximations to the entropy rate of related symbolic dynamics. The convergences of per-symbol and conditional entropies are examined in order to recognize their behavior when identifying unknown processes. Additionally, the connection from Markov processes with varying memory length to hidden Markov models is illustrated enabling further analysis. Hence, the Kolmogorov-Sinai entropy of hidden Markov chains is calculated by means of Blackwell’s entropy rate involving Blackwell’s measure. These results are used to verify the previous computations.

Dans cette recherche, un modèle de propagation d'ondes de choc sur grandes distances sur un environnement urbain est construit et validé. L'approche consiste à utiliser l'Equation Parabolique Nonlinéaire (NPE) comme base. Ce modèle est ensuite étendu afin de prendre en compte d'autres effets relatifs à la propagation du son en milieu extérieur (surfaces non planes, couches poreuses, etc.). La NPE est résolue en utilisant la méthode des différences finies et donne des résultats en accord avec d'autres méthodes numériques. Ce modèle déterministe est ensuite utilisé comme base pour la construction d'un modèle stochastique de propagation sur environnements urbains. La Théorie de l'Information et le Principe du Maximum d'Entropie permettent la construction d'un modèle probabiliste d'incertitudes intégrant la variabilité du système dans la NPE. Des résultats de référence sont obtenus grâce à une méthode exacte et permettent ainsi de valider les développements théoriques et l'approche utilisée

Le travail de recherche porte sur deux thèmes: 1. développement d'un modèle dynamique multimodal basé sur les activités ; 2. développement de méthodes de résolution de l'équilibre du réseau multimodal dynamique. Nous proposons un modèle dynamique multimodal simulant l'enchaînement des déplacements basé sur les activités. Deux nouvelles méthodes de résolution du problème d'équilibre du réseau sont proposées : 1. l'algorithme de colonie de fourmis en discrétisation temporelle ; 2. la méthode de l'Entropie Relative. Cette dernière constitue une avancée méthodologique qui considère que l'équilibre du réseau est un événement rare parmi les états possibles du réseau. Pour réduire les besoins en moyens de calcul pour l'application dans un grand réseau, nous simulons les voyageurs par paquets en nous appuyant sur un nouveau modèle macroscopique de trafic en coordonnées Lagrangiennnes. Ce modèle permet de décrire la propagation des paquets conformément au modèle macroscopique du premier ordre.

Cette thèse traite de la modélisation de prix boursiers par les exponentielles de processus de Lévy. La première partie développe une méthode non-paramétrique stable de calibration de modèles exponentielle-Lévy, c'est-à-dire de reconstruction de ces modèles à partir des prix d'options cotées sur un marché financier. J'étudie les propriétés de convergence et de stabilité de cette méthode de calibration, décris sa réalisation numérique et donne des exemples de son utilisation. L'approche adoptée ici consiste à reformuler le problème de calibration comme celui de trouver un modèle exponentielle-Lévy risque-neutre qui reproduit les prix d'options cotées avec la plus grande précision possible et qui a l'entropie relative minimale par rapport à un processus "a priori" donné. Ce problème est alors résolu en utilisant la méthode de régularisation, provenant de la théorie de problèmes inverses mal posés. L'application de ma méthode de calibration aux données empiriques de prix d'options sur indice permet d'étudier certaines propriétés des mesures de Lévy implicites qui correspondent aux prix de marché. <br /><br />La deuxième partie est consacrée au développement d'une méthode permettant de caractériser les structures de dépendance entre les composantes d'un processus de Lévy multidimensionnel et de construire des modèles exponentielle-Lévy multidimensionnels. Cet objectif est atteint grâce à l'introduction de la notion de copule de Lévy, qui peut être considérée comme l'analogue pour les processus de Lévy de la notion de copule, utilisée en statistique pour modéliser la dépendance entre les variables aléatoires réelles. Les exemples de familles paramétriques de copules de Lévy sont donnés et une méthode de simulation de processus de Lévy multidimensionnels, dont la structure de dépendance est décrite par une copule de Lévy, est proposée.

L'auto-organisation de réseaux radio multi-sauts a pour objectif de structurer/organiser un réseau à l'aide d'une structure logique. Pourquoi le structurer ? Pour introduire de la stabilité en ne tenant pas compte de voisins instables ou fortement mobiles, pour fédérer l'ensemble des noeuds, pour introduire une hiérarchie dans le réseau afin de faciliter le passage à l'échelle, pour introduire plus de capacité dans le réseau, etc. L'auto-organisation telle que nous la considérons vise à construire une topologie logique basée sur la topologie physique de telle sorte que les protocoles réseaux (routage, inondation, etc.) et applicatifs (agrégation et dissémination de données) soient plus efficace et plus robuste. La littérature propose essentiellement 4 façons de structurer un réseau en ayant recours aux tables de hachage distribuées (DHT), aux stratégies de clustering, à la construction d'overlays ou en construisant un réseau maillé logique. Bien entendu, il s'agit ici de proposer des protocoles localisés, voire distribuées. Dans nos travaux, nous avons proposé plusieurs algorithmes localisés de construction et de maintenance de backbone virtuel construit sous forme d'arbre ou de treillis. Après avoir étudié les propriétés intrinsèques de ces protocoles en termes de cardinalité, de convergence (auto-stabilisation), de complexité, etc. nous nous sommes intéressé à l'apport de ces structures logiques dans les problématiques réseaux. Ainsi, et que ce soit dans le domaine des réseaux ad hoc, des réseaux hybrides et des réseaux de capteurs, nous avons re-visité les principaux défis posés en développant des protocoles basés sur les auto-organisations proposées plutôt que de considérer le réseau à plat comme c'est souvent le cas. Des protocoles de routage unicast, de localisation, d'auto-configuration mais également de diffusion de données ont été proposés. L'ensemble des publications obtenues mettent en évidence la pertinence de cette démarche. A côté de ces travaux orientés réseaux nous avons montré, dans des travaux plus théoriques, l'apport en terme de stabilité que permettait l'auto-organisation notamment dans le cas de topologies fortement dynamique. Ce résultat est basé sur l'application de l'entropie statistique utilisée classiquement en thermodynamique. Ces travaux ont été menés depuis le point de vue théorique jusqu'à l'expérimentation.

De nos jours, les données disponibles deviennent de plus en plus volumineuses et elles peuvent être de nature très diverse : vagues, manquantes, numériques, symboliques par exemple. Or ce qui importe à l'utilisateur, ce ne sont pas les données elles-mêmes, mais les connaissances qu'on peut en extraire. Face à la quantité de données disponibles, le traitement efficace de données est problématique. Dans cette thèse, nous adoptons une approche d'extraction de connaissances à partir de données basée sur l'apprentissage inductif, plus précisément, par arbres de décision.<br /><br />De façon générale, un système construit par apprentissage inductif a pour but de discriminer les individus de différentes classes. Sa qualité dépend de la capacité de discrimination qu'il acquiert au cours de l'apprentissage au travers des données. En particulier, un algorithme de construction d'arbre de décision procède par évaluation successive de la capacité de discrimination des attributs pour construire l'arbre de décision.<br /><br />Nos travaux concernent l'étude des mesures de discrimination tant classiques que floues, et leurs applications en apprentissage inductif. <br /><br />D'une part, nous nous intéressons aux mesures de discrimination dans la construction des arbres de décision. Dans un premier temps, ces mesures font l'objet d'une étude selon une approche axiomatique. Nous développons un nouveau modèle pour caractériser les mesures de discriminations floues. Dans un deuxième temps, nous proposons d'utiliser ces mesures dans les différentes étapes de la construction des arbres de décision flous. <br /><br />D'autre part, nous étudions l'utilisation de ces mesures de discrimination pour d'autres aspects de l'apprentissage. Nous examinons tout d'abord le problème de l'évaluation des classifieurs et proposons une méthode basée sur l'utilisation de la notion de capacité de discrimination. Enfin, nous considérons le problème du traitement des données manquantes et proposons une technique de substitution des valeurs manquantes, qui restitue la capacité de discrimination des attributs. <br /><br />Ces travaux sont validés sur des données conventionnelles et appliqués à des données réelles dans le cadre de deux applications qui concernent la classification de courriers électroniques et la classification de traces d'interactions homme-machine.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Thèse effectuée en cotutelle avec l’Université de Montréal et l’Université Paris 1 Panthéon-Sorbonne (IHPST) / L’entropie est généralement considérée comme une propriété émergente, tandis que l’émergence de certaines structures organisées serait le résultat d’une dissipation d’entropie. Ainsi, l’émergence est parfois présentée comme ce qui expliquerait l’entropie alors que l’entropie expliquerait l’émergence. Tels quels, ces deux énoncés ne peuvent être tous deux vrais. Face à la polysémie déconcertante des concepts d’émergence, d’entropie et d’explication, je soutiens que cet apparent paradoxe peut être résolu formellement ainsi : l’émergence (en un sens A) explique (en un sens B) l’entropie (en un sens C) et l’entropie (en un sens D) explique (en un sens E) l’émergence (en un sens F). La solution revient donc à préciser A, B, C, D, E, et F. Pour ce faire, je propose un modèle pluraliste (restreint) de l’explication et un examen critique du concept d’entropie. Dans le cas de l’entropie comme explanandum de l’émergence (A, B et C), ce qui émerge est l’irréversibilité comme propriété essentielle de l’entropie thermodynamique, mais l’émergence ne peut être synonyme de non-explicabilité. Je montre alors trois possibilités où l’émergence peut expliquer l’entropie thermodynamique : selon (i) un sens fort, comme une modalité ontologique, (ii) selon un sens intermédiaire d’après ce que j’appelle l’émergence méthodologique (où il y a possibilité d’explication réductive sans réduction dérivationnelle), et (iii) selon un sens faible, comme sa désignation comme membre d’une classe d’émergents. Dans le cas de l’entropie comme explanans de l’émergence (D, E, et F), il faut distinguer l’approche substantielle de l’approche analogique. Dans le premier cas, l’entropie renvoie à une propriété macroscopique robuste et autonome pouvant être mobilisée au sein d’un explanans de l’émergence de nouvelles structures complexes. Dans le second cas, l’entropie exemplifie la réalisabilité multiple et peut être mobilisée, modulo une justification, au sein d’un explanans de l’émergence de propriétés à des niveaux supérieurs. En définitive, la polysémie de ces concepts peut être fructueuse au sein de ce cadre explicatif de phénomènes divers et complexes, de la physique à la biologie. / Entropy is generally considered as an emergent property, while the emergence of certain organized structures is supposed to be the result of entropy dissipation. Thus, emergence is sometimes seen as explaining entropy, whereas sometimes the explanation is the other way around, as entropy would explain emergence. As such both statements cannot be true. Faced with the daunting polysemy of these concepts of emergence, entropy and explanation, I argue that this apparent paradox can be formally solved as follows: the emergence (in a sense A) explains (in a sense B) entropy (in a sense, C) and entropy (in a sense D) explains (in a sense E) emergence (in a sense F). The solution is therefore to specify A, B, C, D, E, and F. To do this, I suggest a (restricted) pluralistic model of explanation and a critical examination of the concept of entropy. In the case of entropy as explanandum of emergence (A, B and C), what is emerging is irreversibility as an essential property of thermodynamic entropy, but it cannot be emergence of synonymous of non-explicability. I then show three possibilities that can explain the emergence of thermodynamic entropy: (i) in a strong sense, as an ontological modality, (ii) in an intermediate sense, from what I call ‘methodological emergence’ (where there is a possibility of reductive explanation but no derivational reduction), or (iii) in a weak sense, as its designation as a member of an emergence class. In the case of entropy as explanans of emergence (D, E, and F), one must distinguish the substantive approach from the analogical approach. In the first case, entropy refers to a robust and autonomous macroscopic property that can be mobilized in an explanans of the emergence of new complex structures. In the second case, the entropy exemplifies multiple realizability and can be mobilized, with a proper justification, within an explanans of the emergence of properties at higher levels. Ultimately, the polysemy of these concepts can be fruitful in this explanatory framework for various complex phenomena, from physics to biology.

Le problème de la direction du temps est un problème classique autant en physique qu’en philosophie. Quoiqu’il existe plusieurs façons de s’interroger sur ce problème, l’approche thermodynamique est la plus fréquemment utilisée. Cette approche consiste à considérer la flèche du temps thermodynamique comme la flèche fondamentale de laquelle les autres flèches ne sont que des manifestations. Ce mémoire vise à fournir une analyse philosophique de cette approche. Pour ce faire, nous esquisserons la problématique générale, nous exposerons les différentes approches et théories alternatives visant à résoudre ce problème et nous présenterons la thèse forte soutenant l’approche thermodynamique. Ensuite, nous évaluerons la pertinence du recours à la mécanique statistique et à la cosmologie visant à remédier aux déficiences de cette même approche. Enfin, nous analyserons en quoi cette approche, et plus particulièrement la notion d’entropie, est en mesure de fournir un cadre conceptuel pour la résolution du problème de la flèche du temps. / The problem of the direction of time is a classical problem in both physics and philosophy. Although there are various ways to tackle this problem, the thermodynamic approach is the most commonly used. This approach considers the thermodynamic arrow of time as the fundamental arrow of which all others arrows are only manifestations. This essay aims to provide a philosophical analysis of this approach. To do this, we sketch the research question, we introduce various alternate theories and approaches set to answer this problem, and present the strong thesis underlying the thermodynamic approach. Then we will evaluate the use of statistical mechanics and cosmology that are used in attempt to mitigate the deficiencies of this approach. Finally, we will analyze how this approach, and more importantly the notion of entropy, can provide an adequate conceptual scheme to solve the problem of the arrow of time.

Diese Arbeit beschäftigt sich mit dem Thema Evolutionäre Algorithmen und deren Verwendung für Optimierungsaufgaben. Im ersten Teil der Arbeit werden die theoretischen Grundlagen ausführlich dargelegt, die zum Verständnis der Problemstellung und der vorgeschlagenen Lösungsmöglichkeiten notwendig sind. Dazu gehören die Einführung des Konzeptes von Fitneßlandschaften, deren Eigenschaften sowie die kurze Darstellung bekannter stochastischer Optimierungsverfahren wie z.B. Simulated Annealing. Im Anschluß daran wird auf neue Verfahren - insbesondere gemischte Strategien - eingegangen und diese vergleichend gegenüber den herkömmlichen Verfahren abgegrenzt. Die neu entwickelten Verfahren werden an Modellproblemen getestet, welche im zweiten Teil der Arbeit vorgestellt werden. Verwendet wurden sowohl einfache theoretische Modelle wie Frustrierte Periodische Sequenzen als auch praktisch relevante Probleme wie das der RNA Sekundärstrukturen. Die verschiedenen Modellprobleme werden bezüglich ihrer Eigenschaften und Schwierigkeitsgrade untersucht und miteinander verglichen, um die Effizienz der verwendeten Optimierungsverfahren abschätzen zu können. Der dritte Teil der Arbeit präsentiert wichtige Ergebnisse der im Rahmen dieser Arbeit durchgeführten umfangreichen numerischen Simulationen. Es wird demonstriert, wie sensitiv die Optimierungsergebnisse von den verwendeten Parametern der Algorithmen (wie z.B. Ensemblegröße, Temperatur oder Mutationsrate) abhängen und das ein relativ scharf umrissenes evolutionäres Fenster der Parameter existiert, innerhalb dessen die Optimierungsresultate deutlich besser sind. Eine im Rahmen dieser Arbeit entwickelte adaptive Parametersteuerung wird an den im zweiten Teil vorgestellten Modellproblemen getestet und gezeigt, daß es möglich ist, den Optimierungsprozeß automatisch innerhalb des evolutionären Fensters zu halten. Der letzte Teil gibt Einblick in die im Rahmen dieser Arbeit verwendete Computer-Software und das vom Autor entwickelte Programmpaket. Es wird hervorgehoben, daß die in C++ objektorientiert und modular geschriebene Software leicht an andere Optimierungsaufgaben angepaßt werden kann und dank graphischer Benutzeroberfläche auch einfach zu bedienen ist. / This work explores Evolutionary Algorithms and their application to optimization tasks. The work's first part gives detailed theoretical background information necessary to understand the problem and proposed solutions. This theoretical part includes the introduction of fitness landscapes, the investigation of their properties, and it briefly reiterates well known stochastic optimization strategies like Simulated Annealing. Finally, new strategies, in particular mixed stategies, are introduced and compared to traditional optimization techniques. In the second part of this work, the newly developed strategies are benchmarked using model problems such as 'Frustrated Periodic Sequences', or the analysis of RNA secondary structures. To evaluate the efficiency of different optimization strategies, the introduced model problems are compared with respect to their difficulty level. The third part of this work presents results of extensive numerical simulations demonstrating how sensitive the investigated algorithms depend on their respective control parameters (ensemble size, temperature, mutation rate). It is shown that there is always a distinct parameter window, the so-called evolutionary window, that clearly leads to improved optimization results. Going back to the model problems introduced in part two, a newly developed adaptive parameter control is presented that automatically keeps the optimization algorithm's parameters within the evolutionary window. In the final part of this work not only the software used, but also the software newly developed by this work's author is illuminated. It is emphasized that the new software was designed highly flexible to allow for easy adaptation to different optimization problems. A graphical user interface is provided for convenience.