Algorithms, words and random texts
| Autor: | Clément, Julien |
|---|---|
| Přispěvatelé: | Clément, Julien |
| Jazyk: | francouzština |
| Rok vydání: | 2011 |
| Předmět: | |
| Popis: | In this memoir , I examine different aspects of a simple but ubiquitous computer object: the string or sequence of symbols. The string of characters concept is at the crossroads of areas as information theory and language theory. Although simple, this notion is fundamental: data will always be represented, encoded and stored in computers as sequences of symbols at one time or another The increasing amount of information and data to which we have access, such as genomes of individuals or scanned documents, justifies that the algorithms and data structures handling them need to be optimized. Consequently, rigourous analysis is needed in order to guide the end-user and the designer of programs that manipulate these data. The average analysis is particularly appropriate here because the data reach such variety and large volumes that the typical case is best reflected than with the more usual worst case complexity. This obviously raises the very difficult problem of data modeling. Indeed in our setting we want two contradictory things: a model closer to the data, which really translates their specificities, but also a model yielding results, that is to say, able to predict the performance. Methods are most often those of analytic combinatorics and use a mathematical object , generating functions, to carry out the analyzes. Dans ce mémoire, j'examine différents aspects d'un objet simple mais omniprésent en informatique: la séquence de symboles (appelée selon le contexte mot ou chaîne de caractères). La notion de mot est au carrefour de domaines comme la théorie de l'information et la théorie des langages. S'il est simple, il reste fondamental: nous n'avons, au plus bas niveau, que cela à disposition puisqu'il arrive toujours un moment où une donnée doit être encodée en symboles stockables en mémoire. La quantité d'information croissante de données mise à disposition et qu'on peut stocker, par exemple des génomes d'individus ou des documents numérisés, justifie que les algorithmes et les structures de données qui les manipulent soient optimisés. En conséquence, les besoins d'analyse se font sentir pour guider le choix et la conception des programmes qui manipulent ces données. L'analyse en moyenne est ici particulièrement adaptée puisque les données atteignent une variété et des volumes tellement importants que c'est le cas typique qui traduit le mieux la complexité et non pas le cas le pire. Cela évidemment pose le problème de la modélisation de données qui reste encore très épineux. En effet on souhaite deux choses contradictoires: un modèle au plus près des données, qui traduise vraiment leurs spécificités, mais aussi un modèle permettant de donner des résultats, c'est-à-dire de prédire les performances (et on comprend vite que le modèle doit donc rester relativement simple pour qu'il subsiste un espoir de le traiter!). Les méthodes sont le plus souvent celles de la combinatoire analytique et font appel à un objet mathématique, les séries génératrices, pour mener les analyses à bien. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|