FH-HOME

06-0120: I-TI04-THEORETISCHE INFORMATIK - ZEITPLAN WS04

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

Inhalt laut Lehrplan

Literatur und Software

Leistungsnachweise

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

Automaten - informell

44

Turingmaschine formalisiert

45

Wegen Hochschultag keine VL

46

Formale Sprachen - Grundbegriffe

47

Aufzählbare Sprache, akzeptierte Sprache L(M), Entscheidungsverfahren, entscheidbare Sprache DEC(L,m)

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

Typ2-Sprachen - Der Parsergenerator bison, Teil 1

2

Typ2-Sprachen - Der Parsergenerator bison, Teil 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!)
Klausurergebnisse
Nachklausur 25.April 2005
Ergebnisse Nachklausur

START


Inhalt laut Lehrplan

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.

START

Literatur

Als primäre Referenz wird in dieser Vorlesung benutzt werden:

  1. Alfred V.AHO/ Ravi SETHI/ Jeffrey D.ULLMAN [1988], "Compilerbau", Bd 1+2, Addison-Wesley Company, Reading (MA) et al.
    /* Für Compilerbau zur Einführung immer noch sehr empfehlenswert. Mittlerweile auch in neuren Auflagen erhältlich */

  2. Alexander ASTEROTH/Christel BAIER [2002] "Theoretische Informatik. Eine Einführung in die Berechenbarkeit, Komplexität und formale Sprachen mit 101 Beispielen"; Pearson Studium
    /*Exzellente Einführung und Darstellung der theoretischen Grundbegriffe */

  3. H.HEROLD [1992], "lex und yacc. Lexikalische und syntaktische Analyse", Addison-Wesley Publ.Comp., Reading (MA) et al.
    /* Immer noch ein Klassiker zur Einführung von flex (= lex) und bison (=yacc).Mittlerweile auch in neueren Auflagen erhältlich */

  4. Robert CALLAN [2003] "Neuronale Netze im Klartext"; Pearson Studium
    /*Gute kompakte Einführung in die Thematik neuronales Netze */

Als Ergänzung und Vertiefung sei auf die folgende Auswahl hingewiesen:

  1. 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

  2. W.BALZER: Empirische Theorien. Modelle, Strukturen, Beispiele. Braunschweig - Wiesbaden: Fr.Viehweg & Sohn 1982

  3. W.BALZER/ C.U.MOULINES/ J.D.SNEED: An Architectonic for Science. The Structuralist Program, Dordrecht: Reidel 1987

  4. 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

  5. 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 */

  6. A.CHURCH: A proof from freedom of contradiction, In: Proc.Nat.Ac.Sci., vol(21)1935, pp.275-281

  7. 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.

  8. 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.

  9. A.CHURCH: Reviews of Turing 1936-7 and Post 1936, In: Journal of Symbolic Logic, vol(2)1937, pp.42-43

  10. M.DAVIS (ed): The Undecidable. Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions, Hewlett (NY): Raven Press 1965

  11. 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

  12. Gerd DOEBEN [1990], "Nichttheoreme. Eine logische Untersuchung unter Verwendung von Tableauerzeugungen und Reduktionsklassen", Peter Lang, Frankfurt et al.

  13. 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

  14. 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. */

  15. J.DUDEL/ R.MENZEL/ R.F.SCHMIDT (eds.) [1996], "Neurowissenschaft. Vom Molekül zur Kognition", Springer-Verlag

  16. A.FRENKEL [1927, Reprint 1972], "10 Vorlesungwen über die Grundlegung der Mengenlehre", Wiss.Buchgesellschaft, Darmstadt

  17. Robin GANDY: The Confluence of Ideas in 1936. In: R.HERKEN 1988:55-111

  18. 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. */

  19. 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

  20. K.GÖDEL: Remarks before the princeton bicentennial conference on problems in mathematics 1946. In: DAVIS 1965:84-87

  21. K.John GOUGH: Syntax Analysis and Software Tools, 1988; Reading (MA): Addison-Wesley
    /* Etwas kompakter als AHO und Co., gute Ergänzung. */

  22. Simon HAYKIN [1999] "Neural Networks. A Comprehensive Foundation", Prentice Hall
    /* Klassiker: Klar, ausführlich, kompetent */

  23. U.HEDSTÜCK [2003, 2.Aufl.], "Einführung in die Theoretische Informatik. Formale Sprachen und Automatentheorie", Oldenbourg Verlag, München - Wien.

  24. J.L.HEIN [1995], "Discrete Structures, Logic, and Computability", Jones and Bartlett Publ., Sudbury (MA)

  25. R.HERKEN (ed.): The Universal Turing Machine. A Half-Century Survey. , Hamburg - Berlin: Verlag Kammerer & Unverzagt 1988

  26. H.HERMES [1971, 2.Aufl.], "Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit. Einführung in die Theorie der rekursiven Funktionen", Springer Verlag, Berlin - Heidelberg - New York

  27. Helmut HEROLD [1992], "lex und yacc. Lexikalische und syntaktische Analyse", Addison-Wesley Publishing Company, Bonn - München - Paris et al


  28. D.HILBERT/ W.ACKERMANN: Grundzüge der theoretischen Logik. Berlin: Springer Verlag 1928

  29. 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.

  30. 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.

  31. A.HODGES: Alan Turing, Enigma. Transl. by R.HERKEN/ E.LACK. Wien - New York:Springer-Verlag (engl.: 1983) 1994, 2nd ed.

  32. 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. */

  33. H.L.HOPCROFT/ J.D.ULLMAN [1979], "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley Publ.Company, Reading (MA) et al.

  34. 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 */

  35. 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.

  36. 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.

  37. Christof KOCH/ Idan SEGEV (eds.)[1998, 2nd ed.] "Methods in Neironal Modeling. From Ions to Networks"; MIT Press

  38. William KNEALE/Martha KNEALE: The Development of Logic. Oxford: Clarendon Press 1962, repr. 1986

  39. Sovan LEK/ Jean-François GUÉGAN [2000] "Artificial Neuronal Networks. Application to Ecology and Evolution"; Springer Verlag

  40. G.LUDWIG: Die Grundstrukturen einer physikalischen Theorie, Berlin - Heidelberg - New York: Springer 1978

  41. G.LUDWIG: Einführung in die Grundlagen der Theoretischen Physik, Braunschweig: Viehweg 1978b (2nd. ed.)

  42. T.MASON/ D.BROWN [1991, 2.Aufl.], "lex & yacc", O'Reilly & Associates, Sebastopol (CA)

  43. M.L.MINSKY [1967], "Computation: Finite and Infinite Machines", Prentice Gall, Englewood Cliffs (NJ)
    /* Bis heute Genuss pur; ein wunderbares Buch */

  44. 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

  45. J.NIEVERGELT [1997], "Algorithmen und Datenstrukturen", in: P.RECHENBERG/ G.POMBERGER (eds.) [1997], "Informatik Handbuch", Carl Hanser Verlag, München - Wien, pp.321 - 361

  46. H.NOLTEMEIER [1981], "Informatik I. Einführung in Algorithmen und Berechenbarkeit", Carl Hanser, München - Wien

  47. A.OBERSCHELP [1966, repr. 1976], "Berechenbarkeit", in: H.BEHNKE/ H.TIETZ (eds.) "Mathematik, Bd.2", Fischer, Frankfurt a.M., SS.30 - 57

  48. P.RECHENBERG/ G.POMBERGER (eds.) [1997], "Informatik Handbuch", Carl Hanser Verlag, München - Wien

  49. Helmut Richter [2000], Online-Skript: Reguläre Sprachen, Leibniz-Rechenzentrum, München


  50. G.ROZENBERG/ A.SALOMAA (eds.) [1997], "Handbook of Formal Languages", Bd. 1-3, Springer Verlag, Heidelberg - Berlin et al.

  51. 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... */

  52. 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... */

  53. A.K.SALOMAA [1978, engl. 1973], "FORMALE SPRACHEN", Springer Verlag, Heidelberg - New York

  54. 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

  55. U.SCHÖNING [2001, 4.Aufl.], "Theoretische Informatik kurzgefasst", Spektrum Akademischer Verlag, Heidelberg - Berlin.

  56. G.M.SHEPHERD[1994, 3rd rev.ed], "Neurobiology", Oxford University Press

  57. 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

  58. S.SUPPE (ed): The Structure of Scientific Theories, Urbana - Chicago - London: University of Illinois Press 1977 (2nd ed.1979)

  59. 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).

  60. A.M.TURING: Computability and lambda.definability, In: J.Symb.Log., vol(2)1937, pp.153-163

  61. A.M.TURING: Intelligente Maschinen, In: Intelligent Service - Schriften, Hrsg.v. B.DOTZLER u. F. KITTLER 1987: pp. 81 - 113. (Engl.: Intelligent Machinery ( 1948)).

  62. J. van HEIJENOORT: From Frege to Gödel: A Source Book in Mathematical Logic 1879-1931. Cambridge (MA) : Harvard University Press 1967

  63. Reinhard Völler [1999?], Online-Skript: Automaten und formale Sprachen, Hochschule für angewandte Wissenschaften, Hamburg.


  64. I.WEGENER [1993], "Theoretische Informatik. Eine algorithmenorientierte Einführung", B.G.Teubner, Stuttgart

  65. S.WOLFRAM [2002], "A New Kind of Science", Wolfram Media, Champaign (Il)

  66. K.WEXLER/ P.W.CULICOVER [1980], "Formal Principles of Language Acquisition", MIT Press, Cambridge (MA) - London (Engl.)

  67. 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

START



Software


In der Regel wird ausschliesslich FREIE SOFTWARE benutzt.

START


Leistungsnachweise

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.


START