Volker Diekert

Das Lehrbuch besch ftigt sich mit den Elementen der Diskreten Mathematik und deren algebraischen Grundlagen, die relevante Anwendungen in der Informatik haben. Notwendige Hilfsmittel werden behandelt, um moderne Entwicklungen im Informationszeitalter der KI kompetent zu beurteilen. Wichtige mathematischen Behauptungen werden vollst ndig bewiesen. bungsaufgaben jeweils mit vollst ndigen L sungen vertiefen das Erlernte.

This book treats the elements of discrete mathematics that have important applications in computer science, thus providing the necessary tools for the reader to come to a competent mathematical judgement of modern developments in the age of information. Almost all assertions are shown with full proofs. Exercises are provided, with solutions presented in full detail.

The idea behind this book is to provide the mathematical foundations for assessing modern developments in the Information Age. It deepens and complements the basic concepts, but it also considers instructive and more advanced topics. The treatise starts with a general chapter on algebraic structures; this part provides all the necessary knowledge for the rest of the book. The next chapter gives a concise overview of cryptography. Chapter 3 on number theoretic algorithms is important for developping cryptosystems, Chapter 4 presents the deterministic primality test of Agrawal, Kayal, and Saxena. The account to elliptic curves again focuses on cryptographic applications and algorithms. With combinatorics on words and automata theory, the reader is introduced to two areas of theoretical computer science where semigroups play a fundamental role. The last chapter is devoted to combinatorial group theory and its connections to automata. Contents:Algebraic structuresCryptographyNumber theoretic algorithmsPolynomial time primality testElliptic curvesCombinatorics on wordsAutomataDiscrete infinite groups

Bei diskreten algebraischen Methoden handelt es sich um ein zukunftsweisendes Gebiet, dessen Grundlagen weiter an Bedeutung gewinnen werden. Die Grundidee des vorliegenden Lehrbuchs ist, wesentliche Elemente der diskreten Mathematik zu vermitteln, um die modernen Entwicklungen im Informationszeitalter kompetent mathematisch beurteilen zu k nnen. Es beginnt mit einem allgemeinen Kapitel ber algebraische Strukturen, welches die Grundlage f r das gesamte Buch bereitstellt. Das folgende Kapitel vermittelt Grundkenntnisse in Kryptographie. Kapitel 3 ber zahlentheoretische Algorithmen ist wichtig f r das Erzeugen von Kryptosystemen, f r die beispielsweise gro e "zuf llige" Primzahlen ben tigt werden. In Kapitel 4 ber Primzahlerkennung in Polynomialzeit stellen die Autoren den deterministischen Polynomialzeittest von Agrawal, Kayal und Saxena vor. Im folgenden Kapitel ber elliptische Kurven stehen wieder die zahlentheoretischen und kryptographischen Anwendungen im Vordergrund. Mit den beiden Kapiteln "Kombinatorik auf W rtern" und "Automatentheorie" begibt sich der Leser in das Teilgebiet der theoretischen Informatik, in dem die Halbgruppentheorie eine zentrale Rolle spielt. Das letzte Kapitel widmet sich diskreten unendlichen Gruppen. Das Buch erg nzt und vertieft Grundlagen und zeigt m gliche Anwendungen auf. Es werden aber auch Themen behandelt, die ber den Standardstoff hinaus gehen. Einen hohen Stellenwert nehmen Aufgaben und L sungen ein. F r alle wichtigen Aussagen geben die Autoren vollst ndige Beweise an. Am Ende eines jeden Kapitels sind kurze Kapitelzusammenfassungen als Lern- und Merkhilfe hinzugef gt. Das Buch wendet sich an Masterstudierende der Mathematik und Informatik mit fortgeschrittenen Kenntnissen in Mathematik. Die behandelten Grundlagen sind keine blo en Aneinanderreihungen von Definitionen und elementaren Zusammenh ngen. Das Buch vermittelt ein tieferes Verst ndnis f r die behandelten mathematischen Zusammenh nge und stellt Wissen, Techniken und Denkweisen vor, welche den Leser in die Lage versetzen, selbstst ndig mathematische Probleme zu l sen.

Die Grundidee des vorliegenden Lehrbuchs ist, wesentliche Elemente der diskreten Mathematik zu vermitteln, um die modernen Entwicklungen im Informationszeitalter kompetent mathematisch beurteilen zu k nnen. Hierzu geh ren das Verst ndnis von Graphen, das Rechnen mit gro en Zahlen und das Rechnen modulo n. Die Autoren beginnen mit einer Darstellung der elementaren Zahlentheorie. Insbesondere wird die Verschl sselung mit dem RSA-Verfahren erl utert. Danach werden Absch tzungen behandelt, die unerl sslich sind, wenn man Objekte z hlen oder Laufzeiten wichtiger Algorithmen verstehen m chte. Diverse in der Praxis vollkommen zuverl ssige Algorithmen nehmen den Zufall zu Hilfe, um berhaupt zu einem Ergebnis zu kommen. Daher darf ein Kapitel zur diskreten Wahrscheinlichkeit nicht fehlen. Danach begibt sich der Leser ins Zentrum der diskreten Mathematik. Es werden Kombinatorik, erzeugende Funktionen und Graphentheorie behandelt. Zum Abschluss widmen sich die Autoren Ordnungsstrukturen und Verb nden sowie booleschen Funktionen und Schaltkreisen. Das Buch erg nzt und vertieft Grundlagen und zeigt m gliche Anwendungen auf. Es werden aber auch Themen behandelt, die ber den Standardstoff hinaus gehen. Einen hohen Stellenwert nehmen Aufgaben und L sungen ein. F r alle wichtigen Aussagen geben die Autoren vollst ndige Beweise an. Am Ende eines jeden Kapitels sind kurze Kapitelzusammenfassungen als Lern- und Merkhilfe hinzugef gt. Das ben tigte Vorwissen ist gering. Die behandelten Grundlagen sind keine blo en Aneinanderreihungen von Definitionen und elementaren Zusammenh ngen. Das Buch vermittelt ein tieferes Verst ndnis f r die behandelten mathematischen Zusammenh nge und stellt Wissen, Techniken und Denkweisen vor, welche den Leser in die Lage versetzen, selbstst ndig mathematische Probleme zu l sen.

Parallelism or concurrency is one of the fundamental concepts in computer science. But in spite of its importance, theoretical methods to handle concurrency are not yet sufficiently developed. This volume presents a comprehensive study of Mazurkiewicz' trace theory from an algebraic-combinatorial point of view. This theory is recognized as an important tool for a rigorous mathematical treatment of concurrent systems. The volume covers several different research areas, and contains not only known results but also various new results published nowhere else. Chapter 1 introduces basic concepts. Chapter 2 gives a straight path to Ochmanski's characterization of recognizable trace languages and to Zielonka's theory of asynchronous automata. Chapter 3 applies the theory of traces to Petri nets. A kind of morphism between nets is introduced which generalizes the concept of synchronization. Chapter 4 provides a new bridge between the theory of string rewriting and formal power series. Chapter 5 is an introduction to a combinatorial theory of rewriting on traces which can be used as an abstract calculus for transforming concurrent processes.