Diese Vorlesung bildet zusammen mit der Vorlesung 'Rechnerarchitektur' eine Einheit; die abschliessende Klausur gilt für beide Lehrveranstaltungen
(Dieser Plan kann Änderungen unterliegen.
Letzte Änderung: Febr-04, 2003)
KW |
LEHRVERANSTALTUNG |
BERECHENBARKEIT |
AUTOMATEN |
SPRACHEN |
KOMPLEXITÄT |
ZEIT: VL Mo 10:00-11:30 (BCN 121); Üb.A: Fr, 8:15-9:00 (BCN 104), Üb.B: Fr, 9:00-9:45 (BCN 104) |
|
||||
40 |
|
|
|
|
|
41 |
|
|
|
|
|
42 |
|
|
|
|
|
43 |
Von der universellen Turingmaschine zu Intelligenten Systemen |
|
|
|
|
44 |
|
|
|
|
|
45 |
|
|
|
|
|
46 |
Formale Grammatiken, Syntaxdiagramme, Chomsky-Hierarchie, Endliche Automaten und Reguläre Sprachen |
|
|
|
|
47 |
|
|
|
|
|
48 |
|
|
|
|
|
49 |
Endliche Automaten und Reguläre Sprachen III; Benutzung von flex |
|
|
|
|
50 |
|
|
|
|
|
51 |
|
||||
52 |
KEINE LEHRVERANSTALTUNG |
||||
1 |
KEINE LEHRVERANSTALTUNG |
||||
2 |
Tutorium |
|
|||
3 |
KLAUSUR mit Ergebnissen |
|
Als primäre Referenz wird in dieser Vorlesung benutzt werden:
|
---|
Beide Bücher geben einen verständlichen und kompakten Überblick über die Themen Berechenbarkeit, Automaten und Sprachen, wobei sich HEDSTÜCK als erster Einstieg empfielt. Als Ergänzung und Vertiefung sei auf die folgende Auswahl hingewiesen:
Alfred V.AHO/ Ravi SETHI/ Jeffrey D.ULLMAN [1988], "Compilerbau", Bd 1+2, Addison-Wesley Company, Reading (MA) et al.
J-M.AUTEBERT/ J.BERSTEL/ L.BOASSON [1997], "Context-Free Languages and Pushdown Automata", in: G.ROZENBERG/ A.SALOMAA (eds.) [1997], "Handbook of Formal Languages", Bd. 1, Springer Verlag, Heidelberg - Berlin et al., pp.111-172
W. BALZER: Empirische Theorien. Modelle, Strukturen, Beispiele. Braunschweig - Wiesbaden: Fr.Viehweg & Sohn 1982
W.BALZER/ C.U.MOULINES/ J.D.SNEED: An Architectonic for Science. The Structuralist Program, Dordrecht: Reidel 1987
E.BÖRGER [1992, 3.Aufl.], "Berechenbarkeit, Komplexität, Logik. Algorithmen, Sprachen und Kalküle unter besonderer Berücksichtigung ihrer Komplexität", Friedr. Vieweg & Sohn, Braunschweig - Wiesbaden
A.CHURCH: A proof from freedom of contradiction, In: Proc.Nat.Ac.Sci., vol(21)1935, pp.275-281
A.CHURCH [1936a], An unsolvable problem of elementary number theory, In: Amer.J.Math., vol.(58)1936, pp.345-363. Presented to the American Mathematical Society, April 19, 1935; abstract in B.Am.Math. S., vol(41), May 1935.
A.CHURCH [1936b], A note on the Entscheidungsproblem, In: Journal of Symbolic Logic, vol.1(1936a), pp:40-41, 356-361(received April 15, 1936). Correction ibid. (1936) 101-102; received August 13, 1936.
A.CHURCH: Reviews of Turing 1936-7 and Post 1936, In: Journal of Symbolic Logic, vol(2)1937, pp.42-43
M.DAVIS (ed): The Undecidable. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions, Hewlett (NY): Raven Press 1965
Nachum DERSHOWITZ/ Jean-Pierre JOUANNAUD [1990], "Rewrite Systems", in: J. van Leeuwen (ed.), "Handbook of theoretical Computer Science", Volume B, Elsevier Science Publ., Amsterdam et al, pp.243 - 320
Gerd DOEBEN [1990], "Nichttheoreme. Eine logische Untersuchung unter Verwendung von Tableauerzeugungen und Reduktionsklassen", Peter Lang, Frankfurt et al.
Gerd DOEBEN-HENISCH [1999], "Alan Matthew Turing, the Turing Machine, and the Concept of Sign", In: W.Schmitz, Th.A.Sebeok (eds.),Das Europäische Erbe der Semiotik; The European Heritage of Semiotics, ISBN 3933592062, to be published 2002
B.DOTZLER/ F.KITTLER (eds.) [1987], "Alan M.Turing: Intelligence Service. Schriften", Brinkmann & Bose, Berlin
/*
Deutsche Übersetzung er wichtigsten Aufsätze von A.M.Turing, dem 'Vater' der Turingmaschine. Interessantes
historisches Hintegrundmaterial zur Theorie der Berechenbarkeit und der Idee der Computer. */
J.DUDEL/ R.MENZEL/ R.F.SCHMIDT (eds.) [1996], "Neurowissenschaft. Vom Molekül zur Kognition", Springer-Verlag
A.FRENKEL [1927, Reprint 1972], "10 Vorlesungwen über die Grundlegung der Mengenlehre", Wiss.Buchgesellschaft, Darmstadt
Robin GANDY: The Confluence of Ideas in 1936. In: R.HERKEN 1988:55-111
Michael R.GAREY/ David S.Johnson [1979], "Computers and Intractability. A Guide to the Theory of NP-Completeness",
W.H.Freeman and Company, San Francisco.
/* Die bislang beste Einführung, die ich für das Komplexitätsproblem gefunden habe.1979
erhielten beide Autoren für dieses Buch den Lanchester Prize der Operations Research Society von USA. */
K.GÖDEL: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. In: Mh.Math.Phys., vol.38(1931),pp:175-198
K.GÖDEL: Remarks before the princeton bicentennial conference on problems in mathematics 1946. In: DAVIS 1965:84-87
J.L.HEIN [1995], "Discrete Structures, Logic, and Computability", Jones and Bartlett Publ., Sudbury (MA)
R.HERKEN (ed.): The Universal Turing Machine. A Half-Century Survey. , Hamburg - Berlin: Verlag Kammerer & Unverzagt 1988
H.HERMES [1971, 2.Aufl.], "Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit. Einführung in die Theorie der rekursiven Funktionen", Springer Verlag, Berlin - Heidelberg - New York
H.HEROLD [1992], "lex und yacc. Lexikalische und syntaktische Analyse", Addison-Wesley Publ.Comp., Reading (MA) et al.
D.HILBERT/ W.ACKERMANN: Grundzüge der theoretischen Logik. Berlin: Springer Verlag 1928
P.HINST: A Rigorous Set Theoretical Foundation of the Structuralist Approach. In: W. BALZER/ C.U.MOULINES (eds): Structuralist Theory of Science. Focal Issues, New Results. Berlin - New York: Walter de Gruyter Verlag 1996, 233-263.
A.HODGES: Alan Turing and the Turing Machine, In: R.HERKEN (ed)The Universal Turing Machine. A Half-Century Survey. Oxford - New York - Toronto: Oxford University Press 1988, pp. 3 - 15.
A.HODGES: Alan Turing, Enigma. Transl. by R.HERKEN/ E.LACK. Wien - New York:Springer-Verlag (engl.: 1983) 1994, 2nd ed.
D.HOFSTADTER [1980], "Gödel, Escher, Bach: An Eternal Golden Braid", Vintage Books, New York
/* Kein
wissenschaftliches Buch im üblichen Sinne, aber sehr geeignet, die zentralen Themen der theoretischen Informatik auf etwas
unterhaltsamere Art kennen zu lernen. */
H.L.HOPCROFT/ J.D.ULLMAN [1979], "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley Publ.Company, Reading (MA) et al.
Stephen C. KLEENE: General recursive functions of natural numbers, In: Math.Annal., vol(112)1936, pp.727-742. Presented by title to theAmerican Mathematical Society Sept 1935. Abstract in B.Am.Math. S., July 1935.
Stephen C. KLEENE: lambda-definability and recursiveness, In: Duke Math.J., vol(2)1936a, pp.340-353. Abstract in B.Am.Math. S., July 1935.
William KNEALE/Martha KNEALE: The Development of Logic. Oxford: Clarendon Press 1962, repr. 1986
G.LUDWIG: Die Grundstrukturen einer physikalischen Theorie, Berlin - Heidelberg - New York: Springer 1978
G.LUDWIG: Einführung in die Grundlagen der Theoretischen Physik, Braunschweig: Viehweg 1978b (2nd. ed.)
T.MASON/ D.BROWN [1991, 2.Aufl.], "lex & yacc", O'Reilly & Associates, Sebastopol (CA)
M.L.MINSKY [1967], "Computation: Finite and Infinite Machines", Prentice Gall, Englewood Cliffs (NJ)
R.M.MOLL/ M.A.ARBIB/ A.J.KFOURY with Contributions by J.PUSTEJOVSKY [1988], "An Introduction to Formal Language Theory", Springer Verlag, Berlin - New York
J.NIEVERGELT [1997], "Algorithmen und Datenstrukturen", in: P.RECHENBERG/ G.POMBERGER (eds.) [1997], "Informatik Handbuch", Carl Hanser Verlag, München - Wien, pp.321 - 361
H.NOLTEMEIER [1981], "Informatik I. Einführung in Algorithmen und Berechenbarkeit", Carl Hanser, München - Wien
A.OBERSCHELP [1966, repr. 1976], "Berechenbarkeit", in: H.BEHNKE/ H.TIETZ (eds.) "Mathematik, Bd.2", Fischer, Frankfurt a.M., SS.30 - 57
P.RECHENBERG/ G.POMBERGER (eds.) [1997], "Informatik Handbuch", Carl Hanser Verlag, München - Wien
G.ROZENBERG/ A.SALOMAA (eds.) [1997], "Handbook of Formal Languages", Bd. 1-3, Springer Verlag, Heidelberg - Berlin et al.
A.K.SALOMAA [1978, engl. 1973], "FORMALE SPRACHEN", Springer Verlag, Heidelberg - New York
A.K.SALOMAA [1990], "Formal Languages and Power Series", in: J. van Leeuwen (ed.), "Handbook of theoretical Computer Science", Volume B, Elsevier Science Publ., Amsterdam et al, pp.103 - 132
G.M.SHEPHERD[1994, 3rd rev.ed], "Neurobiology", Oxford University Press
K.SIKKEL/ A.NIJHOLT [1997], "Parsing of Context-Free Languages", in: G.ROZENBERG/ A.SALOMAA (eds.) [1997], "Handbook of Formal Languages", Bd. 2, Springer Verlag, Heidelberg - Berlin et al., pp.61-100
S.SUPPE (ed): The Structure of Scientific Theories, Urbana - Chicago - London: University of Illinois Press 1977 (2nd ed.1979)
A.M.TURING: On Computable Numbers with an Application to the Entscheidungsproblem, In: Proc. London Math. Soc., Ser.2, vol.42(1936), pp.230-265; received May 25, 1936; Appendix added August 28; read November 12, 1936; corr. Ibid. vol.43(1937), pp.544-546. Turing's paper appeared in Part 2 of vol.42 which was issued in December 1936 (Reprint in M.DAVIS 1965, pp.116-151; corr. ibid. pp.151-154).
A.M.TURING: Computability and lambda.definability, In: J.Symb.Log., vol(2)1937, pp.153-163
A.M.TURING: Intelligente Maschinen, In: Intelligent Service - Schriften, Hrsg.v. B.DOTZLER u. F. KITTLER 1987: pp. 81 - 113. (Engl.: Intelligent Machinery ( 1948)).
J. van HEIJENOORT: From Frege to Gödel: A Source Book in Mathematical Logic 1879-1931. Cambridge (MA) : Harvard University Press 1967
I.WEGENER [1993], "Theoretische Informatik. Eine algorithmenorientierte Einführung", B.G.Teubner, Stuttgart
S.WOLFRAM [2002], "A New Kind of Science", Wolfram Media, Champaign (Il)
K.WEXLER/ P.W.CULICOVER [1980], "Formal Principles of Language Acquisition", MIT Press, Cambridge (MA) - London (Engl.)
Sheng YU [1997], "Regular Languages", in: G.ROZENBERG/ A.SALOMAA (eds.) [1997], "Handbook of Formal Languages", Bd. 1-3, Springer Verlag, Heidelberg - Berlin et al., pp41-110
Software (Wir verwenden ausschliesslich 'freie' Software!)
Name |
Kurzbeschreibung |
---|---|
SuSe 7.2/ 7.3 / 8.0/ 8.1 Linux Distribution |
Freie Version des Betriebssystems GNU-Linux |
GNU xemacs |
Mehr als ein Editor |
GNU gcc/ g++ ab Vers. 2.95 |
C++-Compiler |
as |
Assembler zusammen mit gcc/g++ |
ld |
Linker zusammen mit as |
GNU make |
Tool zum Verwalten von Dateien eines SW-Projektes |
GNU (xx)gdb ab Vers. 5.0 |
Tool zum Debuggen von Objekt-Code |
XFree86 ab Version 3.3.5 |
Freies X-Wondow-System mit Unterstützung von Hardwarebeschleunigung im Fenster |
Konzeptualisierungstool für die Methoden SA (Structured Analysis) und UML |
|
cpp2html |
c++/Java-zu-HTML-Konverter |
HTML-Editor |
|
HTML-Browser (für Windows, Linux und Mac!); ideale Arbeitsplattform für Entwickler |
|
GNU gimp |
GNU Image Manipulation Program, zum Editieren und Umformatieren von 2D-Bildern |
starOffice 5.2 |
Vergleichbar mit MS-Office; läuft unter Linux und MS-Windows. Damit kann man u.a. HTML-Seiten gut formatiert ausrucken (passt auch die Bilder an die Seitengrösse an). |
htmldoc |
Konvertierer von HTML nach PDF. Text sehr gut, Bilder werden nicht angepasst. |
klogic |
Editor und Simulator für logische Schaltungen, frei unter Linux. |
Für die Prüfungsleistung werden Noten von 1-5 vergeben:
NOTE |
PUNKTE |
---|---|
1 |
>70 |
2 |
55-69 |
3 |
40-54 |
4 |
25-39 |
5 |
<25 |
Diese Punkte kann man erlangen, wenn man am Ende des Semesters an einer Klausur teilnimmt (Termin siehe oben). Aufgrund der Prüfungsordnung ist es nicht möglich, Übungsleistungen während des Semesters mit Punkten zu belegen. Mit Blick auf ein vertieftes Verständnis des Stoffs wird aber dringend empfohlen, während des Semesters regelmässig an den Übungen teilzunehmen. Dies erleichtert die Prüfungsvorbereitungen erheblich. Dazu werden zu Beginn des Semesters 3er-Gruppen gebildet. In jeder Übungsstunde wird mindestens 1 Aufgabe ausführlich vorgestellt, die gelöst werden muss. Jede Übungsgruppe hat in der nächsten Übungstunde Gelegenheit, ihre Lösung vorzustellen.