Download e-book for kindle: Algorithmentheorie by Prof. Dr. Jacques Loeckx (auth.)

By Prof. Dr. Jacques Loeckx (auth.)

ISBN-10: 3540079335

ISBN-13: 9783540079330

ISBN-10: 3642664903

ISBN-13: 9783642664908

Show description

Read Online or Download Algorithmentheorie PDF

Best german_5 books

Download PDF by Helmut Wittlage: Moderne Organisationskonzeptionen: Grundlagen und

Helmut Wittlage ist Professor an der FH Münster mit dem Lehrgebiet der Allgemeinen BWL und insbesondere der agency und Wirtschaftsinformatik.

Extra resources for Algorithmentheorie

Example text

Diese Darstellung ist eine Funktion F : wobei Q Q ...... =Y*. 3 Q abzahlbar. 5 ist ist auch S abzahlbar. Nehffien wir jetzt an, daB Seine abzahlbare Menge und (y,A) ein gegebenes Alphabet ist. Sei E eine Abzahlung der Menge S und E die inverse Funktion von E. Dann definiert die Funktion E 0 NV eine Darstellung der Elemente von ~ als Worte aus y*. J Genauso wie die Funktion VN es erm6glicht, das Studium von Worten durch ein Studium von nicht-negativen ganzen Zahlen zu ersetzen, geht aus dem so eben bewiesenen Satz hervor, daB das Studium von abzahlbaren Mengen durch ein Studium von Worten ersetzt werden kann.

Fur eine Menge sind. a. die der Konfiguration, definiert; in Abschn. 3 wird eine Funktion eingefuhrt und in Abschn. 4 zwei Relationen. ,B,qs) eine gegebene Turing-Maschine. 2. Auf eine Konfiguration ist ubrigens hochstens eine 1nstruktion anwendbar, weil die Menge! eine Funktion ist. Eine Konfiguration (q,~,~) heiBt Beginnkon[igupation, wenn Eine Konfiguration heiBt Endkon[igupation, wenn keine 1nstruktion auf sie anwendbar ist. Die Menge aller Konfigurationen der Turing-Maschine T wird mit C bezeichnet; es gilt also ~ = Q x Ye x Y~ 1m physikalischen Modell stellt die Konfiguration (q,~,~) eine "Moment- aufnahme" der Turing-Maschine dar: q ist der Zustand der zentralen Einheit, ~ und ist der 1nhalt des benutzten Teils des Bandes rechts vom Kopf ein- ~ ist der 1nhalt des benutzten Teils des Bandes links vom Kopf 9 Man verwechsle eine Konfiguration nicht mit dem rechten Glied einer 1nstruktion !

Zum SchluB folgen noch einige Bemerkungen. Insbesondere wird ein Satz bewiesen, der es ermoglicht, die Resultate der Algorithmentheorie zu verallgemeinern. 1. Eine Abzahtung von V. 1 Einfuhrung Es wird nun eine einfache Abzahlung der von einem Zeichenvorrat erzeugten Halbgruppe eingefUhrt, die weiter in diesem Buch ofter benutzt wird. Sei (y,A) ein beliebiges Alphabet. Seien a und h das erste bzw. h. A(O) und = a A(card(Y)-1) = h • Die Abzahlung, die jetzt eingefUhrt wird, wird NV genannt. Dabei solI die Notation NV daran erinnern, daB die Abzahlung ~ ~uf Y* abbildet; man darf aber nicht vergessen, daB die Abzahlung - wie aus der jetzt folgenden Definition klar werden wird - nicht nur von V (und ~), son- dern auch von A abhangt.

Download PDF sample

Algorithmentheorie by Prof. Dr. Jacques Loeckx (auth.)


by John
4.4

Rated 4.44 of 5 – based on 42 votes