Theoretical Computer Science - Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography

The aim of this textbook is not only to provide an elegant route through the theoretical fundamentals of computer science, but also to show that theoretical computer science is a fascinating discipline, full of spectacular contributions and miracles, and depth in research, and yet directly applicable. Thus, we aim to excite people about its study. To achieve these goals we do not hesitate to take a lot of space to present motivations, and especially to give the informal development of crucial ideas and concepts and their transparent, but rigorous presentation.
An additional aim is to present the development of the computer scientist's way of thinking, so we do not restrict this book to the classic areas like computability and automata theory but we also present fundamental concepts such as approximation and randomization in algorithmics and we explain the basic ideas of cryptography and interconnection network design.

List of contents

Introduction; Alphabets, Words, Languages and Algorithmic Problems; Finite Automata; Turing Machines; Computability; Complexity Theory; Algorithmics for Hard Problems; Randomization; Communication and Cryptography; References.

About the author

Prof. Dr. Juraj Hromkovic war 1997 - 2003 Professor für Algorithmen und Komplexität an der RWTH Aachen. Seit Januar 2004 ist er Professor für Informatik an der ETH Zürich. Seit 2010 ist er Mitglied der Academia Europaea.

Summary

This textbook provides an elegant route through the theoretical fundamentals of computer science. In doing so, it shows that theoretical computer science is a fascinating discipline, full of spectacular contributions and miracles. The book also presents the development of the computer scientist's way of thinking as well as fundamental concepts such as approximation and randomization in algorithmics, and the basic ideas of cryptography and interconnection network design.
 

Product details

• Authors: Juraj Hromkovi, Juraj Hromkovic, Juraj Hromkovič
• Publisher: Springer, Berlin
• Languages: English
• Product format: Hardback
• Released: 09.10.2003
• EAN: 9783540140153
• ISBN: 978-3-540-14015-3
• No. of pages: 313
• Dimensions: 156 mm x 243 mm x 20 mm
• Weight: 608 g
• Illustrations: X, 313 p.
• Series: Texts in Theoretical Computer Science EATCS; Texts in Theoretical Computer Science. An EATCS Series; Texts in Theoretical Computer Science. An EATCS Series
• Subjects: Natural sciences, medicine, IT, technology > IT, data processing > IT; B, Algorithms, computer science, Theory of Computation, Discrete Mathematics in Computer Science, Discrete Mathematics, Computers, Algorithms & data structures, Coding and Information Theory, Information theory, Coding theory & cryptology, Mathematical theory of computation, Coding theory, Computer science—Mathematics, Maths for computer scientists, Algorithm Analysis and Problem Complexity, Computation by Abstract Devices