This two-volume set of LNCS 7391 and LNCS 7392 constitutes the refereed proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP 2012, held in Warwick, UK, in July 2012. The total of 123 revised full papers presented in this volume were carefully reviewed and selected from 432 submissions. They are organized in three tracks focussing on algorithms, complexity and games; logic, semantics, automata and theory of programming; and foundations of networked computation.

This two-volume set of LNCS 7391 and LNCS 7392 constitutes the refereed proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP 2012, held in Warwick, UK, in July 2012. The total of 123 revised full papers presented in this volume were carefully reviewed and selected from 432 submissions. They are organized in three tracks focussing on algorithms, complexity and games; logic, semantics, automata and theory of programming; and foundations of networked computation.

Sponsored by AFCET (Association Francaise pour la Cybern;&AAe;tique Economique et Technique) and GI (Gesellschaft fur Informatik)

Algorithms are at the heart of every nontrivial computer application, and algorithmics is a modern and active area of computer science. Every computer scientist and every professional programmer should know about the basic algorithmic toolbox: structures that allow efficient organization and retrieval of data, frequently used algorithms, and basic techniques for modeling, understanding and solving algorithmic problems.

This book is a concise introduction addressed to students and professionals familiar with programming and basic mathematical language. Individual chapters cover arrays and linked lists, hash tables and associative arrays, sorting and selection, priority queues, sorted sequences, graph representation, graph traversal, shortest paths, minimum spanning trees, and optimization. The algorithms are presented in a modern way, with explicitly formulated invariants, and comment on recent trends such as algorithm engineering, memory hierarchies, algorithm libraries and certifying algorithms. The authors use pictures, words and high-level pseudocode to explain the algorithms, and then they present more detail on efficient implementations using real programming languages like C++ and Java.

The authors have extensive experience teaching these subjects to undergraduates and graduates, and they offer a clear presentation, with examples, pictures, informal explanations, exercises, and some linkage to the real world. Most chapters have the same basic structure: a motivation for the problem, comments on the most important applications, and then simple solutions presented as informally as possible and as formally as necessary. For the more advanced issues, this approach leads to a more mathematical treatment, including some theorems and proofs. Finally, each chapter concludes with a section on further findings, providing views on the state of research, generalizations and advanced solutions.

This textbook is a concise introduction to the basic toolbox of structures that allow efficient organization and retrieval of data, key algorithms for problems on graphs, and generic techniques for modeling, understanding, and solving algorithmic problems. The authors aim for a balance between simplicity and efficiency, between theory and practice, and between classical results and the forefront of research. Individual chapters cover arrays and linked lists, hash tables and associative arrays, sorting and selection, priority queues, sorted sequences, graph representation, graph traversal, shortest paths, minimum spanning trees, optimization, collective communication and computation, and load balancing. The authors also discuss important issues such as algorithm engineering, memory hierarchies, algorithm libraries, and certifying algorithms. Moving beyond the sequential algorithms and data structures of the earlier related title, this book takes into account the paradigm shift towards the parallel processing required to solve modern performance-critical applications and how this impacts on the teaching of algorithms. The book is suitable for undergraduate and graduate students and professionals familiar with programming and basic mathematical language. Most chapters have the same basic structure: the authors discuss a problem as it occurs in a real-life situation, they illustrate the most important applications, and then they introduce simple solutions as informally as possible and as formally as necessary so the reader really understands the issues at hand. As they move to more advanced and optional issues, their approach gradually leads to a more mathematical treatment, including theorems and proofs. The book includes many examples, pictures, informal explanations, and exercises, and the implementation notes introduce clean, efficient implementations in languages such as C++ and Java.

Algorithms are at the heart of every nontrivial computer application, and algorithmics is a modern and active area of computer science. Every computer scientist and every professional programmer should know about the basic algorithmic toolbox: structures that allow efficient organization and retrieval of data, frequently used algorithms, and basic techniques for modeling, understanding and solving algorithmic problems.

This book is a concise introduction addressed to students and professionals familiar with programming and basic mathematical language. Individual chapters cover arrays and linked lists, hash tables and associative arrays, sorting and selection, priority queues, sorted sequences, graph representation, graph traversal, shortest paths, minimum spanning trees, and optimization. The algorithms are presented in a modern way, with explicitly formulated invariants, and comment on recent trends such as algorithm engineering, memory hierarchies, algorithm libraries and certifying algorithms. The authors use pictures, words and high-level pseudocode to explain the algorithms, and then they present more detail on efficient implementations using real programming languages like C++ and Java.

The authors have extensive experience teaching these subjects to undergraduates and graduates, and they offer a clear presentation, with examples, pictures, informal explanations, exercises, and some linkage to the real world. Most chapters have the same basic structure: a motivation for the problem, comments on the most important applications, and then simple solutions presented as informally as possible and as formally as necessary. For the more advanced issues, this approach leads to a more mathematical treatment, including some theorems and proofs. Finally, each chapter concludes with a section on further findings, providing views on the state of research, generalizations and advanced solutions.

This textbook is a concise introduction to the basic toolbox of structures that allow efficient organization and retrieval of data, key algorithms for problems on graphs, and generic techniques for modeling, understanding, and solving algorithmic problems. The authors aim for a balance between simplicity and efficiency, between theory and practice, and between classical results and the forefront of research. Individual chapters cover arrays and linked lists, hash tables and associative arrays, sorting and selection, priority queues, sorted sequences, graph representation, graph traversal, shortest paths, minimum spanning trees, optimization, collective communication and computation, and load balancing. The authors also discuss important issues such as algorithm engineering, memory hierarchies, algorithm libraries, and certifying algorithms. Moving beyond the sequential algorithms and data structures of the earlier related title, this book takes into account the paradigm shift towards the parallel processing required to solve modern performance-critical applications and how this impacts on the teaching of algorithms. The book is suitable for undergraduate and graduate students and professionals familiar with programming and basic mathematical language. Most chapters have the same basic structure: the authors discuss a problem as it occurs in a real-life situation, they illustrate the most important applications, and then they introduce simple solutions as informally as possible and as formally as necessary so the reader really understands the issues at hand. As they move to more advanced and optional issues, their approach gradually leads to a more mathematical treatment, including theorems and proofs. The book includes many examples, pictures, informal explanations, and exercises, and the implementation notes introduce clean, efficient implementations in languages such as C++ and Java.

Der Entwurf und die Analyse von Datenstrukturen und effizienten Algorithmen hat in den letzten Jahren grosse Bedeutung erlangt: Algorithmus ist der zentrale Begriff der Informatik und Effizienz bedeutet Geld. Ich habe den Stoff in drei Bande und neun Kapitel gegliedert. Band 1: Sortieren und Suchen (Kapitel I bis ill) Band 2: Graphenalgorithmen und NP-Vollstandigkeit (Kapitel IV bis VI) Band 3: Mehrdimensionales Suchen und Algorithmische Geometrie (Kapitel VII und Vill), Algorithmische Paradigmen (Kapitel IX) Die Bande 2 und 3 haben Band 1 als gemeinsame Basis, sind aber voneinander un- abhangig. Grosse Teile dieser Bande koennen ohne detaillierte Kenntnis von Band 1 gelesen werden; eine Kenntnis der algorithmischen Grundprinzipien, wie sie etwa in Kapitel I oder in vielen anderen Buchern uber Datenstrukturen und Algorith- men vermittelt werden, genugt. Die spezifischen Voraussetzungen fur die Bande 2 und 3 sind in den jeweiligen Vorworten angegeben. In allen drei Banden stellen wir wichtige effiziente Algorithmen fur die grundlegenden Probleme in dem jeweiligen Gebiet vor und analysieren sie. Wir messen dabei Effizienz durch die Laufzeit auf einem realistischen Modell einer Rechenanlage, das wir in Kapitel I einfuhren. Die meisten der vorgestellten Algorithmen wurden erst in den letzten Jahren gefunden; die Informatik ist ja schliesslich eine sehr junge Wissenschaft. Es gibt kaum Satze in diesem Buch, die alter als 20 Jahre sind, und mindestens die Halfte des Stoffes ist junger als 10 Jahre. Ich habe stets versucht, den Leser bis an den Stand der Forschung heranzufuhren.

Die Gesellschaft fur Informatik veranstaltet ihre 30. Jahrestagung, die Informatik 2000, vom 19.- 22. September 2000 in Berlin. Die Jahrestagung 2000 beschaftigt sich mit den zentralen Themen "Zukunft der Informatik-Ausbildung,""Bioinformatik," "Aktuelle Trends in der Informatik" und "Softwaretechnik 2000."
Neben Praxisberichten aus der Industrie finden sich Forschungsberichte namhafter aber auch junger Forscher. Die genannten Schwerpunktthemen werden durch Workshops, die im Schlusskapitel des Kongressbandes dokumentiert sind, sinnvoll erganzt."

Dieses Buch behandelt Grundlagen von Programmiersprachen, deren Verknupfung mit realen Rechenmaschinen und - exemplarisch - Algorithmen. Das Ziel des Buches ist es, eine solide Basis fur das Studium der Informatik zu legen. Es ist ins besondere fur Studenten im Grundstudium des Studienganges Informatik gedacht. Ein Programm ist nur dann brauchbar, wenn es das gestellte Problem korrekt loest, und dies daruber hinaus mit der gewunschten Effizienz tut. Aussagen uber die Korrektheit und Effizienz eines Programms sind nur dann moeglich, wenn die verwendete Programmiersprache exakt definiert ist, d.h., wenn die Menge der Pro gramme (Syntax) und deren Bedeutung (Semantik) festliegen. Die Definition von Syntax und Semantik nimmt daher in diesem Buch einen wichtigen Platz ein. For male Definitionen werden erst dann lebendig, wenn sie auf einem guten intuitiven Verstandnis aufbauen, und wenn sie zu Folgerungen in der Form von Satzen fuhren. Daher enthalt dieses Buch eine grosse Anzahl von Beispielen, Satzen und Aufgaben. Die Grundlagen der Programmiersprachen werden eingefuhrt anhand einer spezifischen Programmiersprache, PROSA genannt (PROgrammiersprache SAar brucken). PROSA ist der Programmiersprache Pascal sehr ahnlich, weicht aber in einigen Punkten (z.B. dynamische Felder, geschachtelte Verbunde) aus didaktischen Grunden ab. Die Abweichungen dienen zum einen der Vereinfachung, und zum an deren der lllustration einiger Konzepte, die Pascal nicht kennt. Die Benutzung von Pascal in einem begleitenden Programmierpraktikum stellt aber keinerlei Problem dar.

Algorithmen bilden das Herzstuck jeder nichttrivialen Anwendung von Computern, und die Algorithmik ist ein modernes und aktives Gebiet der Informatik. Daher sollte sich jede Informatikerin und jeder Informatiker mit den algorithmischen Grundwerkzeugen auskennen. Dies sind Strukturen zur effizienten Organisation von Daten, haufig benutzte Algorithmen und Standardtechniken fur das Modellieren, Verstehen und Losen algorithmischer Probleme. Dieses Buch ist eine straff gehaltene Einfuhrung in die Welt dieser Grundwerkzeuge, gerichtet an Studierende und im Beruf stehende Experten, die mit dem Programmieren und mit den Grundelementen der Sprache der Mathematik vertraut sind. Die einzelnen Kapitel behandeln Arrays und verkettete Listen, Hashtabellen und assoziative Arrays, Sortieren und Auswahlen, Prioritatswarteschlangen, sortierte Folgen, Darstellung von Graphen, Graphdurchlaufe, kurzeste Wege, minimale Spannbaume und Optimierung. Die Algorithmen werden auf moderne Weise prasentiert, mit explizit angegebenen Invarianten, und mit Kommentaren zu neueren Entwicklungen wie Algorithm Engineering, Speicherhierarchien, Algorithmenbibliotheken und zertifizierenden Algorithmen. Die Algorithmen werden zunachst mit Hilfe von Bildern, Text und Pseudocode erlautert; dann werden Details zu effizienten Implementierungen gegeben, auch in Bezug auf konkrete Sprachen wie C++ und Java.

"