Home Page of Roland Steinbauer

• Home
• Research
• Teaching
• Vita

Links

• A new Geometry
• Research Seminar
  
  
  
• IAGF
  
• ISAAC



Book Videos Service Page

• MaThX



• Math Library
• Math Faculty
• Vienna University
• u:space
• u:find
• MCMP
• VSM



• LISA
• Gravitational Physics




• GWUP
  
  
  
• 

EDV und Mathematik

Lehrveranstaltungsnummer: 877841, 877983
Lehrveranstaltungstyp: KO, SE
Stundenzahl: 2, 1
Zeit und Ort: Di 15:30-17:30, UZA4, C1(=C 2.09)
Beginn: 2.3.2004
Inhaltsverzeichnis
Informationen zur Prüfung

Allgemeines: Die Präzisierung des Begriffs Algorithmus und eines umfassenden Begriffs formaler Sprachen stellen eine der herausragenden Leistungen der Mathematik der letzten 100 Jahre dar. Das mathematische Studium dieser Begriffe hat nicht nur bahnbrechende geistesgeschichtliche Ergebnisse gebracht (Gödel Sätze), sondern auch die Entwicklung programmierbarer Rechenanlagen entscheidend beeinflusst und so die Grundlagen der Informatik gelegt.

Inhalt: In dieser Lehrveranstaltung begeben wir uns auf einen mathematischen Streifzug durch die Grundlagen der Informatik mit Hauptziel und Schwerpunkt Komplexitätstheorie.
Wir beginnen die LVA mit einem Abschnitt über endliche Automaten und ihre Sprachen, sie sog. regulären Sprachen. Die Formalisierung des Begriffs "Algorithmus" führt uns danach zum Modell der Turing-Maschine und zur Frage nach der Entscheidbarkeit von Problemen. Danach befassen wir uns mit der Komplexität von Problemen, insbesondere den Klassen der sog. N- und NP-vollständigen Probleme und der Frage ob, P=NP gilt.
Der Aufbau der Lehrveranstaltung orientiert sich stark am Standardlehrbuch von Hopcroft und Ullman (siehe Literatur), wobei die Schwerpunkte auf die Kapitel 2, 3, 7, 8, 12 und 13 (Nummerierung folgt der 1979er-Auflage) gelegt werden.

Modus: Das 2-std. Konversatorium besteht aus einem Vorlesungsteil (am Anfang des Semesters) und einem seminarartigen Teil in dem Studierende den Vortrag übernehmen.
Das 1-std. Seminar kann nur gemeinsam mit dem Konversatorium besucht werden (und dient dazu, das 2-std. Konversatorium als insgesamt 3-std. Wahlpflichtveranstaltung für das Lehramtsstudium Informatik und Informatikmanagement anrechenbar zu machen; Details siehe unten). Im Seminar übernehmen ebenfalls die Studierenden den Vortrag.
Konversatorium und Seminar finden teilgeblock statt; das Konversatorium bis Ende Mai, das Seminar im Juni. Die Details werden am 2.3. in der LVA geklärt.

Voraussetzungen sind lediglich die (Bereitschaft zum und die) Freude am abstrakten Denken, sowie die Beherrschung einiger grundlegender mathematischer Begriffe und Methoden wie etwa Mengen, Relationen, Funktionen und vollständige Induktion. Die Lehrveranstaltung ist also definitiv bereits für Studierende im ersten Abschnitt geeignet. Andererseits müssen Studierende im zweiten Abschnitt nicht befürchten unterfordert zu werden, da vieles am Stoff zwar elementar ist, aber knifflig!

Zielpublikum: Prinzipiell alle am Thema Interessierten; das inkludiert insbesondere:

• Diplomstudierende der Mathematik, die über Anwendungen ihres Fachs in (den Grundlagen) der Informatik Bescheid wissen wollen.
• Lehramtsstudierende der Mathematik, die Interesse an den Zusammenhängen ihres Fachs mit den Grundlagen der Informatik haben. Außerdem eignet sich der Themenbereich m.E. besonders gut für projektorientierten/fächerübergreifenden Unterricht---kombiniert etwa mit Informatik und/oder Philosophie (Gödel Sätze) und/oder Geschichte ("Ur-Geschichte" der Computer; es bestehen Querbeziehungen zur Kryptographie, i.e., Turing und seine mechanischen "Rechenmaschinen" und ihre Rolle bei der Entschlüsselung der Enigma).
• Studierende des Lehramts Informatik und Informatikmanagements, die sich den Grundlagen ihres Faches von einer "mathematischen Seite" her nähern wollen.

Literatur:

• J. Hopcroft, J. Ullman, R. Motwani
  • Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie (Addison Wesley, 2002), bzw.
  • Introduction to Automata Theory, Languages, and Computation (Addison Wesley, 2002)
  [Wir werden allerdings auch die 1979-er Auflage bzw. deren 1993-er deutsche Übersetzung verwenden, da diese bei großteils gleichem Inhalt mathematisch interessierte, fortgeschrittene Informatikstudierende als Zielpublikum hat, während die neueren Auflagen sich vornehmlich an StudienanfängerInnen der Informatik wendet.]
• E. Börger, Berechenbarkeit, Komplexität, Logik (Vieweg, 1998)
• C. Papadimitriou, Computational Complexity (Addison Wesley, 1994)

Positionierung im Studienplan/Anrechenbarkeit:

• Mathematik Diplom, neuer Studienplan: (nur Konversatorium) Wahlpflichtfach im 2. Abschnitt
• Mathematik Diplom, alter Studienplan: (nur Konversatorium) Vorprüfungsfach (EDV in der Mathematik I)
• Mathematik Lehramt: (nur Konversatorium) Freies Wahlfach
  
• Lehramt Informatik und Informatikmanagement: (Konversatorium und Seminar gemeinsam als 3-std. LVA) Wahlpflichtfach aus Theoretische und mathematische Grundlagen der Informatik

Beurteilung: Es bestehen wahlweise zwei Möglichkeiten eine postive Beurteilung zu erreichen:

1. Halten eines Seminarvortrags; hier sind sowohl anwendungsorientiertere Themen (etwa für Studierende des Lehramts Informatik und Informatikmanagement), wie auch theoretischere möglich. Neben der (selbstverständlichen) fachlichen Qualität des Vortrags ist mir das Vermitteln einer guten, dem Inhalt angepassten Präsentationstechnik ein besonderes Anliegen, das bei von mir angebotenen Vorbereitungstreffen nicht zu kurz kommen wird.
2. Ablegen einer klassischen (mündlichen) Prüfung über den Stoff der Lehrveranstaltung.

Informationen zur Prüfung:
TeilnehmerInnen des Konversatoriums resp. des Seminars können eine mündliche Prüfung ablegen. Termine können mit mir persönlich vereinbart werden (nicht zwischen 6.7. und 10.8. bzw. 20.9. und 31.10.) Der Stoff für das Konversatoriums endet mit Kapitel 12 (Postsches Korrespondezproblem; Vortrag Manfred Hubauer), der des Seminars beginnt mit Kapitel 13 (Nichthandhabbare Probleme; Vortrag Christoph Hödl). Das Kapitel 18 (Minesweeper ist NP-vollständig; Abschlußvortrag von Christoph Marx) gehört nicht zum Prüfungsstoff.

Die PrüfungskandidatInnen können sich eine beliebige Frage aus dem Stoffgebiet selbst aussuchen; weitere Fragen kommen von mir. Die Dauer der Prüfung ist ca. 45 Minuten (nur Konversatorium) bzw. ca. 60 Minuten (Konversatorium und Seminar). Beweise müssen nur unter Verwendung der Unterlagen erklärt werden können (der Rest natürlich ohne!). Die vollständigen (und tw. korrigierten) Unterlagen können bei mir zum Kopieren entlehnt werden.

Viel Spaß und Erfolg beim Lernen!