FH-HOME

THEORETISCHE INFORMATIK - ZEITPLAN

 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

Ankündigung des Kurses

Literatur und Software

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)

Leistungsnachweise


40

Einführung





41

Wichtige Begriffe im Umfeld der Turingmaschine





42

Die universelle Turingmaschine; Lernfähigkeit





43

Von der universellen Turingmaschine zu Intelligenten Systemen




44

Fokussierung auf formale Sprachen





45

Entscheidbare Mengen





46

Formale Grammatiken, Syntaxdiagramme, Chomsky-Hierarchie, Endliche Automaten und Reguläre Sprachen





47

Endliche Automaten und Reguläre Sprachen I





48

Endliche Automaten und Reguläre Sprachen II





49

Endliche Automaten und Reguläre Sprachen III; Benutzung von flex





50

Kontextfreie Sprachen I - Kellerautomaten (PDAs)





51

Kontextfreie Sprachen II - Parsing


52

KEINE LEHRVERANSTALTUNG

1

KEINE LEHRVERANSTALTUNG

2

Tutorium


3

KLAUSUR mit Ergebnissen




START


Literatur

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

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


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


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:

  1. Alfred V.AHO/ Ravi SETHI/ Jeffrey D.ULLMAN [1988], "Compilerbau", Bd 1+2, Addison-Wesley Company, Reading (MA) et al.

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

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

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

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

  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

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

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

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

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

  23. H.HEROLD [1992], "lex und yacc. Lexikalische und syntaktische Analyse", Addison-Wesley Publ.Comp., Reading (MA) et al.

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

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

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

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

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

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

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

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

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

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

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

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

  36. M.L.MINSKY [1967], "Computation: Finite and Infinite Machines", Prentice Gall, Englewood Cliffs (NJ)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

tcm

Konzeptualisierungstool für die Methoden SA (Structured Analysis) und UML

cpp2html

c++/Java-zu-HTML-Konverter

quanta

HTML-Editor

mozilla

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.

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



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.

START