FH-HOME

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

Letzte �derung: 20.Juli 2005

	  Diese Vorlesung bildet zusammen mit der Vorlesung 'Rechnerarchitektur'
           eine Einheit;  die abschliessende Klausur gilt fr 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

�UNGEN

Inhalt laut Lehrplan

Literatur und Software

Leistungsnachweise

Zus�zliches 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�lbare Sprache, akzeptierte Sprache L(M), Entscheidungsverfahren, entscheidbare Sprache DEC(L,m)

48

Formale Sprachen: Grammatik - Chomsky Hierarchie - Regul�e Sprachen 1

49

Formale Sprachen: Grammatik - Chomsky Hierarchie - Regul�e Sprachen 2

50

Wegen Fachbereichsratssitzung keine Vorlesung

51

Typ3-Sprachen - Regul�e Sprachen - Der Scannergenerator flex 1

52

Typ3-Sprachen - Regul�e 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�lich, einen Komplexit�sbegriff einzufhren, der fr die Einsch�zung 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 knstlicher Intelligenz, nach maschinellem Lernen und maschinengesttzter menschen�nlicher Kommunikation. In dieser Lehrveranstaltung wird versucht werden, neben der Vermittlung der Grundbegriffe (Berechenbarkeit, Entscheidbarkeit, Automat, Formale Sprachen, Komplexit�) dieser neuen Dimension der Informatik, n�lich der menschen�nlichen Intelligenz mit dem zentralen Begriffen Lernen Rechnung zu tragen. Letzteres soll an den Ergebnissen der modernen Gehirnforschung und der knstlichen neuronalen Netzen diskutiert werden.

START

Literatur

Als prim�e 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.
    /* Fr Compilerbau zur Einfhrung immer noch sehr empfehlenswert. Mittlerweile auch in neuren Auflagen erh�tlich */

  2. Alexander ASTEROTH/Christel BAIER [2002] "Theoretische Informatik. Eine Einfhrung in die Berechenbarkeit, Komplexit� und formale Sprachen mit 101 Beispielen"; Pearson Studium
    /*Exzellente Einfhrung 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 Einfhrung von flex (= lex) und bison (=yacc).Mittlerweile auch in neueren Auflagen erh�tlich */

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

Als Erg�zung 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�GER [1992, 3.Aufl.], "Berechenbarkeit, Komplexit�, Logik. Algorithmen, Sprachen und Kalkle unter besonderer Bercksichtigung ihrer Komplexit�", 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�t 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�sche 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 �ersetzung er wichtigsten Aufs�ze 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 Molekl 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 Einfhrung, die ich fr das Komplexit�sproblem gefunden habe.1979 erhielten beide Autoren fr 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�zung. */

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

  23. U.HEDST�K [2003, 2.Aufl.], "Einfhrung in die Theoretische Informatik. Formale Sprachen und Automatentheorie", Oldenbourg Verlag, Mnchen - 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�lbarkeit, Entscheidbarkeit, Berechenbarkeit. Einfhrung 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 - Mnchen - 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�el, 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 einfhrung 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, Mnchen - Wien, pp.321 - 361

  46. H.NOLTEMEIER [1981], "Informatik I. Einfhrung in Algorithmen und Berechenbarkeit", Carl Hanser, Mnchen - 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, Mnchen - Wien

  49. Helmut Richter [2000], Online-Skript: Regul�e Sprachen, Leibniz-Rechenzentrum, Mnchen


  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�ING [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�ler [1999?], Online-Skript: Automaten und formale Sprachen, Hochschule fr angewandte Wissenschaften, Hamburg.


  64. I.WEGENER [1993], "Theoretische Informatik. Eine algorithmenorientierte Einfhrung", 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

Fr die Prfungsleistung werden Noten von 1-5 vergeben:

NOTE

PUNKTE

1

>70

2

55-69

3

40-54

4

25-39

5

<25



Grunds�zlich gilt, dass Leistungspunkte in der Klausur erworben werden. Da es sich bei I-TI um eine Prfungsleistung handelt, ist es nicht m�lich, Leistungen aus den �ungen fr die Klausur anzurechnen. Dies ist ein Nachteil der aktuellen PO. Da erfahrungsgem�s ein gutes Klausurergebnis entscheidend von der eigenen aktiven �ung abh�gt, kann hier nur dringend empfohlen werden, die angebotenen �ungsm�lichkeiten ernsthaft zu nutzen. Wer will, kann auch seine �ungsergebnisse vorstellen und testweise bewerten lassen. Damit kann man eine gewisse Kontrolle ber seinen tats�hlichen Leistungsstand bekommen.


START