Blick ins Buch

Algorithmentheorie

J. Loeckx (Autor)

Buch | Softcover

XVI, 226 Seiten

1976
Springer Berlin (Verlag)
978-3-540-07933-0 (ISBN)

Lese- und Medienproben

Inhaltsverzeichnis (PDF)

Artikel merken

Die Algorithmentheorie ist Ende der dreiBiger Jahre entstanden in Ver bindung mit Problemen der mathematischen Logik. Hit dem Aufkommen einer wissenschaftlich fundierten Informatik hat sie, insbesondere in den letzten zwanzig Jahren, an Bedeutung und Tragweite gewonnen. Das wird begreiflich, wenn man bedenkt, daB ein Programm flir eine elektronische Rechenanlage im wesentlichen ein Algorithmus ist und daB Resultate der Algorithmentheorie deshalb auch auf Programme anwendbar sind. Insbeson dere gibt es eine enge Verbindung zwischen der Algorithmentheorie und anderen flir die Informatik bedeutsamen Zweigen, wie der Automatentheorie, der Theorie der formalen Sprachen und der sich in den letzten Jahren heranbildenden Theorie der Programmierung. Wahrend die meisten Blicher liber Algorithmentheorie sich an Studenten der mathematischen Logik richten, ist dieses Buch flir Informatikstuden ten bestimmt. Zwar wird das Thema mit mathematischer Scharfe behandelt, aber es werden keine besonderen mathematischen Kenntnisse vorausgesetzt und die zahlreichen Kommentare zielen daraufhin, ein gutes intuitives Verstandnis zu ermoglichen; auBerdem hebt das Buch regelmaBig die Be deutung der Resultate flir die Informatik hervor. SchlieBlich sind die Notationen und bestimmte Beweismethoden der Automatentheorie und der Theorie der formalen Sprachen entnommen; insbesondere wird grundsatz lich mit Worten statt mit natlirlichen Zahlen gearbeitet.

0: Einige Begriffe und Notationen.- 0.1 Mengen und Funktionen.- 0.2 Zeichen und Worte.- 1 Grundbegriffe.- 1.1 Algorithmen.- 1.2 Abzählbarkeit.- 1.3 Abzählungen von Worten.- 2: Die Turing-Maschine.- 2.1 Definition der Turing-Maschine.- 2.2 Einige spezielle Turing-Maschinen.- 2.3 Die universelle Turing-Maschine.- 2.4 Einige nicht-berechenbare Funktionen.- 2.5 Rekursiv-aufzählbare und rekursive Mengen.- 3: Andere Formalismen als Turing-Maschinen.- 3.1 Die rekursiven Funktionen.- 3.2 Die Markov-Algorithmen.- 4: Nicht-deterministische Algorithmen und Grammatiken.- 4.1 Die Begriffe.- 4.2 Semi-Thue-Algorithmen und semi-Thue-Grammatiken.- Eine Schlußbemerkung.- Literatur.- Lösungen und Lösungshinweise der wichtigsten Übungen.- Die wichtigsten Notationen.- Alphabetische Liste der wichtigsten Funktionen.- Alphabetisches Sachregister.

Erscheint lt. Verlag	1.9.1976
Reihe/Serie	Hochschultext
Zusatzinfo	XVI, 226 S.
Verlagsort	Berlin
Sprache	deutsch
Maße	170 x 244 mm
Gewicht	380 g
Themenwelt	Informatik ► Theorie / Studium ► Algorithmen
Themenwelt	Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
Schlagworte	Algorithm analysis and problem complexity • Algorithmen • Algorithmus • Äquivalenzproblem • Berechenbarkeit • Halteproblem • Notation • Reduktion • Rekursion • Wortfunktion
ISBN-10	3-540-07933-5 / 3540079335
ISBN-13	978-3-540-07933-0 / 9783540079330
Zustand	Neuware