Grundbegriffe der theoretischen Informatik (GTI)

im Sommersemester 2000

Prof. Dr. Ingo Wegener

• Informationen zur Vorlesung
• Übungsblätter
• Informationen zu den Übungen

Informationen zur Vorlesung

• Vorlesungstermin: !!!HÖRSAAL-ÄNDERUNG!!!
  
  

  Wochentag	Uhrzeit	Hörsaal
  Dienstag	14-16 Uhr	HGII / HS 5
  Donnerstag	10-12 Uhr	neuer Hörsaal: Emil-Figge-Str. 50 (altes PH-Gebäude) / HS 1

  
  
• Die erste Vorlesung findet am 11.04.2000 statt!
  
  
• Anfang Juli findet im Rahmen der Vorlesung eine Testklausur über den Stoff der Vorlesungen Datenstrukturen und GTI statt:
  

  Inhalte Vorlesung Datenstrukturen WS 99/00

  Abweichend von nachfolgend genannten Themen entspricht der Inhalt der Vorlesung dem Skript Datenstrukturen von I. Wegener, Version vom 20.11.97.
  Nicht behandelt wurden: Kap. 2.7, 3.8, 5.5, 5.8, 5.9 und 6. Zwei-Phasen-Drei-Band-Sortieren aus Kap. 3.5. Algorithmisches Lernen in Kap. 5.4.
  Zusätzlich behandelt wurden: Breadth-First-Search. Greedy Algorithmus und Matroide.
  
  
  

  Inhalte Vorlesung GTI SS 2000

  Die in der Vorlesung behandelten Themen sind im Vorwort des Buches
  
  

  • Ingo Wegener:
    Theoretische Informatik - eine algorithmische Einfürung
    2. Auflage, B.G.Teubner Verlag, Stuttgart, 1999
    
    

  aufgelistet.
  
  
• Vorlesungsinhalt:
  
  Die Grundvorlesung "Grundbegriffe der Theoretischen Informatik" ist die Einführungsvorlesung in verschiedene Gebiete der Theoretischen Informatik. Sie gliedert sich in vier Teile.
  
  Zunächst wird untersucht, welche Probleme prinzipiell nicht mit Rechnerhilfe lösbar sind. Dazu gehören so wichtige Probleme wie die Verifikation von Programmen und die Entscheidung, ob zwei Grammatiksysteme dieselbe Programmiersprache beschreiben. Für die Praxis ergibt sich die Konsequenz, nach Algorithmen für wichtige Spezialfälle zu suchen.
  
  Allerdings ist die Lösbarkeit eines Problems mit Rechnerhilfe nicht gleichbedeutend mit der praktischen Lösbarkeit des Problems. Erst die effiziente Lösbarkeit eines Problems ist praktisch relevant. Für eine große Klasse von Problemen ist bekannt, dass sie entweder alle in polynomieller Zeit lösbar sind oder alle nicht in polynomieller Zeit lösbar sind. Seit fast 30 Jahren ist es das größte offene Problem der Theoretischen Informatik zu entscheiden, ob diese Probleme effizient lösbar sind. Es soll herausgearbeitet werden, warum die Vermutung "NP ungleich P", die besagt, dass die betrachteten Probleme nicht effizient lösbar sind, wohlfundiert ist.
  
  Endliche Automaten modellieren Schaltwerke, Rechnerkomponenten und Rechner mit beschränktem Speicher ebenso wie Cola-Automaten. Die Behandlung endlicher Automaten ist grundlegend für die Synthese und Analyse von Rechnern, die Verifikation von Hardwarekomponenten, den Entwurf von CAD-Werkzeugen und vieles andere.
  
  Die Syntax von Programmiersprachen wird durch Grammatiken beschrieben. Grammatiken sollten einerseits komfortabel sein, um Programmkonstrukte elegant zu unterstützen. Andererseits ist es notwendig, dass der Test der syntaktischen Korrektheit, die syntaktische Zerlegung und die Compilierung effizient möglich sind. Dazu muss die Klasse der erlaubten Grammatiksysteme genügend eingeschränkt sein. Es wird gezeigt, warum kontextfreie Grammatiken und ihre Einschränkungen als Grundlage von Programmiersprachen geeignet sind.
  
  Die Vorlesung enthält negative Ergebnisse (Probleme erweisen sich als unlösbar oder nicht effizient lösbar) und positive Ergebnisse. Im ersten Fall sparen wir uns die Zeit bei der Suche nach nicht existierenden Algorithmen oder effizienten Algorithmen und sind motiviert, eingeschränkte Ziele zu verfolgen. In zweiten Fall werden stets theoretisch effiziente und praktisch anwendbare Algorithmen beschrieben und analysiert.
  
  Die Hauptschwierigkeit dieser Vorlesung besteht in der Aufnahme neuer Denkweisen, insbesondere bei den negativen Resultaten, und der Betrachtung nichtrealistischer Rechnertypen, um zu Resultaten über reale Rechner zu gelangen. Ein Lernerfolg ist erfahrungsgemäß nur möglich durch
  
  
  • Teilnahme an der Vorlesung mit regelmäßiger Nacharbeit und Darstellung des Stoffes in eigenen Worten
  
  UND
  
  
  • aktiver Teilnahme an den Übungen, d.h. regelmäßiges Bearbeiten der Aufgaben und der Bereitschaft, die Lösungsversuche vor der Gruppe vorzustellen.
  
  Das Lesen von Büchern zum Vorlesungsthema ist eine begrüßenswerte Ergänzung, kann aber den Besuch von Vorlesungen und die aktive Teilnahme in den Übungen nicht ersetzen. (Sonst würde der Staat aus Kostengründen ganz sicher alle Präsenz-Universitäten durch Fern-Universitäten ersetzen.)
  
  
• Die Vorlesung basiert auf den folgenden Büchern:
  
  
  • Ingo Wegener:
    Theoretische Informatik - eine algorithmische Einfürung
    2. Auflage, B.G.Teubner Verlag, Stuttgart, 1999
    
    
  • Ingo Wegener:
    Kompendium Theoretische Informatik - eine Ideensammlung
    B.G.Teubner Verlag, Stuttgart, 1996
    
    
  
  
  

Übungsblätter

• Präsenzaufgaben
  (Ausgabe: 11.4., keine Abgabe, Besprechung in erster Übung)
• Blatt 1
  (Ausgabe: 13.4., Abgabe: 20.4.)
• Blatt 2
  (Ausgabe: 20.4., Abgabe: 27.4.)
• Blatt 3
  (Ausgabe: 27.4., Abgabe: 4.5.)
• Blatt 4
  (Ausgabe: 4.5., Abgabe: 11.5.)
• Blatt 5
  (Ausgabe: 11.5., Abgabe: 18.5.)
• Blatt 6
  (Ausgabe: 18.5., Abgabe: 25.5.)
• Blatt 7
  (Ausgabe: 23.5., Abgabe: 31.5.)
• Blatt 8
  (Ausgabe: 30.5., Abgabe: 8.6.)
• Blatt 9
  (Ausgabe: 8.6., Abgabe: 15.6.)
• Blatt 10
  (Ausgabe: 15.6., Abgabe: 21.6.)
• Blatt 11
  (Ausgabe: 20.6., Abgabe: 29.6.)
• Blatt 12
  (Ausgabe: 29.6., Abgabe: 6.7.)
• Zusatzaufgaben
  (Ausgabe: 6.7., keine Abgabe, keine Korrektur, keine Besprechung)
  Musterlösung für die Zusatzaufgaben (ab 20.7.2000)

Informationen zu den Übungen

• Ein Wechseln der Übungsgruppe ist NICHT möglich!
  Den GTI-Schein gibt es nur für die kontinuierliche Abgabe, Anwesenheit und Mitarbeit in der Übungsgruppe, für die man eingeteilt ist!!!
  
  
• Übungstermine: Es gibt 13 Übungsgruppen
  
  

  Nr	Tag	Zeit	Raum	Betreuer
  1	Dienstag	8:00 - 10:00	OH 16, SR E07	Tanja Kiseliova
  2	Dienstag	10:00 - 12:00	Campus Süd, ZB C links	Daniel Becker
  3	Dienstag	10:00 - 12:00	Campus Süd, ZB C rechts	Gerrit Rothmaier
  4	Dienstag	12:00 - 14:00	Campus Süd, ZB C links	Daniel Becker
  5	Dienstag	12:00 - 14:00	Campus Süd, ZB C rechts	Timm Euler
  6	Mittwoch	8:00 - 10:00	Campus Süd, ZB C rechts	Gero Presser
  7	Mittwoch	8:00 - 10:00	GB IV, SR 113	Claudia Gsottberger
  8	Mittwoch	10:00 - 12:00	Campus Süd, ZB C rechts	Gero Presser
  9	Mittwoch	10:00 - 12:00	GB IV, SR 113	Claudia Gsottberger
  10	Mittwoch	12:00 - 14:00	Campus Süd, ZB C rechts	Timm Euler
  11	Mittwoch	12:00 - 14:00	GB IV, SR 318	Tobias Hüllen
  12	Mittwoch	14:00 - 16:00	Campus Süd, ZB C rechts	Gerrit Rothmaier
  13	Mittwoch	14:00 - 16:00	GB IV, SR 318	Tobias Hüllen

  
  
• Die endgültige Einteilung in die Übungsgruppen wird ab Donnerstag, den 13.04.2000, hier auf dieser WWW-Seite und durch einen Aushang am LS II (GB IV, 2.OG) bekanntgegeben.
  
  
• Ein Wechseln der Übungsgruppe ist grundsätzlich NICHT möglich!
  
  
• Ansprechpartner bei Rückfragen ist Claudia Gsottberger (GB IV, R 123).
  Dies gilt auch für Studierende, die sich noch nachträglich für eine Übunsgruppe anmelden möchten.
  
  
• Die erste Übung findet in der zweiten Semesterwoche statt!
  Dort werden Präsenzaufgaben bearbeitet.
  
  
• Die Übungblätter werden immer donnerstags in der Vorlesung verteilt (ab 13.04.2000!). Ist Donnerstag ein Feiertag, verschiebt sich die Ausgabe auf den Dienstag davor! Danach sind die Übungsblätter auch auf dieser Seite zu finden bzw. können am LS II (Campus Süd, GB IV, 2.OG) auf dem Flur zwischen Raum 335 und Raum 336 abgeholt werden.
  
  
• Die Lösungen zu den jeweiligen Übungblättern müssen spätestens bis Donnerstag 14 Uhr der darauffolgenden Woche abgegeben werden (Einwurf in den für die jeweilige Übungsgruppe bestimmten Briefkasten am Campus Süd, Pavillon 6). Ist Donnerstag ein Feiertag, verschiebt sich die Abgabe auf den Mittwoch davor!
  Bitte Namen, MatrNr und Übungsgruppennummer nicht vergessen!
  
  
• Pro Übungsblatt gibt es 6 Aufgaben aus drei Schwierigkeitsstufen:
  
  

  Schwierigkeitsgrad	Punkte	Anzahl
  easy	2	3 x
  medium	4	2 x
  difficult	8	1 x

  
  
• Scheinkriterien:
  
  
  • mindestens 6 Punkte pro Blatt
  • regelmäßige Anwesenheit und Mitarbeit in der Übung
  • Vorstellen der eigenen Lösung zu einzelnen Aufgaben in der Übung
  
  
• Um die Arbeit in Gruppen zu ermöglichen, dürfen bis zu drei Studentinnen/Studenten eine gemeinsame Lösung abgeben. Dann muss aber jede/jeder dieser Gruppe in der Lage sein, die Lösung in der Übungsgruppe vorzustellen.