This volume constitutes the refereed post-workshop proceedings of a workshop on graph-theoretic concepts in computer science. The papers provide results for various classes of graphs, graph computations, graph algorithms and graph-theoretic applications in computer science.
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.
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.
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.
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.
InhaltsverzeichnisInvited Papers.On Computation and Communication with Small Bias.Design Strategies for Minimal Perfect Hash Functions.Hamming, Permutations and Automata.Probabilistic Techniques in Algorithmic Game Theory.Randomized Algorithms and Probabilistic Analysis in Wireless Networking.Contributed Papers.A First Step Towards Analyzing the Convergence Time in Player-Specific Singleton Congestion Games.Communication Problems in Random Line-of-Sight Ad-Hoc Radio Networks.Approximate Discovery of Random Graphs.A VNS Algorithm for Noisy Problems and Its Application to Project Portfolio Analysis.Digit Set Randomization in Elliptic Curve Cryptography.Lower Bounds for Hit-and-Run Direct Search.An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata.Stochastic Methods for Dynamic OVSF Code Assignment in 3G Networks.On the Support Size of Stable Strategies in Random Games.
Introduction to Design Paradigms
Randomness is a powerful phenomenon that can be harnessed to solve various problems in all areas of computer science. Randomized algorithms are often more efficient, simpler and, surprisingly, also more reliable than their deterministic counterparts. Computing tasks exist that require billions of years of computer work when solved using the fastest known deterministic algorithms, but they can be solved using randomized algorithms in a few minutes with negligible error probabilities. Introducing the fascinating world of randomness, this book systematically teaches the main algorithm design paradigms – foiling an adversary, abundance of witnesses, fingerprinting, amplification, and random sampling, etc. – while also providing a deep insight into the nature of success in randomization. Taking sufficient time to present motivations and to develop the reader's intuition, while being rigorous throughout, this text is a very effective and efficient introduction to this exciting field.
Due to advancements in hardware technologies like VLSI in the early 1980s, interest in parallel and distributed computing surged, leading to significant studies in parallel algorithms and architectures by the late 1980s. To educate both students and educators, several texts on parallel computing emerged, including a pivotal textbook in 1992 that contributed to the understanding of parallel architectures and algorithms. However, in recent years, the focus has shifted from designing parallel algorithms and costly parallel computers to the new reality of interconnected computers that collaborate, often asynchronously, to address various tasks. Communication has become a central theme in computer science for several reasons: first, the high performance of modern computers often makes communication more time-consuming than processing, making communication channel capacity a bottleneck for many distributed algorithms; second, numerous Internet tasks are purely communicative, prioritizing the quick and cost-effective execution of information over computation. Additionally, rather than relying on a central database, knowledge is now distributed across the local memories of numerous computers. This growing significance of addressing pure communication tasks in our interconnected world serves as the primary motivation for this exploration.
The communication complexity of two-party protocols, a relatively new measure in complexity theory, has quickly become a fundamental aspect of the field. Similar to Kolmogorov complexity in sequential computations, it serves as a method for analyzing the complexity of problems in parallel information processing. This measure is particularly useful for establishing lower bounds that indicate the necessary computer resources—such as time, hardware, and memory size—required to solve specific tasks. These lower bounds not only help in assessing the computational difficulty of problems but also in validating the optimality of existing algorithms. Furthermore, understanding the communication complexity of a problem can aid in the search for efficient algorithms. As a distinct area within complexity theory, communication complexity is closely linked to several essential complexity measures and contributes to our understanding of determinism, nondeterminism, and randomness in algorithms. A robust mathematical framework has already been developed to address the communication complexity of various computing problems, suggesting that this approach may play a crucial role in tackling several significant open problems in contemporary complexity theory.
Allgemeinverständlich und spannend zeigt Juraj Hromkovic seinen Lesern, was Informatik heute leisten kann, was morgen möglich sein könnte und welche Grenzen vermutlich nie überschritten werden. Dabei bleibt der Leser aber nicht auf die Rolle des passiven Rezipienten beschränkt. Er erhält Aufgaben, die mit den im Buch vermittelten Kenntnissen lösbar sind und ihm ermöglichen, die spannenden Wege der grundlegenden Entdeckungen noch einmal für sich durchzugehen und dadurch die Begeisterung ihrer Entdecker zu erleben. „[Das Buch] ist gleichsam die etwas andere Einführung in das, was dieses Fach ausmacht [...] Potenzielles Geschenk für unschlüssige Abiturienten“ ix - Magazin für professionelle Informationstechnik, 03/07 „Lebendig geschrieben, didaktisch sehr gut gestaltet.“ ekz-Informationsdienst, ID 50/06