Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 19 avril 2011 à 14h00 en B311, Wojciech Szpankowski nous parlera de : Discrete divide and conquer recurrences

Résumé : Divide-and-conquer recurrences are one of the most studied equations in computer science. Yet, discrete versions of these recurrences still present some challenges. The discrete nature of this recurrence (represented by quantization) introduces certain oscillations not captured by the traditional Master Theorem of divide and conquer recurrence, for example due to Akra and Bazzi who primary studied the continuous version of the recurrence. We show how powerful techniques such as Dirichlet series, Mellin-Perron formula, and (extended) Tauberian theorems of Wiener-Ikehara can be used to provide a complete and precise solution to this basic computer science recurrence. We illustrate applicability of our results on several examples including a popular and fast arithmetic coding algorithm due to Boncelet for which we estimate its average redundancy and prove the Central Limit Theorem for the phrase length. This allows us to compare the redundancy of Boncelet's algorithm to the (asymptotically) optimal Tunstall scheme. Join work with M. Drmota (TU Wien)

 [Slides.pdf]


Dernière modification : mercredi 06 juillet 2011 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr