Titre de l'écran-titre (visionné le 7 février 2024) / La croissance rapide des données dans différentes applications telles que la communication en temps réel, les systèmes automobiles et la visioconférence a souligné la nécessité de techniques efficaces de compression des données. La compression des données réduit les besoins de stockage et de transmission des données. La codification d'entropie, qui est une compression de données sans perte, est une méthode largement utilisée. La codification d'entropie consiste à coder des symboles d'une séquence d'entrée en utilisant moins de bits pour les représenter, ce qui réduit la taille totale des données. La codification de Huffman, qui est une technique rapide de codage d'entropie, est utilisée pour sa vitesse et son accélération matérielle. Cependant, son taux de compression n'est pas toujours optimal. Cela devient évident lorsqu'il s'agit de petits alphabets et de symboles avec des probabilités d'occurrence élevées. La codification arithmétique, une méthode alternative, offre de meilleurs taux de compression, mais elle a une complexité computationnelle élevée. Les systèmes de numération asymétriques (ANS), qui sont une approche de codage d'entropie, visent à approcher la limite théorique de la compression des données tout en maintenant une complexité computationnelle inférieure par rapport à la codification arithmétique. ANS comprend deux versions principales : ANS à plage et ANS tabulé. Ce dernier, appelé tANS, utilise une table pour les procédures de codage et de décodage, ce qui le rend plus adapté à une implémentation matérielle. Cependant, bien qu'ANS présente des avantages, des défis subsistent. Trouver une table de codage appropriée, ou un segment clé, pour tANS est important pour son efficacité. Des recherches récentes explorent différentes techniques pour concevoir des segments clés optimaux, en tenant compte de facteurs tels que les probabilités des symboles, l'alphabet source et la taille de la table souhaitée. Le défi consiste à construire un segment clé qui satisfait aux conditions de codage et qui conduit à une longueur moyenne minimale des codes. La technique de tri d'états proposée par Yokoo et Dubé vise à optimiser les segments clés en triant les états en fonction de leurs probabilités stationnaires. Cependant, cette méthode est sous-optimale dans certains cas. L'objectif de cette recherche est d'étudier les limitations et la sous-optimalité de l'algorithme de tri des états en présentant un exemple dans lequel la stratégie de Yokoo et Dubé ne créera pas le segment optimal. Cela permettra une meilleure compréhension des complexités de la conception de clés tANS optimales. Cette étude contribue à l'avancement des techniques de compression des données en abordant les défis et les améliorations possibles dans le contexte du codage d'entropie, en particulier dans le cadre d'ANS et de ses variantes. Cette recherche vise à améliorer notre compréhension de la conception de clés pour tANS et à ouvrir la voie à des solutions plus efficaces pour la compression et la transmission des données dans le paysage numérique en constante évolution. / In the modern world, the significant increase of data has resulted in the demand for efficient data handling in terms of transfer and storage. As hardware advances, data compression has become an essential research field to address this challenge. Rooted in the fusion of mathematics and computer science, data compression utilizes algorithms to reduce data size and optimize storage capacity. This process involves both compression and reconstruction algorithms, seeking to keep similarity of the original data and the reconstructed data. By compression data, the speed of data transfer increases significantly, while the costs of storage hardware and network bandwidth decrease. Data compression divides into two categories: lossy and lossless compression. In lossy compression we may have some loss of information during reconstruction. Contrarily, lossless compression, in which input and output remain equal, is suited for systems involving sensitive data or databases. This thesis focuses on addressing weaknesses of the tANS method, with a particular emphasis on investigating the sub-optimality of the state-sorting technique presented by Yokoo and Dubé. The study discusses the limitations of this technique and explains ANS methods, particularly the theoretical analysis of tANS. The research illustrates an example emphasizing sub-optimality in the state-sorting technique. In conclusion, this research offers valuable insights into the challenges and potential enhancements of tANS compression technique. By delving deeper into the intricacies of ANS-based methods, researchers can contribute to the development of more efficient compression strategies, providing better data handling in an increasingly digitized world.

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

Il est raisonnable de considérer qu'un auditeur ne perçoit pas la musique comme une simple séquence de sons, pas plus que le compositeur n'a conçu son morceau comme tel. La musique est en effet constituée de motifs dont l'organisation intrinsèque et les relations mutuelles participent à la structuration du propos musical, et ce à plusieurs échelles simultanément. Cependant, il est aujourd'hui encore très difficile de définir précisément le terme de concept musicale. L'un des principaux aspects de la musique est qu'elle est en grande partie constituée de redondances, sous forme de répétitions exactes et variées. L'organisation de ces redondances permet de susciter une attente chez l'auditeur. Une surprise peut alors être créée en présentant des éléments qui ne correspondent pas à cette attente. Ce travail de thèse se base sur l'hypothèse que les redondances, l'attente et la surprise sont des éléments essentiels pour la description de la structure musicale d'un segment. Un certain nombre de questions découlent de ce constat: quels sont les éléments musicaux qui participent à la structure d'un objet musical ? Quelles sont les dépendances entre ces éléments qui jouent un rôle essentiel dans la structuration d'un objet musical ? Comment peut-on décrire une relation entre deux éléments musicaux tels que des accords, des motifs rythmiques ou mélodiques ? Dans ce manuscrit, des éléments de réponse sont proposés par la formalisation et l'implémentation d'un modèle multi-échelle de description de la structure d'un segment musical : les Graphes Polytopiques à Relations Latentes (GPRL/PGLR). Dans ce travail, les segments considérés sont les sections successives qui forment une pièce musicale. Dans le cas de la pop, genre musical sur lequel se concentre ce travail, il s'agit typiquement d'un couplet ou d'un refrain, de 15 sec. environ, comprenant un début et une fin bien définis. En suivant le formalisme PGLR, les relations de dépendance prédominantes entre éléments musicaux d'un segment sont celles qui relient les éléments situés à des positions homologues sur la grille métrique du segment. Cette approche généralise sur le plan multi-échelle le modèle Système&Contraste qui décrit sous la forme d'une matrice 2×2 le système d'attente logique au sein d'un segment et la surprise qui découle de la réalisation de cette attente. Pour des segments réguliers de taille 2^n, le PGLR peut être représenté sur un n-cube (carré, cube, tesseract, ...), où n est le nombre d'échelles considérées. Chaque nœud du polytope correspond à un élément musical fondamental (accord, motif, note...), chaque arête représente une relation entre deux nœuds et chaque face représente un système de relations. La recherche du PGLR correspondant à la meilleure description de la structure d'un segment musical s'opère par l'estimation jointe : de la description du polytope (un n-polytope plus ou moins régulier) ; de la configuration du graphe sur le polytope, permettant de décrire le flux de dépendance et les interactions entre les éléments par des implications élémentaires systémiques au sein du segment ; la description de l'ensemble des relations entre les nœuds du graphe. Le but du modèle PGLR est à la fois de décrire les dépendances temporelles entre les éléments d'un segment et de modéliser l'attente logique et la surprise qui découlent de l'observation et de la perception des similarités et des différences entre ces éléments. Cette approche a été formalisée et implémentée pour décrire la structure de séquences d'accords ainsi que de segments rythmiques et mélodiques, puis évaluée par sa capacité à prédire des segments inconnus. La mesure utilisée pour cette évaluation est la perplexité croisée calculée à partir des données du corpus RWC POP. Les résultats obtenus donnent un large avantage à la méthode multi-échelle proposée, qui semble mieux à même de décrire efficacement la structure des segments testés. / In this thesis, we approach these questions by defining and implementing a multi-scale model for music segment structure description, called Polytopic Graph of Latent Relations (PGLR). In our work, a segment is the macroscopic constituent of the global piece. In pop songs, which is the main focus here, segments usually correspond to a chorus or a verse, lasting approximately 15 seconds and exhibiting a clear beginning and end. Under the PGLR scheme, relationships between musical elements within a musical segment are assumed to be developing predominantly between homologous elements within the metrical grid at different scales simultaneously. This approach generalises to the multi-scale case the System&Contrast framework which aims at describing, as a 2×2 square matrix, the logical system of expectation within a segment and the surprise resulting from that expectation. For regular segments of 2^n events, the PGLR lives on a n-dimensional cube (square, cube, tesseract, etc...), n being the number of scales considered simultaneously in the multi-scale model. Each vertex in the polytope corresponds to a low-scale musical element, each edge represents a relationship between two vertices and each face forms an elementary system of relationships. The estimation of the PGLR structure of a musical segment can then be obtained computationally as the joint estimation of : the description of the polytope (as a more or less regular n-polytope) ; the nesting configuration of the graph over the polytope, reflecting the flow of dependencies and interactions as elementary implication systems within the musical segment, the set of relations between the nodes of the graph. The aim of the PGLR model is to both describe the time dependencies between the elements of a segment and model the logical expectation and surprise that can be built on the observation and perception of the similarities and differences between elements with strong relationships. The approach is presented conceptually and algorithmically, together with an extensive evaluation of the ability of different models to predict unseen data, measured using the cross-perplexity value. These experiments have been conducted both on chords sequences, rhythmic and melodic segments extracted from the RWC POP corpus. Our results illustrate the efficiency of the proposed model in capturing structural information within such data.

Un stable (ou ensemble indépendant) est un ensemble de sommets qui sont deux à deux non adjacents. De nombreux résultats classiques en optimisation combinatoire portent sur le nombre de stabilité (défini comme la plus grande taille d'un stable), et les stables se classent certainement parmi les structures les plus simples et fondamentales en théorie des graphes.<p><p>La thèse est divisée en deux parties, toutes deux liées à la notion de stables dans un graphe. Dans la première partie, nous étudions un problème de coloration de graphes, c'est à dire de partition en stables, où le but est de minimiser l'entropie de la partition. C'est une variante du problème classique de minimiser le nombre de couleurs utilisées. Nous considérons aussi une généralisation du problème aux couvertures d'ensembles. Ces deux problèmes sont appelés respectivement minimum entropy coloring et minimum entropy set cover, et sont motivés par diverses applications en théorie de l'information et en bioinformatique. Nous obtenons entre autres une caractérisation précise de la complexité de minimum entropy set cover :le problème peut être approximé à une constante lg e (environ 1.44) près, et il est NP-difficile de faire strictement mieux. Des résultats analogues sont prouvés concernant la complexité de minimum entropy coloring.<p><p>Dans la deuxième partie de la thèse, nous considérons les graphes dont le nombre de stabilité augmente dès qu'une arête est enlevée. Ces graphes sont dit être "alpha-critiques", et jouent un rôle important dans de nombreux domaines, comme la théorie extrémale des graphes ou la combinatoire polyédrique. Nous revisitons d'une part la théorie des graphes alpha-critiques, donnant à cette occasion de nouvelles démonstrations plus simples pour certains théorèmes centraux. D'autre part, nous étudions certaines facettes du polytope des ordres totaux qui peuvent être vues comme une généralisation de la notion de graphe alpha-critique. Nous étendons de nombreux résultats de la théorie des graphes alpha-critiques à cette famille de facettes.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

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 / This research aims at developing and validating a numerical model for the study of blast wave propagation over large distances and over urban environments. The approach consists in using the Nonlinear Parabolic Equation (NPE) model as a basis. The model is then extended to handle various features of sound propagation outdoors (non-flat ground topographies, porous ground layers, etc.). The NPE is solved using the finite-difference method and is proved to be in good agreement with other numerical methods. This deterministic model is then used as a basis for the construction of a stochastic model for sound propagation over urban environments. Information Theory and the Maximum Entropy Principle enable the construction of a probabilistic model of uncertainties, which takes into account the variability of the urban environment within the NPE model. Reference results are obtained with an exact numerical method and allow us to validate the theoretical developments and the approach used