Noam Nisan

Many aspects of the internal and external workings of computers can be viewed as a series of communication processes. Communication complexity is the mathematical theory of such communication processes. It is also often used as an abstract model of other aspects of computation. This book surveys this mathematical theory, concentrating on the question of how much communication is necessary for any particular process. The first part of the book is devoted to the simple two-party model introduced by Yao in 1979, which is still the most widely studied model. The second part treats newer models developed to deal with more complicated communication processes. Finally, applications of these models, including computer networks, VLSI circuits, and data structures, are treated in the third part of the book. This is an essential resource for graduate students and researchers in theoretical computer science, circuits, networks and information theory.

A new and extensively revised edition of a popular textbook used in universities, coding boot camps, hacker clubs, and online courses. The best way to understand how computers work is to build one from scratch, and this textbook leads learners through twelve chapters and projects that gradually build the hardware platform and software hierarchy for a simple but powerful computer system. In the process, learners gain hands-on knowledge of hardware, architecture, operating systems, programming languages, compilers, data structures and algorithms, and software engineering. Using this constructive approach, the book introduces learners to a significant body of computer science knowledge and demonstrates how theoretical and applied techniques taught in other computer science courses fit into the overall picture. The outcome of these efforts is known as Nand to Tetris a journey that starts with the most elementary logic gate, called Nand, and ends, twelve projects later, with a general-purpose computer system capable of running Tetris. The first edition of this popular textbook inspired Nand to Tetris classes in universities, coding boot camps, hacker clubs, and online course platforms. This second edition has been extensively revised. It has been restructured into two distinct parts--Part I, hardware, and Part II, software--with six projects in each part. All chapters and projects have been rewritten, with an emphasis on separating abstraction from implementation, and many new sections, figures, and examples have been added. Substantial new appendixes offer focused presentation on technical and theoretical topics.

Luchshij sposob ponjat, kak rabotajut kompjutery - eto postroit odin iz nikh s nulja! Tak schitajut avtory etoj knigi i potomu predlagajut prakticheskij podkhod k izucheniju kompjuternykh sistem. Vnutri vas zhdet ne tolko ischerpyvajuschee teoreticheskoe opisanie raboty sovremennogo kompjutera, no i algoritm konkretnykh shagov, neobkhodimykh dlja ego konstruirovanija. Blagodarja knige vy nauchites razbiratsja v sledujuschikh temakh: * Apparatnoe obespechenie * Kompjuternaja arkhitektura * Jazyki nizkogo i vysokogo urovnja * Virtualnye mashiny * Kompiljatory * Programmirovanie * Operatsionnye sistemy * Struktury dannykh i algoritmy * Programmnaja inzhenerija Unikalnaja osobennost knigi zakljuchaetsja v tom, chto vse eti temy tesno svjazany i chetko orientirovany na glavnuju tsel: sozdanie sovremennoj kompjuternoj sistemy s nulja. Uchebnik polnostju samodostatochen: vse neobkhodimye znanija dlja postroenija opisannykh v nej apparatnykh i programmnykh sistem est vnutri. Chast I "Apparatnoe obespechenie" ne trebuet predvaritelnykh znanij, chto delaet proekty 1-6 dostupnymi dlja ljubogo studenta i samouchki. Chast II "Programmnoe obespechenie" i proekty 7-12 trebujut predvaritelnogo izuchenija programmirovanija (na ljubom jazyke vysokogo urovnja). V otlichie ot drugikh uchebnikov, kotorye okhvatyvajut tolko odin aspekt temy, "Arkhitektura kompjuternykh sistem" daet tselostnoe i ischerpyvajuschee znanie prikladnoj informatiki, neobkhodimoe dlja sozdanija sobstvennykh proektov. "My napisali etu knigu, poskolku u nas slozhilos vpechatlenie, chto mnogie iz tekh, kto izuchaet informatiku, ne vidjat lesa za derevjami. Tipichnyj student probegaet cherez seriju kursov po programmirovaniju, teorii i inzhenerii, ne ostanavlivajas, chtoby otsenit krasotu obschej kartiny. A kartina v tselom takova, chto apparatnye, programmnye i prikladnye sistemy tesno svjazany mezhdu soboj, chto ne ochevidno, cherez skrytuju pautinu abstraktsij, interfejsov i kontraktnykh realizatsij". - Noam Nisan, Shimon Shoken

Using a unique pedagogical approach, this text introduces mathematical logic by guiding students in implementing the underlying logical concepts and mathematical proofs via Python programming. This approach, tailored to the unique intuitions and strengths of the ever-growing population of programming-savvy students, brings mathematical logic into the comfort zone of these students and provides clarity that can only be achieved by a deep hands-on understanding and the satisfaction of having created working code. While the approach is unique, the text follows the same set of topics typically covered in a one-semester undergraduate course, including propositional logic and first-order predicate logic, culminating in a proof of Gödel's completeness theorem. A sneak peek to Gödel's incompleteness theorem is also provided. The textbook is accompanied by an extensive collection of programming tasks, code skeletons, and unit tests. Familiarity with proofs and basic proficiency in Python is assumed.

Using a unique pedagogical approach, this text introduces mathematical logic by guiding students in implementing the underlying logical concepts and mathematical proofs via Python programming. This approach, tailored to the unique intuitions and strengths of the ever-growing population of programming-savvy students, brings mathematical logic into the comfort zone of these students and provides clarity that can only be achieved by a deep hands-on understanding and the satisfaction of having created working code. While the approach is unique, the text follows the same set of topics typically covered in a one-semester undergraduate course, including propositional logic and first-order predicate logic, culminating in a proof of Gödel's completeness theorem. A sneak peek to Gödel's incompleteness theorem is also provided. The textbook is accompanied by an extensive collection of programming tasks, code skeletons, and unit tests. Familiarity with proofs and basic proficiency in Python is assumed.

Randomization is an important tool in the design of algorithms, and the ability of randomization to provide enhanced power is a major research topic in complexity theory. Noam Nisan continues the investigation into the power of randomization and the relationships between randomized and deterministic complexity classes by pursuing the idea of emulating randomness, or pseudorandom generation. Pseudorandom generators reduce the number of random bits required by randomized algorithms, enable the construction of certain cryptographic protocols, and shed light on the difficulty of simulating randomized algorithms by deterministic ones. The research described here deals with two methods of constructing pseudorandom generators from hard problems and demonstrates some surprising connections between pseudorandom generators and seemingly unrelated topics such as multiparty communication complexity and random oracles. Nisan first establishes a precise connection between computational complexity and pseudorandom number generation, revealing that efficient deterministic simulation of randomized algorithms is possible under much weaker assumptions than was previously known, and bringing to light new consequences concerning the power of random oracles. Using a remarkable argument based on multiparty communication complexity, Nisan then constructs a generator that is good against all tests computable in logarithmic space. A consequence of this result is a new construction of universal traversal sequences. ContentsIntroduction * Hardness vs. Randomness * Pseudorandom Generators for Logspace and Multiparty Protocols