Let <b>A</b> and <b>B</b> be finite sets with |<b>A</b>|=<i>n</i> and |<b>B</b>|=<i>m</i>. An (<i>n</i>,<i>m</i>,<i>w</i>)-<i>perfect hash</i> family</i> is a collection <i>F</i> of functions from <b>A</b> to <b>B</b> such that for any <b>X</b> &#8838; <b>A</b> with |<b>X</b>|=<i>w</i>, there exists at least one ? &#8712; <i>F</i> such that ? is one-to-one when restricted to <b>X</b>. Perfect hash families are basic combinatorial structures and they have played important roles in Computer Science in areas such as database management, operating systems, and compiler constructions. Such hash families are used for memory efficient storage and fast retrieval of items such as reserved words in programming languages, command names in interactive systems, or commonly used words in natural languages. More recently, perfect hash families have found numerous applications to cryptography, for example, to broadcast encryption schemes, secret sharing, key distribution patterns, visual cryptography, cover-free families and secure frameproof codes. In this thesis, we survey constructions and applications of perfect hash families. For constructions, we divided the results into three parts, depending on underlying structure and properties of the constructions: combinatorial structures, linear functionals, and algebraic structures. For applications, we focus on those related to cryptography.

Let <b>A</b> and <b>B</b> be finite sets with |<b>A</b>|=<i>n</i> and |<b>B</b>|=<i>m</i>. An (<i>n</i>,<i>m</i>,<i>w</i>)-<i>perfect hash</i> family</i> is a collection <i>F</i> of functions from <b>A</b> to <b>B</b> such that for any <b>X</b> &#8838; <b>A</b> with |<b>X</b>|=<i>w</i>, there exists at least one ? &#8712; <i>F</i> such that ? is one-to-one when restricted to <b>X</b>. Perfect hash families are basic combinatorial structures and they have played important roles in Computer Science in areas such as database management, operating systems, and compiler constructions. Such hash families are used for memory efficient storage and fast retrieval of items such as reserved words in programming languages, command names in interactive systems, or commonly used words in natural languages. More recently, perfect hash families have found numerous applications to cryptography, for example, to broadcast encryption schemes, secret sharing, key distribution patterns, visual cryptography, cover-free families and secure frameproof codes. In this thesis, we survey constructions and applications of perfect hash families. For constructions, we divided the results into three parts, depending on underlying structure and properties of the constructions: combinatorial structures, linear functionals, and algebraic structures. For applications, we focus on those related to cryptography.

This report covers one of the most demanding issues of network users i.e. network testing. Network testing in this study is about performance evaluation of networks, by putting traffic load gradually to determine the queuing delay for different traffics. Testing of such operations is becoming complex and necessary due to use of real time applications such as voice and video traffic, parallel to elastic data of ordinary applications over WAN links. Huge size elastic data occupies almost 80% resources and causes delay for time sensitive traffic. Performance parameters like service outage, delay, packet loss and jitter are tested to assure the reliability factor of provided Quality of Service (QoS) in the Service Level Agreements (SLAs). Normally these network services are tested after deployment of physical networks. In this case most of the time customers have to experience unavailability (outage) of network services due to increased levels of load and stress. According to user-centric point of view these outages are violation and must be avoided by the net-centric end. In order to meet these challenges network SLAs are tested on simulators in lab environment. This study provides a solution for this problem in a form of testbed simulator named Combinatorial TestBed Simulator (CTBS). Prototype of this simulator is developed for conducting experiment. It provides a systematic approach of combinatorial structures for finding such traffic patterns that exceeds the limit of queuing delay, committed in SLAs. Combinatorics is a branch of mathematics that deals with discrete and normally finite elements. In the design of CTBS, technique of combinatorics is used to generate a variety of test data that cannot be generated manually for testing the given network scenario. To validate the design of CTBS, results obtained by pilot runs are compared with the results calculated using timeline. After validation of CTBS design, actual experiment is conducted to determine the set of traffic patterns that exceeds the threshold value of queuing delay for Voice over Internet Protocol (VOIP) traffic. / 14:36 Folkparksvagan Ronneby 372 40 Sweden

Le cadre générale de cette thèse est l'analyse quantitative des objets issus de la théorie des langages rationnels. On adapte des techniques d'analyse d'algorithmes (complexité en moyenne, complexité générique, génération aléatoire, ...) à des objets et à des algorithmes qui font intervenir des classes particulières d'automates. Dans une première partie nous étudions la complexité de l'algorithme de minimisation de Brzozowski. Bien qu'ayant une mauvaise complexité dans le pire des cas, cet algorithme a la réputation d'être efficace en pratique. En utilisant les propriétés typiques des applications et des permutations aléatoires, nous montrons que la complexité générique de l'algorithme de Brzozowski appliqué à un automate déterministe croît plus vite que tout polynôme en n, où n est le nombre d'états de l'automate. Dans une seconde partie nous nous intéressons à la génération aléatoire d'automates acycliques. Ces automates sont ceux qui reconnaissent les ensembles finis de mots et sont de ce fait utilisés dans de nombreuses applications, notamment en traitement automatique des langues. Nous proposons deux générateurs aléatoires. Le premier utilise le modèle des chaînes de Markov, et le second utilise la "méthode récursive", qui tire partie des décompositions combinatoires des objets pour faire de la génération. La première méthode est souple mais difficile à calibrer, la seconde s'avère plutôt efficace. Une fois implantée, cette dernière nous a notamment permis d'observer les propriétés typiques des grands automates acycliques aléatoires / The general context of this thesis is the quantitative analysis of objects coming from rational language theory. We adapt techniques from the field of analysis of algorithms (average-case complexity, generic complexity, random generation...) to objects and algorithms that involve particular classes of automata. In a first part we study the complexity of Brzozowski's minimisation algorithm. Although the worst-case complexity of this algorithm is bad, it is known to be efficient in practice. Using typical properties of random mappings and random permutations, we show that the generic complexityof Brzozowski's algorithm grows faster than any polynomial in n, where n is the number of states of the automaton. In a second part, we study the random generation of acyclic automata. These automata recognize the finite sets of words, and for this reason they are widely use in applications, especially in natural language processing. We present two random generators, one using a model of Markov chain, the other a ``recursive method", based on a cominatorics decomposition of structures. The first method can be applied in many situations cases but is very difficult to calibrate, the second method is more efficient. Once implemented, this second method allows to observe typical properties of acyclic automata of large size

- / -