Formale Systeme, Winter semester 2011/2012

Department of Computer Sciences, University of Salzburg

Lecturer (VO):      Dr. A. Sokolova, ana.sokolova"at"cs.uni-salzburg.at, office 2.17

Instructions (PS):      Dr. A. Sokolova, ana.sokolova"at"cs.uni-salzburg.at, office 2.17 (Group 1) and A. Haas, dra.haas"at"gmail.com, office 2.17 (Group 2)

Schedule:      Lectures (VO) Wednesdays 1pm-2pm, room T01 and Thursdays 1pm-3pm, room T01
Instructions (PS) Thursdays 10am-12am, room T02 (Group 1) and Thursdays 3pm-5pm, room T01 (Group 2)
Tutorium Wednesdays 12am-1pm, room T02 (with Guenther Eder and Ann-Christin Knoll)

Office hours:      Tuesdays 2pm-3pm or on other days upon email appointment.

First meeting:    Wednesday, 5.10.2011, 1pm, room T01

First PS meeting:    Thursday, 13.10.2011

Language:      German (slides, book, and web info in English)

Course description: This is a first-semester obligatory course on basics of theoretical computer science: logic and sets. More information on the course content will be added here before the course starts.

Literature:
Thanks: Many thanks to Bas Luttik from TU/e for helpful discussions and for letting me use some of his course material.

What is theory good for? A typical question asked by (practically oriented) students. Luca Aceto has compiled a nice webpage answering this question. Click on the corresponding link on the left to get to the needed subpage.

Prerequisites: None, the course material is self-contained, as is the textbook.

Exam: At the bottom of this page there is some detailed information regarding the exam rules and grading (in German).
Exam dates: The first partial exam (Test 1) will be held on Friday, 2.12.2011, in T01, starting at 12 noon. The second partial exam (Test 2) will be held on Monday, 13.2.2012, in T01, starting at 1pm. The first regular (full) exam will be held on Tuesday, 28.2.2012, in T01, starting at 1pm. The second full exam will be held on Wednesday, 2.5.2012, in T01, starting at 1:30pm. The third full exam will be held on Monday, 9.7.2012, in T02, starting at 1:30pm.

Slides: Occasionaly (see e.g. Week1 below) slides will be used during the lecture. Whenever slides are used, they will be made available on this webpage (as in e.g. Week1 below). The slides are by no means complete and only serve as occasional help for better presentation. Much more material is covered during the class (on the blackboard) than is visible on the slides.

Announcements: On Wednesday 7.12.2011, we will have an additional class: instead of the usual 1pm-2pm in T01, we will do 12noon-2pm. This is for the lost class on the 13th of October (due to room problems).

Schedule:
Exercises for the instructions:
Solutions of some exercises from the instructions:
Pruefung: VORLESUNG: Die Vorlesungspruefung besteht aus einem schriftlichen und einem optionalen muendlichen Teil. Es gibt zwei Moeglichkeiten, den schriftlichen Pruefungsteil zu absolvieren:

(1) Durch die Teilnahme an zwei Zwischentests im Laufe des Wintersemesters. Der Stoff fuer diese Tests beschraenkt sich auf die bis dahin vorgetragenen Inhalte der Vorlesung.

(2) Durch das Ablegen einer Klausur. Fuer die Klausur werden drei Termine im Sommersemester angeboten.

Die genauen Termine werden rechtzeitig in der Vorlesung und auf dieser Seite bekanntgegeben. Der Stoff der Pruefungen sind Uebungsbeispiele, wie sie im Proseminar gerechnet werden, und die Theorie, die in der Vorlesung vorgetragen wurde. Die Anmeldung zur schriftlichen Pruefung erfolgt ueber Plus-Online. Zum Bestehen der schriftlichen Pruefung sind 55% der Gesamtpunkteanzahl notwendig. Wenn man mit dem Ergebnis der schriftlichen Pruefung zufrieden ist, ist keine muendliche Pruefung notwendig. Ohne einer zusaetzlichen muendlichen Pruefung ist die beste erreichbare Note ein "Gut(2)".

Hat man den schriftlichen Pruefungsteil positiv absolviert, und moechte seine Note veraendern(!), insbesondere also wenn man ein "Sehr Gut (1)" erreichen moechte, so kann man eine muendliche Pruefung absolvieren.

Stoff der muendlichen Pruefung ist der Stoff der Vorlesung. Die Anmeldung zur muendlichen Pruefung ist bis spaetestens eine Woche nach der Bekanntgabe der schriftlichen Note per E-Mail moeglich. Termine nach Vereinbarung.

PROSEMINAR: Der Proseminarmodus ist "Kreuzluebungen", d.h.:

(1) Sie bekommen woechentlich fuer das jeweils naechste Proseminar Aufgaben, und loesen diese zu Hause.

(2) Vor dem Proseminar kreuzln Sie auf einer Liste jene Beispiele an, die Sie loesen konnten UND gemeinsam mit dem notwendigen theoretischen Umfeld soweit verstanden haben, dass Sie sie vernuenftig erklaeren koennen.

(3) In dem Proseminar ruft der Proseminarleiter zu den Aufgaben jemanden auf, der die jeweilige Aufgabe dann an der Tafel praesentiert. Im Idealfall machen wir alle Beispiele durch, meistens werden wir ungefaehr 3/4 der gestellten Aufgaben schaffen.

Die Beurteilung richtet sich nach zwei Komponenten, naemlich der Anzahl der angekreuzten Beispiele und der Qualitaet ihrer Praesentationen an der Tafel.

Notwendig fuer eine positive Note sind zwei positive Tafelleistungen und 60 Prozent angekreuzte Beispiele.

NACHBRINGEN VERSAEUMTER PROSEMINARE:

Sie koennen ohne weitere Begruendung ein Proseminar versaeumen und diese dann nachholen. Dazu vereinbaren Sie mit Ihrem Proseminarleiter einen Termin, wo Sie dann kommen und ein paar Aufgaben des versaeumten Proseminars praesentieren. Nachgebrachte Proseminare erhoehen die Anzahl der Kreuzl, zaehlen aber nicht als Tafelleistung.

Sollten Sie aus triftigen Gruenden (z.B. Spitalsaufenthalt) mehrere Proseminare versaeumen und diese nachbringen wollen, dann besprechen Sie das im Einzelfall mit dem Proseminarleiter.