LS 2

Home
Teaching (German)
Winter 04/05
Sommer 04
Diplomarbeiten (pdf)
Frühere Semester
Service
Travel
Staff
Contact
Private

External Links

Universität Dortmund
Computer Science Faculty
Collab. Research Center 531
Collab. Research Center 475
Research Cluster 1126
Student Advisory

Grundbegriffe der theoretischen Informatik (GTI)

im Sommersemester 2001

Prof. Dr. Susanne Albers



Die Übungsscheine zur Vorlesung GTI können ab sofort am Lehrstuhl Informatik 2 in R. 336 (Frau Kühn) abgeholt werden.

Der Übungsschein in der Vorlesung Grundbegriffe der theoretischen Informatik ist ein Leistungsnachweis, der für den Studiengang Angewandte Informatik sogar obligatorisch ist. Um einen solchen Nachweis ausstellen zu können, ist eine individuelle Leistungsbewertung notwendig. In diesem Semester standen Lösungen zu den Aufgaben für GTI stets lange von dem Abgabetermin im Internet bereit. Diese wurden ausgiebig genutzt und in die Abgaben übernommen. Eine individuelle Bewertung der Einzelleistungen ist so unmöglich gemacht worden. Um trotzdem die Möglichkeit zum Scheinerwerb zu schaffen, bieten wir allen, die die alten Scheinkriterien erfüllt haben, die Gelegenheit zu einem Abschlussgespräch. Dieses wird jeweils 15 min dauern. Wir werden Sie darin bitten, Fragen, die ähnlich zu den in diesem Semester gestellten Übungsaufgaben sind, zu beantworten. Wir bieten Termine am Dienstag, 17.07., Mittwoch, 18.07., Freitag, 20.07., sowie Montag, 23.07., an. Im Folgenden finden Sie die Uhrzeiten, zu denen im viertelstündlichen Rhythmus an diesen Tagen Gespräche angeboten werden, sowie Ihren Gesprächspartner angegeben. Melden Sie sich bitte für diese Gespräche bitte direkt (persönlich oder per E-Mail) bei demjenigen Veranstalter an, mit dem Sie das Abschlussgespräch führen möchten.

Susanne Albers Freitag, 20.07., 08:00-11:30
Paul Fischer Mittwoch, 18.07., 09:00-11:30 und 12:30-14:00
Freitag, 20.07., 08:00-11:30 und 12:30-14:00 sowie
Montag, 23.07., 09:00-12:00
Oliver Giel Freitag, 20.07., 08:15-11:30 und 12:30-15:30
Carsten Witt Dienstag, 17.07., 14:00-17:00 sowie
Montag, 23.07., 09:00-12:00 Uhr

Die Uhrzeiten in dieser Tabelle umfassen jeweils den Zeitraum vom Beginn des ersten bis zum Ende des letzten Gespräches. Die Veranstalter vergeben die Termine für jeden Tag, an dem sie zu Abschlussgesprächen zur Verfügung stehen, jeweils in der Reihenfolge der eintreffenden Anmeldungen.

Weitere Termine sind bei triftigen Begründungen nach individueller Absprache möglich.


Informationen zur Vorlesung

  • Vorlesungstermine:

    Aufgrund der hohen zu erwartenden Hörerzahl wird die Vorlesung zweimal gehalten.
    Vorlesung A
    Wochentag Uhrzeit Hörsaal
    Dienstag 14-16 Uhr EF 50/HS 1
    Donnerstag 10-12 Uhr HG 3/Audimax
    		         
    Vorlesung B
    Wochentag Uhrzeit Hörsaal
    Dienstag 16-18 Uhr HG 2/HS 6
    Donnerstag 16-18 Uhr HG 2/HS 5

  • Die erste Vorlesung findet am 17.04.2001 statt.

  • Vorlesungsinhalt:

    Die Grundvorlesung "Grundbegriffe der theoretischen Informatik" ist die Einführungsvorlesung in verschiedene Gebiete der theoretischen Informatik. Die Vorlesung gliedert sich in vier Teile.

    Zunächst geht es um die Frage, was mit Computern überhaupt berechenbar ist. Es stellt sich heraus, dass es Probleme gibt, die selbst mit beliebig viel Speicherplatz und beliebig langen Rechenzeiten nicht lösbar sind. Zu diesen Problemen gehören auch so fundamentale Probleme wie das, zu entscheiden, ob ein gegebenes Computerprogramm mit einer gegebenen Eingabe überhaupt hält.

    In der Praxis stellt sich selbst für Probleme, die die von einem Rechner gelöst werden können, noch die Frage, ob eine Lösung effizient möglich ist. Wir werden sehen, wie man den Begriff "Effizienz" präzise fassen kann und Probleme danach klassifiziern, ob sie effizient lösbar sind oder nicht. Dabei zeigt es sich, dass sehr viele wichtige Probleme in diesem Sinne sehr wahrscheinlich nicht effizient lösbar sind. Dazu gehören zum Beispiel Stundenplanentwurf, Tourenplanung von Transportunternehmen, Auswahl eines optimalen Aktienpaketes, optimale Beladung eines Containers, Auswahl einer möglichst kleinen Testmenge zur Fehlererkennung und so weiter. Wenn man weiß, dass ein Problem nicht effizient lösbar ist, so muss man keine Zeit auf die Suche nach effizienten Lösungsalgorithmen verschwenden. Wir werden verschiedene Techniken zum Nachweis dieser Tatsache kennen lernen.

    Die "endlichen Automaten" stellen eine einfache Modellierung für Schaltwerke, Rechnerkomponenten und Rechner mit beschränktem Speicher dar. Sie erlauben in diesen Bereichen die Synthese, Analyse und Verifikation der Korrektheit. In der Vorlesung werden die grundlegenden Eigenschaften von endlichen Automaten untersucht. Auch ihre nichtdeterministische Variante wird behandelt.

    Schließlich untersuchen wir Grammatiken, die die Grundlage für Programmiersprachen bilden. Anforderungen an solche Grammatiken sind, dass sie ausreichend mächtig sind, um die gewünschten Konstrukte der Programmiersprache zu unterstützen, und andererseites einfach genug, um von einem Compiler schnell geprüft werden zu können. Es wird gezeigt, dass die so genannten kontextfreien Grammatiken diese Anforderungen erfüllen.

    In der Vorlesung wird eine Reihe von neuen und zum Teil ungewohnten Denkweisen vermittelt. Insbesondere trifft dies auf den Umgang mit negativen Resultaten und die Untersuchung von abstrakten Rechnertypen zu. Eine erfolgreiche Teilnahme erfordert daher die regelmäßige Nachbearbeitung der Vorlesung ebenso wie das regelmäßige Bearbeiten der Übungsaufgaben und die Diskussion der Ergebnisse in den Übungsgruppen.

  • Die Vorlesung basiert auf den folgenden Büchern:

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

    • Ingo Wegener:
      Kompendium Theoretische Informatik - eine Ideensammlung
      B. G. Teubner Verlag, Stuttgart, 1996





Informationen zu den Übungen


  • Übungstermine: Es gibt 18 Übungsgruppen.

    Nr Tag Zeit Raum Betreuer
    1 Montag 8:00-10:00 GB 4, R. 318 Paul Fischer
    2 Montag 10:00-12:00 Pav. 6, R. 18 Paul Fischer
    3 Montag 12:00-14:00 GB 4, R. 013 Ulf Schellbach
    4 Montag 16:00-18:00 GB 4, R. 013 Steffen Gregorius
    5 Dienstag 08:00-10:00 GB 4, R. 318 Oliver Giel
    6 Dienstag 10:00-12:00 GB 4, R. 318 Oliver Giel
    7 Dienstag 10:00-12:00 GB 5, R. 420 Ulf Schellbach
    8 Mittwoch 08:00-10:00 ZB C links Marc Nunkesser
    9 Mittwoch 08:00-10:00 ZB C rechts Daniel Becker
    10 Mittwoch 10:00-12:00 ZB C links Carsten Witt
    11 Mittwoch 10:00-12:00 ZB C rechts Daniel Becker
    12 Mittwoch 12:00-14:00 ZB C rechts Tobias Storch
    13 Mittwoch 14:00-16:00 ZB C links Carsten Witt
    14 Mittwoch 14:00-16:00 ZB C rechts Steffen Gregorius
    15 Donnerstag 14:00-16:00 GB 4, R. 113 Marc Nunkesser
    16 Donnerstag 14:00-16:00 GB 4, R. 318 Tobias Storch
    17 Freitag 08:00-10:00 GB 5, R. 420 Kai Plociennik
    18 Freitag 12:00-14:00 GB 5, R. 420 Kai Plociennik

  • Die Anmeldung zu den Übungsgruppen findet ausschließlich in den beiden Vorlesungen am 17.04.2001 statt. Sie erhalten dort die Möglichkeit, von Ihnen bevorzugte Übungsgruppen schriftlich anzugeben. Die endgültige Einteilung in die Übungsgruppen wird am Abend des 19.04.2001 hier (aus Gründen des Datenschutzes gelöscht) auf dieser Webseite und durch einen Aushang am LS 2 (GB 4, 2. OG) bekannt gegeben.

  • Ein Wechsel der Übungsgruppe ist nicht möglich.

  • Bei Rückfragen wenden Sie sich an Paul Fischer, Oliver Giel oder Carsten Witt.

  • Das erste Übungsblatt wird am 17.04.2001 sowohl in Vorlesung A als auch in Vorlesung B verteilt. Dieses Übungsblatt enthält eine (bewertet) zu bearbeitende Aufgabe, deren Lösung bis zum Freitag, den 20.04.2001 um 14.00 Uhr abgegeben werden muss. Darüber hinaus enthält Blatt 1 drei Präsenzaufgaben, die in der ersten Übung bearbeitet werden.

  • Die erste Übung findet in der zweiten Semesterwoche statt.

  • Die Übungsblätter 2 bis 13 werden immer donnerstags sowohl in Vorlesung A als auch Vorlesung B verteilt (ab 19.04.2001). Ist ein 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 2 (GB 4, 2. OG) auf dem Flur zwischen Raum 335 und Raum 336 abgeholt werden.

  • Die Lösungen zu den Übungsblättern 2 bis 13 müssen spätestens bis Freitag um 14 Uhr in der auf die Ausgabe folgenden Woche abgegeben werden (Einwurf in den für die jeweilige Übungsgruppe bestimmten Briefkasten im Pavillon 6). Bitte Namen, Matrikelnummer und Übungsgruppennummer nicht vergessen.

  • Auf Blatt 1 können Sie maximal 10 Punkte erreichen. Jedes weitere Übungsblatt enthält vier Aufgaben, für deren Lösung man je 10 Punkte erlangen kann. Maximal können Sie für Ihre Lösungen daher 490 Punkte erhalten.

  • Kriterien zum Erwerb eines Scheines:

    • Insgesamt mindestens die Hälfte der erzielbaren Punkte,
    • außerdem bei mindestens 9 von 13 Übungsblättern die Hälfte der bei diesem Blatt erzielbaren Punkte,
    • regelmäßige Anwesenheit in der Übung, nämlich an mindestens 10 von 13 Terminen,
    • Vorstellen der eigenen Lösung zu einzelnen Aufgaben in der Übung, und zwar mindestens zweimal pro Person während der 13 Termine.

    Achtung! Beachten Sie außerdem diese Hinweise.


  • Um die Arbeit in Gruppen zu ermöglichen, dürfen bis zu zwei Studentinnen/Studenten eine gemeinsame Lösung abgeben. Dann muss aber jede(r) dieser Gruppe in der Lage sein, die Lösung in der Übungsgruppe vorzustellen.




Übungsblätter

Die Übungsblätter werden am Tag ihrer Ausgabe
automatisch um 18.00 Uhr elektronisch bereitgestellt.

Carsten Witt
Letzte Änderung: 13. August 2001