✓ Schweizer Online-Shop
Grundkurs Theoretische Informatik

Grundkurs Theoretische Informatik

von Stefan Neubert

Verlag
Rheinwerk
Unsere Artikel-Nr.
RQEGNNP

Beschreibung

Theoretische Informatik - der Vorlesungsbegleiter. Berechenbarkeit, formale Sprachen, Algorithmik und Komplexitätstheorie sind theoretische Themen mit praktischer Relevanz, zu denen es ebenso praktische Zugänge gibt. Freuen Sie sich auf eine moderene Didaktik, die streng Formales mit Ihrer Intuition verknüpft, lernfreundlich ausarbeitet und schließlich zu jedem Thema Anwendungsfelder der Informatik vorstellt. Stefan Neubert hat nicht nur selbst Freude an der theoretischen Informatik, sondern widmet sich auch mit Leidenschaft ihrer Vermittlung zu Beginn und im Laufe des Bachelorstudiums. Eine Einführung mit vielen Aufgaben und Beispielen, auch zum Selbststudium geeignet. Aus dem Inhalt: Grundlegende mathematische Notation Modelle und Grenzen der Berechenbarkeit Formale Sprachen: Endliche Automaten, kontextfreie Grammatiken, Pumping Lemmata und mehr Beweisverfahren für Korrektheit und Laufzeit von Algorithmen Paradigmen für den Algorithmenentwurf Amortisierte Analyse und untere Schranke für Laufzeiten NP-Vollständigkeit und Reduktion

Spezifikationen

SpracheDeutsch
AutorStefan Neubert
ThemaSoftwareentwicklung: Programmiersprachen
Auflage1
Erscheinungsjahr2021
ErscheinungslandDeutschland
FormatBuch (Softcover)
DetailformatSoftcover
Anzahl Seiten416

Inhaltsverzeichnis



  1.  Einführung ... 15


       1.1 ... Kompetenzen für die theoretische Arbeit ... 16

       1.2 ... Themen der theoretischen Informatik ... 18

       1.3 ... Anleitung fürs Buch ... 20

       1.4 ... Danksagungen ... 21



  2.  Mathematische Notation ... 23


       2.1 ... Logische Aussagen ... 24

       2.2 ... Mengen ... 27

       2.3 ... Relationen und Funktionen ... 32

       2.4 ... Graphen ... 37

       2.5 ... Unendlichkeiten und Abzählbarkeit ... 40

       2.6 ... Beweistechniken ... 42

       2.7 ... Aufgaben ... 57

       2.8 ... Lösungen ... 58



TEIL I.  Berechenbarkeit und formale Sprachen ... 65


  3.  Einführung in die Berechenbarkeitstheorie ... 67


       3.1 ... Algorithmus ... 68

       3.2 ... Zu viele Funktionen ... 69

       3.3 ... Das Halteproblem ... 70

       3.4 ... Kontrollfragen ... 72

       3.5 ... Antworten ... 72



  4.  Problemtypen ... 73


       4.1 ... Formalisierung von Problemen ... 73

       4.2 ... Funktionen berechnen ... 75

       4.3 ... Datencodierung ... 75

       4.4 ... Sprachen entscheiden ... 78

       4.5 ... Problemklassen der Berechenbarkeitstheorie ... 79

       4.6 ... Aufgaben ... 82

       4.7 ... Lösungen ... 83



  5.  Einführung in formale Sprachen ... 85


       5.1 ... Definition ... 85

       5.2 ... Die Chomsky-Hierarchie ... 88

       5.3 ... Aufgaben ... 89

       5.4 ... Lösungen ... 90



  6.  Reguläre Sprachen ... 91


       6.1 ... Deterministische endliche Automaten ... 92

       6.2 ... Nichtdeterministische endliche Automaten ... 103

       6.3 ... Grammatiken ... 111

       6.4 ... Reguläre Ausdrücke ... 120

       6.5 ... Abschlusseigenschaften ... 127

       6.6 ... Entscheidungsprobleme auf regulären Sprachen ... 132

       6.7 ... Äquivalenzklassenzerlegung ... 134

       6.8 ... Nichtreguläre Sprachen ... 139

       6.9 ... Ausblick ... 144

       6.10 ... Aufgaben ... 144

       6.11 ... Lösungen ... 149



  7.  Kontextfreie Sprachen ... 161


       7.1 ... Kontextfreie Grammatiken ... 162

       7.2 ... Eindeutige Ableitungsbäume ... 164

       7.3 ... Chomsky-Normalform ... 166

       7.4 ... Exkurs: Kellerautomaten ... 170

       7.5 ... Abschlusseigenschaften ... 175

       7.6 ... Entscheidungsprobleme auf kontextfreien Sprachen ... 176

       7.7 ... Nicht-kontextfreie Sprachen ... 181

       7.8 ... Ausblick ... 183

       7.9 ... Aufgaben ... 184

       7.10 ... Lösungen ... 186



  8.  Kontextsensitive Sprachen ... 193


       8.1 ... Kontextsensitive und monotone Grammatiken ... 194

       8.2 ... Das Wortproblem auf kontextsensitiven Sprachen ... 195



  9.  Aufzählbare Sprachen ... 197


       9.1 ... Turingmaschinen ... 199

       9.2 ... While-Programme ... 202

       9.3 ... Gödelnummern ... 218

       9.4 ... Das universelle While-Programm ... 220

       9.5 ... Das schrittbeschränkte universelle While-Programm ... 223

       9.6 ... Diagonalisierung und min-Suche ... 224

       9.7 ... Prädikate für semi-entscheidbare Sprachen ... 226

       9.8 ... Semi-Entscheidbarkeit vs. Aufzählbarkeit ... 227

       9.9 ... Das S-m-n-Theorem ... 228

       9.10 ... Das kleenesche Rekursionstheorem ... 230

       9.11 ... Weitere Modelle und Charakterisierungen ... 233

       9.12 ... Aufgaben ... 233

       9.13 ... Lösungen ... 235



10.  Nicht Berechenbares ... 241


       10.1 ... Beweise mit KRT ... 243

       10.2 ... Der Satz von Rice ... 244

       10.3 ... Reduktionen ... 246

       10.4 ... RE-Vollständigkeit ... 250

       10.5 ... Ausblick: Die arithmetische Hierarchie ... 251

       10.6 ... Aufgaben ... 252

       10.7 ... Lösungen ... 254



TEIL II.  Algorithmik ... 259


11.  Einführung in Algorithmik ... 261


12.  Obere Schranken für Laufzeiten ... 263


       12.1 ... Das Maschinenmodell ... 264

       12.2 ... Die Laufzeit eines Algorithmus ... 267

       12.3 ... Die Größe einer Eingabe ... 268

       12.4 ... Die Landau-Notation ... 268

       12.5 ... Aufgaben ... 271

       12.6 ... Lösungen ... 272



13.  Laufzeiten von Datenstrukturen ... 275


       13.1 ... Arrays ... 275

       13.2 ... Listen ... 277

       13.3 ... Verschachtelte Datenstrukturen und Graphen ... 279

       13.4 ... Aufgaben ... 281

       13.5 ... Lösungen ... 282



14.  Brute-Force-Algorithmen ... 285


       14.1 ... Lineare Suche ... 286

       14.2 ... Backtracking/Tiefensuche ... 288

       14.3 ... Aufgaben ... 292

       14.4 ... Lösungen ... 293



15.  Greedy-Algorithmen ... 295


       15.1 ... Beweis mit Austauschargument ... 296

       15.2 ... Greedy stays ahead ... 302

       15.3 ... Aufgaben ... 304

       15.4 ... Lösungen ... 306



16.  Divide and Conquer ... 313


       16.1 ... Mergesort ... 314

       16.2 ... Binäre Suche ... 319

       16.3 ... Multiplikation großer Zahlen ... 321

       16.4 ... Das Mastertheorem ... 325

       16.5 ... Ausblick ... 326

       16.6 ... Aufgaben ... 327

       16.7 ... Lösungen ... 329



17.  Dynamische Programmierung ... 335


       17.1 ... Fibonacci-Zahlen ... 336

       17.2 ... Rückgeld geben ... 337

       17.3 ... Der Algorithmus von Dijkstra ... 341

       17.4 ... Aufgaben ... 344

       17.5 ... Lösungen ... 346



18.  Amortisierte Analyse ... 351


       18.1 ... Dynamische Arrays ... 351

       18.2 ... Guthabenmethode ... 353

       18.3 ... Ausblick ... 353



TEIL III.  Komplexitätstheorie ... 355


19.  Einführung in die Komplexitätstheorie ... 357


       19.1 ... Die Komplexität eines Problems ... 358

       19.2 ... Bedingte Schranken ... 358

       19.3 ... Auswege für schwierige Probleme ... 359



20.  Beweistechniken für untere Schranken ... 361


       20.1 ... Die Ausgabegröße ... 362

       20.2 ... Das informationstheoretische Argument ... 363

       20.3 ... Das Adversary-Argument ... 367

       20.4 ... Reduktionen ... 370

       20.5 ... Aufgaben ... 372

       20.6 ... Lösungen ... 374



21.  P vs. NP: Bedingte untere Schranken ... 377


       21.1 ... Die Komplexitätsklasse P ... 378

       21.2 ... Die Komplexitätsklasse NP ... 380

       21.3 ... Polynomialzeitreduktionen ... 388

       21.4 ... NP-schwere und NP-vollständige Probleme ... 392

       21.5 ... Ausblick: Mehr NP-vollständige Probleme ... 404

       21.6 ... Aufgaben ... 405

       21.7 ... Lösungen ... 406



22.  Ausblick: Parametrisierte Analyse ... 408


  Index ... 410

Leserkritik

»Ein anspruchsvolles Buch für Informatikstudenten und für alle, die sich für das theoretische Fundament der Informatik interessieren.«
»Sein Buch vermittelt die theoretischen Grundlagen auf eine Weise, die den Praxisnutzen leicht erkennen lässt. Sein Titel aus der Reihe „Informatik verstehen“ verknüpft die theoretischen Darlegungen mit zahlreichen Beispielen, anhand derer die Leser Erfahrungen mit der Suche nach Problemlösungen und auch mit der kommunikativen Darstellung von Lösungswegen sammeln können. Zugleich folgt das Buch einer Didaktik, die dem Weg vom Einfachen zum Komplexen folgt, mit Aufgaben und Kontrollfragen arbeitet und den Lernenden die hilfreiche Spaßkomponente belässt. Auf diese Weise ist das Buch ein hilfreicher Begleiter für Informatik-Vorlesungen.«
»Das Buch hier bietet einen guten, intuitiven Zugang zu diesem Fach und eignet sich hervorragend als Vorlesungsbegleiter und auch zum Selbststudium.«

Bewertungen

Produkt bewerten

Für dieses Produkt liegt noch keine Bewertung vor. Wenn Sie es gekauft haben, teilen Sie gerne Ihre Erfahrung.

Zahlungsarten

payment-einzahlungsscheinpayment-twintpayment-mastercardpayment-visapost-finance-paypayment-apple-paypayment-google-paysamsung-pay

Rechnung (Einzahlungsschein mit QR-Code), Twint, Kreditkarte, PostFinance, Apple, Google oder Samsung Pay.

Versand

Kostenlos: Schweiz & Liechtenstein

Rückgabe

30 Tage Rückgaberecht

Sie können das Produkt innerhalb von 30 Wochentagen ohne Angabe von Gründen zurücksenden, sofern es unbeschädigt und in der Originalverpackung ist.

Weitere Hinweise finden Sie in unseren AGB unter D.1.