Ingo Wegener's Kompendium Theoretische Informatik — eine Ideensammlung PDF

By Ingo Wegener

ISBN-10: 3322800903

ISBN-13: 9783322800909

ISBN-10: 3519021455

ISBN-13: 9783519021452

Das "Kompendium Theoretische Informatik - eine Ideensammlung" ergänzt das Lehrbuch "Theoretische Informatik - eine algorithmenorientierte Einführung" vom gleichen Autor. An Stelle von formalen Beweisen werden die wesentlichen Ideen herausgearbeitet und vorgestellt. Die Vertiefung und Auffrischung von Kenntnissen in Theoretischer Informatik wird unterstützt. Die Ideensammlung wird ergänzt durch Übungsaufgaben mit Lösungen und Lösungsmethoden sowie Testfragen mit knappen Antworten.

Show description

Read or Download Kompendium Theoretische Informatik — eine Ideensammlung PDF

Similar german_5 books

Egon Börger's Berechenbarkeit Komplexität Logik: Algorithmen, Sprachen und PDF

Endlich liegt der ,,Klassiker" der Theoretischen Informatik, der Studenten und Forschern ein unentbehrliches Standardwerk ist, in neuer Auflage vor.

Das Mathematica Arbeitsbuch by Elkedagmar Heinrich, Hans-D. Janetzko PDF

Nachdem Computeralgebra-Pakete wie Mathematica immer mehr Verbreitung finden, entsteht oft die Frage, welche mathematischen Probleme damit überhaupt angegangen werden können. Dieses Buch beschreibt die Mathematik, wie sie Studierende an Fachhochschulen oder Universitäten brauchen, an vielen Beispielen mit Hilfe von Mathematica.

Bestimmen des Bürstenverhaltens anhand einer Einzelborste - download pdf or read online

Die vorliegende Dissertation entstand wahrend meiner Tatig keit als wissenschaftlicher Mitarbeiter am Fraunhofer - In stitut fur Produktionstechnik und Automatisierung (IPA) in Stuttgart. Herrn Professor Dr. -Ing. H. -J. Warnecke, dem Direktor des IPA und Leiter des Instituts fur Industrielle Fertigung und Fabrikbetrieb der Universitat Stuttgart, bin ich fur seine wohlwollende Unterstutzung und Forderung sowie fur die wertvollen Hinweise zu der Arbeit zu grossem Dank ver pflichtet.

Extra resources for Kompendium Theoretische Informatik — eine Ideensammlung

Sample text

Die Ergebnisse sind aber leicht auf allgemeinere Problemtypen ubertragbar. Fur die in der Praxis so wichtigen Optimierungsprobleme wollen wir an zwei wichtigen Beispielen (zwei weitere in den Ubungsaufgaben) nachweisen, daB die allgemeinste Optimierungsvariante genau dann effizient losbar ist, d. h. in P ist, wenn dies fUr eine viel einfacher aussehende Entscheidungsvariante gilt. Nur diese Resultate rechtfertigen die Einschrankung auf Entscheidungsprobleme im Rest des Kapitels. Allgemein unterscheiden wir bei Optimierungsproblemen drei Varianten.

Fur Worter der passenden Lange mussen wir entscheiden, ob w E f-l(l} ist. Dazu benutzen wir die Zustandsmenge der Turingmaschine als Speicher fur das bereits gelesene Wort. Wir benutzen 2n+l + 1 Zustande. Fur jedes Wort w E {O, l}k mit 0 ~ k ~ n gibt es einen Extrazustand, und zusatzlich gibt es einen akzeptierenden und einen verwerfenden Stoppzustand. Wir starten im Zustand fur das leere Wort. Wenn wir im Zustand w mit Iwl < n eine 0, eine 1 oder B lesen, gehen wir in den Zustand fur wO, wI bzw.

Die Konsequenzen aus A ~ B sind: - B rekursiv =} A rekursiv. - A nicht rekursiv =} B nicht rekursiv. Anwendung finden Reduktionen vor aHem in Situationen, in denen bekannt ist, daB A nicht rekursiv ist, und bewiesen werden soll, daB B nicht rekursiv ist. Folgende Reduktionen wurden beschrieben: jj $ U, H $ MPKP, MPKP $ PKP, PKP ~ PKPO,l. Dabei wurden auch die Ideen herausgearbeitet. Nur in der Reduktion H $ MPKP wird ein Problem auf ein intuitiv ganz andersartiges Problem reduziert. 13. Die wichtigsten Ideen finden sich im entsprechenden Unterpunkt in Kap.

Download PDF sample

Kompendium Theoretische Informatik — eine Ideensammlung by Ingo Wegener


by James
4.4

Rated 4.62 of 5 – based on 27 votes