Burgisser, P., University of Zurich, Switzerland
2000. Approx. 170 pp., 16 figs.
3-540-66752-0
The theory of NP-completeness is a cornerstone
of computational
complexity. This monograph
provides a thorough and comprehensive treatment
of this concept
in the framework of algebraic
complexity theory. Many of the results presented
are new and
published for the first time. Topics
include: complete treatment of Valiant's
algebraic theory of
NP-completeness, interrelations with
the classical theory as well as the Blum-Shub-Smale
model of
computation, questions of structural
complexity, fast evaluation of representations
of general linear
groups, and complexity of
immanants. The book can be used at the advanced
undergraduate or
at the beginning graduate
level in either mathematics or computer science.
Keywords: complexity, NP-completeness
Contents: 1. Introduction.- 2. Valiant's
Algebraic Model of
NP-Completeness.- 3. Some Complete
Families of Polynomials.- 4. Cook's versus
Valiant's Hypothesis.-
5. The Structure of Valiant's
Complexity Classes.- 6. Fast Evaluation of
Representations of
General Linear Groups.- 7. The
Complexity of Immanants.- 8. Separation Results
and Future
Directions.- References.- List of
Notations.- Index
Series: Algorithms and Computation in Mathematics.VOL.
7
@
Pomerance, C., University of Georgia, Athens,
GA, USA
Crandall, R., Portland, OR, USA
A Computational Perspective
2000. Approx. 350 pp. 13 figs., 10 in color.
0-387-94777-9
Destined to become a definitive textbook
conveying the most
modern computational ideas about
prime numbers and factoring, this book will
stand as an excellent
reference for this kind of
computation, and thus be of interest to both
educators and
researchers. It is also a timely book,
since primes and factoring have reached a
certain vogue, partly
because of cryptography. The final
chapter focusses on "applications"
of prime numbers,
incorporating the mathematics of finance,
via
quasi-Monte Carlo theory. Historical comments
are contained in
every chapter.
Contents: The World of Prime Numbers; Fundamental
Algorithms;
Useful Algorithms; Recognizing
Primes and Composites; Primality Proving;
Exponential Factoring
Algorithms; Sub-Exponential
Factoring Algorithms; Applications of Prime
Numbers; Sparse Bit
Matrices; Appendix
Edited by: Werner Haussmann
Kurt Jetter
Manfred Reimer
ISBN: 3-527-40236-5
Hardcover
Pages: 334
Published: Oct 1999
Copyright: 1999
Imprint: A Wiley-VCH Publication
This book details the results of the 3rd
International Conference
on Multivariate Approximation organized by
the University of
Dortmund in 1998. Like all volumes in this
series, the book
provides communications links between the
various special groups
within
mathematics.
Table of Contents
Problems of Approximation Theory in Discrete
Geometry (N. Andreev
& V. Yudin).
Dense Vector Spaces of Universal Harmonic
Functions (D.
Armitage).
Best One-sided L1-Approximation by Harmonic
and Subharmonic
Functions (D. Armitage & S. Gardiner).
Numerical Stability of Fast Fourier Transforms
(G. Baszenski, et
al.).
The Saturation Theorem for Box Spline Orthogonal
Projection (M.
Bes\aaka & K. Dziedziul).
Problem on Monotonic Behaviour of Bernstein
Operators (M.
Bes\aaka & K. Dziedziul).
Best One-Sided L1-Approximation by Blending
Functions (B.
Bojanov, et al.).
On the Asymptotics of Points which Maximize
Determinants of the
Form det [g(\p8vxi - xj\p8v)] (L. Bos &
U. Maier).
Besov Regularity for the Stokes Problem (S.
Dahlke).
Optimal Periodic Interpolation in Multivariate
Periodic Hilbert
Spaces (F.-J. Delvos).
Multiscale Modelling from Geopotential Data
(W. Freeden, et al.).
On a Family of Orthogonal Wavelets on the
Quincunx Grid: Open
Regularity Questions (A. Gottscheber &
G. Steidl).
Average Case Analysis of Numerical Integration
(P. Grabner, et
al.).
Cubature Formulas on Spheres (H. König).
Numerical Calculation of Spherical Designs
(U. Maier).
On Bivariate Spline Spaces (G. NEnberger
& F. Zeilfelder).
Spherical Polynomial Approximations: A Survey
(M. Reimer).
Range Restricted Interpolation by Cubic C1-Splines
on
Clough-Tocher Splits (J. Schmidt).
Some Error Estimates for Periodic Interpolation
of Functions from
Besov Spaces (W. Sickel & F. Sprengel).
The Uniform Error of Hyperinterpolation on
the Sphere (I. Sloan
& R. Womersley).
Simultaneous Approximation in the Dirichlet
Space (A. Stray).
The Equivalence between Weighted K-Functionals
and Moduli of
Smoothness on a Simplex and their Applications
(P.-C. Xuan).
@
Rio, E., Universite Paris Sud, Orsay, France
2000. XII, 170 p.
3-540-65979-X
Ces notes sont consacrees aux inegalites
et aux theoremeses limites classiques pour
les suites de
variables aleatoires absolument regulieres
ou fortement melangeantes au sens de Rosenblatt.
Le
but poursuivi est de donner des outils techniques
pour l'etude des processus faiblement
dependants aux statisticiens ou aux probabilistes
travaillant sur ces processus. Nos resultats
et
nos preuves sont essentiellement fond sur
des inegalites de covariance et des lemmes
de
couplage parfois recents, que nous appliquons
pour obtenir des theoremes limites classiques
tels
que la loi forte des grands nombres avec
ou sans vitesses de convergence, le theoreme
limite
central et le theoreme limite central fonctionnel
pour les sommes partielles normalisees, la
loi du
logarithme itere, l'etude des processus empiriques.
Enfin nous donnons quelques resultats
theoriques sur les relations entre la vitesse
d'ergodicite et la vitesse de melange fort
des chaaines
de Markov irreductibles.
Keywords: strongly mixing sequences, absolutely
regular sequences, covariance inequalities,
coupling, central limit theorem
Contents: Variance des sommes partielles.-
Moments algebriques. Premieres inegalites
exponentielles.- Inegalites maximales et
lois fortes.- Le theoreme limite central.-
Couplage et
melange.- Inegalites de Fuk-Nagaev, moments
d'ordre quelconque.- Fonction de repartition
empirique.- Processus empiriques indexes
par des classes de fonctions.- Chaines de
Markov
irreductibles.- Annexes.
Series: Mathematiques & Applications.VOL.
31
Chalmond, B., Ecole Normale Superieure de Cachan, France
2000. XVIII, 331 p.
3-540-66563-3
Cet ouvrage decrit une methodologie et un
savoir-faire pour la construction effective
de modeles en
analyse d'images. Les taches d'imagerie y
sont le plus souvent formalisees comme des
problemes
inverses solutionnes dans un cadre Bayesien.
Ce livre est organise en 3 parties. Les 2
premieres
decrivent les bases necessaires aux modeles
developpes dans la troisieme partie sous
la forme d'
d'energie. Ces bases sont les splines et
les champs aleatoires. La plupart des modeles
sont issus
de projets industriels auxquels l'auteur
a participe en radiographie et en controle
non desttructif:
suivi de lignes 3D, traitement de degradation
en radiographie, reconstruction 3D et tomographie,
mise en correspondance, apprentissage de
deformations. De nombreuses illustrations
graphiques
accompagnent le texte montrant les performances
des modeles proposes.
Keywords: analyse d ' image Problemes inverses
approximation spline champs de Markov
radiographie
Contents: Introduction.- A propos de modelisation.-
Structure de l'ouvrage.- Modeles splines:
Modeles splines non parametriques.- Modeles
splines parametriques.- Modeles auto-associatifs.-
Modeles markoviens: Aspects fondamentaux.-
Estimation bayesienne.- Estimation et
optimisation.- Estimation des parametres.-
Modelisation en action: Construction de modele.-
Degradation en imagerie.- Detection d'entites
filiformes.- Reconstruction et projections.-
Reconstruction regularisee.- Reconstruction
avec une seule vue.- Mise en correspondance.
Series: Mathematiques & Applications.VOL.
33