Combinatorial Techniques in Computer Science
Identifieur interne : 00DC88 ( Main/Curation ); précédent : 00DC87; suivant : 00DC89Combinatorial Techniques in Computer Science
Auteurs : R. SchottSource :
- Bulletin de la Société Mathématique de Belgique ; 1990.
English descriptors
Abstract
Combinatorial techniques became growing interest in computer science during the last decade. D.E. Knuth showed that several problems arising in algorithms design and analysis can only been solved with the help of sophisticated mathematical tools. In general, simulation techniques are not relevant since time and space performances must be given for large sized data structures. Exact enumeration formula are necessary for the average case analysis but also for the design of algorithms (example\, : uniform generation of binary trees). We show through several examples how\, : \begin{itemize} \item[-]The continued fraction and orthogonal polynomials theories can be successfully applied in dynamic algorithms analysis. \item[-]The symbolic computation techniques developed recently by P. Flajolet and al. work. They are the basic tools for the automatic enumeration of combinatorial structures. \item[-]Dershowitz - Zaks formula permits easily the enumeration of large classes of trees. \end{itemize} Finally we mention some open chalenging combinatorial problems arising in computer science.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000983
- to stream Crin, to step Curation: Pour aller vers cette notice dans l'étape Curation :000983
- to stream Crin, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :003C33
- to stream Main, to step Merge: Pour aller vers cette notice dans l'étape Curation :00E568
Links to Exploration step
CRIN:schott90cLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="248">Combinatorial Techniques in Computer Science</title></titleStmt><publicationStmt><idno type="RBID">CRIN:schott90c</idno><date when="1990" year="1990">1990</date><idno type="wicri:Area/Crin/Corpus">000983</idno><idno type="wicri:Area/Crin/Curation">000983</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">000983</idno><idno type="wicri:Area/Crin/Checkpoint">003C33</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">003C33</idno><idno type="wicri:Area/Main/Merge">00E568</idno><idno type="wicri:Area/Main/Curation">00DC88</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Combinatorial Techniques in Computer Science</title><author><name sortKey="Schott, R" sort="Schott, R" uniqKey="Schott R" first="R." last="Schott">R. Schott</name></author></analytic><series><title level="j">Bulletin de la Société Mathématique de Belgique</title><imprint><date when="1990" type="published">1990</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>analysis</term><term>continued fractions</term><term>data structures</term><term>symbolic calculation</term><term>trees</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="3740">Combinatorial techniques became growing interest in computer science during the last decade. D.E. Knuth showed that several problems arising in algorithms design and analysis can only been solved with the help of sophisticated mathematical tools. In general, simulation techniques are not relevant since time and space performances must be given for large sized data structures. Exact enumeration formula are necessary for the average case analysis but also for the design of algorithms (example\, : uniform generation of binary trees). We show through several examples how\, : \begin{itemize} \item[-]The continued fraction and orthogonal polynomials theories can be successfully applied in dynamic algorithms analysis. \item[-]The symbolic computation techniques developed recently by P. Flajolet and al. work. They are the basic tools for the automatic enumeration of combinatorial structures. \item[-]Dershowitz - Zaks formula permits easily the enumeration of large classes of trees. \end{itemize} Finally we mention some open chalenging combinatorial problems arising in computer science.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00DC88 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Curation/biblio.hfd -nk 00DC88 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Curation
|type= RBID
|clé= CRIN:schott90c
|texte= Combinatorial Techniques in Computer Science
}}
| This area was generated with Dilib version V0.6.33. |  |