Resultado de la búsqueda
28 búsqueda de la palabra clave 'Algorithm'
Refinar búsqueda Generar rss de la búsqueda
Link de la búsqueda
Título : Approximation Algorithms and Semidefinite Programming Tipo de documento: documento electrónico Autores: Bernd Gärtner ; SpringerLink (Online service) ; Jirí Matoušek Editorial: Berlin, Heidelberg : Springer Berlin Heidelberg Fecha de publicación: 2012 Número de páginas: XI, 251 p Il.: online resource ISBN/ISSN/DL: 978-3-642-22015-9 Idioma : Inglés (eng) Palabras clave: Mathematics Computers Algorithms Computer science Applied mathematics Engineering Mathematical optimization Applications of Theory Computation Algorithm Analysis and Problem Complexity Discrete in Science Optimization Clasificación: 51 Matemáticas Resumen: Semidefinite programs constitute one of the largest classes of optimization problems that can be solved with reasonable efficiency - both in theory and practice. They play a key role in a variety of research areas, such as combinatorial optimization, approximation algorithms, computational complexity, graph theory, geometry, real algebraic geometry and quantum computing. This book is an introduction to selected aspects of semidefinite programming and its use in approximation algorithms. It covers the basics but also a significant amount of recent and more advanced material. There are many computational problems, such as MAXCUT, for which one cannot reasonably expect to obtain an exact solution efficiently, and in such case, one has to settle for approximate solutions. For MAXCUT and its relatives, exciting recent results suggest that semidefinite programming is probably the ultimate tool. Indeed, assuming the Unique Games Conjecture, a plausible but as yet unproven hypothesis, it was shown that for these problems, known algorithms based on semidefinite programming deliver the best possible approximation ratios among all polynomial-time algorithms. This book follows the “semidefinite side” of these developments, presenting some of the main ideas behind approximation algorithms based on semidefinite programming. It develops the basic theory of semidefinite programming, presents one of the known efficient algorithms in detail, and describes the principles of some others. It also includes applications, focusing on approximation algorithms Nota de contenido: Part I (by Bernd Gärtner): 1 Introduction: MAXCUT via Semidefinite Programming -- 2 Semidefinite Programming -- 3 Shannon Capacity and Lovász Theta.- 4 Duality and Cone Programming.- 5 Approximately Solving Semidefinite Programs -- 6 An Interior-Point Algorithm for Semidefinite Programming -- 7 Compositive Programming.- Part II (by Jiri Matousek): 8 Lower Bounds for the Goemans–Williamson MAXCUT Algorithm -- 9 Coloring 3-Chromatic Graphs -- 10 Maximizing a Quadratic Form on a Graph -- 11 Colorings With Low Discrepancy -- 12 Constraint Satisfaction Problems, and Relaxing Them Semidefinitely -- 13 Rounding Via Miniatures -- Summary -- References -- Index En línea: http://dx.doi.org/10.1007/978-3-642-22015-9 Link: https://biblioteca.cunef.edu/gestion/catalogo/index.php?lvl=notice_display&id=32919 Approximation Algorithms and Semidefinite Programming [documento electrónico] / Bernd Gärtner ; SpringerLink (Online service) ; Jirí Matoušek . - Berlin, Heidelberg : Springer Berlin Heidelberg, 2012 . - XI, 251 p : online resource.
ISBN : 978-3-642-22015-9
Idioma : Inglés (eng)
Palabras clave: Mathematics Computers Algorithms Computer science Applied mathematics Engineering Mathematical optimization Applications of Theory Computation Algorithm Analysis and Problem Complexity Discrete in Science Optimization Clasificación: 51 Matemáticas Resumen: Semidefinite programs constitute one of the largest classes of optimization problems that can be solved with reasonable efficiency - both in theory and practice. They play a key role in a variety of research areas, such as combinatorial optimization, approximation algorithms, computational complexity, graph theory, geometry, real algebraic geometry and quantum computing. This book is an introduction to selected aspects of semidefinite programming and its use in approximation algorithms. It covers the basics but also a significant amount of recent and more advanced material. There are many computational problems, such as MAXCUT, for which one cannot reasonably expect to obtain an exact solution efficiently, and in such case, one has to settle for approximate solutions. For MAXCUT and its relatives, exciting recent results suggest that semidefinite programming is probably the ultimate tool. Indeed, assuming the Unique Games Conjecture, a plausible but as yet unproven hypothesis, it was shown that for these problems, known algorithms based on semidefinite programming deliver the best possible approximation ratios among all polynomial-time algorithms. This book follows the “semidefinite side” of these developments, presenting some of the main ideas behind approximation algorithms based on semidefinite programming. It develops the basic theory of semidefinite programming, presents one of the known efficient algorithms in detail, and describes the principles of some others. It also includes applications, focusing on approximation algorithms Nota de contenido: Part I (by Bernd Gärtner): 1 Introduction: MAXCUT via Semidefinite Programming -- 2 Semidefinite Programming -- 3 Shannon Capacity and Lovász Theta.- 4 Duality and Cone Programming.- 5 Approximately Solving Semidefinite Programs -- 6 An Interior-Point Algorithm for Semidefinite Programming -- 7 Compositive Programming.- Part II (by Jiri Matousek): 8 Lower Bounds for the Goemans–Williamson MAXCUT Algorithm -- 9 Coloring 3-Chromatic Graphs -- 10 Maximizing a Quadratic Form on a Graph -- 11 Colorings With Low Discrepancy -- 12 Constraint Satisfaction Problems, and Relaxing Them Semidefinitely -- 13 Rounding Via Miniatures -- Summary -- References -- Index En línea: http://dx.doi.org/10.1007/978-3-642-22015-9 Link: https://biblioteca.cunef.edu/gestion/catalogo/index.php?lvl=notice_display&id=32919 Ejemplares
Signatura Medio Ubicación Sub-localización Sección Estado ningún ejemplar Harmonic Analysis, Signal Processing, and Complexity / SpringerLink (Online service) ; Irene Sabadini ; Daniele C. Struppa ; David F. Walnut (2005)
Título : Harmonic Analysis, Signal Processing, and Complexity : Festschrift in Honor of the 60th Birthday of Carlos A. Berenstein Tipo de documento: documento electrónico Autores: SpringerLink (Online service) ; Irene Sabadini ; Daniele C. Struppa ; David F. Walnut Editorial: Boston, MA : Birkhäuser Boston Fecha de publicación: 2005 Colección: Progress in Mathematics num. 238 Número de páginas: XI, 162 p. 15 illus Il.: online resource ISBN/ISSN/DL: 978-0-8176-4416-1 Idioma : Inglés (eng) Palabras clave: Mathematics Algorithms Mathematical analysis Analysis (Mathematics) Harmonic Applied mathematics Engineering Abstract Applications of Signal, Image and Speech Processing Algorithm Problem Complexity Clasificación: 51 Matemáticas Resumen: Carlos A. Berenstein has had a profound influence on scholars and practitioners alike amid a distinguished mathematical career spanning nearly four decades. His uncommon capability of adroitly moving between these parallel worlds is demonstrated by the breadth of his research interests, from his early theoretical work on interpolation in spaces of entire functions with growth conditions and residue theory to his later work on deconvolution and its applications to issues ranging from optics to the study of blood flow. This volume, which celebrates his sixtieth birthday, reflects the state-of-the-art in these areas. Original articles and survey articles, all refereed, cover topics in harmonic and complex analysis, as well as more applied work in signal processing. Contributors: C.A. Berenstein; R.W. Braun; O. Calin; D-C. Chang; G. Dafni; L. Ehrenpreis; G. Kaiser; C.O. Kiselman; P. Krishnaprasad; B.Q. Li; B. Matt; R. Meise; D. Napoletani; R. Poovendran; Y. Qiao; J. Ryan; C. Sadosky; D.C. Struppa; B.A. Taylor; J. Tie; D.F. Walnut; and A. Yger Nota de contenido: Some Novel Aspects of the Cauchy Problem -- Analytic and Algebraic Ideas: How to Profit from Their Complementarity -- On Certain First-Order Partial Differential Equations in C n -- Hermite Operator on the Heisenberg Group -- A Div-Curl Lemma in BMO on a Domain -- Subharmonic Functions on Discrete Structures -- Nearly Hyperbolic Varieties and Phragmén-Lindelöf Conditions -- Sampling and Local Deconvolution -- Orthogonal Projections on Hyperbolic Space -- Eigenwavelets of the Wave Equation -- Security Analysis and Extensions of the PCB Algorithm for Distributed Key Generation -- Quotient Signal Estimation En línea: http://dx.doi.org/10.1007/0-8176-4416-4 Link: https://biblioteca.cunef.edu/gestion/catalogo/index.php?lvl=notice_display&id=35174 Harmonic Analysis, Signal Processing, and Complexity : Festschrift in Honor of the 60th Birthday of Carlos A. Berenstein [documento electrónico] / SpringerLink (Online service) ; Irene Sabadini ; Daniele C. Struppa ; David F. Walnut . - Boston, MA : Birkhäuser Boston, 2005 . - XI, 162 p. 15 illus : online resource. - (Progress in Mathematics; 238) .
ISBN : 978-0-8176-4416-1
Idioma : Inglés (eng)
Palabras clave: Mathematics Algorithms Mathematical analysis Analysis (Mathematics) Harmonic Applied mathematics Engineering Abstract Applications of Signal, Image and Speech Processing Algorithm Problem Complexity Clasificación: 51 Matemáticas Resumen: Carlos A. Berenstein has had a profound influence on scholars and practitioners alike amid a distinguished mathematical career spanning nearly four decades. His uncommon capability of adroitly moving between these parallel worlds is demonstrated by the breadth of his research interests, from his early theoretical work on interpolation in spaces of entire functions with growth conditions and residue theory to his later work on deconvolution and its applications to issues ranging from optics to the study of blood flow. This volume, which celebrates his sixtieth birthday, reflects the state-of-the-art in these areas. Original articles and survey articles, all refereed, cover topics in harmonic and complex analysis, as well as more applied work in signal processing. Contributors: C.A. Berenstein; R.W. Braun; O. Calin; D-C. Chang; G. Dafni; L. Ehrenpreis; G. Kaiser; C.O. Kiselman; P. Krishnaprasad; B.Q. Li; B. Matt; R. Meise; D. Napoletani; R. Poovendran; Y. Qiao; J. Ryan; C. Sadosky; D.C. Struppa; B.A. Taylor; J. Tie; D.F. Walnut; and A. Yger Nota de contenido: Some Novel Aspects of the Cauchy Problem -- Analytic and Algebraic Ideas: How to Profit from Their Complementarity -- On Certain First-Order Partial Differential Equations in C n -- Hermite Operator on the Heisenberg Group -- A Div-Curl Lemma in BMO on a Domain -- Subharmonic Functions on Discrete Structures -- Nearly Hyperbolic Varieties and Phragmén-Lindelöf Conditions -- Sampling and Local Deconvolution -- Orthogonal Projections on Hyperbolic Space -- Eigenwavelets of the Wave Equation -- Security Analysis and Extensions of the PCB Algorithm for Distributed Key Generation -- Quotient Signal Estimation En línea: http://dx.doi.org/10.1007/0-8176-4416-4 Link: https://biblioteca.cunef.edu/gestion/catalogo/index.php?lvl=notice_display&id=35174 Ejemplares
Signatura Medio Ubicación Sub-localización Sección Estado ningún ejemplar
Título : Numerical Optimization : Theoretical and Practical Aspects Tipo de documento: documento electrónico Autores: J. Frédéric Bonnans ; SpringerLink (Online service) ; J. Charles Gilbert ; Claude Lemaréchal ; Claudia A. Sagastizábal Editorial: Berlin, Heidelberg : Springer Berlin Heidelberg Fecha de publicación: 2006 Número de páginas: XIV, 494 p Il.: online resource ISBN/ISSN/DL: 978-3-540-35447-5 Idioma : Inglés (eng) Palabras clave: Mathematics Algorithms Computer science Numerical analysis Mathematical optimization Calculus of variations Operations research Management Optimization Research, Science Variations and Optimal Control; Analysis Algorithm Problem Complexity Computing Clasificación: 51 Matemáticas Resumen: Just as in its 1st edition, this book starts with illustrations of the ubiquitous character of optimization, and describes numerical algorithms in a tutorial way. It covers fundamental algorithms as well as more specialized and advanced topics for unconstrained and constrained problems. Most of the algorithms are explained in a detailed manner, allowing straightforward implementation. Theoretical aspects of the approaches chosen are also addressed with care, often using minimal assumptions. This new edition contains computational exercises in the form of case studies which help understanding optimization methods beyond their theoretical, description, when coming to actual implementation. Besides, the nonsmooth optimization part has been substantially reorganized and expanded Nota de contenido: Unconstrained Problems -- General Introduction -- Basic Methods -- Line-Searches -- Newtonian Methods -- Conjugate Gradient -- Special Methods -- A Case Study: Seismic Reection Tomography -- Nonsmooth Optimization -- to Nonsmooth Optimization -- Some Methods in Nonsmooth Optimization -- Bundle Methods. The Quest for Descent -- Applications of Nonsmooth Optimization -- Computational Exercises -- Newton's Methods in Constrained Optimization -- Background -- Local Methods for Problems with Equality Constraints -- Local Methods for Problems with Equality and InequalityConstraints -- Exact Penalization -- Globalization by Line-Search -- Quasi-Newton Versions -- Interior-Point Algorithms for Linear and QuadraticOptimization -- Linearly Constrained Optimization and SimplexAlgorithm -- Linear Monotone Complementarity and Associated Vector Fields -- Predictor-Corrector Algorithms -- Non-Feasible Algorithms -- Self-Duality -- One-Step Methods -- Complexity of Linear Optimization Problems with Integer Data -- Karmarkar's Algorithm En línea: http://dx.doi.org/10.1007/978-3-540-35447-5 Link: https://biblioteca.cunef.edu/gestion/catalogo/index.php?lvl=notice_display&id=34986 Numerical Optimization : Theoretical and Practical Aspects [documento electrónico] / J. Frédéric Bonnans ; SpringerLink (Online service) ; J. Charles Gilbert ; Claude Lemaréchal ; Claudia A. Sagastizábal . - Berlin, Heidelberg : Springer Berlin Heidelberg, 2006 . - XIV, 494 p : online resource.
ISBN : 978-3-540-35447-5
Idioma : Inglés (eng)
Palabras clave: Mathematics Algorithms Computer science Numerical analysis Mathematical optimization Calculus of variations Operations research Management Optimization Research, Science Variations and Optimal Control; Analysis Algorithm Problem Complexity Computing Clasificación: 51 Matemáticas Resumen: Just as in its 1st edition, this book starts with illustrations of the ubiquitous character of optimization, and describes numerical algorithms in a tutorial way. It covers fundamental algorithms as well as more specialized and advanced topics for unconstrained and constrained problems. Most of the algorithms are explained in a detailed manner, allowing straightforward implementation. Theoretical aspects of the approaches chosen are also addressed with care, often using minimal assumptions. This new edition contains computational exercises in the form of case studies which help understanding optimization methods beyond their theoretical, description, when coming to actual implementation. Besides, the nonsmooth optimization part has been substantially reorganized and expanded Nota de contenido: Unconstrained Problems -- General Introduction -- Basic Methods -- Line-Searches -- Newtonian Methods -- Conjugate Gradient -- Special Methods -- A Case Study: Seismic Reection Tomography -- Nonsmooth Optimization -- to Nonsmooth Optimization -- Some Methods in Nonsmooth Optimization -- Bundle Methods. The Quest for Descent -- Applications of Nonsmooth Optimization -- Computational Exercises -- Newton's Methods in Constrained Optimization -- Background -- Local Methods for Problems with Equality Constraints -- Local Methods for Problems with Equality and InequalityConstraints -- Exact Penalization -- Globalization by Line-Search -- Quasi-Newton Versions -- Interior-Point Algorithms for Linear and QuadraticOptimization -- Linearly Constrained Optimization and SimplexAlgorithm -- Linear Monotone Complementarity and Associated Vector Fields -- Predictor-Corrector Algorithms -- Non-Feasible Algorithms -- Self-Duality -- One-Step Methods -- Complexity of Linear Optimization Problems with Integer Data -- Karmarkar's Algorithm En línea: http://dx.doi.org/10.1007/978-3-540-35447-5 Link: https://biblioteca.cunef.edu/gestion/catalogo/index.php?lvl=notice_display&id=34986 Ejemplares
Signatura Medio Ubicación Sub-localización Sección Estado ningún ejemplar
Título : Optimal Design and Related Areas in Optimization and Statistics Tipo de documento: documento electrónico Autores: SpringerLink (Online service) ; Luc Pronzato ; Anatoly Zhigljavsky Editorial: New York, NY : Springer New York Fecha de publicación: 2009 Colección: Springer Optimization and Its Applications, ISSN 1931-6828 num. 28 Número de páginas: XV, 224 p. 23 illus Il.: online resource ISBN/ISSN/DL: 978-0-387-79936-0 Idioma : Inglés (eng) Palabras clave: Mathematics Algorithms Mathematical optimization Operations research Management science Probabilities Statistics Optimization Probability Theory and Stochastic Processes Research, Science Statistics, general Algorithm Analysis Problem Complexity Clasificación: 51 Matemáticas Resumen: This edited volume, dedicated to Henry P. Wynn, reflects his broad range of research interests, focusing in particular on the applications of optimal design theory in optimization and statistics. It covers algorithms for constructing optimal experimental designs, general gradient-type algorithms for convex optimization, majorization and stochastic ordering, algebraic statistics, Bayesian networks and nonlinear regression. Written by leading specialists in the field, each chapter contains a survey of the existing literature along with substantial new material. This work will appeal to both the specialist and the non-expert in the areas covered. By attracting the attention of experts in optimization to important interconnected areas, it should help stimulate further research with a potential impact on applications Nota de contenido: W-Iterations and Ripples Therefrom -- Studying Convergence of Gradient Algorithms Via Optimal Experimental Design Theory -- A Dynamical-System Analysis of the Optimum s-Gradient Algorithm -- Bivariate Dependence Orderings for Unordered Categorical Variables -- Methods in Algebraic Statistics for the Design of Experiments -- The Geometry of Causal Probability Trees that are Algebraically Constrained -- Bayes Nets of Time Series: Stochastic Realizations and Projections -- Asymptotic Normality of Nonlinear Least Squares under Singular Experimental Designs -- Robust Estimators in Non-linear Regression Models with Long-Range Dependence En línea: http://dx.doi.org/10.1007/978-0-387-79936-0 Link: https://biblioteca.cunef.edu/gestion/catalogo/index.php?lvl=notice_display&id=33885 Optimal Design and Related Areas in Optimization and Statistics [documento electrónico] / SpringerLink (Online service) ; Luc Pronzato ; Anatoly Zhigljavsky . - New York, NY : Springer New York, 2009 . - XV, 224 p. 23 illus : online resource. - (Springer Optimization and Its Applications, ISSN 1931-6828; 28) .
ISBN : 978-0-387-79936-0
Idioma : Inglés (eng)
Palabras clave: Mathematics Algorithms Mathematical optimization Operations research Management science Probabilities Statistics Optimization Probability Theory and Stochastic Processes Research, Science Statistics, general Algorithm Analysis Problem Complexity Clasificación: 51 Matemáticas Resumen: This edited volume, dedicated to Henry P. Wynn, reflects his broad range of research interests, focusing in particular on the applications of optimal design theory in optimization and statistics. It covers algorithms for constructing optimal experimental designs, general gradient-type algorithms for convex optimization, majorization and stochastic ordering, algebraic statistics, Bayesian networks and nonlinear regression. Written by leading specialists in the field, each chapter contains a survey of the existing literature along with substantial new material. This work will appeal to both the specialist and the non-expert in the areas covered. By attracting the attention of experts in optimization to important interconnected areas, it should help stimulate further research with a potential impact on applications Nota de contenido: W-Iterations and Ripples Therefrom -- Studying Convergence of Gradient Algorithms Via Optimal Experimental Design Theory -- A Dynamical-System Analysis of the Optimum s-Gradient Algorithm -- Bivariate Dependence Orderings for Unordered Categorical Variables -- Methods in Algebraic Statistics for the Design of Experiments -- The Geometry of Causal Probability Trees that are Algebraically Constrained -- Bayes Nets of Time Series: Stochastic Realizations and Projections -- Asymptotic Normality of Nonlinear Least Squares under Singular Experimental Designs -- Robust Estimators in Non-linear Regression Models with Long-Range Dependence En línea: http://dx.doi.org/10.1007/978-0-387-79936-0 Link: https://biblioteca.cunef.edu/gestion/catalogo/index.php?lvl=notice_display&id=33885 Ejemplares
Signatura Medio Ubicación Sub-localización Sección Estado ningún ejemplar
Título : Algorithmic Randomness and Complexity Tipo de documento: documento electrónico Autores: Rodney G. Downey ; SpringerLink (Online service) ; Denis R. Hirschfeldt Editorial: New York, NY : Springer New York Fecha de publicación: 2010 Colección: Theory and Applications of Computability, In cooperation with the association Computability in Europe, ISSN 2190-619X Número de páginas: XXVIII, 855 p. 8 illus Il.: online resource ISBN/ISSN/DL: 978-0-387-68441-3 Idioma : Inglés (eng) Palabras clave: Mathematics Computers Algorithms Algorithm Analysis and Problem Complexity Theory of Computation by Abstract Devices Clasificación: 51 Matemáticas Resumen: Intuitively, a sequence such as 101010101010101010… does not seem random, whereas 101101011101010100…, obtained using coin tosses, does. How can we reconcile this intuition with the fact that both are statistically equally likely? What does it mean to say that an individual mathematical object such as a real number is random, or to say that one real is more random than another? And what is the relationship between randomness and computational power. The theory of algorithmic randomness uses tools from computability theory and algorithmic information theory to address questions such as these. Much of this theory can be seen as exploring the relationships between three fundamental concepts: relative computability, as measured by notions such as Turing reducibility; information content, as measured by notions such as Kolmogorov complexity; and randomness of individual objects, as first successfully defined by Martin-Löf. Although algorithmic randomness has been studied for several decades, a dramatic upsurge of interest in the area, starting in the late 1990s, has led to significant advances. This is the first comprehensive treatment of this important field, designed to be both a reference tool for experts and a guide for newcomers. It surveys a broad section of work in the area, and presents most of its major results and techniques in depth. Its organization is designed to guide the reader through this large body of work, providing context for its many concepts and theorems, discussing their significance, and highlighting their interactions. It includes a discussion of effective dimension, which allows us to assign concepts like Hausdorff dimension to individual reals, and a focused but detailed introduction to computability theory. It will be of interest to researchers and students in computability theory, algorithmic information theory, and theoretical computer science Nota de contenido: Background -- Preliminaries -- Computability Theory -- Kolmogorov Complexity of Finite Strings -- Relating Complexities -- Effective Reals -- Notions of Randomness -- Martin-Löf Randomness -- Other Notions of Algorithmic Randomness -- Algorithmic Randomness and Turing Reducibility -- Relative Randomness -- Measures of Relative Randomness -- Complexity and Relative Randomness for 1-Random Sets -- Randomness-Theoretic Weakness -- Lowness and Triviality for Other Randomness Notions -- Algorithmic Dimension -- Further Topics -- Strong Jump Traceability -- ? as an Operator -- Complexity of Computably Enumerable Sets En línea: http://dx.doi.org/10.1007/978-0-387-68441-3 Link: https://biblioteca.cunef.edu/gestion/catalogo/index.php?lvl=notice_display&id=33497 Algorithmic Randomness and Complexity [documento electrónico] / Rodney G. Downey ; SpringerLink (Online service) ; Denis R. Hirschfeldt . - New York, NY : Springer New York, 2010 . - XXVIII, 855 p. 8 illus : online resource. - (Theory and Applications of Computability, In cooperation with the association Computability in Europe, ISSN 2190-619X) .
ISBN : 978-0-387-68441-3
Idioma : Inglés (eng)
Palabras clave: Mathematics Computers Algorithms Algorithm Analysis and Problem Complexity Theory of Computation by Abstract Devices Clasificación: 51 Matemáticas Resumen: Intuitively, a sequence such as 101010101010101010… does not seem random, whereas 101101011101010100…, obtained using coin tosses, does. How can we reconcile this intuition with the fact that both are statistically equally likely? What does it mean to say that an individual mathematical object such as a real number is random, or to say that one real is more random than another? And what is the relationship between randomness and computational power. The theory of algorithmic randomness uses tools from computability theory and algorithmic information theory to address questions such as these. Much of this theory can be seen as exploring the relationships between three fundamental concepts: relative computability, as measured by notions such as Turing reducibility; information content, as measured by notions such as Kolmogorov complexity; and randomness of individual objects, as first successfully defined by Martin-Löf. Although algorithmic randomness has been studied for several decades, a dramatic upsurge of interest in the area, starting in the late 1990s, has led to significant advances. This is the first comprehensive treatment of this important field, designed to be both a reference tool for experts and a guide for newcomers. It surveys a broad section of work in the area, and presents most of its major results and techniques in depth. Its organization is designed to guide the reader through this large body of work, providing context for its many concepts and theorems, discussing their significance, and highlighting their interactions. It includes a discussion of effective dimension, which allows us to assign concepts like Hausdorff dimension to individual reals, and a focused but detailed introduction to computability theory. It will be of interest to researchers and students in computability theory, algorithmic information theory, and theoretical computer science Nota de contenido: Background -- Preliminaries -- Computability Theory -- Kolmogorov Complexity of Finite Strings -- Relating Complexities -- Effective Reals -- Notions of Randomness -- Martin-Löf Randomness -- Other Notions of Algorithmic Randomness -- Algorithmic Randomness and Turing Reducibility -- Relative Randomness -- Measures of Relative Randomness -- Complexity and Relative Randomness for 1-Random Sets -- Randomness-Theoretic Weakness -- Lowness and Triviality for Other Randomness Notions -- Algorithmic Dimension -- Further Topics -- Strong Jump Traceability -- ? as an Operator -- Complexity of Computably Enumerable Sets En línea: http://dx.doi.org/10.1007/978-0-387-68441-3 Link: https://biblioteca.cunef.edu/gestion/catalogo/index.php?lvl=notice_display&id=33497 Ejemplares
Signatura Medio Ubicación Sub-localización Sección Estado ningún ejemplar PermalinkPermalinkPermalinkPermalinkPermalink
