close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

1 Was ist als Zusatzliteratur zur Vorlesung zu empfeh- len?

EinbettenHerunterladen
1
Was ist als Zusatzliteratur zur Vorlesung zu empfehlen?
Aho, A. V. & Ullman, J.: "Foundations of Computer Science", Computer Science Press, New
York, 1994. (Es ist 1996 auch in deutscher Sprache bei Addison-Wesley zu erhalten: "Foundations of Computer Science“)
Asteroth, A. & Baier, Ch.: „Theoretische Informatik”, Pearson Studium, 2002 (Hat schöne
Beispiele, aber den Aufbau des Buches finde ich nicht ganz gelungen.)
Barthelmann, K.: „Grundzüge der Informatik I + II”, Skript, FB 17, Uni-Mainz, 2003/04
(Aktueller Stand der Veranstaltung; s. a. Vorbemerkung)
Blum, N.: „Theoretische Informatik”, Oldenburg, 2001.
Cohen, D.I.A.: "Introduction to Computer Theory", John Wiley & Sons, New York, 1986. (Es
ist spezialisiert auf den Teil Formale Sprachen und Automatentheorie der Vorlesung und
beinhaltet viele schöne Beispiele.)
Dewdney, A.K.: "The Turing Omnibus", Computer Science Press, W.H. Freeman & Co., New
York, 1989. (Es greift viele Themen im Stil des 'Scientific American' bzw. 'Spektrum der
Wissenschaft', in denen Dewdney eine Kolumne hatte. Man kann es im Bett lesen.)
Dewdney, A.K.: "The New Turing Omnibus", Computer Science Press, W.H. Freeman & Co.,
New York, 1993. (Eine überarbeitete Neuauflage.)
Erk, K. & Priese, L.: „Theoretische Informatik - Eine umfassende Einführung”, Springer, 2002.
Goos, G.: "Vorlesungen über Informatik I + II + III", Springer Verlag, Berlin, 1997
Hopcroft, J. E. & Ullman, J. D.: „Einführung in die Automatentheorie, formale Sprachen und
Komplexitätstheorie“, Addison-Wesley, New York, 1994 (sehr lesenswert)
Hopcroft, J. E. & Motwani, R. & Ullman, J. D.: „Einführung in die Automatentheorie, formale
Sprachen und Komplexitätstheorie“, Pearson Studium, München, 2002 (die abgespeckte
Version, wichtige Kapitel der Urform fehlen, aber didaktisch besser aufbereitet und sehr
lesenswert)
Horn, Ch., Kerner, I. O.: "Lehr- und Übungsbuch Informatik Band 2: Theorie der Informatik”
(Eine schöne Buchreihe, die die ganze Breite der Informatik zwar knapp, aber nicht oberflächlich, und sehr verständlich darstellt)
Hromkovi , Juraj: „Theoretische Informatik”, Teubner, Wiesbaden, 2004. (Ist recht kompakt
geschrieben.)
5
Penrose, R.: "Computerdenken", Spektrum Akademischer Verlag, 1991. (Lesenswert, durchaus
als Bettlektüre geeignet.)
Rechenberg, P & Pomberger, G.: „Informatik-Handbuch“, Hanser Verlag, München, 1999.
(Manches ist knapper gehalten als in der Reihe von Horn&Kerner. Ist wirklich nur ein
Nachschlagewerk und kein Lehrbuch)
Schöning, U.: „Theoretische Informatik - kurzgefasst“, Spektrum-Verlag, Berlin, 2001.
van de Snepscheut, J. L. A. : "What Computing Is All About", Springer, Berlin, 1993.
Socher, R.: „Theoretische Grundlagen der Informatik”, (Auf einer CD mitgeliefert sind Animationen z.B. für die endlichen Automaten, die wir in der Vorlesung kennen lernen werden. Zum
weiteren Verständnis braucht man Kenntnisse der Programmiersprache Prolog.)
Vossen, G. & Witt, K.-U.: Grundlagen der Theoretischen Informatik mit Anwendungen,
Vieweg, 2000 (Das Buch kann man durchaus empfehlen, obgleich ich einen anderen Aufbau
vorziehe.)
Wagenknecht, Ch.: „Algorithmen und Komplexität”, Fachbuchverlag Leipzig, 2003. (Mehr für
den 2. Teil der Vorlesung geeignet, außerdem benötigt man Kenntnisse der Programmiersprache
Scheme.)
Wegener, I. „Theoretische Informatik“, Teubner Verlag, Stuttgart, 1993. (Ein schönes Buch. Es
stellt die Sachverhalte ohne definitorischen Overkill dar.)
Wegener, I.: „Kompendium Theoretische Informatik - eine Ideensammlung“, Teubner Verlag,
Stuttgart, 1996. (Auch sehr schön.)
6
2
Wozu die Beschäftigung mit der Theoretischen Informatik?
>
Frage: Macht man nur den Informatik, wenn ein Computer beteiligt ist? Nein!
>
Aussagen wie „ein Computer verarbeitet Informationen” sind Unsinn. Lapidar ausgedrückt kann man sagen, dass ein Computer Zeichenketten verarbeitet. Das tut auch jeder
Mathematiker, wenn er rechnet, d.h. nach gewissen Regeln Zeichenketten in andere
umformt. Man kann sagen, dass gilt:
Rechnen = Zeichenkettenumformen
egal ob ein Mensch oder ein Computer die Rechnung durchführt.
>
>
Um Zeichenkettenumformungen durchführen zu können, braucht man einen Kalkül. Ein
solcher besteht im Wesentlichen aus drei Dingen:
>>
der Angabe einer endlichen Menge von Elementarzeichen
>>
einer endlichen Menge von Vorschriften, wie man aus den Elementarzeichen
Komplexzeichen, also letztlich Zeichenketten bilden kann, was man auch als
Syntax des Kalküls bezeichnet
>>
einer endlichen Menge von Vorschriften, wie man (Teil-)Zeichenketten des
Kalküls in andere umformt, sodass sich wieder eine erlaubte Zeichenkette des
Kalküls ergibt.
Fragen, die sich diesbezüglich ergeben:
>>
Wie beschreibe ich möglichst prägnant die Syntax eines Kalküls?
>>
Wie beschreibe ich möglichst prägnant die Rechenregeln eines Kalküls?
>>
Gibt es bei der Zeichenkettenumformung einen Zustand, wo man keine Regel
mehr anwenden kann? Terminierung?
>>
Wenn man Umformungsregeln in verschiedener Reihenfolge anwendet, ist das
Ergebnis das selbe? (Konfluenz)
>>
Gibt es Eigenschaften, die man mittels solcher Kalküle nicht beschreiben kann?
>>
Wie viele Rechenschritte muss ich ausführen, um zu einem Endzustand zu
kommen?
>>
u.v.a.m
7
Die Theorie gibt Antworten zu den o.a. Fragen, die überaus praxisrelevant sind. Sie gibt
Hilfen z.B. zur Definition von Programmiersprachen, zur Frage ob ein Programm richtig
in dem Sinne ist, dass es das Gewünschte tut, wie groß der Rechenaufwand für meinen
Algorithmus ist, usw.
Ein gern zitierter Satz: „Nichts ist praktischer als eine gute Theorie.”
8
3
Was sind wichtige Meilensteine der Informatik?
>
Wenn man so will, beginnt's bei den Schriftsystemen zum Speichern "flüchtiger" Informationen.
>
Aber sicher ginge es nicht ohne
Zahlensysteme:
-3000 Zahlensystem der Sumerer
-2000 Zahlensystem der Ägypter und Babylonier
-300
Indisches (Brahmi) Dezimalsystem ohne die Null
0
Zahlensystem der Römer und Chinesen
800
Indisches Dezimalsystem mit der Null \ Leonardo von Pisa, genannt Fibonnaci (1180-1240), insbesondere Adam Riese (1492 - 1559), helfen
dem Dezimalsystem zum Durchbruch
Diese Systeme sind 'fingerorientiert'.
1646-1716
Dualsystem von Leibniz (vermutlich schon bei den Chinesen)
nach F.L. Bauer1 (Informatik-Spektrum 4 (August) 1994) im Artikel
"Multiplikation und Dualsystem":
"Tatsächlich fanden sich im Nachlass von Thomas Harriot (1560-1621)
mehrere Manuskripte über das Rechnen im Zahlensystem zur Basis
Zwei."
"John Napier (1550-1617) diskutierte im Anhang der 1617 gedruckt
erschienenen 'Rhabdologie' ebenfalls das Rechnen im Zahlensystem
Zwei."
"... bevor Leibniz das Stellenwertsystem zur Potenzbasis Zwei (mit der
Notiz 'De Progressione Dyadica' vom 15. März 1679) aus der Taufe hob
und fortan so nachhaltig propagierte, dass man an ihn zuerst denkt, wenn
von Dualzahlen die Rede ist."
1
Mainzer Alt-Informatiker \ Sein Bild hängt im "Hilbert-Raum"
9
>
Geräte:
-1100
Abakus (vertikale Stäbe mit Perlen zu je 5 und 2 \ Übertragssystem
1623
Rechenuhr von Wilhelm Schickard (nachgebaut durch Bruno Baron v.
Freytag Löringhoff, *1912 +1996) \ erste urkundlich dokumentierte
Rechenmaschine \ Zählwerk mit Übertrag
1641
(Manchmal findet man auch 1642) Rechenmaschine von Blaise Pascal
(war damals 19 Jahre; wollte seinem Papa, der in der Finanzverwaltung
tätig war, das Leben erleichtern)
1673
(Manchmal findet man auch 1671): Rechenmaschine von Gottfried
Wilhelm Leibniz (kannte die Pascal'sche; verbesserte diese jedoch stark)
1728
Speicherung von Information auf Holzbrettchen (für Webmuster) \
frühes ROM (frühe Lochkarten)
1774
Serienmäßig hergestellte Rechenmaschine von Philipp Matthäus Hahn;
er war Pfarrer. (Im Deutschen Museum in München in der InformatikAbteilung gibt es viele dieser Geräte zu bewundern.)
Herausforderung bei allen: Lösung des "Übertragproblems"
1805
Webstuhl von Joseph-Maria Jacquard (Lochstreifen für die Muster)
10
1822
Charles Babbage (in Zusammenarbeit mit Joseph Clement) und seine
Difference Engine \ Nie ganz fertig geworden \ The Table Crises
Berechnung von 53 nach dem Differenzenverfahren
1834
Ch. Babbage und seine Analytical Engine \ Auch nie fertig geworden
\ War weniger eine einzelne Maschine, sondern eine Folge von Entwürfen \ Lochstreifen für die Programme \ Ada Lovelace (Tochter von
Lord Byron) erläuterte die Ideen von Babbage und schrieb schon Programme
1843
Georg und Edvard Scheutz (Vater und Sohn) realisieren ihre Version der
Difference Engine \ stellte gleich die Druckplatten her.
1886
Herrmann Hollerith2 und seine Maschine zum Auswerten von Volksstatistiken in den USA \ vervollkommnet die Lochkartenverarbeitung
(Sortier- und Zählmaschinen)
2
IBM zählt ihn zu seinen Ahnen
11
19373
Konrad Zuses (1910 - 1995) erster Rechner mit bistabilen mechanischen
Schaltelementen (sog. "Z1")
1941
Zuses (in Zusammenarbeit mit Helmut Schreyer: "Das musst Du mit
Röhren machen.") erster funktionsfähiger Relaisrechner Z3 (Die Z2 war
aus alten Telefonrelais hergestellt und funktionierte nicht.) \ Die Z3 war
der erste funktionsfähige Computer überhaupt! 600 Relais im Rechenwerk, 1400 Relais im Speicherwerk, binäres Zahlensystem, Gleitkommaarithmetik, Wortlänge 22 Bit, Speicherkapazität von 64 Wörtern,
Steuerung durch 8-Kanal-Lochstreifen, Eingabe auf Spezialtastatur,
Ausgabe durch Anzeige auf Lampenstreifen einschließlich der Lage des
Kommas, 3 Sekunden pro Operation
Rechner im Krieg zerstört; jetzt Nachbau im Deutschen Museum
Bau ohne Kenntnis von anderen!
1944
Mark I, elektromechanischer Rechner von Howard H. Aiken an der
Harvard-Universität \ 15 m groß; 100.000 Einzelteile 80 km Leitungsdrähte; Addition 0,3 sec
1946
ENIAC, Röhrenrechner von I.P. Eckert und J.M. Mauchly, Univ. of
Pennsylvania \ 20t Gewicht, 18.000 Röhren, 1.500 Relais \ Operationen im Millisekundenbereich \ Dezimalzahlen!
1949
EDSAC von M.V. Wilkes, erster universeller Digitalrechner mit intern
gespeichertem Programm.
Die Idee zur "internen" Speicherung des Programms (und seiner möglichen Veränderung!) wird zwar John v. Neumann zugeschrieben. Es gab
aber später eine Schlammschlacht hinsichtlich Patentrechten zwischen
ihm sowie H. Goldstine einerseits und Eckert sowie Mauchly andererseits über die Priorität.
ab 1950
kommerzielle Systeme
ab 1982
PC
3
In "Der Computer, mein Lebenswerk" schreibt K. Zuse (S. 31): "Ich selber verstand, als ich mit dem
Computerbau begann, weder etwas von Rechenmaschinen noch hatte ich je von Babbage gehört. Erst viele
Jahre später, als meine Konstruktionen und Schaltungen im wesentlichen festlagen, wurde mir seine Maschine
vom Prüfer des amerikanischen Patentamtes entgegen gehalten. Die sonst sehr gründlichen deutschen Prüfer
hatten Babbage nicht gekannt. Dies waren also die Ausgangsbedingungen, als ich 1935 beschloß, Computererfinder zu werden."
12
>
Theorie nebst Programmiersprachen
um 820
Al-Chowarizmi (etwa 780-850) schreibt ein Buch über Algebra
um 1670
Leibniz: "Calculemus" \ Logik-Kalkül
1854
George Boole (1815-1864) macht "An Investigation of the Laws of
Thought"
1893
G. Frege: "Grundgesetze der Arithmetik". Er hätte es heute wohl als
"Grundlagen der Formalen Logik" bezeichnet.
1900
"Hilbert'sches Programm" Kombination aus dem Grundlagenstreit (mit
Hermann Weyl) und der Formulierung des Entscheidungsproblems:
Hilberts Meinung, dass man alles axiomatisieren (nebst "tertium non
datur" / "principium tertii exclusi") muss und aus den Axiomen stets die
Wahrheit oder die Falschheit einer Aussage beweisen kann ("Entscheidungsproblem" / "Hilberts 10. Problem") - "Grundlagen der Geometrie"Buch
1914
Axel Thue: "Probleme über Veränderungen von Zeichenreihen nach
gegebenen Regeln"4
1931
Kurt Gödel: "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I", In "Monatshefte für Mathematik und
Physik" 38 (1931), S. 173 - 198.
1936
Alonzo Church: "An Unsolvable Problem of Elementary Number Theory", Amer. Journal of Mathematics 58 (1936), S. 345 - 363 \ Er schlägt
vor, die Begriffe -definierbare Funktionen und allgemein rekursive
Funktionen mit dem Begriff der berechenbaren Funktionen gleichzusetzen.
✁
[
1937
Alan Turing: "On Computable Numbers with an Application to the
Entscheidungsproblem", Proc. of the London Math. Soc. (2), 42 (1937),
S. 230 - 265 und 43 (1937) S. 544 - 546 \ Frage war: Gibt es ein allgemeines mechanisches Verfahren, das im Prinzip alle Probleme der
Mathematik zu lösen vermag?
1938
C. E. Shannon: "A Symbolic Analysis of Relais and Switching Circuits",
Trans. Amer. Inst. Electr. Engnrs. 57 (1938) Suppl. 718 - 723 \ Er
arbeitete auch über Codierungs-, Informations und Kommunikationstheorie ]
4
Videnskapsselskapets Skrifter, J. Math. Naturw. Kl, S. 3-34.
13
1941
Church: "The Calculi of Lambda-Conversion" Princeton University
Press, 1941 \ Churchsche These, manchmal auch Church-Turing-These
genannt
1946/47
J. v. Neumann, zusammen mit Burks und Goldstine propagieren eine
Idee, die man I. P. Eckert und J. P. Mauchly zuschreiben sollte: Konzept
des Universalrechenautomaten \ Programm und Daten kommen in einen
gemeinsamen Speicher \ Logisch und räumlich besteht die Maschine aus
den Modulen Rechenwerk, Leit/Steuerwerk, Speicherwerk, und Ein/Ausgabewerk
1956
Noam Chomsky: "Three Models for the Description of Language", IRE
Transact. on Information Theory IT-2, 3 (1956), S. 113 - 124 \ Es gibt
allerdings auch Arbeiten aus dem Jahr 1953, die mir nicht zugänglich
waren. Die 'abgerundete' Theorie findet man 1959 in den "Information
and Control" 2 (1959): "On Certain Properties of Formal Grammars"
1956
S. C. Kleene "Representation of Events in Nerve Sets and Finite Automata" in C.E. Shannon & M. McCarthy (eds.): "Automata Studies", Annuals
of Math. Studies, No. 34, Princeton University Press, Princeton, N.J. S.
3 - 41, sicher auch noch Mealy oder Moore zu nennen: E.F. Moore:
Gedanken-Experiments on sequential machines", in: Automata Studies,
Princeton University Press, Princeton N.J. 1956, S. 129 - 153 .
um 1957
FORTRAN auf der IBM 704 \ Nach J. Sammet: "Erste Höhere Programmiersprache 10/92 SHORT CODE for UNIVAC-Rechner" \ Nach
K. Zuse: "1943 der Plankalkül" \ Natürlich ist COBOL nicht zu vergessen, das auch um diese Zeit aufkam.
um 1960
ALGOL 60 und LISP
1965
Juris Hartmanis & R.E. Stearns: "On the Computational Complexity of
Algorithms", Trans. Americ. Math. Soc. 117 (1965), S. 285 - 306
1967
SIMULA 67, die erste objektorientierte Programmiersprache
1968
ALGOL 68, die erste orthogonale Programmiersprache
1968
Software-Krise - Nato Science Conference in Garmisch-Partenkirchen
- Kreierung des Begriffs "Software-Engineering" durch F.L. Bauer
um 1970
PROLOG (logische Programmierung) \ SMALLTALK (Objektorientierung zusammen mit graphischer Oberfläche)
min([X],X).
min([M | R],M) :- min(R,Y), Y=>M.
min([Y | R],M) :- min(R,M), M=<Y.
14
1970
Rechnernetze DARPA-Net (Vorgänger des heutigen Internets) \ Erste
Veröffentlichung: L. G. Roberts & B. D. Wessler: “Resource Sharing
Computer Networks“, Spring Joint Computer Conference
1971
Stephen Cook: NP-Vollständigkeit und P=NP?-Problematik in "The
Complexity of Theorem Proving Procedures"5 \ Er zeigt, dass das Erfüllbarkeitsproblem für Boole'sche Formeln die Eigenschaft hat, dass
jedes andere Problem in Polynomialzeit darauf zurückgeführt werden
kann. Das bedeutet, könnte das SAT-Problem in Polynomialzeit gelöst
werden, dann trifft dies auch für die anderen in der NP-Klasse zu.
um 1980
Internet mit Email und FTP \ Aufkommen verteilter Betriebssysteme
01.01.83
Startpunkt des Internet, als TCP/IP als Standardprotokoll eingeführt wird
1989
WWW beim CERN in Genf \ als Initiator gilt Tim Berners-Lee, der das
Hypertext-Paradigma als Grundlage für eine Vernetzung von Dokumenten vorschlägt, die auf verschiedenen Servern liegen dürfen.
um 1990
Multimedia
1993
Mosaic, der erste graphische Web-Browser, geschrieben von Marc Andreessen
1995
Java (ist zwar nichts völlig Neues, aber der kometenhafte Aufstieg überrascht)
????
Forschung auf allen möglichen Gebieten, aber kein Durchbruch seither
5
Konjunktive Normalform KNF: (x1 x2) (x1 x2 x3) x3 \ Wird die boolsche Variable xi mit 0
oder 1 belegt, ergibt dies entweder 0 oder 1. Insgesamt hat man 2n Möglichkeiten n Variable mit 0 oder 1 zu
belegen. Für n = 50 ergeben sich bei angenommenen Tests von 100.000 Möglichkeiten pro Sekunde etwa 360
Jahre.
✄
✂
✄
☎
15
☎
4
Was braucht man als mathematisches Rüstzeug?
Im Folgenden ist mathematische Notation zusammengestellt, die in der Vorlesung und den
Übungen benutzt wird. Diese Zusammenstellung ist sicher nicht vollständig. Einige Bücher aus
der angegebenen Literaturliste enthalten einführende Kapitel zu den benötigten mathematischen
Grundbegriffen
Mengen
Wir fassen häufig Dinge in Mengen zusammen. In dieser Veranstaltung benutzte Mengen sind
z.B. (die leere Menge),
(die natürlichen Zahlen), Z (die ganzen Zahlen), {0, 1}* (die
Menge aller endlichen 0-1-Folgen (wird später eingeführt). Oft geben wir Mengen explizit durch
die Aufzählung ihrer Elemente an: {0, 1}, {0, ..., 9}, {1, 2, ...}, häufig aber auch durch Festlegung einer Grundmenge und einer definierenden Eigenschaft, z. B. {n
| n 0 mod 2}. Ist
ein Objekt x Element einer Menge M , so schreiben wir x M .
✆
✝
✞
✟
✠
✡
Aus zwei Mengen M und N können wir bilden:
ihre Vereinigung: M N enthält alle Elemente von M und alle Elemente von N ,
ihren Durchschnitt: M N enthält alle Elemente, die sowohl in M als auch in N enthalten sind,
ihr kartesisches Produkt: M × N enthält alle Paare (m, n) mit m M , n N .
☛
☞
✌
✌
Alle diese Operationen können wir auch mit mehr als zwei, sogar mit unendlich vielen
Mengen durchführen (beim kartesischen Produkt von k Mengen erhalten wir k-Tupel). Dazu
geben wir ihnen Namen, die sich leicht aufzählen lassen, meist mit Hilfe von Indexen: M1 , M2,
M3 ; (Mi)i I (hier gibt es zu jedem Index i I eine Menge namens Mi ), (Mw)w * (hier gibt es zu
jeder Zeichenkette w über , d.h. w wird mit den Elementen von gebildet, eine Menge Mw .
Zeichenketten werden später eingeführt).
✎
✍
✍
✑
-
M1
-
M1
-
M1 × M2 × M3 ,
✕
✒
M2
M2
✕
✒
M3 ,
M3 ,
✏
✑
i I
✓
✔
✖
w
✗
Mi
✘
*
Mw
Mk := M × M × ... × M ,
✙
i I
✚
Mi .
k mal
Bei Mengen betrachten wir die Elemente als nicht angeordnet und jedes Element als nur
einmal vorhanden, d.h. z.B. {1, 2, 3} = {2, 3, 1}; anders bei Tupeln: (1, 2, 3) und (2, 3, 1) sind
unterschiedliche Objekte, ebenso wie (1, 2, 2) und (1, 2).
Wenn zwei Mengen M und N kein gemeinsames Element haben, d. h. wenn M N = ist,
nennen wir sie disjunkt. Manchmal wollen wir bei der Vereinigung zweier Mengen ihre Disjunktheit sichern; dann schreiben wir M N .
✛
✢
16
✜
Die Differenz zweier Mengen M und N , M \ N , enthält all diejenigen Elemente von M , die
nicht in N enthalten sind. Ist jedes Element von N auch Element von M, so nennen wir N eine
Teilmenge von M und schreiben N M (bzw. M N ). Die Potenzmenge von M, (M),
(manchmal auch 2M geschrieben), ist die Menge aller Teilmengen von M . Die leere Menge
ist Teilmenge jeder Menge. Jede Menge ist Teilmenge von sich selbst. N ist eine echte Teilmenge von M , falls N M und N M , wir schreiben dann auch N M (bzw. M N ). Zu jeder
Teilmenge N von M ist auch ihr Komplement, C(N) , erklärt als die Menge der Elemente von M
, die nicht in N liegen. Achtung: Das Komplement hängt von der betrachteten Obermenge ab!
✣
✤
✥
✦
✧
★
✩
✪
Die Mächtigkeit, d. h. die Anzahl der Elemente, einer Menge M schreiben wir als #M oder
auch |M|.
Quantoren
Wenn wir darstellen möchten, dass alle Elemente einer Menge M eine Eigenschaft E besitzen,
bringen wir es durch x M : E(x) zum Ausdruck (Allquantor). Wollen wir behaupten, dass
wenigstens ein Element der Menge die Eigenschaft E besitzt, bezeichnen wir dies mit x M :
E(x) (Existenzquantor). Wollen wir sagen, dass es genau ein Element x in der Menge M mit der
E gibt, wird es als !x M : E(x) dargestellt. Wenn es klar ist, aus welcher Menge die Elemente
stammen, kann man die Mengenangabe weglassen.
✫
✬
✭
✭
✮
✮
Logische Zeichen
Die wichtigsten Junktoren sind:
-
Negation ¬p : nicht p (Die Aussage p ist falsch, wenn ¬p, und umgekehrt.)
-
Disjunktion p q : p oder q (Die Aussage p oder q ist wahr, wenn eines von beiden wahr
ist; nicht ausschließend!)
-
Konjunktion p q : p und q (Wenn die Aussagen p und q wahr sind, ist es damit auch
die Gesamtaussage.)
-
Implikation p q : wenn p gilt, dann auch q. Eine Implikation ist immer in ihrer Gesamtheit richtig, wenn p falsch ist! (Aus Falschem kann etwas Richtiges folgen oder
etwas Falsches.)
✯
✰
✱
17
Relationen und Abbildungen
Eine Teilmenge von Mk nennen wir eine k-stellige Relation auf M. Eine besondere Rolle
spielen zweistellige Relationen. Hier schreiben wir statt (x, y) R oft auch xRy. Interessante
mögliche Eigenschaften einer solchen Relation sind z.B.:
Reflexivität: x : xRx,
Symmetrie:
x, y : xRy ! yRx,
Transitivität: x, y; z : xRy yRz xRz.
✲
✳
✳
✳
✴
✵
Eine Relation mit all diesen drei Eigenschaften heißt eine Äquivalenzrelation, und wir nennen
x und y äquivalent, falls xRy. (Oft werden Äquivalenzrelationen mit dem Symbol ~ oder
ähnlichen Symbolen bezeichnet.) Die Menge der zu x äquivalenten Elemente heißt die Äquivalenzklasse von x und wird oft mit [x]R , oder einfach [x] bezeichnet. x ist ein Repräsentant seiner
Äquivalenzklasse. Jedes Element von M gehört genau einer Äquivalenzklasse an.
Eine andere wichtige Klasse von zweistelligen Relationen sind Ordnungsrelationen. Hier gilt
die Transitivität, statt der Symmetrie haben wir ihr Gegenteil, die Antisymmetrie: xRy ¬yRx.
Ist die Relation zusätzlich total, d. h. gilt x y xRy yRx für alle x, y M , so heißt R eine
totale oder lineare Ordnung. Für Ordnungsrelationen werden üblicherweise Zeichen wie < oder
verwendet. Verlangen wir zusätzlich Reflexivität (dann gilt die Antisymmetrie natürlich
nur noch für Paare x, y mit x y), so schreiben wir
bzw. .
✵
✶
✵
✷
✲
✸
✹
✺
✻
Eine k-stellige Abbildung f : M1 × ... × Mk N ist eine (k+1)-stellige Relation Rf , die rechtseindeutig ist, d. h. zu jedem k-Tupel (m1, ..., mk ) M1 × ... × Mk gibt es höchstens ein Element
n N mit (m1, ..., mk, n) Rf . Wir schreiben f(m1, ..., mk) = n statt (m1, ..., mk, n) Rf .
✼
✽
✽
✽
✽
Sei f eine Abbildung f : M N. M nennen wir den Definitionsbereich von f und N den Bildoder Wertebereich. Eine Abbildung ist bei uns stets linkstotal und rechtseindeutig, d.h. jedem
(linkstotal!) Element m M wird genau ein (rechtseindeutig!) Element f(m) N zugeordnet.
Zwei verschiedenen Elemente von M kann dasselbe Element aus N zugeordnet sein.
✼
✽
✽
Wollen wir die Möglichkeit der Nicht-Totalität explizit hervorheben, so sprechen wir von
einer partiellen Abbildung. Die Menge der Elemente m M , für die f(m) existiert, nennen wir
den Definitionsbereich von f . Ist m nicht Element des Definitionsbereichs von f , so sagen wir
f(m) ist undefiniert.
✽
Eine Abbildung f : M N heißt injektiv, wenn keines ihrer Bilder aus N zwei Urbilder in M
hat, d. h. wenn für alle m, m' M gilt f(m) = f(m') m = m'. Hat jedes Element in N ein Urbild
unter f, so heißt f surjektiv. Eine totale Abbildung, die injektiv und surjektiv ist, heißt bijektiv.
✼
✽
✾
Zeichen in Beweisen
Wir verwenden das Zeichen um anzuzeigen, dass das Folgende aus dem Vorherigen folgt;
schreiben wir , so ist der Schluss in beiden Richtungen korrekt. Das Symbol wird gemäß
der üblichen Konvention auch als Zeichen für einen Ableitungsschritt eingesetzt. Aus dem
Kontext ist aber stets klar, was gemeint ist.
✾
✿
❀
18
Das Zeichen bedeutet nur, dass hier etwas, meist ein Beweis oder ein Beispiel, zu Ende ist.
OBdA steht für „Ohne Beschränkung der Allgemeinheit” und bedeutet, dass die im Folgenden
angenommene Situation, selbst wenn sie nicht immer gegeben ist, doch ohne Schwierigkeiten
hergestellt werden kann.
❁
19
5Wie kann man Syntax beschreiben (Grammatiken)?
Bei einer Sprache - natürlich oder künstlich - sind zwei Aspekte von eminenter Bedeutung: (1)
Welche Zeichenfolgen sind Sätze dieser Sprache, also "korrekt" aufgebaut? (2) Welche Bedeutung hat ein gegebener Satz? Diese beiden Aspekte heißen Syntax bzw. Semantik. Die Semiotik kennt noch einen dritten Aspekt, die Pragmatik, die das Verhältnis des Zeichensystems
zu seinen Benutzern untersucht. Auf Programmiersprachen übertragen ist beispielsweise (1)
„Was ist ein syntaktisch korrektes Programm?” (2) „Welche Aktionen werden mit dem Programm im Rechner angestoßen oder anders ausgedrückt: „Was tut das Programm?” oder
„Welche berechenbare Funktion stellt es dar?” (3) „Wie leicht/schwierig war es, das Programm
zu erstellen?”
Die Forderung in ALGOL 60, dass z.B. ein Identifikator erst deklariert sein muss, bevor er in
einer Anweisung verwendet werden darf, war einst als Forderung der statischen Semantik
bezeichnet worden (weil dieser Sachverhalt mit den damals zur Verfügung stehenden syntaktischen Ausdrucksmitteln nicht beschreibbar war). Sie ist aber eindeutig eine syntaktische Anforderung.
Zur Beschreibung von Sprachen werden Grammatiken eingesetzt, mit denen man Sätze bilden
kann.
Ein "wohlgeformter" deutscher Satz:
DIE KATZE FRISST
Subjekt
Prädikat
Satz
20
DIE MAUS
Objekt
Der Linguist NOAM CHOMSKY (* 1928) entwickelte diese "Phrasenstrukturgrammatiken"
für natürliche Sprachen (seit 1950). Sie stellen eine Spezialisierung der Semi-THUE-Systeme
dar.
Chomsky stellt sich vor, dass im Menschen ein Generierungsprinzip für Sätze vorhanden ist,
etwa:
<Satz>
<Subjekt>
<Prädikat>
<Objekt>
<Artikel>
<Subjekt> <Prädikat> <Objekt> .
<Artikel> Katze | <Artikel> Hund | <Artikel> Maus
frisst
<Artikel> Maus
der | die |das
❂
❂
❂
❂
❃
❅
❄
usw.
Diese Analogie wurde Ende der 50-er Jahre erstmals bei der Definition von Algol 60 auf
Programmiersprachen übertragen. Programme werden als Sätze einer Programmiersprache
aufgefasst. Es handelt sich hier um Folgen/Ketten von Symbolen aus einem Alphabet, das
einfach eine endliche Menge ist und dessen Elemente auch Symbole oder Zeichen genannt
werden. Alphabete werden meistens mit großen - manchmal griechischen - Buchstaben bezeichnet.
Sei im Folgenden A ein Alphabet. Eine endliche Folge w = a1 ... an von Zeichen aus A heißt
Wort, Zeichenkette oder String und manchmal auch Satz über A. Für Zeichenketten wählt man
oft kleine griechische Buchstaben oder kleine Buchstaben aus dem Ende des lateinischen
Alphabets. Für Elemente aus einem Alphabet wählt man oft Zeichen aus dem Anfang des
lateinischen Alphabets.
Um den Sachverhalt klarzumachen, benötigen wir einige weitere Schreibweisen für die
Bildung von Zeichenketten (kurz: Kette) und Zeichenkettenmengen. Sei a ein Element eines
Alphabets A. Dann bezeichnet:
an
a0 =
a+
a*
: Kette aus n a's (a3 aaa)
: leere Kette, womit nicht das Leerzeichen der Tastatur gemeint ist!
: {an | n > 0} = {a, aa, aaa, ...}
: {an | n 0} = { } a+
❆
❄
❇
❈
❉
Die *-Operation heißt Sternoperation oder Kleenescher Abschluss
| | steht für die Anzahl der Zeichen, aus denen die Zeichenkette
von . Insbesondere gilt | | = 0.
❊
❋
❊
besteht, und heißt die Länge
●
Sind allgemein u und v Wörter , die natürlich auch nur aus einem Zeichen bestehen können,
so bezeichnet uv die Konkatenation („Neben- / Hintereinanderschreiben”) von u und v, d. h. das
Wort, das entsteht, wenn v hinter u geschrieben wird. (Formal: Ist u = a1 ... am und v = b1 ... bn,
so ist uv = a1 ... am b1 ... bn .) Es gilt |uv| = |u| + |v|.
21
Ist w ein Wort und n eine natürliche Zahl, so bezeichnet analog wie oben wn das Wort, das aus
n Kopien von w besteht. (Formal: w0 = , wn+1 = wn w.)
❍
Sind x, y, z Wörter und ist w = xyz, so heißt x ein Präfix von w, y ein Teilwort von w und z
ein Suffix von w. (Dabei können x, y und/oder z auch leer sein.)
Analoges gilt bei bei einem Alphabet V:
V+
V*
: Menge aller mittels V bildbaren endlich langen, nichtleeren Zeichenketten.
: { } V+.
❍
■
Ist V die leere Menge, so wird definiert V* := { } und V+ := {}.
❍
Beispiel:
Sei V = {a, b, c}, dann ist V* = { , a, b, c, aa, ab, ac, ba, ...}.
❍
Frage: Sei D die Menge aller Druckerzeichen, dann ist D* was ???
❏
Bemerkung:
V+ bzw. V* lassen sich auch etwas anders definieren, z.B. V+ = V V V V V V ... =
n
*
n
n>0 V und V = n 0 V wobei " " die Konkatenation bedeutet. Die Konkatenation in Mengenausdrücken wird wie bei der Konkatenation von Wörtern meist nicht explizit angegeben.
■
▼
❑
▲
❑
❑
▲
▼
❖
◆
Anders ausgedrückt: V* = { }
€
◗
V
◗
V×V
V×V×V
◗
◗
...
wobei die Tupelschreibweise durch die (ggf. implizit angegebene) Konkatenation V* = { }
V VV VVV ... ersetzt wird.
€
◗
◗
◗
Sei V ein Alphabet, dann heißt eine Teilmenge A
◗
❘
V* eine Sprache über V.
❙
Seien A und B Sprachen über V, dann wird analog zu oben auch die Konkatenation von A und
B definiert als die Menge der Zeichenketten ab AB V* mit a A und b B. Entsprechend
ist A0 = { }, An+1 = AnA und n>0 An und A* = n 0 An .
❙
€
❯
❚
❙
❙
❯
◆
Neben der Konkatenation oder der Sternoperation gibt es für Sprachen, weil sie ja gleichzeitig
auch gewöhnliche Mengen sind, die üblichen Operationen wie Vereinigung, Durchschnitt,
Komplement, usw.
22
Bislang können wir die Eigenschaften von Zeichenketten einer Sprache nur über Eigenschaften
definieren, z.B. {w | w = an bn n ist Primzahl}. Es zeigt sich, dass diese Art der Beschreibung
von Eigenschaften von Zeichenketten - insbesondere im programmiersprachlichen Bereich - oft
sehr ungeeignet ist. Deshalb führen wir - inspiriert durch Chomsky - eine neue Methode ein.
❱
Definitionen:
Eine Grammatik G = (VN, VT, P, S) besteht aus einem Alphabet VN von Nichtterminalen oder
Variablen aus einem dazu disjunkten Alphabet VT von Terminalen, einem Startsymbol oder
Axiom S VN und aus einer endlichen Menge von Produktionen P V*VNV* × V*, wobei V = VN
VT ist. Der Ausdruck V*VNV* beschreibt die linke Seite, die also mindestens ein Nonterminal
besitzen muss, und V* die rechte Seite, die insbesondere auch leer sein (also aus dem leeren
Wort bestehen) kann.
❲
❳
❨
Produktionen werden dargestellt als: L
den durch R")
❩
R (i.W.: "L ist definiert als R", "L kann ersetzt wer-
Eine Kette heißt direkt ableitbar aus (i.Z.: "
") gdw. durch Anwendung einer Produktion erzeugt wird, d. h. ist von der Form 1 2 3,
1 2 3, 1
1, 3
3, und es gibt
eine Produktion 2 2.
❬
❭
❪
❪
❪
❪
❫
❪
❬
❪
❬
❬
❬
❴
❬
❬
❪
❴
❬
❪
❴
❬
❬
❵
Eine Kette heißt ableitbar aus , gdw. es eine (möglicherweise leere) Folge von direkten
+
Ableitungen gibt (i.Z.:
* ). Der Ausdruck
steht für mindestens einen (nichttrivialen) Ableitungsschritt.
❬
❭
❪
❫
❬
❪
❫
❬
Eine Satzform ist eine Zeichenkette, die aus dem Startsymbol S der Grammatik ableitbar ist.
Ein Satz oder Wort ist eine nur aus Terminalen bestehende Satzform. Die Menge aller Sätze
heißt Sprache von G oder die von G erzeugte Wörtermenge (i.Z.: L(G)).
Zwei Grammatiken G1 und G2 heißen äquivalent, wenn L(G1 ) = L(G2).
Es gibt auch Grammatik-Definitionen, die die Produktionen als Elemente aus (VN VT)+ × V*
beschreiben, aber eine Produktion der Art a b, in der eine Terminalsymbol a in ein Terminalsymbol b verwandelt wird, widerspricht dem anschaulichen Begriff „terminal”. Deshalb
übernehmen wir diese Definition nicht.
❛
❵
❜
23
Beispiele (wobei auf der linken Seite einer Produktion nur ein einziges Nichtterminal auftritt,
kompliziertere Beispiele kommen später):
>
Palindrome mit GPal = ({P}, {0, 1}, PalProd, {P}) mit
PalProd = {P
❝
❞
,P
❝
0, P
❝
1, P 0P0, P
❝
❝
1P1}
oder kürzer
P
❝
❞
| 0 | 1 | 0P0 | 1P1
Die Frage, die sich hier auftut ist: „Stimmt dies? Werden wirklich alle Palindrome über
der Menge {0, 1} von der Grammatik produziert? Und produziert die Grammatik nicht
mehr, also wirklich genau die Palindrome über {0, 1}? Eine Fragestellung wie diese zu
beantworten, kann u. U. sehr schwierig sein, wie wir später noch sehen werden.
>
Identifikatoren in Pascal:
<Identifikator> <Buchstabe> <Rest>
<Rest> <Alphazeichen> <Rest> |
❝
❝
>
❞
Problematisch ist die Konvention für FORTRAN 77. Ein Identifikator darf nur 6 Zeichen haben.
❡
Wir werden sehen, dass der Begriff „Problem” später ganz allgemein auf den einer „Sprache”
und dann weiter auf den einer „Grammatik” reduziert werden kann.
24
Grammatiken lassen sich hinsichtlich der Gestalt ihrer Produktionen klassifizieren. Dabei
macht man immer mehr Einschränkungen hinsichtlich der Gestalt der Produktionen. Die obige
Grammatik-Definition stellt den allgemeinsten Fall dar. Klar, je eingeschränkter die Produktionsform, desto geringer ist ihre „Beschreibungskraft”.
Man kommt zur Chomsky-Hierarchie. Das Verhältnis der Sprachklassen ist in der folgenden
Abbildung dargestellt, wobei ein Bezug zu den Programmiersprachen genommen wird.
Chomsky-Hierarchie
25
Typ 0 Die Grammatiken nennt man auch Phrasenstrukturgrammatiken, deren Produktionen
keinen Einschränkungen unterliegen, insbesondere ist
erlaubt. Dies führt zum
sog. Wortproblem, d.h. ob von einer vorgegebenen Zeichenkette entscheidbar ist, ob
L(G) einer (ebenfalls vorgegebenen) Grammatik G ist.
❤
✐
❥
❤
❤
❦
Dieser Grammatiktyp hängt eng mit der Ausführung von Programmen zusammen.6
Sprachen, die nur mit diesen Grammatiken beschrieben werden können (d.h. nicht mit
einer Grammatik höheren Typs) heißen rekursiv aufzählbare Sprachen.
Typ 1 Es muss für eine Produktion
gelten: | | | |, wobei | | wieder die Länge der Zeichenkette ist. Die Grammatiken heißen monoton. Manchmal nennt man sie auch kontextsensitiv. Diese Bezeichnung rührt von einer anderen Darstellung her, bei der eine
Produktion dieses Grammatiktyps definiert wird als: 1 2 3
1 2 3, wobei noch gilt:
+
VN, 2 (VN VT) , 3
1
1, 2
3.
❤
✐
❤
❧
♠
❤
❧
❤
❤
❤
♥
❧
❤
❦
❧
❦
♦
❤
♥
❤
❤
✐
❧
❧
❧
❧
Man beachte, dass die Definition einer allgemeinen Grammatik zulässt, dass monotone
Grammatiken auch Produktionen der Art aBc dBe haben können. Man kann aber
beweisen, dass zu jeder monotonen / kontextfreien Grammatik eine äquivalente konstruiert werden kann mit der Eigenschaft, dass in den Produktionen der rechte bzw. linke
Kontext eines abzuleitenden Nichtterminals gleich bleibt.
✐
Damit aber das leere Wort erzeugbar ist, muss man eine Sonderregelung einführen und
fordern, dass es noch die Produktion S
mit S als Startsymbol gibt, wenn man das
leere Wort erzeugen möchte. Dann muss aber noch verlangt werden, dass S in keiner
rechten Seite einer Produktion der Grammatik vorkommt.
✐
❥
Für das Wortproblem hier gibt es keine schnellen Algorithmen. Dieser Grammatiktyp
besitzt eine Entsprechung als semantische Analyse in einem Compiler, auch wenn der
Sachverhalt nicht besonders deutlich wird.
Sprachen, die nur mit diesen Grammatiken beschrieben werden können (d.h. nicht mit
einer Grammatik höheren Typs) heißen kontextsensitive.
6
Es ist z.B. möglich eine Grammatik anzugeben, die addiert. Dazu ist es nötig, mit einer Zeichenkette
zu beginnen, die etwa aus zwei Strichlisten besteht, die durch ein besonderes Zeichen, z.B. "+", getrennt sind.
Jede Strichliste repräsentiert eine zu addierende Zahl. Demnach würde man 2+3 durch "|||+||||" dargestellen (und
ein Strich die 0 bedeuten). Die Produktionen der Grammatik müssen in der Hauptsache so beschaffen sein, dass
sie das Additionszeichen sowie ein | löschen und schließlich |||||| als Ergebnis liefern. Um die Grammatik
einfach zu halten, empfiehlt es sich noch, den Beginn der linken und das Ende der rechten Zahl zu markieren
(etwa mit L bzw. #), so dass das o.g. Beispiel "2+3" durch "L|||+||||#" repräsentiert wird. Die anzugebende
Grammatik lässt den linken Operanden unverändert, indem L mit einer Produktion L| |L nur
"durchgeschoben" wird. Ist "+" erreicht, wird es mit L+ |R in ein "|" umgewandelt und mit "R" festgehalten,
dass der Beginn des rechten Operanden erreicht ist. Analog zum linken Operanden wird das R mit R| |R
durchgeschoben, bis das Begrenzungszeichen "#" und somit die Situation "||||||||R#" erreicht ist. Jetzt müssen
noch zwei Striche und schließlich auch das Nonterminalzeichen entfernt werden, was z.B. mit den Produktionen
|R# T# und |T#
bewirkt werden kann. Das Ergebnis ist "||||||", also die Codierung von "5". Man beachte,
dass das angegebene Verfahren unabhängig von der Anfangssituation - den zu addierenden Zahlen funktioniert.
❢
❢
❢
❢
❢
❣
26
Typ 2 Die kontextfreien Grammatiken haben Produktionen, die nach der Form A
sind, wobei A VN ist.
♣
aufgebaut
q
r
Auch hier ist wieder der Sonderfall zu berücksichtigen, wie er schon beim Typ 1 angemerkt wurde, dass es noch die Produktion S
mit S als Startsymbol gibt, wenn man
das leere Wort erzeugen möchte. Dann muss wieder verlangt werden, dass S in keiner
rechten Seite einer Produktion der Grammatik vorkommt. Aber das gilt ja schon für den
Typ 1 und Typ 2 ist ein Spezialfall davon.
♣
s
Die kontextfreien Grammatiken sind im programmiersprachlichen Bereich die wichtigsten und bilden die Grundlage zur syntaktischen Analysephase eines Compilers.
Für Unterklassen der kontextfreien Grammatiken gibt es schnelle Algorithmen zur
Entscheidung des Wortproblems.
Kontextfreie Grammatiken mit höchstens einem Nonterminal auf der rechten Seite der
Produktionen nennt man linear.
Sprachen, die nur mit diesen Grammatiken beschrieben werden können (d.h. nicht mit
einer Grammatik höheren Typs) heißen kontextfrei.
Typ 3 Dies sind die regulären oder einseitig linearen Grammatiken. Die Produktionen haben
entweder die Form A B und A
, oder A
B und A
, wobei , VT*. Im
ersten Fall heißt eine Produktion linkslinear, im zweiten rechtslinear.
♣
t
✉
✈
✇
①
✇
✈
①
✈
②
Man kann beweisen, dass man zu jeder linkslinearen Grammatik eine äquivalente
rechtslineare Grammatik konstruieren kann.
Entsprechend heißen Sprachen, die „schon” mit Grammatiken dieses Typs generiert
werden können, reguläre Sprachen.
27
Zusammengefasst gesagt:
Die Scanner bei Compilern sind für reguläre Grammatiken ausgelegt, die Parser analysieren
die kontextfreien. Der Typ 3 erkennt die Atome / Tokens einer Programmiersprache.
Der Typ 2 wird bei der für Programmiersprachen wichtigen Klammerstruktur gebraucht.
Für die kontextsensitiven Eigenschaften von Programmiersprachen benötigt man eigentlich
den Typ 1. Er wird aber in der Praxis nicht eingesetzt. Die Ausnahme war ALGOL 68 mit seinen
Zweistufengrammatiken.
Eine Sprache (also eine Wortmenge mit bestimmten Eigenschaften) M heißt vom Typ i, wenn
es eine Grammatik G vom Typ i gibt, mit L(G) = M und keine einfachere.
Eine Frage, die wir uns stellen müssen lautet: „Gibt es zu jeder Sprache eine sie generierende
Grammatik?” Die Antwort ist: „Nein!”
28
Beispiele für Wortmengen und sie produzierende Grammatiken:
L(G1) = {anbncn | n 1} ist kontextsensitiv. Eine Grammatik für diese Menge wäre:
G1 = ({S,B,C}, {a,b,c}, S,P), wobei P = {1S aSBC, 2S abC, 3bB bb, 4bC bc, 5CB BC,
cc}. (Die kleinen Zahlen sind eine Numerierung.) Eine Beispielableitung für aabbcc ist:
6cC
S 1 aSBC 2 aabCBC 5 aabBCC 3 aabbCC 4 aabbcC 6 aabbcc .
③
④
④
④
④
④
④
⑤
⑤
⑤
⑤
⑤
⑤
Die Sprache L(G2) = {anbcn | n 1} ist kontextfrei (und sogar linear). Geeignete Produktionen
sind: S aCc, C aCc, C b .
⑥
⑦
⑦
⑦
L(G3) = {anbcm | n, m 1} ist linear (und sogar regulär), denn das Gewünschte leisten die Produktionen S aS, S aB, B bC, C cC, C c .
⑥
⑦
⑦
⑦
⑦
⑦
29
⑧
Document
Kategorie
Seele and Geist
Seitenansichten
10
Dateigröße
291 KB
Tags
1/--Seiten
melden