Muutke küpsiste eelistusi

E-raamat: Communication Complexity and Parallel Computing

Teised raamatud teemal:
  • Formaat - PDF+DRM
  • Hind: 55,56 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.
Communication Complexity and Parallel ComputingSuurem pilt
Teised raamatud teemal:

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

The communication complexity of two-party protocols is an only 15 years old complexity measure, but it is already considered to be one of the fundamen­ tal complexity measures of recent complexity theory. Similarly to Kolmogorov complexity in the theory of sequential computations, communication complex­ ity is used as a method for the study of the complexity of concrete computing problems in parallel information processing. Especially, it is applied to prove lower bounds that say what computer resources (time, hardware, memory size) are necessary to compute the given task. Besides the estimation of the compu­ tational difficulty of computing problems the proved lower bounds are useful for proving the optimality of algorithms that are already designed. In some cases the knowledge about the communication complexity of a given problem may be even helpful in searching for efficient algorithms to this problem. The study of communication complexity becomes a well-defined indepen­ dent area of complexity theory. In addition to a strong relation to several funda­ mental complexity measures (and so to several fundamental problems of com­ plexity theory) communication complexity has contributed to the study and to the understanding of the nature of determinism, nondeterminism, and random­ ness in algorithmics. There already exists a non-trivial mathematical machinery to handle the communication complexity of concrete computing problems, which gives a hope that the approach based on communication complexity will be in­ strumental in the study of several central open problems of recent complexity theory.

This book shows how to establish the communication complexity of distinct computing problems and to apply this knowledge in parallel processing of computing problems. It gives also a survey of this special topic and includes motivation for further research.
1 Introduction
1(6)
1.1 Motivation and Aims
1(3)
1.2 Concept and Organization
4(2)
1.3 How to Read the Book
6(1)
2 Communication Protocol Models
7(144)
2.1 Basic Notions
7(16)
2.1.1 Introduction
7(1)
2.1.2 Alphabets, Words, and Languages
7(4)
2.1.3 Boolean Functions and Boolean Matrices
11(5)
2.1.4 Representation of Computing Problems
16(4)
2.1.5 Exercises
20(3)
2.2 Communication Complexity According to a Fixed Partition
23(37)
2.2.1 Definitions
23(7)
2.2.2 Methods for Proving Lower Bounds
30(23)
2.2.3 Theoretical Properties of Communication Complexity According to a Fixed Partition
53(4)
2.2.4 Exercises
57(2)
2.2.5 Research Problems
59(1)
2.3 Communication Complexity
60(23)
2.3.1 Introduction
60(1)
2.3.2 Definitions
61(1)
2.3.3 Lower Bound Methods
62(8)
2.3.4 Theoretical Properties of Communication Complexity
70(7)
2.3.5 Communication Complexity and Chomsky Hierarchy
77(5)
2.3.6 Exercises
82(1)
2.3.7 Research Problems
83(1)
2.4 One-Way Communication Complexity
83(14)
2.4.1 Introduction
83(1)
2.4.2 Definitions
84(2)
2.4.3 Methods for Proving Lower Bounds
86(6)
2.4.4 Communication Complexity Versus One-way Communication Complexity
92(3)
2.4.5 Exercises
95(1)
2.4.6 Research Problems
96(1)
2.5 Nondeterministic Communication Complexity and Randomized Protocols
97(34)
2.5.1 Introduction
97(1)
2.5.2 Nondeterministic Protocols
98(7)
2.5.3 Lower Bounds on Nondeterministic Communication Complexity
105(4)
2.5.4 Deterministic Protocols Versus Nondeterministic Protocols
109(6)
2.5.5 Randomized Protocols
115(8)
2.5.6 Randomness Versus Nondeterminism and Determinism
123(4)
2.5.7 Exercises
127(3)
2.5.8 Research Problems
130(1)
2.6 An Improved Model of Communication Protocols
131(13)
2.6.1 Introduction
131(1)
2.6.2 Definitions
132(3)
2.6.3 Lower Bound Methods
135(4)
2.6.4 Communication Complexity Versus S-communication Complexity
139(1)
2.6.5 Some Properties of s-communication Complexity
140(3)
2.6.6 Exercises
143(1)
2.6.7 Problems
144(1)
2.7 Bibliographical Remarks
144(7)
3 Boolean Circuits
151(90)
3.1 Introduction
151(1)
3.2 Definitions and Fundamental Properties
152(12)
3.2.1 Introduction
152(1)
3.2.2 Boolean Circuit Models
152(7)
3.2.3 Fundamental Observations
159(4)
3.2.4 Exercises
163(1)
3.3 Lower Bounds on the Area of Boolean Circuits
164(21)
3.3.1 Introduction
164(1)
3.3.2 Definitions
164(3)
3.3.3 Lower Bounds on the Area Complexity Measures
167(6)
3.3.4 A Comparision of two Area Complexity Measures
173(6)
3.3.5 Three-Dimensional Layout
179(3)
3.3.6 Exercises
182(2)
3.3.7 Problems
184(1)
3.4 Topology of Circuits and Lower Bounds
185(32)
3.4.1 Introduction
185(1)
3.4.2 Separators
185(7)
3.4.3 Lower Bounds on Boolean Circuits with a Sublinear Separator
192(4)
3.4.4 Circuit Structures for Which Communication Complexity Does Not Help
196(4)
3.4.5 Planar Boolean Circuits
200(15)
3.4.6 Exercises
215(2)
3.4.7 Problems
217(1)
3.5 Lower Bounds on the Size of Unbounded Fan-in Circuits
217(8)
3.5.1 Introduction
217(1)
3.5.2 Method of Communication Complexity of Infinite Bases
218(4)
3.5.3 Unbounded Fan-in Circuits with Sublinear Vertex-Separators
222(2)
3.5.4 Exercises
224(1)
3.5.5 Problems
225(1)
3.6 Lower Bounds on the Depth of Boolean Circuits
225(12)
3.6.1 Introduction
225(1)
3.6.2 Monotone Boolean Circuits
226(3)
3.6.3 Communication Complexity of Relations
229(2)
3.6.4 Characterizations of Circuit Depth by the Communication Complexity of Relations
231(5)
3.6.5 Exercises
236(1)
3.6.6 Research Problems
237(1)
3.7 Bibliographical Remarks
237(4)
4 VLSI Circuits and Interconnection Networks
241(42)
4.1 Introduction
241(1)
4.2 Definitions
242(10)
4.2.1 Introduction
242(1)
4.2.2 A VLSI circuit Model
242(5)
4.2.3 Complexity Measures
247(3)
4.2.4 Probabilistic Models
250(1)
4.2.5 Exercises
251(1)
4.3 Lower Bounds on VLSI Complexity Measures
252(12)
4.3.1 Introduction
252(1)
4.3.2 Lower Bounds on Area Complexity
252(2)
4.3.3 Lower Bounds on Tradeoffs of Area and Time
254(4)
4.3.4 VLSI circuits with Special Communication Structures
258(5)
4.3.5 Exercises
263(1)
4.3.6 Problems
264(1)
4.4 Interconnection Networks
264(6)
4.4.1 Introduction
264(1)
4.4.2 A Model of Interconnection Networks
265(1)
4.4.3 Separators and Lower Bounds
266(4)
4.4.4 Exercises
270(1)
4.4.5 Problems
270(1)
4.5 Multilective VLSI circuits
270(10)
4.5.1 Introduction and Definitions
270(1)
4.5.2 Multilectivity Versus Semilectivity
271(1)
4.5.3 Lower Bounds on Multilective VLSI Programs
272(7)
4.5.4 Exercises
279(1)
4.5.5 Problems
280(1)
4.6 Bibiliographical Remarks
280(3)
5 Sequential Computations
283(34)
5.1 Introduction
283(1)
5.2 Finite Automata
284(11)
5.2.1 Introduction
284(1)
5.2.2 Definitions
285(2)
5.2.3 One-Way Communication Complexity and Lower Bounds on the Size of Finite Automata
287(1)
5.2.4 Uniform Protocols
288(6)
Exercises
294(1)
5.2.6 Research Problems
295(1)
5.3 Turing Machines
295(7)
5.3.1 Introduction
295(1)
5.3.2 Time Complexity of Classical Turing Machines
296(3)
5.3.3 Sequential Space and Time-Space Complexity
299(2)
5.3.4 Exercises
301(1)
5.3.5 Research Problems
302(1)
5.4 Decision Trees and Branching Programs
302(9)
5.4.1 Introduction
302(1)
5.4.2 Definitions
303(3)
5.4.3 Capacity of Branching Programs
306(3)
5.4.4 Lower Bounds on the Depth of Decision Trees
309(1)
5.4.5 Exercises
310(1)
5.4.6 Research Problems
311(1)
5.5 Bibliographical Remarks
311(6)
References 317(14)
Index 331


Lisainfo e-raamatute kohta Lisainfo e-raamatute kohta
Püsilink: https://www.kriso.ee/db/97836620344222e.html
Märksõnad: