Juraj Hromkovič

Das Buch versteht sich als einfache Einführung in die grundlegenden algorithmischen Konzepte der Informatik. Die Konzepte werden in ihrer historischen Entwicklung und in größeren Zusammenhängen dargestellt, um so die eigentliche Faszination der Informatik, die viel kontraintuitive Überraschungen bereithält, zu wecken. "Um den Leser nicht zu überfordern, werden Definitionen und Merksätze auf das notwendige Maß reduziert. Fazit: Ein aktuelles und beliebtes Lehrbuch zu einem wenig beliebten Thema." Buchkatalog.de, 29.05.2008

Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie

Theoretische Informatik

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.

Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography

Theoretical Computer Science

An introduction to the methods of designing algorithms for hard computing tasks, concentrating mainly on approximate, randomized, and heuristic algorithms, and on the theoretical and experimental comparison of these approaches according to the requirements of the practice. This is the first book to systematically explain and compare all the main possibilities of attacking hard computing problems. It also closes the gap between theory and practice by providing at once a graduate textbook and a handbook for practitioners dealing with hard computing problems.

Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics

Algorithmics for Hard Problems

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.

Communication Complexity and Parallel Computing

Rastislav Královic

Jan Vahrenhold

Richard Královič

This book constitutes the refereed proceedings of the fourth International Conference on Informatics in Secondary Schools - Evolution and Perspectives, ISSEP 2010, held in Zurich, Switzerland in January 2010. The 14 revised full papers presented together with 6 invited papers were carefully reviewed and selected from 32 submissions. A broad variety of topics related to teaching informatics in secondary schools is addressed ranging from national experience reports to paedagogical and methodological issues. Contributions solicited cover a variety of topics including but not limited to accessibility, assessment, classroom management, communication skills, computer science contests, computers and society, courseware, curriculum issues, research in informatics education, diagnostic teaching, empirical methods, ethical/societal issues, gender and diversity issues, high school/college transition issues, information systems, information technology, interdisciplinary courses and projects, laboratory/active learning, multimedia, object-oriented issues, pedagogy, student retention and persistence, role of programming and algorithmics, using emerging instructional, technologies and web-based techniques/web services.

4th International Conference on Informatics in Secondary Schools - Evolution and Perspectives, ISSEP 2010, Zurich, Switzerland, January 13-15, 2010, Proceedings

Teaching Fundamental Concepts of Informatics

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.

Dennis Komm

Hans-Joachim Böckenhauer

A Technique to Obtain Hardness Results for Randomized Online Algorithms - a Survey

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.

Keith Jeffery

Stefan Wolf

Ivana Cerná

Tibor Gyimóthy

Rastislav Kralovic

Marko Vukolic

This book constitutes the refereed proceedings of the 37th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011, held in Nový, Smokovec, Slovakia in January 2011. The 41 revised full papers, presented together with 5 invited contributions, were carefully reviewed and selected from 122 submissions. SOFSEM 2011 was organized around the following four tracks: foundations of computer science; software, systems, and services; processing large datasets; and cryptography, security, and trust.

37th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 22-28, 2011. Proceedings

SOFSEM 2011: Theory and Practice of Computer Science

Karin Freiermuth

Lucia Keller

Björn Steffen

Mit großem didaktischen Geschick gelingt es den Autoren, Begeisterung für die Welt der geheimen Botschaften zu wecken. So gelingt der Einstieg in die Kryptologie ganz leicht. Viele Beispiele und Aufgaben regen dazu an, sich selbständig mit diesem faszinierenden Gebiet zu beschäftigen und helfen dabei, den erlernten Stoff weiter zu vertiefen.

Lehrbuch für Unterricht und Selbststudium

Einführung in die Kryptologie

Zufall ist ein erfolgreiches Mittel für Entwurf und Entwicklung vieler Systeme in Informatik und Technik. Zufallsgesteuerte Algorithmen sind oft effizienter, einfacher, preiswerter und überraschenderweise auch zuverlässiger als die besten deterministischen Programme. Warum ist die Zufallssteuerung so erfolgreich und wie entwirft man randomisierte Systeme? Einfach, intuitiv und trotzdem formal präzise gibt dieses Buch dem Leser einen Einstieg in die wunderbare Welt zufallsgesteuerter Algorithmen.

Methoden zum Entwurf von zufallsgesteuerten Systemen für Einsteiger

Randomisierte Algorithmen

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.

From Knowledge to Magic

Algorithmic Adventures

Peter Widmayer

Richard Královiç

Marc Nunkesser

This book constitutes the refereed proceedings of the 4th International Symposium on Stochastic Algorithms: Foundations and Applications, SAGA 2007, held in Zurich, Switzerland, in September 2007. The 9 revised full papers and 5 invoted papers presented were carefully reviewed and selected out of 31 submissions for inclusion in the book. The contributed papers included in this volume cover both theoretical as well as applied aspects of stochastic computations whith a special focus on investigating the power of randomization in algorithmics.

4th International Symposium, SAGA 2007, Zurich, Switzerland, September 13-14, 2007, Proceedings

Stochastic Algorithms: Foundations and Applications

Bernhard Westfechtel

Manfred Nagl

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.

Juraj Hromkovič

About

Books

Join the club