Resultado de la búsqueda
3 búsqueda de la palabra clave 'by'
Refinar búsqueda Generar rss de la búsqueda
Link de la búsqueda
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
Título : Instruction Sequences for Computer Science Tipo de documento: documento electrónico Autores: Jan A. Bergstra ; SpringerLink (Online service) ; Cornelis A. Middelburg Editorial: Paris : Atlantis Press Fecha de publicación: 2012 Colección: Atlantis Studies in Computing, ISSN 2212-8557 num. 2 Número de páginas: XVI, 232 p Il.: online resource ISBN/ISSN/DL: 978-94-91216-65-7 Idioma : Inglés (eng) Palabras clave: Computer science organization Programming languages (Electronic computers) Computers logic Mathematical Science Computation by Abstract Devices Logics and Meanings of Programs Logic Formal Languages Languages, Compilers, Interpreters Systems Organization Communication Networks Clasificación: 51 Matemáticas Resumen: This book demonstrates that the concept of an instruction sequence offers a novel and useful viewpoint on issues relating to diverse subjects in computer science. Selected issues relating to well-known subjects from the theory of computation and the area of computer architecture are rigorously investigated in this book thinking in terms of instruction sequences. The subjects from the theory of computation, to wit the halting problem and non-uniform computational complexity, are usually investigated thinking in terms of a common model of computation such as Turing machines and Boolean circuits. The subjects from the area of computer architecture, to wit instruction sequence performance, instruction set architectures and remote instruction processing, are usually not investigated in a rigorous way at all Nota de contenido: Introduction -- Instruction Sequences -- Instruction Processing -- Expressiveness of Instruction Sequences -- Computation-Theoretic Issues -- Computer-Architectural Issues -- Instruction Sequences and Process Algebra -- Variations on a Theme -- Appendix A: Five Challenges for Projectionism -- Appendix B: Natural Number Functional Units -- Appendix C: Dynamically Instantiated Instructions -- Appendix D: Analytic Execution Architectures En línea: http://dx.doi.org/10.2991/978-94-91216-65-7 Link: https://biblioteca.cunef.edu/gestion/catalogo/index.php?lvl=notice_display&id=33067 Instruction Sequences for Computer Science [documento electrónico] / Jan A. Bergstra ; SpringerLink (Online service) ; Cornelis A. Middelburg . - Paris : Atlantis Press, 2012 . - XVI, 232 p : online resource. - (Atlantis Studies in Computing, ISSN 2212-8557; 2) .
ISBN : 978-94-91216-65-7
Idioma : Inglés (eng)
Palabras clave: Computer science organization Programming languages (Electronic computers) Computers logic Mathematical Science Computation by Abstract Devices Logics and Meanings of Programs Logic Formal Languages Languages, Compilers, Interpreters Systems Organization Communication Networks Clasificación: 51 Matemáticas Resumen: This book demonstrates that the concept of an instruction sequence offers a novel and useful viewpoint on issues relating to diverse subjects in computer science. Selected issues relating to well-known subjects from the theory of computation and the area of computer architecture are rigorously investigated in this book thinking in terms of instruction sequences. The subjects from the theory of computation, to wit the halting problem and non-uniform computational complexity, are usually investigated thinking in terms of a common model of computation such as Turing machines and Boolean circuits. The subjects from the area of computer architecture, to wit instruction sequence performance, instruction set architectures and remote instruction processing, are usually not investigated in a rigorous way at all Nota de contenido: Introduction -- Instruction Sequences -- Instruction Processing -- Expressiveness of Instruction Sequences -- Computation-Theoretic Issues -- Computer-Architectural Issues -- Instruction Sequences and Process Algebra -- Variations on a Theme -- Appendix A: Five Challenges for Projectionism -- Appendix B: Natural Number Functional Units -- Appendix C: Dynamically Instantiated Instructions -- Appendix D: Analytic Execution Architectures En línea: http://dx.doi.org/10.2991/978-94-91216-65-7 Link: https://biblioteca.cunef.edu/gestion/catalogo/index.php?lvl=notice_display&id=33067 Ejemplares
Signatura Medio Ubicación Sub-localización Sección Estado ningún ejemplar
Título : The Pillars of Computation Theory : State, Encoding, Nondeterminism Tipo de documento: documento electrónico Autores: Arnold L. Rosenberg ; SpringerLink (Online service) Editorial: New York, NY : Springer New York Fecha de publicación: 2010 Colección: Universitext, ISSN 0172-5939 Número de páginas: XVIII, 326 p. 49 illus Il.: online resource ISBN/ISSN/DL: 978-0-387-09639-1 Idioma : Inglés (eng) Palabras clave: Computer science Computers Algorithms Mathematical logic Mathematics Science Theory of Computation Computing Algorithm Analysis and Problem Complexity Logic Foundations by Abstract Devices Formal Languages Clasificación: 51 Matemáticas Resumen: Computation theory is a discipline that strives to use mathematical tools and concepts in order to expose the nature of the activity that we call “computation” and to explain a broad range of observed computational phenomena. Why is it harder to perform some computations than others? Are the differences in difficulty that we observe inherent, or are they artifacts of the way we try to perform the computations? Even more basically: how does one reason about such questions? This book strives to endow upper-level undergraduate students and lower-level graduate students with the conceptual and manipulative tools necessary to make Computation theory part of their professional lives. The author tries to achieve this goal via three stratagems that set this book apart from most other texts on the subject. (1) The author develops the necessary mathematical concepts and tools from their simplest instances, so that the student has the opportunity to gain operational control over the necessary mathematics. (2) He organizes the development of the theory around the three “pillars” that give the book its name, so that the student sees computational topics that have the same intellectual origins developed in physical proximity to one another. (3) He strives to illustrate the “big ideas” that computation theory is built upon with applications of these ideas within “practical” domains that the students have seen elsewhere in their courses, in mathematics, in computer science, and in computer engineering Nota de contenido: PROLEGOMENA -- Mathematical Preliminaries -- STATE -- Online Automata: Exemplars of #x201C;State#x201D; -- Finite Automata and Regular Languages -- Applications of the Myhill#x2013;Nerode Theorem -- Enrichment Topics -- ENCODING -- Countability and Uncountability: The Precursors of #x201C;Encoding#x201D; -- Enrichment Topic: #x201C;Efficient#x201D; Pairing Functions, with Applications -- Computability Theory -- NONDETERMINISM -- Nondeterministic Online Automata -- Nondeterministic FAs -- Nondeterminism in Computability Theory -- Complexity Theory En línea: http://dx.doi.org/10.1007/978-0-387-09639-1 Link: https://biblioteca.cunef.edu/gestion/catalogo/index.php?lvl=notice_display&id=33493 The Pillars of Computation Theory : State, Encoding, Nondeterminism [documento electrónico] / Arnold L. Rosenberg ; SpringerLink (Online service) . - New York, NY : Springer New York, 2010 . - XVIII, 326 p. 49 illus : online resource. - (Universitext, ISSN 0172-5939) .
ISBN : 978-0-387-09639-1
Idioma : Inglés (eng)
Palabras clave: Computer science Computers Algorithms Mathematical logic Mathematics Science Theory of Computation Computing Algorithm Analysis and Problem Complexity Logic Foundations by Abstract Devices Formal Languages Clasificación: 51 Matemáticas Resumen: Computation theory is a discipline that strives to use mathematical tools and concepts in order to expose the nature of the activity that we call “computation” and to explain a broad range of observed computational phenomena. Why is it harder to perform some computations than others? Are the differences in difficulty that we observe inherent, or are they artifacts of the way we try to perform the computations? Even more basically: how does one reason about such questions? This book strives to endow upper-level undergraduate students and lower-level graduate students with the conceptual and manipulative tools necessary to make Computation theory part of their professional lives. The author tries to achieve this goal via three stratagems that set this book apart from most other texts on the subject. (1) The author develops the necessary mathematical concepts and tools from their simplest instances, so that the student has the opportunity to gain operational control over the necessary mathematics. (2) He organizes the development of the theory around the three “pillars” that give the book its name, so that the student sees computational topics that have the same intellectual origins developed in physical proximity to one another. (3) He strives to illustrate the “big ideas” that computation theory is built upon with applications of these ideas within “practical” domains that the students have seen elsewhere in their courses, in mathematics, in computer science, and in computer engineering Nota de contenido: PROLEGOMENA -- Mathematical Preliminaries -- STATE -- Online Automata: Exemplars of #x201C;State#x201D; -- Finite Automata and Regular Languages -- Applications of the Myhill#x2013;Nerode Theorem -- Enrichment Topics -- ENCODING -- Countability and Uncountability: The Precursors of #x201C;Encoding#x201D; -- Enrichment Topic: #x201C;Efficient#x201D; Pairing Functions, with Applications -- Computability Theory -- NONDETERMINISM -- Nondeterministic Online Automata -- Nondeterministic FAs -- Nondeterminism in Computability Theory -- Complexity Theory En línea: http://dx.doi.org/10.1007/978-0-387-09639-1 Link: https://biblioteca.cunef.edu/gestion/catalogo/index.php?lvl=notice_display&id=33493 Ejemplares
Signatura Medio Ubicación Sub-localización Sección Estado ningún ejemplar
