Dynamic algorithms in D.E. Knuth's model: A probabilistic analysis
Identifieur interne : 003027 ( Istex/Corpus ); précédent : 003026; suivant : 003028Dynamic algorithms in D.E. Knuth's model: A probabilistic analysis
Auteurs : G. Louchard ; B. Randrianarimanana ; R. SchottSource :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: By dynamic algorithms, we mean algorithms that operate on dynamically varying data structures (dictionaries, priority queues, linear lists) subject to insertions I, deletions D, positive (resp. negative) queries Q+ (resp. Q−). Let us remember that dictionaries are implementable by unsorted or sorted lists, binary search trees, priority queues by sorted lists, binary search trees, binary tournaments, pagodas, binomial queues and linear lists by sorted or unsorted lists etc. At this point the following question is very natural in computer science: for a given data structure which representation is the most efficient? In comparing the space or time costs of two data organizations A and B for the same operations, we cannot merely compare the costs of individual operations for data of given sizes: A may be better than B on some data, and conversely on others. A reasonable way to measure the efficiency of a data organization is to consider sequences of operations on the structure. J. Françon [6], [7] and D.E. Knuth [12] discovered that the number of possibilities for the i-th insertion or negative query is equal to i but that for deletions and positive queries this number depends of the size of the data structure. Answering the questions raised in [6], [7] and [12] is the main object of this paper. More precisely we show: i) how to compute explicitely the average costs, ii) how to obtain variance estimates, iii) that the costs converge as n→∞ to random variables either Gaussian or depending on Brownian Excursions functionals (the limiting distributions are therefore completely described). At our knowledge such a complete analysis has never been done before for dynamic algorithms in Knuth's model.
Url:
DOI: 10.1007/BFb0035781
Links to Exploration step
ISTEX:CB569FDADC0F6DAD8F5A62C8345B71B4BB6FAEE2Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Dynamic algorithms in D.E. Knuth's model: A probabilistic analysis</title><author><name sortKey="Louchard, G" sort="Louchard, G" uniqKey="Louchard G" first="G." last="Louchard">G. Louchard</name><affiliation><mods:affiliation>Laboratoire d'Informatique Théorique, Université Libre de Bruxelles, B-1050, Brussels, Belgium</mods:affiliation></affiliation></author><author><name sortKey="Randrianarimanana, B" sort="Randrianarimanana, B" uniqKey="Randrianarimanana B" first="B." last="Randrianarimanana">B. Randrianarimanana</name><affiliation><mods:affiliation>C.R.I.N. Université Nancy 1, 54506, Vandoeuvre-lès-Nancy, France</mods:affiliation></affiliation></author><author><name sortKey="Schott, R" sort="Schott, R" uniqKey="Schott R" first="R." last="Schott">R. Schott</name><affiliation><mods:affiliation>C.R.I.N. Université Nancy 1, 54506, Vandoeuvre-lès-Nancy, France</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:CB569FDADC0F6DAD8F5A62C8345B71B4BB6FAEE2</idno><date when="1989" year="1989">1989</date><idno type="doi">10.1007/BFb0035781</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-THTN10PP-R/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">003027</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003027</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Dynamic algorithms in D.E. Knuth's model: A probabilistic analysis</title><author><name sortKey="Louchard, G" sort="Louchard, G" uniqKey="Louchard G" first="G." last="Louchard">G. Louchard</name><affiliation><mods:affiliation>Laboratoire d'Informatique Théorique, Université Libre de Bruxelles, B-1050, Brussels, Belgium</mods:affiliation></affiliation></author><author><name sortKey="Randrianarimanana, B" sort="Randrianarimanana, B" uniqKey="Randrianarimanana B" first="B." last="Randrianarimanana">B. Randrianarimanana</name><affiliation><mods:affiliation>C.R.I.N. Université Nancy 1, 54506, Vandoeuvre-lès-Nancy, France</mods:affiliation></affiliation></author><author><name sortKey="Schott, R" sort="Schott, R" uniqKey="Schott R" first="R." last="Schott">R. Schott</name><affiliation><mods:affiliation>C.R.I.N. Université Nancy 1, 54506, Vandoeuvre-lès-Nancy, France</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><title level="s" type="abbrev">Lect Notes Comput Sci</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: By dynamic algorithms, we mean algorithms that operate on dynamically varying data structures (dictionaries, priority queues, linear lists) subject to insertions I, deletions D, positive (resp. negative) queries Q+ (resp. Q−). Let us remember that dictionaries are implementable by unsorted or sorted lists, binary search trees, priority queues by sorted lists, binary search trees, binary tournaments, pagodas, binomial queues and linear lists by sorted or unsorted lists etc. At this point the following question is very natural in computer science: for a given data structure which representation is the most efficient? In comparing the space or time costs of two data organizations A and B for the same operations, we cannot merely compare the costs of individual operations for data of given sizes: A may be better than B on some data, and conversely on others. A reasonable way to measure the efficiency of a data organization is to consider sequences of operations on the structure. J. Françon [6], [7] and D.E. Knuth [12] discovered that the number of possibilities for the i-th insertion or negative query is equal to i but that for deletions and positive queries this number depends of the size of the data structure. Answering the questions raised in [6], [7] and [12] is the main object of this paper. More precisely we show: i) how to compute explicitely the average costs, ii) how to obtain variance estimates, iii) that the costs converge as n→∞ to random variables either Gaussian or depending on Brownian Excursions functionals (the limiting distributions are therefore completely described). At our knowledge such a complete analysis has never been done before for dynamic algorithms in Knuth's model.</div></front></TEI><istex><corpusName>springer-ebooks</corpusName><author><json:item><name>G. Louchard</name><affiliations><json:string>Laboratoire d'Informatique Théorique, Université Libre de Bruxelles, B-1050, Brussels, Belgium</json:string></affiliations></json:item><json:item><name>B. Randrianarimanana</name><affiliations><json:string>C.R.I.N. Université Nancy 1, 54506, Vandoeuvre-lès-Nancy, France</json:string></affiliations></json:item><json:item><name>R. Schott</name><affiliations><json:string>C.R.I.N. Université Nancy 1, 54506, Vandoeuvre-lès-Nancy, France</json:string></affiliations></json:item></author><arkIstex>ark:/67375/HCB-THTN10PP-R</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>ReviewPaper</json:string></originalGenre><abstract>Abstract: By dynamic algorithms, we mean algorithms that operate on dynamically varying data structures (dictionaries, priority queues, linear lists) subject to insertions I, deletions D, positive (resp. negative) queries Q+ (resp. Q−). Let us remember that dictionaries are implementable by unsorted or sorted lists, binary search trees, priority queues by sorted lists, binary search trees, binary tournaments, pagodas, binomial queues and linear lists by sorted or unsorted lists etc. At this point the following question is very natural in computer science: for a given data structure which representation is the most efficient? In comparing the space or time costs of two data organizations A and B for the same operations, we cannot merely compare the costs of individual operations for data of given sizes: A may be better than B on some data, and conversely on others. A reasonable way to measure the efficiency of a data organization is to consider sequences of operations on the structure. J. Françon [6], [7] and D.E. Knuth [12] discovered that the number of possibilities for the i-th insertion or negative query is equal to i but that for deletions and positive queries this number depends of the size of the data structure. Answering the questions raised in [6], [7] and [12] is the main object of this paper. More precisely we show: i) how to compute explicitely the average costs, ii) how to obtain variance estimates, iii) that the costs converge as n→∞ to random variables either Gaussian or depending on Brownian Excursions functionals (the limiting distributions are therefore completely described). At our knowledge such a complete analysis has never been done before for dynamic algorithms in Knuth's model.</abstract><qualityIndicators><refBibsNative>false</refBibsNative><abstractWordCount>276</abstractWordCount><abstractCharCount>1729</abstractCharCount><keywordCount>0</keywordCount><score>9.614</score><pdfWordCount>4614</pdfWordCount><pdfCharCount>22291</pdfCharCount><pdfVersion>1.3</pdfVersion><pdfPageCount>13</pdfPageCount><pdfPageSize>468 x 684 pts</pdfPageSize></qualityIndicators><title>Dynamic algorithms in D.E. Knuth's model: A probabilistic analysis</title><chapterId><json:string>34</json:string><json:string>Chap34</json:string></chapterId><genre><json:string>conference</json:string></genre><serie><title>Lecture Notes in Computer Science</title><language><json:string>unknown</json:string></language><copyrightDate>1989</copyrightDate><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn><editor><json:item><name>G. Goos</name></json:item><json:item><name>J. Hartmanis</name></json:item><json:item><name>D. Barstow</name></json:item><json:item><name>W. Brauer</name></json:item><json:item><name>P. Brinch Hansen</name></json:item><json:item><name>D. Gries</name></json:item><json:item><name>D. Luckham</name></json:item><json:item><name>C. Moler</name></json:item><json:item><name>A. Pnueli</name></json:item><json:item><name>G. Seegmüller</name></json:item><json:item><name>J. Stoer</name></json:item><json:item><name>N. Wirth</name></json:item></editor></serie><host><title>Automata, Languages and Programming</title><language><json:string>unknown</json:string></language><copyrightDate>1989</copyrightDate><doi><json:string>10.1007/BFb0035746</json:string></doi><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn><eisbn><json:string>978-3-540-46201-9</json:string></eisbn><bookId><json:string>3-540-51371-X</json:string></bookId><isbn><json:string>978-3-540-51371-1</json:string></isbn><volume>372</volume><pages><first>521</first><last>533</last></pages><genre><json:string>book-series</json:string></genre><editor><json:item><name>Giorgio Ausiello</name></json:item><json:item><name>Mariangiola Dezani-Ciancaglini</name></json:item><json:item><name>Simonetta Ronchi Della Rocca</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Mathematical Logic and Formal Languages</value></json:item><json:item><value>Logics and Meanings of Programs</value></json:item><json:item><value>Computation by Abstract Devices</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Combinatorics</value></json:item><json:item><value>Processor Architectures</value></json:item></subject></host><ark><json:string>ark:/67375/HCB-THTN10PP-R</json:string></ark><publicationDate>1989</publicationDate><copyrightDate>1989</copyrightDate><doi><json:string>10.1007/BFb0035781</json:string></doi><id>CB569FDADC0F6DAD8F5A62C8345B71B4BB6FAEE2</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-THTN10PP-R/fulltext.pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-THTN10PP-R/bundle.zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/HCB-THTN10PP-R/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Dynamic algorithms in D.E. Knuth's model: A probabilistic analysis</title></titleStmt><publicationStmt><authority>ISTEX</authority><availability><licence>Springer-Verlag</licence></availability><date when="1989">1989</date></publicationStmt><notesStmt><note type="conference" source="proceedings" scheme="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</note><note type="publication-type" subtype="book-series" scheme="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</note></notesStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Dynamic algorithms in D.E. Knuth's model: A probabilistic analysis</title><author><persName><forename type="first">G.</forename><surname>Louchard</surname></persName><affiliation><orgName type="department">Laboratoire d'Informatique Théorique</orgName><orgName type="institution">Université Libre de Bruxelles</orgName><address><postCode>B-1050</postCode><settlement>Brussels</settlement><country key="BE">BELGIUM</country></address></affiliation></author><author><persName><forename type="first">B.</forename><surname>Randrianarimanana</surname></persName><affiliation><orgName type="institution">C.R.I.N. Université Nancy 1</orgName><address><postCode>54506</postCode><settlement>Vandoeuvre-lès-Nancy</settlement><country key="FR">FRANCE</country></address></affiliation></author><author><persName><forename type="first">R.</forename><surname>Schott</surname></persName><affiliation><orgName type="institution">C.R.I.N. Université Nancy 1</orgName><address><postCode>54506</postCode><settlement>Vandoeuvre-lès-Nancy</settlement><country key="FR">FRANCE</country></address></affiliation></author><idno type="istex">CB569FDADC0F6DAD8F5A62C8345B71B4BB6FAEE2</idno><idno type="ark">ark:/67375/HCB-THTN10PP-R</idno><idno type="DOI">10.1007/BFb0035781</idno></analytic><monogr><title level="m" type="main">Automata, Languages and Programming</title><title level="m" type="sub">16th International Colloquium Stresa, Italy, July 11–15, 1989 Proceedings</title><idno type="DOI">10.1007/BFb0035746</idno><idno type="book-id">3-540-51371-X</idno><idno type="ISBN">978-3-540-51371-1</idno><idno type="eISBN">978-3-540-46201-9</idno><idno type="chapter-id">Chap34</idno><editor><persName><forename type="first">Giorgio</forename><surname>Ausiello</surname></persName></editor><editor><persName><forename type="first">Mariangiola</forename><surname>Dezani-Ciancaglini</surname></persName></editor><editor><persName><forename type="first">Simonetta</forename><forename type="first">Ronchi</forename><nameLink>Della</nameLink><surname>Rocca</surname></persName></editor><imprint><biblScope unit="vol">372</biblScope><biblScope unit="page" from="521">521</biblScope><biblScope unit="page" to="533">533</biblScope><biblScope unit="chapter-count">51</biblScope></imprint></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><title level="s" type="abbrev">Lect Notes Comput Sci</title><editor><persName><forename type="first">G.</forename><surname>Goos</surname></persName></editor><editor><persName><forename type="first">J.</forename><surname>Hartmanis</surname></persName></editor><editor><persName><forename type="first">D.</forename><surname>Barstow</surname></persName></editor><editor><persName><forename type="first">W.</forename><surname>Brauer</surname></persName></editor><editor><persName><forename type="first">P.</forename><forename type="first">Brinch</forename><surname>Hansen</surname></persName></editor><editor><persName><forename type="first">D.</forename><surname>Gries</surname></persName></editor><editor><persName><forename type="first">D.</forename><surname>Luckham</surname></persName></editor><editor><persName><forename type="first">C.</forename><surname>Moler</surname></persName></editor><editor><persName><forename type="first">A.</forename><surname>Pnueli</surname></persName></editor><editor><persName><forename type="first">G.</forename><surname>Seegmüller</surname></persName></editor><editor><persName><forename type="first">J.</forename><surname>Stoer</surname></persName></editor><editor><persName><forename type="first">N.</forename><surname>Wirth</surname></persName></editor><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="seriesID">558</idno></series></biblStruct></sourceDesc></fileDesc><profileDesc><abstract xml:lang="en"><head>Abstract</head><p>By dynamic algorithms, we mean algorithms that operate on dynamically varying data structures (dictionaries, priority queues, linear lists) subject to insertions I, deletions D, positive (resp. negative) queries Q<hi rend="superscript">+</hi> (resp. Q<hi rend="superscript">−</hi>). Let us remember that <hi rend="italic">dictionaries</hi> are implementable by unsorted or sorted lists, binary search trees, <hi rend="italic">priority queues</hi> by sorted lists, binary search trees, binary tournaments, pagodas, binomial queues and <hi rend="italic">linear lists</hi> by sorted or unsorted lists etc. At this point the following question is very natural in computer science: for a given data structure which representation is the most efficient? In comparing the space or time costs of two data organizations A and B for the same operations, we cannot merely compare the costs of individual operations for data of given sizes: A may be better than B on some data, and conversely on others. A reasonable way to measure the efficiency of a data organization is to consider sequences of operations on the structure. J. Françon [6], [7] and D.E. Knuth [12] discovered that the number of possibilities for the i-th insertion or negative query is equal to i but that for deletions and positive queries this number depends of the size of the data structure. Answering the questions raised in [6], [7] and [12] is the main object of this paper. More precisely we show:<list type="ordered"><item n="i)"><p>how to compute explicitely the <hi rend="italic">average costs</hi>,</p></item><item n="ii)"><p>how to obtain <hi rend="italic">variance estimates</hi>,</p></item><item n="iii)"><p>that the <hi rend="italic">costs converge</hi> as n→∞ to random variables either <hi rend="italic">Gaussian</hi> or depending on <hi rend="italic">Brownian Excursions functionals</hi> (the limiting distributions are therefore completely described). At our knowledge such a complete analysis has never been done before for dynamic algorithms in Knuth's model.</p></item></list></p></abstract><textClass ana="subject"><keywords scheme="book-subject-collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass ana="subject"><keywords scheme="book-subject"><list><label>I</label><item><term type="Primary">Computer Science</term></item><label>I16048</label><item><term type="Secondary" subtype="priority-1">Mathematical Logic and Formal Languages</term></item><label>I1603X</label><item><term type="Secondary" subtype="priority-2">Logics and Meanings of Programs</term></item><label>I16013</label><item><term type="Secondary" subtype="priority-3">Computation by Abstract Devices</term></item><label>I16021</label><item><term type="Secondary" subtype="priority-4">Algorithm Analysis and Problem Complexity</term></item><label>M17009</label><item><term type="Secondary" subtype="priority-5">Combinatorics</term></item><label>I13014</label><item><term type="Secondary" subtype="priority-6">Processor Architectures</term></item></list></keywords></textClass><langUsage><language ident="EN"></language></langUsage></profileDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-THTN10PP-R/fulltext.txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="corpus springer-ebooks not found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle><SeriesAbbreviatedTitle>Lect Notes Comput Sci</SeriesAbbreviatedTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>G.</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>J.</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>D.</GivenName><FamilyName>Barstow</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>W.</GivenName><FamilyName>Brauer</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>P.</GivenName><GivenName>Brinch</GivenName><FamilyName>Hansen</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>D.</GivenName><FamilyName>Gries</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>D.</GivenName><FamilyName>Luckham</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>C.</GivenName><FamilyName>Moler</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>A.</GivenName><FamilyName>Pnueli</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>G.</GivenName><FamilyName>Seegmüller</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>J.</GivenName><FamilyName>Stoer</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>N.</GivenName><FamilyName>Wirth</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo MediaType="eBook" Language="En" BookProductType="Proceedings" TocLevels="0" NumberingStyle="Unnumbered"><BookID>3-540-51371-X</BookID><BookTitle>Automata, Languages and Programming</BookTitle><BookSubTitle>16th International Colloquium Stresa, Italy, July 11–15, 1989 Proceedings</BookSubTitle><BookVolumeNumber>372</BookVolumeNumber><BookDOI>10.1007/BFb0035746</BookDOI><BookTitleID>24389</BookTitleID><BookPrintISBN>978-3-540-51371-1</BookPrintISBN><BookElectronicISBN>978-3-540-46201-9</BookElectronicISBN><BookChapterCount>51</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1989</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16048" Priority="1" Type="Secondary">Mathematical Logic and Formal Languages</BookSubject><BookSubject Code="I1603X" Priority="2" Type="Secondary">Logics and Meanings of Programs</BookSubject><BookSubject Code="I16013" Priority="3" Type="Secondary">Computation by Abstract Devices</BookSubject><BookSubject Code="I16021" Priority="4" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="M17009" Priority="5" Type="Secondary">Combinatorics</BookSubject><BookSubject Code="I13014" Priority="6" Type="Secondary">Processor Architectures</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Giorgio</GivenName><FamilyName>Ausiello</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Mariangiola</GivenName><FamilyName>Dezani-Ciancaglini</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Simonetta</GivenName><GivenName>Ronchi</GivenName><Particle>Della</Particle><FamilyName>Rocca</FamilyName></EditorName></Editor></EditorGroup></BookHeader><Chapter ID="Chap34" Language="En"><ChapterInfo ChapterType="ReviewPaper" NumberingStyle="Unnumbered" TocLevels="0" ContainsESM="No"><ChapterID>34</ChapterID><ChapterDOI>10.1007/BFb0035781</ChapterDOI><ChapterSequenceNumber>34</ChapterSequenceNumber><ChapterTitle Language="En">Dynamic algorithms in D.E. Knuth's model: A probabilistic analysis</ChapterTitle><ChapterFirstPage>521</ChapterFirstPage><ChapterLastPage>533</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1989</CopyrightYear></ChapterCopyright><ChapterHistory><OnlineDate><Year>2005</Year><Month>11</Month><Day>29</Day></OnlineDate></ChapterHistory><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><BookID>3-540-51371-X</BookID><BookTitle>Automata, Languages and Programming</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>G.</GivenName><FamilyName>Louchard</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>B.</GivenName><FamilyName>Randrianarimanana</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>R.</GivenName><FamilyName>Schott</FamilyName></AuthorName></Author><Affiliation ID="Aff1"><OrgDivision>Laboratoire d'Informatique Théorique</OrgDivision><OrgName>Université Libre de Bruxelles</OrgName><OrgAddress><Postcode>B-1050</Postcode><City>Brussels</City><Country>Belgium</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>C.R.I.N. Université Nancy 1</OrgName><OrgAddress><Postcode>54506</Postcode><City>Vandoeuvre-lès-Nancy</City><Country>France</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>By dynamic algorithms, we mean algorithms that operate on dynamically varying data structures (dictionaries, priority queues, linear lists) subject to insertions I, deletions D, positive (resp. negative) queries Q<Superscript>+</Superscript> (resp. Q<Superscript>−</Superscript>). Let us remember that <Emphasis Type="Italic">dictionaries</Emphasis> are implementable by unsorted or sorted lists, binary search trees, <Emphasis Type="Italic">priority queues</Emphasis> by sorted lists, binary search trees, binary tournaments, pagodas, binomial queues and <Emphasis Type="Italic">linear lists</Emphasis> by sorted or unsorted lists etc. At this point the following question is very natural in computer science: for a given data structure which representation is the most efficient? In comparing the space or time costs of two data organizations A and B for the same operations, we cannot merely compare the costs of individual operations for data of given sizes: A may be better than B on some data, and conversely on others. A reasonable way to measure the efficiency of a data organization is to consider sequences of operations on the structure. J. Françon [6], [7] and D.E. Knuth [12] discovered that the number of possibilities for the i-th insertion or negative query is equal to i but that for deletions and positive queries this number depends of the size of the data structure. Answering the questions raised in [6], [7] and [12] is the main object of this paper. More precisely we show:<OrderedList><ListItem><ItemNumber>i)</ItemNumber><ItemContent><Para>how to compute explicitely the <Emphasis Type="Italic">average costs</Emphasis>,</Para></ItemContent></ListItem><ListItem><ItemNumber>ii)</ItemNumber><ItemContent><Para>how to obtain <Emphasis Type="Italic">variance estimates</Emphasis>,</Para></ItemContent></ListItem><ListItem><ItemNumber>iii)</ItemNumber><ItemContent><Para>that the <Emphasis Type="Italic">costs converge</Emphasis> as n→∞ to random variables either <Emphasis Type="Italic">Gaussian</Emphasis> or depending on <Emphasis Type="Italic">Brownian Excursions functionals</Emphasis> (the limiting distributions are therefore completely described). At our knowledge such a complete analysis has never been done before for dynamic algorithms in Knuth's model.</Para></ItemContent></ListItem></OrderedList></Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Dynamic algorithms in D.E. Knuth's model: A probabilistic analysis</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Dynamic algorithms in D.E. Knuth's model: A probabilistic analysis</title></titleInfo><name type="personal"><namePart type="given">G.</namePart><namePart type="family">Louchard</namePart><affiliation>Laboratoire d'Informatique Théorique, Université Libre de Bruxelles, B-1050, Brussels, Belgium</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">B.</namePart><namePart type="family">Randrianarimanana</namePart><affiliation>C.R.I.N. Université Nancy 1, 54506, Vandoeuvre-lès-Nancy, France</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">R.</namePart><namePart type="family">Schott</namePart><affiliation>C.R.I.N. Université Nancy 1, 54506, Vandoeuvre-lès-Nancy, France</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre displayLabel="ReviewPaper" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" type="conference" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">1989</dateIssued><copyrightDate encoding="w3cdtf">1989</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><abstract lang="en">Abstract: By dynamic algorithms, we mean algorithms that operate on dynamically varying data structures (dictionaries, priority queues, linear lists) subject to insertions I, deletions D, positive (resp. negative) queries Q+ (resp. Q−). Let us remember that dictionaries are implementable by unsorted or sorted lists, binary search trees, priority queues by sorted lists, binary search trees, binary tournaments, pagodas, binomial queues and linear lists by sorted or unsorted lists etc. At this point the following question is very natural in computer science: for a given data structure which representation is the most efficient? In comparing the space or time costs of two data organizations A and B for the same operations, we cannot merely compare the costs of individual operations for data of given sizes: A may be better than B on some data, and conversely on others. A reasonable way to measure the efficiency of a data organization is to consider sequences of operations on the structure. J. Françon [6], [7] and D.E. Knuth [12] discovered that the number of possibilities for the i-th insertion or negative query is equal to i but that for deletions and positive queries this number depends of the size of the data structure. Answering the questions raised in [6], [7] and [12] is the main object of this paper. More precisely we show: i) how to compute explicitely the average costs, ii) how to obtain variance estimates, iii) that the costs converge as n→∞ to random variables either Gaussian or depending on Brownian Excursions functionals (the limiting distributions are therefore completely described). At our knowledge such a complete analysis has never been done before for dynamic algorithms in Knuth's model.</abstract><relatedItem type="host"><titleInfo><title>Automata, Languages and Programming</title><subTitle>16th International Colloquium Stresa, Italy, July 11–15, 1989 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Giorgio</namePart><namePart type="family">Ausiello</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Mariangiola</namePart><namePart type="family">Dezani-Ciancaglini</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Simonetta</namePart><namePart type="given">Ronchi</namePart><namePart type="family">Della Rocca</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</genre><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">1989</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16048">Mathematical Logic and Formal Languages</topic><topic authority="SpringerSubjectCodes" authorityURI="I1603X">Logics and Meanings of Programs</topic><topic authority="SpringerSubjectCodes" authorityURI="I16013">Computation by Abstract Devices</topic><topic authority="SpringerSubjectCodes" authorityURI="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="M17009">Combinatorics</topic><topic authority="SpringerSubjectCodes" authorityURI="I13014">Processor Architectures</topic></subject><identifier type="DOI">10.1007/BFb0035746</identifier><identifier type="ISBN">978-3-540-51371-1</identifier><identifier type="eISBN">978-3-540-46201-9</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">24389</identifier><identifier type="BookID">3-540-51371-X</identifier><identifier type="BookChapterCount">51</identifier><identifier type="BookVolumeNumber">372</identifier><part><date>1989</date><detail type="volume"><number>372</number><caption>vol.</caption></detail><extent unit="pages"><start>521</start><end>533</end></extent></part><recordInfo><recordOrigin>Springer-Verlag, 1989</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">G.</namePart><namePart type="family">Goos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">J.</namePart><namePart type="family">Hartmanis</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">D.</namePart><namePart type="family">Barstow</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">W.</namePart><namePart type="family">Brauer</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">P.</namePart><namePart type="given">Brinch</namePart><namePart type="family">Hansen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">D.</namePart><namePart type="family">Gries</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">D.</namePart><namePart type="family">Luckham</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Moler</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">A.</namePart><namePart type="family">Pnueli</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">G.</namePart><namePart type="family">Seegmüller</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">J.</namePart><namePart type="family">Stoer</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">N.</namePart><namePart type="family">Wirth</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">1989</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag, 1989</recordOrigin></recordInfo></relatedItem><identifier type="istex">CB569FDADC0F6DAD8F5A62C8345B71B4BB6FAEE2</identifier><identifier type="ark">ark:/67375/HCB-THTN10PP-R</identifier><identifier type="DOI">10.1007/BFb0035781</identifier><identifier type="ChapterID">34</identifier><identifier type="ChapterID">Chap34</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag, 1989</accessCondition><recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-RLRX46XW-4">springer</recordContentSource><recordOrigin>Springer-Verlag, 1989</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-THTN10PP-R/record.json</uri></json:item></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003027 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 003027 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:CB569FDADC0F6DAD8F5A62C8345B71B4BB6FAEE2
|texte= Dynamic algorithms in D.E. Knuth's model: A probabilistic analysis
}}
| This area was generated with Dilib version V0.6.33. |  |