Letzte Änderung: 20.Juli 2005
Diese Vorlesung bildet zusammen mit der Vorlesung 'Rechnerarchitektur' eine Einheit; die abschliessende Klausur gilt für beide Lehrveranstaltungen
VORLESUNG |
:
VL Raum: BCN 121
Erste Vorlesung: Mi, 13.10.04, 16:00h
ÜBUNGEN:
Gruppe 1: 10:00h BCN 103
Gruppe 2: 11:45h Raum: BCN 103
Erste Übung: Do, 14.Okt.2004
KW |
VORLESUNG |
ÜBUNGEN |
Zusätzliches Material auf dem eLearning-Server der FH Frankfurt(verlangt Anmeldung und Passwort). |
||
42 |
Einführung in die Thematik und Plan der Vorlesung; Einteilung der Gruppen | |
43 |
||
44 |
|
|
45 |
Wegen Hochschultag keine VL |
|
46 |
|
|
47 |
|
|
48 |
Formale Sprachen: Grammatik - Chomsky Hierarchie - Reguläre Sprachen 1 |
|
49 |
Formale Sprachen: Grammatik - Chomsky Hierarchie - Reguläre Sprachen 2 |
|
50 |
Wegen Fachbereichsratssitzung keine Vorlesung |
|
51 |
Typ3-Sprachen - Reguläre Sprachen - Der Scannergenerator flex 1 |
|
52 |
Typ3-Sprachen - Reguläre Sprachen - Der Scannergenerator flex 2 |
|
53 |
Keine Vorlesung |
|
1 |
|
|
2 |
|
|
3 |
Zusammenfassung | |
4 |
Ausblick: Universelle Turingmachine - Unentscheidbarkeit - Lernen - Gehirn - Neuronale Netze |
|
5 |
Klausur Mo,31.Jan.2005, 10:00-12:00h, Raum BCN 224 (nicht BCN 121!) |
Der bisherige Lehrplan umschreibt die Lehrinhalte für Theoretische Informatik wie folgt:
Das Fundament der theoretischen Informatik bilden die Begriffe der Berechenbarkeit und Entscheidbarkeit, die mit Hilfe der Formalisierung des Begriffs des Automaten und der formalen Sprachen definiert werden konnten. Aufbauend auf diesen Begriffen ist es möglich, einen Komplexitätsbegriff einzuführen, der für die Einschätzung der praktischen Machbarkeit von Aufgabenstellungen der Informatik von zentraler Bedeutung ist. Durch das Zusammenspiel von Mensch und Maschine (MMI := Man-Machine-Interaction, auch HCI := Human-Computer-Interaction) in den hochtechnisierten Gesellschaften kommt der Frage der Vergleichbarkeit von Mensch und Maschine eine neue Bedeutung zu, ebenso die Frage nach künstlicher Intelligenz, nach maschinellem Lernen und maschinengestützter menschenähnlicher Kommunikation. In dieser Lehrveranstaltung wird versucht werden, neben der Vermittlung der Grundbegriffe (Berechenbarkeit, Entscheidbarkeit, Automat, Formale Sprachen, Komplexität) dieser neuen Dimension der Informatik, nämlich der menschenähnlichen Intelligenz mit dem zentralen Begriffen Lernen Rechnung zu tragen. Letzteres soll an den Ergebnissen der modernen Gehirnforschung und der künstlichen neuronalen Netzen diskutiert werden.
Als primäre Referenz wird in dieser Vorlesung benutzt werden:
|
---|
Als Ergänzung und Vertiefung sei auf die folgende Auswahl hingewiesen:
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
James M.BOWER/ David BEEMAN [1998, 2nd ed.] "The Book of GENESIS. Exploring Realistic Neural Models with the GEneral NEural SImulation System"; Springer Verlag
/* Das Buch enthält eine CD mit der kompletten Software */
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
K.John GOUGH: Syntax Analysis and Software Tools, 1988; Reading (MA): Addison-Wesley
/* Etwas kompakter als AHO und Co., gute Ergänzung. */
Simon HAYKIN [1999] "Neural Networks. A Comprehensive Foundation", Prentice Hall
/* Klassiker: Klar, ausführlich, kompetent */
U.HEDSTÜCK [2003, 2.Aufl.], "Einführung in die Theoretische Informatik. Formale Sprachen und Automatentheorie", Oldenbourg Verlag, München - Wien.
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
Helmut HEROLD [1992], "lex und yacc. Lexikalische und syntaktische Analyse", Addison-Wesley Publishing Company, Bonn - München - Paris 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.
Daniel JURAFSKY/ James H.MARTIN [2000], "Speech and Language Processing. An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition",
Prentice Hall, Upper Saddle River (NJ)
/*Exzellentes Buch zur einführung in die Thematik */
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.
Christof KOCH/ Idan SEGEV (eds.)[1998, 2nd ed.] "Methods in Neironal Modeling. From Ions to Networks"; MIT Press
William KNEALE/Martha KNEALE: The Development of Logic. Oxford: Clarendon Press 1962, repr. 1986
Sovan LEK/ Jean-François GUÉGAN [2000] "Artificial Neuronal Networks. Application to Ecology and Evolution"; Springer Verlag
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)
/* Bis heute Genuss pur; ein wunderbares Buch */
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
Helmut Richter [2000], Online-Skript: Reguläre Sprachen, Leibniz-Rechenzentrum, München
G.ROZENBERG/ A.SALOMAA (eds.) [1997], "Handbook of Formal Languages", Bd. 1-3, Springer Verlag, Heidelberg - Berlin et al.
David E.RUMELHART/ James L.McCLELLAND et al. [1986] "Parallel Distributed Processing. Exlorations in the Microstructure of Cognition. Vol.1: Foundations"; The MIT Press
/*Der Klassiker schlechthin... Das war quasi die Wiedergeburt des neuronalen Paradigmas... */
David E.RUMELHART/ James L.McCLELLAND et al. [1986] "Parallel Distributed Processing. Exlorations in the Microstructure of Cognition. Vol.2: Psychological and Biological Models"; The MIT Press
/*Der Klassiker schlechthin... Das war quasi die Wiedergeburt des neuronalen Paradigmas... */
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
U.SCHÖNING [2001, 4.Aufl.], "Theoretische Informatik kurzgefasst", Spektrum Akademischer Verlag, Heidelberg - Berlin.
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
Reinhard Völler [1999?], Online-Skript: Automaten und formale Sprachen, Hochschule für angewandte Wissenschaften, Hamburg.
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
In der Regel wird ausschliesslich FREIE SOFTWARE benutzt.
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 |
Grundsätzlich gilt, dass Leistungspunkte in der Klausur erworben werden. Da es sich bei I-TI um eine Prüfungsleistung handelt, ist es nicht möglich, Leistungen aus den Übungen für die Klausur anzurechnen. Dies ist ein Nachteil der aktuellen PO. Da erfahrungsgemäss ein gutes Klausurergebnis entscheidend von der eigenen aktiven Übung abhängt, kann hier nur dringend empfohlen werden, die angebotenen Übungsmöglichkeiten ernsthaft zu nutzen. Wer will, kann auch seine Übungsergebnisse vorstellen und testweise bewerten lassen. Damit kann man eine gewisse Kontrolle über seinen tatsächlichen Leistungsstand bekommen.