Der Autor bietet eine umfassende Einführung sowohl in die Automatentheorie und die Formalen Sprachen als auch in die Berechenbarkeits- und Komplexitätstheorie sowie in die Algorithmik. Der Verzicht auf die übliche Trennung der ´´klassischen´´ Theoretischen Informatik von der Algorithmik macht es möglich, Automatentheorie und Formale Sprachen anwendungsorientiert aus der Sicht des Übersetzerbaus einzuführen. Gelernte Methoden der Algorithmik werden angewendet, damit effiziente Algorithmen zur Lösung von Aufgaben der lexikalischen Analyse und der Syntaxanalyse entwickelt werden können. Ebenso werden Algorithmen zur Lösung von grundlegenden Problemen auf Graphen und auf Strings vorgestellt und eine Einführung in die schnelle Fouriertransformation sowie in die lineare Programmierung gegeben. Die Stoffauswahl erfolgte so, dass die Inhalte auch für die Praxis relevant sind. Das Buch baut auf Vorlesungen des Autors im Grund- und Hauptstudium auf. Weiterführende Hinweise zum Buch.
Dieses Lehrbuch der Algorithmik stellt die grundlegenden Algorithmen dar und vermittelt die Prinzipien von Algorithmusanalyse und -entwurf. In einem einführenden Kapitel werden die benötigten Grundbegriffe aus der Theoretischen Informatik, der Stochastik und der Komplexitätsanalyse bereitgestellt. Die folgenden Kapiteln behandeln die Gebiete Sortieren und Selektion, Hashing, Dynamisches Programmieren, Greedy-Algorithmen, Algorithmen auf Graphen, Optimiertes Suchen in Bäumen, Datenkompression sowie algebraische Algorithmen, String Matching und Heuristiken. Im abschließenden Kapitel werden die effizientesten Algorithmen für das Erfüllbarkeitsproblem der Aussagenlogik diskutiert. Prof. Schöning gelingt durch seinen verständlichen Stil, viele Beispiele und das Aufzeigen von Querverbindungen eine lebendige und gut verständliche Gesamtdarstellung der Algorithmik.
This book constitutes the refereed post-conference proceedings of the 30th International Workshop on Combinatorial Algorithms, IWOCA 2019, held in Pisa, Italy, in July 2019. The 36 regular papers presented in this volume were carefully reviewed and selected from 73 submissions. They cover diverse areas of combinatorical algorithms, complexity theory, graph theory and combinatorics, combinatorial optimization, cryptography and information security, algorithms on strings and graphs, graph drawing and labelling, computational algebra and geometry, computational biology, probabilistic and randomized algorithms, algorithms for big data analytics, and new paradigms of computation.
This book constitutes the proceedings of the 23rd International Conference on Developments in Language Theory, DLT 2019, held in Warsaw, Poland, in August 2019. The 20 full papers presented together with three invited talks were carefully reviewed and selected from 30 submissions. The papers cover the following topics and areas: combinatorial and algebraic properties of words and languages; grammars, acceptors and transducers for strings, trees, graphics, arrays; algebraic theories for automata and languages; codes; efficient text algorithms; symbolic dynamics; decision problems; relationships to complexity theory and logic; picture description and analysis, polyominoes and bidimensional patterns; cryptography; concurrency; celluar automata; bio-inspired computing; quantum computing.
Richard Bird takes a radical approach to algorithm design, namely, design by calculation. These 30 short chapters each deal with a particular programming problem drawn from sources as diverse as games and puzzles, intriguing combinatorial tasks, and more familiar areas such as data compression and string matching. Each pearl starts with the statement of the problem expressed using the functional programming language Haskell, a powerful yet succinct language for capturing algorithmic ideas clearly and simply. The novel aspect of the book is that each solution is calculated from an initial formulation of the problem in Haskell by appealing to the laws of functional programming. Pearls of Functional Algorithm Design will appeal to the aspiring functional programmer, students and teachers interested in the principles of algorithm design, and anyone seeking to master the techniques of reasoning about programs in an equational style.
This book is an essential desktop reference for the CERT C coding standard. The CERT C Coding Standard is an indispensable collection of expert information. The standard itemizes those coding errors that are the root causes of software vulnerabilities in C and prioritizes them by severity, likelihood of exploitation, and remediation costs. Each guideline provides examples of insecure code as well as secure, alternative implementations. If uniformly applied, these guidelines will eliminate the critical coding errors that lead to buffer overflows, format string vulnerabilities, integer overflow, and other common software vulnerabilities.
Despite growing interest in the mathematical analysis of algorithms, basic information on methods and models has rarely been directly accessible to practitioners, researchers, or students. This book organizes and presents that knowledge, fully introducing today´s primary techniques for mathematically analyzing algorithms. Robert Sedgewick and the late Philippe Flajolet have drawn from both classical mathematical and computer science material, integrating discrete mathematics, elementary real analysis, combinatorics, algorithms, and data structures. They focus on ´´average-case´´ or ´´probabilistic´´ analysis, while also covering tools for ´´worst case´´ or ´´complexity´´ analysis. Improvements in this edition include: * Upgraded figures and code * Newer style for presenting much of the text´s math * An all-new chapter on trees This book´s thorough, self-contained coverage will help readers appreciate the field´s challenges, prepare them for advanced results covered in Donald Knuth´s books, and provide the background they need to keep abreast of new research. Coverage includes: recurrences, generating functions, asymptotics, trees, strings, maps, sorting, tree search, string search, and hashing algorithms. Ideal for junior- or senior-level courses on mathematical analysis of algorithms, this book will also be useful in courses on discrete mathematics for computer scientists, and in introducing mathematics students to computer science principles related to algorithms and data structures. Product Description Despite growing interest, basic information on methods and models for mathematically analyzing algorithms has rarely been directly accessible to practitioners, researchers, or students. An Introduction to the Analysis of Algorithms, Second Edition, organizes and presents that knowledge, fully introducing primary techniques and results in the field. Robert Sedgewick and the late Philippe Flajolet have drawn from both classical mathematics and computer science, integrating discrete mathematics, elementary real analysis, combinatorics, algorithms, and data structures. They emphasize the mathematics needed to support scientific studies that can serve as the basis for predicting algorithm performance and for comparing different algorithms on the basis of performance. Techniques covered in the first half of the book include recurrences, generating functions, asymptotics, and analytic combinatorics. Structures studied in the second half of the book include permutations, trees, strings, tries, and mappings. Numerous examples are included throughout to illustrate applications to the analysis of algorithms that are playing a critical role in the evolution of our modern computational infrastructure. Improvements and additions in this new edition include Upgraded figures and code Despite growing interest, basic information on methods and models for mathematically analyzing algorithms has rarely been directly accessible to practitioners, researchers, or students. An Introduction to the Analysis of Algorithms, Second Edition, organizes and presents that knowledge, fully introducing primary techniques and results in the field. Authors Robert Sedgewick and the late Philippe Flajolet emphasize the mathematics needed to support scientific studies that can serve as the basis for predicting algorithm performance and for comparing different algorithms on the basis of performance. Improvements and additions in this new edition include upgraded figures and code, an all-new chapter introducing analytic combinatorics, and simplified derivations via analytic combinatorics throughout. The book´s thorough, self-contained coverage will help readers appreciate the field´s challenges and prepare them for advanced study.
Essential Information that Every Serious Programming Student Needs to Know about Algorithms and Data Structures A Classic Reference The latest version of Sedgewick´s best-selling series, reflecting an indispensable body of knowledge developed over the past several decades. Broad Coverage Full treatment of data structures and algorithms for sorting, searching, graph processing, string processing, and geometric applications, including fifty algorithms every programmer should know. See www.cs.princeton.edu/algs4/top50 . Completely Revised Code New Java implementations written in an accessible, modular programming style, where all of the code is exposed to the reader and ready to use. New versions of quicksort, LZW compression, red-black tree search, RE pattern matching, and many other algorithms. Engages with Applications Algorithms are studied in the context of important scientific, engineering, and commercial applications. Clients and algorithms are expressed in real code, not the pseudo-code found in many other books. Intellectually Stimulating Engages reader interest with clear, concise text, detailed examples with visuals, carefully crafted code, historical and scientific context, and exercises at all levels. A Scientific Approach Develops precise statements about performance, supported by appropriate mathematical models and empirical studies validating those models. Integrated with the Web Visit www.cs.princeton.edu/algs4 for a freely accessible, comprehensive Web site, including text digests, program code, test data, programming projects, exercises, lecture slides, and other resources. Product Description This fourth edition of Robert Sedgewick and Kevin Wayne?s Algorithms is the leading textbook on algorithms today and is widely used in colleges and universities worldwide. This book surveys the most important computer algorithms currently in use and provides a full treatment of data structures and algorithms for sorting, searching, graph processing, and string processing -- including fifty algorithms every programmer should know. In this edition, new Java implementations are written in an accessible modular programming style, where all of the code is exposed to the reader and ready to use. The algorithms in this book represent a body of knowledge developed over the last 50 years that has become indispensable, not just for professional programmers and computer science students but for any student with interests in science, mathematics, and engineering, not to mention students who use computation in the liberal arts. The companion web site, algs4.cs.princeton.edu contains An online synopsis Full Java implementations Test data Exercises and answers Dynamic visualizations Lecture slides Programming assignments with checklists Links to related material The MOOC related to this book is accessible via the ´´Online Course´´ link at algs4.cs.princeton.edu . The course offers more than 100 video lecture segments that are integrated with the text, extensive online assessments, and the large-scale discussion forums that have proven so valuable. Offered each fall and spring, this course regularly attracts tens of thousands of registrants. Robert Sedgewick and Kevin Wayne are developing a modern approach to disseminating knowledge that fully embraces technology, enabling people all around the world to discover new ways of learning and teaching. By integrating their textbook, online content, and MOOC, all at the state of the art, they have built a unique resource that greatly expands the breadth and depth of the educational experience. Features + Benefits The #1 practical resource for everyone seeking to run programs faster or solve larger problems Surveys today´s most useful algorithms, with copious illustrations and examples Contains many new examples, ranging from physics, biology, and engineering to data compression and web search Contains real (not pseudocode) implementations, with detailed performance insights A companion web site, algs4.cs.princeton.edu , with many more resources for instructors, including text digests, program code, test data, programming projects, exercises, lecture slides, and other resources Preface viii Chapter 1: Fundamentals 3 1.1 Basic Programming Model 8 1.2 Data Abstraction 64 1.3 Bags, Queues, and Stacks 120 1.4 Analysis of Algorithms 172 1.5 Case Study: Union-Find 216 Chapter 2: Sorting 243 2.1 Elementary Sorts 244 2.2 Mergesort 270 2.3 Quicksort 288 2.4 Priority Queues 308 2.5 Applications