direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Theoretische Grundlagen der Informatik 1 (TheGI1)

Inhalt

  • Pflichtveranstaltung im Grundstudium Informatik (2 SWS Vorlesung, 2 SWS Tutorium)
  • Lehrveranstaltungsnummer: 0401 L 145.
  • Prüfungsrelevante Studienleistungen: Schriftliche Ausarbeitungen, Abschlussprüfung.

Orte und Zeiten

  • Vorlesung: Dienstags 8.30 - 10.00 Uhr (Beginn 25.10.), Raum HE 101.
  • Tutorien: Es finden jede Woche Tutorien statt (Montag bis Freitag). Ihr müsst ein Tutorium besuchen. Anmelden könnt Ihr Euch unter www.moses.tu-berlin.de/Konto. Eine Übersicht über Zeiten und Räume gibt es hier (PDF, 2,8 KB).
  • Eine Anmeldung zu den Tutorien ist auch für Nachzügler zwingend erforderlich!
    Special note: One class (Johannes Borgström) on Wednesday 12-14 will be held in English. This class addresses both foreigners who feel more comfortable with English and Germans who would like to improve their English.
  • Fachmentorium - neue Zeit: Freitags, 12-14 Uhr, Raum MA 545. Das Fachmentorium richtet sich insbesondere, aber nicht ausschließlich, an ausländische Studierende.
  • Mündliche Prüfungsgespräche: 13.2. und 14.2.2006. Die Prüfungsgespräche finden in den Räumen FR 6507, FR 6508 und FR 6022 statt. Ihr müsst bereits eine halbe Stunde vor Prüfungsbeginn mit Eurer jeweiligen Gruppe an der Vorbereitung teilnehmen, die im FR 6515 stattfindet. Die Prüfungstermine gab es hier.
  • Der Nachprüfungstermin findet am 19. Juli 2006 statt. Anmeldungen zur Terminvergabe bitte im Sekretariat FR 6021.

Veranstalter

Inhaltsübersicht

    Formale Grammatiken und Automaten, Erzeugen und Akzeptieren formaler Sprachen, Nichtdeterminismus, Turingmaschinen, Halteproblem, Komplexität, P-NP-Problem.

Tutorien

Im Tutorium arbeitet Ihr Euch in einer Gruppe von ca. 20 Personen in das jeweilige Thema ein, löst Aufgaben, diskutiert Probleme; genauer macht Ihr das mit den Tutoren aus. Es gibt ein zusätzliches Fachmentorium, vor allem für ausländische Studierende, die Probleme mit der Sprache und der ungewohnten Arbeitsweise haben. Dozenten, WMs und Tutoren bieten alle Sprechstunden an, in denen ihr Probleme auch nochmal einzeln diskutieren könnt. Dort oder nach der Vorlesung könnt Ihr alles fragen, was Ihr Euch in der Vorlesung nicht zu fragen traut.

Arbeitsgruppen

Die Basis Eurer Arbeit bildet eine Arbeitsgruppe von zwei oder drei Studenten, die Ihr Euch in der Einführungswoche oder im 1. Tutorium sucht. Ihr bearbeitet die Projektaufgaben als Arbeitsgruppe. Wie gut und gleichermaßen beteiligt Ihr in der Gruppe zusammenarbeitet, kann entscheidend für Euer Studium sein - besonders, wenn sie für mehrere Lehrveranstaltungen besteht. Redet deswegen über Probleme in der Gruppe (Terminschwierigkeiten Krankheit, Mitläufer, Aussteiger) mit Euren Tutoren oder den Assistenten.

Skript

Das Skript ist zum Selbststudium gedacht, es enthält viele Beispiele, Aufgaben und Beweise, an denen Ihr im Tutorium und zu Hause arbeiten könnt.

Folien
Datum
Thema
Link
2005-10-19
Einführung
(Handzettel (PDF, 364,6 KB))
2005-10-25
Reguläre Sprachen und Grammatiken
(Handzettel (PDF, 277,9 KB))
2005-11-01
Endliche deterministische Automaten
(Handzettel (PDF, 481,5 KB))
2005-11-08
Nichtdeterministische Automaten
(Handzettel (PDF, 110,6 KB))
2005-11-15
Endliche Automaten und Reguläre Sprachen
(Handzettel (PDF, 104,3 KB))
2005-11-22
Kontextfreie Grammatiken und Sprachen
(kein Handzettel, da kein Projektor benutzt)
2005-11-29
Deterministische Turing-Maschinen
(Handzettel (PDF, 163,5 KB))
2005-12-06
Nichtdeterministische Turing-Maschinen
(Handzettel (PDF, 123,1 KB))
2005-12-13
Allgemeine Grammatiken und akzeptierbare Sprachen
(Handzettel (PDF, 85,6 KB))
2006-01-03
Berechenbarkeit, Diagonalisierung, Selbstanwendung
(Handzettel (PDF, 142,9 KB))
2006-01-10
Akzeptierbare und entscheidbare Sprachen
(Handzettel (PDF, 941,1 KB))
2006-01-17
Unentscheidbarkeit
(Handzettel (PDF, 92,8 KB))
2006-01-24
Rechenaufwand von Turingmaschinen
(Handzettel (PDF, 93,3 KB))
2006-01-31
Komplexitätsklassen
(Handzettel (PDF, 110,5 KB))
2006-02-07
Rückblick und Ausblick
(Handzettel (PDF, 170,9 KB))
2006-02-14
(entfällt wegen Prüfungsgesprächen)

Projektaufgaben

Beim Lernen verändert man sich, verändern kann man nur durch Tun; also kann man nur durch Tun lernen. Deshalb ist das selbstständige Lösen der Projektaufgaben, von denen es sieben Stück gibt, für Euren Lernerfolg am wichtigsten.
Es wird sieben Aufgabenblätter geben, die hier (als pdf-Datei) veröffentlicht werden.

Prüfungsbedingungen

Ihr meldet Euch beim Prüfungsamt im Hauptgebäude einmal für alle Prüfungen und prüfungsrelevanten Studienleistungen (PS) des Grundstudiums an. Dabei erhaltet Ihr einen Laufzettel, mit dem Ihr Euch in den einzelnen Lehrveranstaltungen anmeldet und in den die Ergebnisse eingetragen werden. In TheGI~1 gibt es keine Klausur; die PS werden in zwei Teilen erbracht, den Projektaufgaben während des Semesters und dem Prüfungsgespräch. Ihr meldet Euch in Euren Tutorien an, vor der Weihnachtspause. Dazu bringt Ihr den Laufzettel mit und unterschreibt in der Tutoriumsliste. Bei Erkrankung gebt Ihr uns Bescheid und reicht innerhalb von fünf Tagen nach dem Prüfungstag ein ärztliches Attest nach; das Prüfungsgespräch kann dann einzeln nachgeholt werden, die Projektaufgaben in der Regel nicht. Wer nur einen Teil der PS erbringt, braucht nur den fehlenden im nächsten Winter zu wiederholen.

Kooperatives Arbeiten

Ihr müßt die Mängel einer Massenuniversität durch selbständigere Arbeit ausgleichen. In Vorlesung und Tutorien wird Euch nicht der Stoff eingetrichtert, sondern Eure eigene Arbeit unterstützt. Ihr müßt also das Skript rechtzeitig lesen und dann mit Fragen kommen. Ihr müßt die Übungsaufgaben wechselseitig korrigieren. Ihr müßt Euch gegenseitig unterstützen, statt Euch auszustechen. Dann kann es ein schönes Semester werden.

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe