Analysis of Dynamic Algorithms in D.E. Knuth's Model
Identifieur interne : 000842 ( Crin/Corpus ); précédent : 000841; suivant : 000843Analysis of Dynamic Algorithms in D.E. Knuth's Model
Auteurs : J. Françon ; B. Randrianarimanana ; R. SchottSource :
- Theoretical Computer Science ; 1990.
English descriptors
- KwdEn :
Abstract
This paper analyses the average behaviour of algorithms that operate on dynamically varying data structures subject to insertions I, deletions D, positive (resp. negative) queries Q^{+} (resp.Q^{.} under the following assumptions\, : if the size of the data structure is k (k \in N), then the number of possibilities for the operations D and Q^{+} is a linear function of k, whereas the number of possibilities for the i-th insertion or negative query is equal to i. This statistical model was introduced by J. Françon and D.E. Knuth and differes from the model used in previous analyses. Integrated costs for these dynamic structures are defined as averages of costs taken over the set of all their possible histories (i.e. evolutions considered up to order isomorphism) of lenght n. We show that the costs can be calculated for the data structures serving as implementations of linear lists, priority queues and dictionaries. The problem of finding the limiting distributions is also considered and the linear list case is treated in detail. The method uses continued fractions and orthogonal polynomials but in a paper in preparation, we show that the same results can be recovered with the help of a probabilistic model.
Links to Exploration step
CRIN:francon90aLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="274">Analysis of Dynamic Algorithms in D.E. Knuth's Model</title></titleStmt><publicationStmt><idno type="RBID">CRIN:francon90a</idno><date when="1990" year="1990">1990</date><idno type="wicri:Area/Crin/Corpus">000842</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Analysis of Dynamic Algorithms in D.E. Knuth's Model</title><author><name sortKey="Francon, J" sort="Francon, J" uniqKey="Francon J" first="J." last="Françon">J. Françon</name></author><author><name sortKey="Randrianarimanana, B" sort="Randrianarimanana, B" uniqKey="Randrianarimanana B" first="B." last="Randrianarimanana">B. Randrianarimanana</name></author><author><name sortKey="Schott, R" sort="Schott, R" uniqKey="Schott R" first="R." last="Schott">R. Schott</name></author></analytic><series><title level="j">Theoretical Computer Science</title><imprint><date when="1990" type="published">1990</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Knuth's model</term><term>continued fractions</term><term>dynamic algorithms</term><term>limiting profiles</term><term>orthogonal polynomials</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="2173">This paper analyses the average behaviour of algorithms that operate on dynamically varying data structures subject to insertions I, deletions D, positive (resp. negative) queries Q^{+} (resp.Q^{.} under the following assumptions\, : if the size of the data structure is k (k \in N), then the number of possibilities for the operations D and Q^{+} is a linear function of k, whereas the number of possibilities for the i-th insertion or negative query is equal to i. This statistical model was introduced by J. Françon and D.E. Knuth and differes from the model used in previous analyses. Integrated costs for these dynamic structures are defined as averages of costs taken over the set of all their possible histories (i.e. evolutions considered up to order isomorphism) of lenght n. We show that the costs can be calculated for the data structures serving as implementations of linear lists, priority queues and dictionaries. The problem of finding the limiting distributions is also considered and the linear list case is treated in detail. The method uses continued fractions and orthogonal polynomials but in a paper in preparation, we show that the same results can be recovered with the help of a probabilistic model.</div></front></TEI><BibTex type="article"><ref>francon90a</ref><crinnumber>89-R-164</crinnumber><category>1</category><equipe>EURECA</equipe><author><e>Françon, J.</e><e>Randrianarimanana, B.</e><e>Schott, R.</e></author><title>Analysis of Dynamic Algorithms in D.E. Knuth's Model</title><journal>Theoretical Computer Science</journal><year>1990</year><volume>72</volume><number>2,3</number><pages>147-167</pages><month>May</month><keywords><e>dynamic algorithms</e><e>Knuth's model</e><e>continued fractions</e><e>orthogonal polynomials</e><e>limiting profiles</e></keywords><abstract>This paper analyses the average behaviour of algorithms that operate on dynamically varying data structures subject to insertions I, deletions D, positive (resp. negative) queries Q^{+} (resp.Q^{.} under the following assumptions\, : if the size of the data structure is k (k \in N), then the number of possibilities for the operations D and Q^{+} is a linear function of k, whereas the number of possibilities for the i-th insertion or negative query is equal to i. This statistical model was introduced by J. Françon and D.E. Knuth and differes from the model used in previous analyses. Integrated costs for these dynamic structures are defined as averages of costs taken over the set of all their possible histories (i.e. evolutions considered up to order isomorphism) of lenght n. We show that the costs can be calculated for the data structures serving as implementations of linear lists, priority queues and dictionaries. The problem of finding the limiting distributions is also considered and the linear list case is treated in detail. The method uses continued fractions and orthogonal polynomials but in a paper in preparation, we show that the same results can be recovered with the help of a probabilistic model.</abstract></BibTex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Crin/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000842 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Crin/Corpus/biblio.hfd -nk 000842 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Crin
|étape= Corpus
|type= RBID
|clé= CRIN:francon90a
|texte= Analysis of Dynamic Algorithms in D.E. Knuth's Model
}}
| This area was generated with Dilib version V0.6.33. |  |