Modul "Theoretische Informatik II" - GTI

 

1 Organisatorisches

Form: 3 VL + 1 Ü    (6 ECTS-Punkte)

Vorlesung:    H. Dierks

Dienstag 10-12, A7 Hörsaal G (0-030) ,    Begin: Do, 16.10.2003
Donnerstag 10-12, A14 Hörsaal 2 (1-102)

Übungen:    A. Schäfer

Mittwoch	18-19,		A5 1-160
Freitag	8- 9,	9-10,	A4 2-221
Freitag	12-13,	13-14,	A4 2-221
Freitag	12-13,		A3 2-209

Bitte beachten: Am ersten Dienstag in der Vorlesungszeit (14.10.2003) findet keine Vorlesung statt - die Vorlesung beginnt also am darauffolgenden Donnerstag (16.10.2003).

 

2 Klausur

Die Ergebnisse der GTI-Klausur sind jetzt hier verfügbar.

Matrikelnummer:   

Einsicht in die 2. Klausur kann am Montag, den 5.4., und am Donnerstag, den 8.4., jeweils von 10h-19h im A3 2-206 (im Büro von Andreas Schäfer) genommen werden.

Notenspiegel:

1. Klausur:

Note:	0.7	1.0	1.3	1.7	2.0	2.3	2.7	3.0	3.3	3.7	4.0	4.3	5.0
Punkte:	100 - 95	94 - 90	89 - 85	84 - 80	79 - 75	74 - 70	69 - 65	64 - 60	59 - 55	54 - 50	49 - 45	44 - 40	39 - 0
Anzahl:	3	3	3	4	8	6	3	17	18	21	18	24	27
Anzahl:	9			18			38			63			27

2. Klausur:

Note:	0.7	1.0	1.3	1.7	2.0	2.3	2.7	3.0	3.3	3.7	4.0	4.3	5.0
Punkte:	100 - 95	94 - 90	89 - 85	84 - 80	79 - 75	74 - 70	69 - 65	64 - 60	59 - 55	54 - 50	49 - 45	44 - 40	39 - 0
Anzahl:	1	0	0	0	1	0	3	3	4	1	9	7	6
Anzahl:	1			1			10			17			6

 

3 Ziele

Einfuehrung in Berechenbarkeits-, Automaten-, Komplexitaetstheorie

 

4 Inhalt

Nach Vermittlung diverser (mathematischer) Grundlagen wird im ersten Teil der Vorlesung untersucht, welche Funktionen algorithmisch berechenbar bzw. welche Probleme algorithmisch entscheidbar sind. Dazu wird der Begriff des Algorithmus formalisiert. Turingmaschinen und Grammatiken stellen sich als äquivalente Ansätze heraus. Es wird gezeigt, daß es Probleme gibt, die nicht algorithmisch entscheidbar sind. Dazu gehören leider auch viele Probleme von praktischem Interesse.

Zur Beschreibung der Syntax von Programmiersprachen sind reguläre und kontextfreie Sprachen am wichtigsten. Im zweiten Teil der Vorlesung wird gezeigt, daß solche Sprachen von einfacheren Maschinen als Turingmaschinen erkannt werden können, nämlich durch endliche Automaten und Kellerautomaten. Ferner werden grundlegende Eigenschaften dieser Sprachen und Automaten hergeleitet.

Im dritten Teil der Vorlesung geht es um die Komplexität von Algorithmen, d. h. wieviel Zeit und Spreicherplatz zum Lösen einer Aufgabe benötigt wird. Insbesondere werden Probleme betrachtet, die deterministisch oder nichtdeterministisch in polynomieller Zeit lösbar sind. Diese Problemklassen sind unter den Namen P und NP bekannt.

 

5 Literatur

essentiell:

• Schoening: "Theoretische Informatik - kurzgefasst", 4. Auflage, Spektrum
  (Die VL wird sich an diesem Buch orientieren)

empfohlen:

• Skriptum "Grundbegriffe der Theoretischen Informatik" von Prof. Claus und Prof. Olderog oder das Skriptum von Prof. Best.
• Hopcroft, Ullman: "Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie", Pearson
  (ein Klassiker...)

gute Sekundärliteratur:

• Erk, Priese: "Theoretische Informatik", Springer-Verlag
• Asteroth, Baier: "Theoretische Informatik", Pearson

 

6 Übungsaufgaben

Hier wird die Möglichkeit geboten, die aktuellen Übungsblätter zu dieser Lehrveranstaltung abzurufen. Wir bitten jedoch im Interesse aller, die Übungsblätter nicht gedankenlos auszudrucken, insbesondere nicht auf den Laserdruckern der ARBI. Photokopien sind unter Berücksichtigung aller Kosten in der Regel günstiger als Laserdrucke!

Dieses Angebot richtet sich hauptsächlich an diejenigen, die auf anderem Wege kein Exemplar der Übungsblätter erhalten konnten, bzw. die die Aufgaben während der Bearbeitung am Bildschirm betrachten möchten.

	pdf	ps
blatt01	(30 KByte)	(94 KByte)
blatt02	(25 KByte)	(122 KByte)
blatt03	(42 KByte)	(172 KByte)
blatt04	(33 KByte)	(145 KByte)
blatt05	(40 KByte)	(169 KByte)
blatt06	(39 KByte)	(159 KByte)
blatt07	(40 KByte)	(163 KByte)
blatt07_toplemma	(43 KByte)	(169 KByte)
blatt08	(42 KByte)	(166 KByte)
blatt09	(56 KByte)	(258 KByte)
blatt10	(36 KByte)	(152 KByte)
blatt11	(33 KByte)	(143 KByte)
blatt12	(32 KByte)	(138 KByte)
blatt13	(75 KByte)	(255 KByte)