Le rapport entre le temps et l'espace pour l'évaluation des polynômes

✍ Scribed by Mikel Aldaz; Joos Heintz; Guillermo Matera; José Luis Montaña; Luis Miguel Pardo

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 491 KB
• Volume: 327
• Category: Article
• ISSN: 0764-4442
• DOI: 10.1016/s0764-4442(99)80042-1

✦ Synopsis

RCsumC.

We develop a new method for showing lower bounds for the time-space tradeoff of polynomial evaluation procedures given by straight-line programs. By means of this method we prove an asymptotically sharp lower bound for the time-space tradeoff of general procedures of polynomial evaluation and exhibit specific families of univariate polynomials where this bound is reached. 0 AcadCmie des SciencesiElsevier, Paris Le rapport entre le temps et l'espace pour l'&aluation des polynhnes Nous pr&entons une mkthode qui nous permet pour la premikre fois d'exhiber des bornes infe'rirures optimales pour le rapport entre Ee temps et l'espace lors de I'e'vuluation de polynlimes en une variable. A /'aide de cette mkthode nous obtenons une estimation asymptotiquement exacte de ce rapport duns le cas des polyn8mes gtWriques. Nous rle'terminons aussi le rapport entre le temps de calcul et l'espace de m&moire pour certaines ,familles explicites de pol.yn6me.s. 0 Acadkmie des SciencesIElsevier, Paris Version frangaise abdgke On &udie le rapport entre le temps de calcul et l'espace de m&moire dans les procCdures (numkiques) d'kvaluation des polyn6mes en une variable. Notre approche est fond&e sur le modkle thkorique des circuits arithmktiques et sur les jeux de jetons (CC pebble games D) dans les graphes orient& acycliques. Un circuit arithm&ique (represent& par un graphe acyclique) muni d'un jeu de jetons est appelC un calcul d'tvaluation ou << straight-line program >F (voir [2]). Note prksentke par Gilles KAHN.