Search

Your search keyword '"Daniel P. Bovet"' showing total 25 results
Start Over Author "Daniel P. Bovet"
25 results on '"Daniel P. Bovet"'

20. An introduction to the theory of computational complexity

Author

Daniel P. Bovet and Pierluigi Crescenzi

Subjects
Computational topology, Theoretical computer science, Dynamic problem, Computer science, Model of computation, Asymptotic computational complexity, Averaging argument, Computational problem, Computational resource, Quantum complexity theory
Published
2008
Full Text
View/download PDF

22. Understanding the Linux Kernel

Author

Daniel P. Bovet, Marco Cesati, Daniel P. Bovet, and Marco Cesati

Subjects
Operating systems (Computers)
Abstract

In order to thoroughly understand what makes Linux tick and why it works so well on a wide variety of systems, you need to delve deep into the heart of the kernel. The kernel handles all interactions between the CPU and the external world, and determines which programs will share processor time, in what order. It manages limited memory so well that hundreds of processes can share the system efficiently, and expertly organizes data transfers so that the CPU isn't kept waiting any longer than necessary for the relatively slow disks.The third edition of Understanding the Linux Kernel takes you on a guided tour of the most significant data structures, algorithms, and programming tricks used in the kernel. Probing beyond superficial features, the authors offer valuable insights to people who want to know how things really work inside their machine. Important Intel-specific features are discussed. Relevant segments of code are dissected line by line. But the book covers more than just the functioning of the code; it explains the theoretical underpinnings of why Linux does things the way it does.This edition of the book covers Version 2.6, which has seen significant changes to nearly every kernel subsystem, particularly in the areas of memory management and block devices. The book focuses on the following topics:Memory management, including file buffering, process swapping, and Direct memory Access (DMA) The Virtual Filesystem layer and the Second and Third Extended FilesystemsProcess creation and schedulingSignals, interrupts, and the essential interfaces to device driversTimingSynchronization within the kernelInterprocess Communication (IPC) Program executionUnderstanding the Linux Kernel will acquaint you with all the inner workings of Linux, but it's more than just an academic exercise. You'll learn what conditions bring out Linux's best performance, and you'll see how it meets the challenge of providing good system response during process scheduling, file access, and memory management in a wide variety of environments. This book will help you make the most of your Linux system.

Published
2005

23. An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs

Author

Daniel P. Bovet, James B. Orlin, and Maurizio A. Bonuccelli

Subjects
Discrete mathematics, Symmetric graph, Voltage graph, law.invention, Combinatorics, law, Graph power, Circular-arc graph, Line graph, Cubic graph, Algorithm, Circle graph, Complement graph, Mathematics
Abstract

A graph is a circular arc graph if each vertex of the graph is associated with an arc on a circle in such a way that two vertices of the graph are adjacent if and only if the corresponding arcs overlap. A circular arc graph is proper if none of the representing arcs is contained within another. An $O(n^2 )$ algorithm is given for determining whether a proper circular arc graph with n nodes may be colored with k colors.

Published
1981
Full Text
View/download PDF

24. Complexity classes and sparse oracles

Author

Daniel P. Bovet, Riccardo Silvestri, and Pierluigi Crescenzi

Subjects
Discrete mathematics, Average-case complexity, General theorem, Computational complexity theory, Computer Networks and Communications, Computer science, Applied Mathematics, Descriptive complexity theory, Theoretical Computer Science, Combinatorics, Set (abstract data type), PH, Structural complexity theory, Computational Theory and Mathematics, If and only if, Complexity class, Alternating Turing machine, Mathematics, Sparse language, Quantum complexity theory
Abstract

Complexity classes are usually defined by referring to computation models and by putting suitable restrictions on them. Following this approach, many proofs of results are tightly bound to the characteristics of the computation model and of its restrictions and therefore they sometimes hide the essential properties which ensure the obtained results. In order to obtain more general results, a uniform family of computation models which encompass most of the complexity classes of interest has been introduced in an earlier paper. As an initial set of results derivable from the proposed approach, a necessary and sufficient condition to prove the separation of relativized complexity classes, a characterization of complexity classes which admit a complete language, and a sufficient condition to prove the strong separation of relativized complexity classes have been presented in that paper. In this paper, we apply this approach to obtain positive relativization results, that is, results similar to those obtained in the literature. In particular, our goal is to prove statements of the kind: "Given two complexity classes C and D, C = D if and only if for every sparse set S, CS = DS." We derive a sufficient condition to prove such results and, as an application, we prove a general theorem from which all of the results obtained previously and new ones can be immediately derived.

Catalog

Books, media, physical & digital resources
See catalog results