Дискретная математика
Математика
  • формат pdf
  • размер 57.38 МБ
  • добавлен 31 января 2012 г.
Paun G., Rozenberg G., Salomaa A. (eds.) Current Trends in Theoretical Computer Science. The Challenge of the New Century
Издательство World Scientific, 2004, -1317 pp.

This book continues the tradition of two previous books Current Trends in Theoretical Computer Science, published by World Scientific Publishing Company in 1993 and 2001. We have been very impressed and encouraged by the exceptionally good reception of the two previous books. The positive comments received show that books of this nature are really needed.
The book is based on columns and tutorials published in the Bulletin of the European Association for Theoretical Computer Science (EATCS) in the period 2000-2003. The columnists selected themselves the material they wanted to be included in the book, and the authors were asked to update their contributions. Special effort has been given to presentation - most articles are reader-friendly and do not presuppose much knowledge of the area in question. We believe that the book will constitute suitable supplementary reading material for various courses in computer science. Indeed, the book highlights some key issues and challenges in theoretical computer science, as they seem to us now at the beginning of the new millennium. A glance through the subsequent table of contents should show that many of the most active current research lines in theoretical computer science are represented. Both survey articles and papers dealing with specific problems are included.
In addition to the chapters covered in the two previous books, the current one has two new chapters, "Algorithmics" and "Distributed Computing", that include selected contributions from the corresponding two new columns of the EATCS Bulletin (i.e., columns initiated in the period 2000-2003).
As a matter of fact, with the two new chapters the ammount of material to be covered became much too big for a single book, and therefore the chapters were divided into two volumes: "Algorithms and Complexity" and "Formal Models and Semantics". This is by now a traditional division of theoretical computer science (used, e.g., by the "Handbook of Theoretical Computer Science" and by ICALP - the major general conference devoted to theoretical computer science).
The current first volume, "Algorithms and Complexity", includes the following chapters: "Algorithmics", "Complexity", "Distributed Computing", and "Natural Computing", while the second volume, "Formal Models and Semantics", consists of the following chapters: "Formal Specification", "Logic in Computer Science", "Concurrency", and "Formal Language Theory".
Volume 1 Algorithms and Complexity.
Chapter 1 Algorithmics.
H-Coloring of Graphs.
Open Problems in the Theory of Scheduling.
Analysis of Algorithms (AofA). Part I: 1993–1998 ("Dagstuhl Period").
Analysis of Algorithms (AofA). Part II: 1998–2000 ("Princeton-Barcelona-Gdansk").
Algorithm Engineering.
PRIMES?P (Without Assumptions).
Selfish Task Allocation.
Chapter 2 Computational Complexity.
A Physics-Free Introduction to the Quantum Computation Model.
The Division Breakthroughs.
Derandomization: A Brief Overview.
Recent Developments in Explicit Constructions of Extractors.
The Art of Uninformed Decisions: A Primer to Property Testing.
Time-Space Lower Bounds for NP-Complete Problems.
Chapter 3 Distributed Computing.
A Combinatorial Characterization of Properties Preserved by Antitokens.
Distributed Computation Meets Design Theory: Local Scheduling for Disconnected Cooperation.
Distributed Communication Algorithms for Ad-hoc Mobile Networks.
Selfish Routing in Non-Cooperative Networks: A Survey.
Distributed Algorithmic Mechanism Design: Recent Results and Future Directions.
Stability in Routing: Networks and Protocols.
Chapter 4 Natural Computing.
Quantum Computation Explained to My Mother.
Universality and Quantum Computing.
Some Open Problems Related to Quantum Computing.
Aqueous Computing: Writing Into Fluid Memory.
Biomolecular Computing in silico.
Gene Assembly in Ciliates. Part I: Molecular Operations.
Gene Assembly in Ciliates. Part II: Formal Frameworks.
A Grand Challenge for Computing: Towards Full Reactive Modeling of a Multi-Cellular Animal.
Evolutionary Computation: A Guided Tour.
Artificial Chemistries.
Neural Computing.
Volume 2 Formal Models and Semantics.
Chapter 1 Formal Specification.
The Role of Mathematics and Formal Specification Techniques in Software System Development.
Failure-Divergence Semantics as a Formal Basis for an Object-Oriented Integrated Formal Method.
Bigraphs Meet Double Pushouts.
A New Experience with Graph Transformation.
Meta-Modelling and Graph Transformation for the Simulation of Systems.
Net Transformations for Petri Net Technology.
On the Relevance of High-Level Net Processes.
Chapter 2 Logic in Computer Science.
A New Zero-One Law and Strong Extension Axioms.
Tree-Decompositions and the Model-Checking Problem.
Is Randomness "Native" to Computer Science?
How to Find a Coin: Prepositional Program Logics Made Easy.
Algorithms vs. Machines.
Pairwise Testing.
Newman's Lemma - A Case Study in Proof Automation and Geometric Logic.
Algorithms: A Quest for Absolute Definitions.
Chapter 3 Concurrency.
Some of My Favourite Results in Classic Process Algebra.
Roadmap of Infinite Results.
Construction and Verification of Concurrent Performance and Reliability Models.
Does Combining Nondeterminism and Probability Make Sense?
The Algebraic Structure of Petri Nets.
Chapter 4 Formal Language Theory.
Combinatorics on Words — A Tutorial.
Two Problems on Commutation of Languages.
Counting (Scattered) Subwords.
Post Correspondence Problem - Recent Results.
The DFOL Language Equivalence Problem.
An Overview of Conjunctive Grammars.
State Complexity of Finite and Infinite Regular Languages.
GSMs and Contexts.
The Depth of Functional Compositions.
Language Generating by Means of Membrane Systems.
Membrane Computing: New Results, New Problems.
Похожие разделы
Смотрите также

Drmota M., Flajolet P., Gardy D., Gittenberger B. (editors) Mathematics and Computer Science III: Algorithms, Trees, Combinatirics and Probabilities

  • формат djvu
  • размер 5.34 МБ
  • добавлен 13 января 2011 г.
Birkh?user Basel, 2004. - 554 pages. This book contains invited and contributed papers on combinatorics, random graphs and networks, algorithms analysis and trees, branching processes, constituting the Proceedings of the 3rd International Colloquium on Mathematics and Computer Science that will be held in Vienna in September 2004. It addresses a large public in applied mathematics, discrete mathematics and computer science, including researchers...

Feil T., Krone J. Essential Discrete Math for Computer Science

  • формат pdf
  • размер 8.91 МБ
  • добавлен 19 января 2011 г.
Prentice Hall, 2002. - 216 Pages. This book introduces readers to the mathematics of computer science and prepares them for the math they will encounter in other college courses. It includes applications that are specific to computer science, helps learners to develop reasoning skills, and provides the fundamental mathematics necessary for computer scientists. Chapter topics include sets, functions and relations, Boolean algebra, natural numbers...

Gazeau J.-P., Ne?et?il N., Rovan B. (eds.) Physics and Theoretical Computer Science. From Numbers and Languages to (Quantum) Cryptography

  • формат pdf
  • размер 5.86 МБ
  • добавлен 31 января 2012 г.
Издательство IOS Press, 2007, -348 pp. As a part of the NATO Security Through Science Programme, the goal of the Advanced Study Institute Physics and Computer Science was to reinforce the interface between physical sciences, theoretical computer science, and discrete mathematics. No one can dispute the current importance of applied as well as theoretical Computer Science in the development and the practice of Physical Sciences. Physicists of cou...

Haggard G., Schlipf J., Whitesides S. Discrete Mathematics for Computer Science

  • формат pdf
  • размер 25.96 МБ
  • добавлен 01 января 2011 г.
Brooks Cole, 2005. - 718 Pages. Master the fundamentals of discrete mathematics with DISCRETE MATHEMATICS FOR COMPUTER SCIENCE! An increasing number of computer scientists from diverse areas are using discrete mathematical structures to explain concepts and problems and this mathematics text shows you how to express precise ideas in clear mathematical language. Through a wealth of exercises and examples, you will learn how mastering discrete mat...

Hromkovi? J. Theoretical Computer Science. Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography

  • формат djvu
  • размер 5.94 МБ
  • добавлен 31 января 2012 г.
Издательство Springer, 2004, -318 pp. This textbook is an introduction to theoretical computer science with a focus on the development of its algorithmic concepts. It is based on a substantially extended translation of the German textbook "Algorithmische Konzepte der Informatik" written for the first introductory course to theoretical fundamentals of computer science at the University of Aachen. The topics have been chosen to strike a balance be...

Ito M. Automata, Formal Languages and Algebraic Systems

  • формат pdf
  • размер 1.69 МБ
  • добавлен 18 октября 2011 г.
World Scientific Publishing Company, 2010. - 248 pages. This volume consists of papers selected from the presentations at the workshop and includes mainly recent developments in the fields of formal languages, automata theory and algebraic systems related to the theoretical computer science and informatics. It covers the areas such as automata and grammars, languages and codes, combinatorics on words, cryptosystems, logics and trees, Grobner ba...

McEvoy K., Tucker J.V. Theoretical Foundations of VLSI Design

  • формат djvu
  • размер 3.02 МБ
  • добавлен 02 февраля 2012 г.
Издательство Cambridge University Press, 1990, -443 pp. The development of VLSI fabrication technology has resulted in a wide range of new ideas for application specific hardware and computer architectures, and in an extensive set of significant new theoretical problems for the design of hardware. The design of hardware is a process of creating a device that realises an algorithm, and many of the problems are concerned with the nature of algorith...

McNaughton R. Elementary Computability, Formal Languages, and Automata

  • формат djvu
  • размер 3.4 МБ
  • добавлен 24 августа 2011 г.
Prentice Hall, 1982. - 417 Pages. This book is an introduction to theoretical computer science emphasizing two interrelated areas: the theory of computability (how to tell whether problems are algorithmically solvable) and the theory of formal languages (how to design and use special languages, as for algorithms). Automata (idealized computer devices) are used as precise models of computation in studies that have actual computers as their primar...

Singh A. Elements of Computation Theory

  • формат pdf
  • размер 4.5 МБ
  • добавлен 08 декабря 2011 г.
Издательство Springer, 2009, -428 pp. The foundation of computer science is built upon the following questions: What is an algorithm? What can be computed and what cannot be computed? What does it mean for a function to be computable? How does computational power depend upon programming constructs? Which algorithms can be considered feasible? For more than 70 years, computer scientists are searching for answers to such questions. Their inge...

Van Steen M. Graph Theory and Complex Networks: An Introduction

  • формат pdf
  • размер 5.02 МБ
  • добавлен 02 ноября 2011 г.
Maarten van Steen, 2010. - 300 pages. Maarten van Steen is full professor at the Computer Science department of VU University Amsterdam, The Netherlands. He mainly teaches in the field of distributed systems, computer networks, and operating systems. Together with Andrew Tanenbaum he has co-authored a well-known textbook on distributed systems. Confronted with the difficulties that undergraduates in computer science have with mathematics, he se...