Preface Due to the development of hardware technologies (such as VLSI) in the early 1980s, the interest in parallel and distributive computing has been rapidly growingandinthelate1980sthestudyofparallelalgorithmsandarchitectures became one of the main topics in computer science. To bring the topic to educatorsandstudents, severalbooksonparallelcomputingwerewritten. The involvedtextbook IntroductiontoParallelAlgorithmsandArchitectures by F. Thomson Leighton in 1992 was one of the milestones in the development of parallel architectures and parallel algorithms. But in the last decade or so the main interest in parallel and distributive computing moved from the design of parallel algorithms and expensive parallel computers to the new distributive reality the world of interconnected computers that cooperate (often asynchronously) in order to solve di?erent tasks. Communication became one of the most frequently used terms of computer science because of the following reasons: (i) Considering the high performance of current computers, the communi- tion is often moretime consuming than the computing time of processors. As a result, the capacity of communication channels is the bottleneck in the execution of many distributive algorithms. (ii) Many tasks in the Internet are pure communication tasks. We do not want to compute anything, we only want to execute some information - change or to extract some information as soon as possible and as cheaply as possible. Also, we do not have a central database involving all basic knowledge. Instead, wehavea distributed memorywherethe basickno- edgeisdistributedamongthelocalmemoriesofalargenumberofdi?erent computers. The growing importance of solving pure communication tasks in the - terconnected world is the main motivation for writing this book."

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."

Juraj Hromkovic takes the reader on an elegant route through the theoretical fundamentals of computer science. The author 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.

The ?rst and foremost goal of this lecture series was to show the beauty, depth and usefulness of the key ideas in computer science. While working on the lecture notes, we came to understand that one can recognize the true spirit of a scienti?c discipline only by viewing its contributions in the framework of science as a whole. We present computer science here as a fundamental science that, interacting with other scienti?c disciplines, changed and changes our view on the world, that contributes to our understanding of the fundamental concepts of science and that sheds new light on and brings new meaning to several of these concepts. We show that computer science is a discipline that discovers spectacular, unexpected facts, that ?nds ways out in seemingly unsolvable s- uations, and that can do true wonders. The message of this book is that computer science is a fascinating research area with a big impact on the real world, full of spectacular ideas and great ch- lenges. It is an integral part of science and engineering with an above-average dynamic over the last 30 years and a high degree of interdisciplinarity. The goal of this book is not typical for popular science writing, whichoftenrestrictsitselftooutliningtheimportanceofaresearch area. Whenever possible we strive to bring full understanding of the concepts and results presented.

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."

Juraj Hromkovic takes the reader on an elegant route through the theoretical fundamentals of computer science. The author 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.

Algorithmic design, especially for hard problems, is more essential for success in solving them than any standard improvement of current computer tech nologies. Because of this, the design of algorithms for solving hard problems is the core of current algorithmic research from the theoretical point of view as well as from the practical point of view. There are many general text books on algorithmics, and several specialized books devoted to particular approaches such as local search, randomization, approximation algorithms, or heuristics. But there is no textbook that focuses on the design of algorithms for hard computing tasks, and that systematically explains, combines, and compares the main possibilities for attacking hard algorithmic problems. As this topic is fundamental for computer science, this book tries to close this gap. Another motivation, and probably the main reason for writing this book, is connected to education. The considered area has developed very dynami cally in recent years and the research on this topic discovered several profound results, new concepts, and new methods. Some of the achieved contributions are so fundamental that one can speak about paradigms which should be in cluded in the education of every computer science student. Unfortunately, this is very far from reality. This is because these paradigms are not sufficiently known in the computer science community, and so they are insufficiently com municated to students and practitioners."

Als mehrbandiges Nachschlagewerk ist das Springer-Handbuch der Mathematik in erster Linie fur wissenschaftliche Bibliotheken, akademische Institutionen und Firmen sowie interessierte Individualkunden in Forschung und Lehregedacht. Es erganzt das einbandige themenumfassende Springer-Taschenbuch der Mathematik (ehemaliger Titel Teubner-Taschenbuch der Mathematik), das sich in seiner begrenzten Stoffauswahl besonders an Studierende richtet. Teil III des Springer-Handbuchs enthalt neben den Kapiteln 5-9 des Springer-Taschenbuchs zusatzliches Material zu stochastischen Prozessen.

This book constitutes the refereed proceedings of the 4th International Symposium on Stochastic Algorithms: Foundations and Applications, SAGA 2007. The nine revised full papers and five invited papers presented were carefully selected for inclusion in the book. The contributed papers included in this volume cover both theoretical as well as applied aspects of stochastic computations with a special focus on investigating the power of randomization in algorithmics.

During its 30-year existence, the International Workshop on Graph-Theoretic Concepts in Computer Science has become a distinguished and high-quality computer science event. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can successfully be applied to v- ious areas of computer science and by exposing new theories emerging from applications. In this way, WG provides a common ground for the exchange of information among people dealing with several graph problems and working in various disciplines. Thereby, the workshop contributes to forming an interdis- plinary research community. The original idea of the Workshop on Graph-Theoretic Concepts in C- puter Science was ingenuity in all theoretical aspects and applications of graph concepts, wherever applied. Within the last ten years, the development has strengthened in particular the topic of structural graph properties in relation to computational complexity. This workshop has become pivotal for the c- munity interested in these areas.An aimspeci?c to the 30thWG was to support the central role of WG in both of the prementioned areas on the one hand and on the other hand to promote its originally broader scope. The 30th WG was held at the Physikzentrum Bad Honnef, which serves as the main meeting point of the German Physical Society. It o?ers a secluded setting for research conferences, seminars, and workshops, and has proved to be especiallystimulatingforfruitful discussions.Talksweregiveninthenewlecture hall with a modern double rear projection, interactive electronic board, and full video conferencing equipment.

The International Workshop on Graph-Theoretic Concepts in Computer Science is one of the most traditional and high quality conferences in Computer Science. PreviousconferenceswereorganizedatvariousplacesinAustria, Germany, Italy, and the Netherlands. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computer science, or by extracting new problems from applications. The goal is to present recent research results and to identify and explore directions of future research. The workshop is well-balanced with respect to established researchers and young scientists. th The24 InternationalWorkshoponGraph-TheoreticConceptsinComputer Science(WG'98)washeldatSmoleniceCastle, nearBratislava, SlovakRepublic, June 18-20, 1998. It was organized by the Slovak Academy of Computer Science in cooperation with the Department of Computer Science I at RWTH Aachen (Germany) and with Slovak Society for Computer Science. For the ?rst time in its history, WG took place in a country of the former eastern block, in the Slovak Republic. The program committee of WG'98 consisted of: H. Bodlaender, Utrecht (NL) A. Brandst] adt, Rostock (D) M. Habib, Montpellier (F) J. Hromkovi? c, Aachen (D) L. Kirousis, Patras (GR) L. Ku? cera, Praha (CR) A. Marchetti-Spaccamela, Roma (I) E. Mayr, Munc ] hen (D) R. Moehring, Berlin (D) M. Nagl, Aachen (D) H. Noltemeier, Wurzburg ] (D) F. Parisi Presicce, Roma (I) O. Syk ora, Bratislava (SK) G. Tinhofer, Munc ] hen (D) D. Wagner, Konstanz (D) P."

There are several approaches to attack hard problems. All have their merits, but also their limitations, and need a large body of theory as their basis. A number of books for each one exist: books on complexity theory, others on approximation algorithms, heuristic approaches, parametrized complexity, and yet others on randomized algorithms. This book discusses thoroughly all of the above approaches. And, amazingly, at the same time, does this in a style that makes the book accessible not only to theoreticians, but also to the non-specialist, to the student or teacher, and to the programmer. Do you think that mathematical rigor and accessibility contradict? Look at this book to find out that they do not, due to the admirable talent of the author to present his material in a clear and concise way, with the idea behind the approach spelled out explicitly, often with a revealing example.Reading this book is a beautiful experience and I can highly recommend it to anyone interested in learning how to solve hard problems. It is not just a condensed union of material from other books. Because it discusses the different approaches in depth, it has the chance to compare them in detail, and, most importantly, to highlight under what circumstances which approach might be worth exploring. No book on a single type of solution can do that, but this book does it in an absolutely fascinating way that can serve as a pattern for theory textbooks with a high level of generality. (Peter Widmayer)The second edition extends the part on the method of relaxation to linear programming with an emphasis on rounding, LP-duality, and primal-dual schema, and provides a self-contained and transparent presentation of the design of randomized algorithms for primality testing.

Das Vieweg+Teubner Taschenbuch der Mathematik erfullt aktuell, umfassend und kompakt alle Erwartungen, die an ein mathematisches Nachschlagewerk gestellt werden. Es vermittelt ein lebendiges und modernes Bild der heutigen Mathematik. Als Taschenbuch begleitet es die Bachelor-Studierenden vom ersten Semester bis zur letzten Prufung und der Praktiker nutzt es als standiges und unentbehrliches Nachschlagewerk in seinem Berufsalltag. Das Taschenbuch bietet alles, was in Bachelor-Studiengangen im Haupt- und Nebenfach Mathematik benotigt wird. Der Text fur diese Ausgabe wurde stark uberarbeitet. Zu spezielle Inhalte wurden herausgenommen und dafur Themen der Wirtschaftsmathematik und Algorithmik hinzugenommen. Das Vieweg+Teubner Handbuch der Mathematik (eAusgabe) enthalt daruberhinaus erganzendes und weiterfuhrendes Material fur das
Masterstudium.
"

The ?rst and foremost goal of this lecture series was to show the beauty, depth and usefulness of the key ideas in computer science. While working on the lecture notes, we came to understand that one can recognize the true spirit of a scienti?c discipline only by viewing its contributions in the framework of science as a whole. We present computer science here as a fundamental science that, interacting with other scienti?c disciplines, changed and changes our view on the world, that contributes to our understanding of the fundamental concepts of science and that sheds new light on and brings new meaning to several of these concepts. We show that computer science is a discipline that discovers spectacular, unexpected facts, that ?nds ways out in seemingly unsolvable s- uations, and that can do true wonders. The message of this book is that computer science is a fascinating research area with a big impact on the real world, full of spectacular ideas and great ch- lenges. It is an integral part of science and engineering with an above-average dynamic over the last 30 years and a high degree of interdisciplinarity. The goal of this book is not typical for popular science writing, whichoftenrestrictsitselftooutliningtheimportanceofaresearch area. Whenever possible we strive to bring full understanding of the concepts and results presented.

Aufbauend auf dem ersten Band, werden in diesem Buch weiterfuhrende Konzepte der Wahrscheinlichkeitstheorie ausfuhrlich und verstandlich diskutiert. Mit vielen exemplarisch durchgerechneten Aufgaben, einer Vielzahl weiterer Problemstellungen und ausfuhrlichen Loesungen bietet es dem Leser die Moeglichkeit, die eigenen Fahigkeiten standig zu erweitern und kritisch zu uberprufen und ein tieferes Verstandnis der Materie zu erlangen. Realitatsnahe Anwendungen ermoeglichen einen Ausblick in die breite Verwendbarkeit dieser Theorie.Auch in diesem Band wird auf die Entwicklung der Begriffsbildung und der mathematischen Konzepte besonderer Wert gelegt, sodass man ihre Bedeutung bei der Erzeugung wie auch standige Verbesserung von Forschungsinstrumenten fur die Untersuchung unserer Welt erleben kann. Gerichtet ist das Buch an Gymnasiasten, Studienanfanger an Hochschulen, Lehrer und Interessierte, die sich mit diesem Gebiet vertraut machen moechten.

The International Conference on Informatics in Secondary Schools: Evolution and Perspective (ISSEP) is an emerging forum for researchers and practitioners in the area of computer science education with a focus on secondary schools. The ISSEP series started in 2005 in Klagenfurt, and continued in 2006 in Vilnius, and in 2008 in Torun. The 4th ISSEP took part in Zurich. This volume presents 4 of the 5 invited talks and 14 regular contributions chosen from 32 submissions to ISSEP 2010. The ISSEP conference series is devoted to all aspects of computer science teaching. In the preface of the proceedings of ISSEP 2006, Roland Mittermeir wrote: "ISSEP aims at educating 'informatics proper' by showing the beauty of the discipline, hoping to create interest in a later professional career in c- puting, and it will give answers di?erent from the opinion of those who used to familiarize pupils with the basics of ICT in order to achieve computer lit- acy for the young generation. " This is an important message at this time, when several countries have reduced teaching informatics to educating about current softwarepackagesthatchangefromyeartoyear. ThegoalofISSEPistosupport teaching of the basic concepts and methods of informatics, thereby making it a subject in secondary schools that is comparable in depth and requirements with mathematics or natural sciences. As we tried to present in our book "Algori- mic Adventures.

Das Ziel dieses Buches ist es, den Leser an den Grundlagen der Informatik zu begeistern. Um dies zu erreichen, bieten wir ausser der ublichen rigorosen und detaillierten Prasentation eine leicht verstandliche und anschauliche Darstellung der Grundkonzepte und Ideen und erweitern die klassischen Themen wie Berechenbarkeit und Komplexitat um die faszinierenden Errungenschaften neuer Gebiete wie Randomisierung, Kryptographie und Kommunikation in Netzen.

Dieses Lehrbuch ermoglicht einen begeisterten Einstieg ins Programmieren ab 10 Jahren. Programmierunterricht wird dabei als Forderung der konstruktiven Losungsfahigkeit und der exakten Kommunikation zur Steuerung eines Computers verstanden. Die Schuler entdecken und entwickeln die Programmiersprache selbststandig mit und lernen, Aufgaben systematisch zu losen. Beginnend mit einzelnen Anweisungen werden einfache Programme spielerisch eingefuhrt. Das Buch zeichnet sich aus durch seine detaillierten Erklarungen und anschaulichen Darstellungen. Die Programmierumgebung sowie die Arbeitshefte fur den Unterricht stehen kostenlos zum Download zur Verfugung.
"

Presents the background and context of all ideas, concepts, algorithms, analyses and arguments before discussing details.
Accessible to both beginners as well as specialists.

Das Buch versteht sich als einfache Einfuhrung in die grundlegenden algorithmischen Konzepte der Informatik. Die Konzepte werden in ihrer historischen Entwicklung und in groesseren Zusammenhangen dargestellt, um so die eigentliche Faszination der Informatik, die viel kontraintuitive UEberraschungen bereithalt, zu wecken.

Zufall ist ein erfolgreiches Mittel fur Entwurf und Entwicklung vieler Systeme in Informatik und Technik. Zufallsgesteuerte Algorithmen sind oft effizienter, einfacher, preiswerter und uberraschenderweise auch zuverlassiger als die besten deterministischen Programme.
Warum ist die Zufallssteuerung so erfolgreich und wie entwirft man randomisierte Systeme? Einfach, intuitiv und trotzdem formal prazise gibt dieses Buch dem Leser einen Einstieg in die wunderbare Welt zufallsgesteuerter Algorithmen."

Mit grossem didaktischen Geschick gelingt es den Autoren, Begeisterung fur die Welt der geheimen Botschaften zu wecken. So gelingt der Einstieg in die Kryptologie ganz leicht. Viele Beispiele und Aufgaben regen dazu an, sich selbstandig mit diesem faszinierenden Gebiet zu beschaftigen und helfen dabei, den erlernten Stoff weiter zu vertiefen.

Allgemeinverstandlich und spannend zeigt Juraj Hromkovic seinen Lesern, was Informatik heute leisten kann, was morgen moeglich sein koennte und welche Grenzen vermutlich nie uberschritten werden. Dabei bleibt der Leser aber nicht auf die Rolle des passiven Rezipienten beschrankt. Er erhalt Aufgaben, die mit den im Buch vermittelten Kenntnissen loesbar sind und ihm ermoeglichen, die spannenden Wege der grundlegenden Entdeckungen noch einmal fur sich durchzugehen und dadurch die Begeisterung ihrer Entdecker zu erleben.

Die Bildung der grundlegenden Begriffe und Konzepte der Informatik und der Mathematik wie Programm, Algorithmus, Beweis und Argumentation, Unendlichkeit und die Grenzen der Automatisierbarkeit werden ohne Vorwissen des Lesers in der Informatik in kleinen Schritten vermittelt.