Logic Programming WS 2010/11

Logic Programming

(V3 resp. 4 + Ü2, WS 2010/11)

Course	Times/Room	Instructor
V3 resp. 4	Tue 11:45 - 13:15 AH 3	Prof. Dr. Jürgen Giesl
	Fri 11:45 - 13:15 AH 1
Ü2	Wed 16:00 - 17:30 AH 3	Prof. Dr. Jürgen Giesl, Carsten Fuhs, Carsten Otto, Thomas Ströder

This is a 3-hour lecture for Bachelor Informatik, Master Informatik, and Master Mathematik. It is a 4-hour lecture for Diplom Informatik and Diplom Mathematik. For Master SSE, the lecture is usually a 3-hour lecture (6 ECTS credits), but these students can also attend the 4-hour lecture (8 ECTS credits).

If you have any questions, please contact the mailing list lp10@i2.informatik.rwth-aachen.de, which is read by the three assistants. More contact information can be found on the homepage of LuFG I2.

News

Bachelor Informatik students who successfully participated in the V3M version of the exam (i.e., they took the exam for their Master) can now fetch a document proving their performance (Schein) in our secretary's office.
The results of the second exam have been updated to take the re-evaluation after the exam inspection into account.
As announced during the second exam, the exam inspection takes place on Tuesday, March 22nd, 2011, from 2:00 pm till 3:00 pm in room 4201b (our seminar room).
Please bring a valid document to prove your identity (i.e., passport or Personalausweis) and your student ID to the inspection!
The results of the exam written on March 18th, 2011, are available.
In the following lists corresponding to the three versions of the exam you can find your public ID if you are registered for and admitted to the particular version of the second exam. Your public ID is shown to you inside our exercise system. If you think that your public ID is missing in one of these lists or if your public ID is in the wrong list, please contact us immediately.

V3B
V3M
V4
The second exam is going to take place on Friday, March 18, 2011, at 2:30 pm in lecture hall AH 5. Please be at the lecture hall on time!
Also for the second exam, there are no aids or auxiliary materials allowed. Just bring a document-quality pen (not red or green), a valid document to prove your identity (i.e., passport or Personalausweis) and your student ID. Your resulting grade for the exam will also be your final grade for the whole course unless you already participated successfully in the first exam.
Bachelor Informatik students who already want to participate in the Master exam of the course should not register via Campus, but send a mail to lp10@i2.informatik.rwth-aachen.de instead.
All other students should make sure that their registration status with the (V)ZPA in Campus is as desired. If this is not the case (and if you cannot fix this yourself in Campus), please contact the ZPA directly.
SSE students who want to participate in the V4 version of the exam (8 credits) instead of the V3M version of the exam (6 credits) should both make sure that they are registered with the (V)ZPA and additionally send a mail to lp10@i2.informatik.rwth-aachen.de.
The deadline for the registration mails to lp10@i2.informatik.rwth-aachen.de (where needed) is Tuesday, March 15, 2011 at 4:00 PM.
The exam sheets from February 23rd and their solutions have been added to the old exams on this website.
The below results of the exam from February 23rd, 2011 have been updated to take the results of the exam inspection into account.
As announced during the exam, the exam inspection takes place on March 3rd, 2011, from 2:00 pm till 4:00 pm in room 5054.
Please bring a valid document to prove your identity (i.e., passport or Personalausweis) and your student ID to the inspection!
The results of the exam from February 23rd, 2011, are available.
The following list contains the public IDs of those students who have obtained the Übungsschein. You can fetch the Übungsschein at our secretary's office.

Schein
In the following lists corresponding to the three versions of the exam you can find your public ID if you are registered for and admitted to the particular version of the exam. Your public ID is shown to you inside our exercise system. If you think that your public ID is missing in one of these lists or if your public ID is in the wrong list, please contact us immediately.

V3B
V3M
V4
The exam will take place on Wednesday, February 23rd 2011, at 9:30 am. Students participating in the V3M version of the exam will have the exam in lecture hall AH 4. Students participating in the V3B or V4 version of the exam will have the exam in lecture hall AH 5. All versions of the exam will last 120 minutes. Please be at the right lecture hall on time!
We have posted two old exams on logic programming lectures on this website which you can use to practice for our exam.
The absolute number of exercise points needed to qualify for the final exam/to obtain the "Übungsschein" (i.e., 50% of the total points obtainable in the exercises for the corresponding version of the lecture) is now known:
- V3B: 78.5 points
- V3M: 78.5 points
- V4: 103 points
Note that the percentages given in the exercise management system refer to the points that could be obtained in the exercises for the V4 version of the lecture. Thus, if you are not attending the V4 version, these percentages do not apply to you. Instead you should check whether your score (after Sheet 12) is at least as high as given above.
After correction of Sheet 12, we are going to put a list on this page which shows which students have qualified for the exam/who have obtained the "Übungsschein".
For the written exam on February 23rd 2011, there are no aids or auxiliary materials allowed. Just bring a document-quality pen (not red or green), a valid document to prove your identity (i.e., passport or Personalausweis) and your student ID. Your resulting grade for the exam will also be your final grade for the whole course. The exact room allocation will be announced on this webpage a few days before the exam takes place.

Course Notes

The course notes are available here (in German): Course Notes (Version of October 11, 2010)

In addition to a short introduction to the programming language Prolog, the lecture deals with the foundations of logic programming, with programming techniques in these languages, with the implementation of logic programming languages, and with their application in several areas. More precisely, these are the topics of the lecture:

Prerequisites from predicate logic
- Unification
- Resolution
- Horn clauses and SLD-resolution
Logic programs
- Operational and denotational semantics
- Evaluation strategies
The programming language Prolog
- Syntax and semantics
- Negation as failure
- Non-logical components of Prolog
- Programming techniques
- Applications and extensions of logic programming

Versions of the Lecture

Not all material of the lecture is needed for all students. More precisely, there are three versions of the lecture:

V4 This version contains the full lecture (with 4 hours per week). It is relevant for students in Diplom Informatik and Diplom Mathematik. Moreover, students in Master SSE may also attend this version instead of V3M.
V3B This version only contains a subset of the full lecture (with 3 hours per week). It is relevant for students in Bachelor Informatik and Master Mathematik. Compared to V4, the following material is missing in V3B:
- Section 4.1.3 (fixpoint semantics of logic programming)
- Section 4.2 (universality of logic programming)
- Section 4.3 up to Example 4.3.7 (exchangement lemma, resolving the indeterminisim of sort 2)
- Section 6 (constraint logic programming)
V3M This version only contains a subset of the full lecture (with 3 hours per week). It is relevant for students in Master Informatik and Master SSE. This is also the version that is relevant for those students in Bachelor Informatik who already want to attend the master-version of this course (they can transfer the credits obtained here as soon as they enter the master program). Compared to V4, the following material is missing in V3M:
- Section 5.5 (input and output)
- Section 5.6 (meta programming)
- Section 5.7 (difference lists and definite clause grammars)
- Section 6 (constraint logic programming)

References

K. R. Apt: From logic programming to Prolog, Prentice Hall, 1997.
I. Bratko: Prolog Programming for Artificial Intelligence, Addison-Wesley, 2001.
W. F. Clocksin, C. S. Mellish: Programming in Prolog, Springer, 2003.
T. Frühwirth, S. Abdennadher: Essentials of Constraint Programming, Springer, 2003.
M. Hanus: Problemlösen mit Prolog, Teubner, 1987.
J. W. Lloyd: Foundations of Logic Programming, Springer, 1987.
K. Marriott, P. J. Stuckey: Programming with Constraints, MIT Press, 1998.
P. H. Schmitt: Theorie der logischen Programmierung, Springer, 1992.
U. Schöning: Logik für Informatiker, Spektrum Akademischer Verlag, 2000.
L. Sterling, E. Shapiro: The art of Prolog, MIT Press, 2000.

Area

Theoretical Computer Science, Area of Specialization

Software

To write Prolog-programs, we recommend the SWI Prolog System.

An alternative to SWI-Prolog is GNU Prolog:

Old exams

Here you find two exams from the 2006 and 2008 lectures on logic programming (in German). However, as the computer science curriculum has been changed since these exams took place, the conditions for these exams were different from the ones for the exam we will have in this lecture. First, the old exams were not designed to determine the final grade for the logic programming course, but only for the acquisition of the Übungsschein. Second, they only took 90 minutes, while our exam will take 120 minutes. Third, we will have three different exams (according to the three versions of the lecture) instead of just one. Keep these differences in mind when practicing with the old exams. Furthermore, we strongly recommend that you solve the old exams without looking into the solutions first and that you also respect the time limit of 90 minutes.

Furthermore, you can now find the first exam sheets from February 23rd and their solutions according to the three versions of the lecture.

The corresponding material of the second exam from March 18th is here as well:

Exercises

For students of Diplom Informatik: To get a certificate for this course (Übungsschein) you must reach at least 50% of the points on the exercise sheets. In general, we advise all Diploma students to work towards the certificate. Working on the exercises is a good preparation for the final oral exam.
For all other students 50% of the points on the exercise sheets are needed in order to take part in the final written exam. The written exam will be on February 23, 2011. If you fail this exam, there will be a second written exam on March 18, 2011.

In order to take part in the exercises, please sign up here.

The exercise sheets should be solved in groups of two. The solutions can be handed in at the beginning of the exercise class on Wednesdays.

Remark regarding Sheet 12:

The predicate transpose/2 from the clpfd constraint theory may not necessarily be available in older Prolog implementations. In that case, another implementation of transpose/2 is used by default which does not have the desired behavior. Therefore, we provide you with the predicate transpose_matrix/2 which exhibits this desired behavior. Of course, you are not obliged to use any of these predicates in your solution.

Transparencies

Here are the transparencies used in the lecture.

Transparency 1 (October 12, 2010)
Transparency 2 (October 15, 2010)
Transparency 3 (October 20, 2010)
Transparency 4 (November 5, 2010)
Transparency 5 (November 5, 2010)
Transparency 6 (November 5, 2010)
Transparency 7 (November 12, 2010)
Transparency 8 (November 12, 2010)
Transparency 9 (November 16, 2010)
Transparency 10 (November 23, 2010)
Transparency 11 (November 23, 2010)
Transparency 12 (November 26, 2010)
Transparency 13 (December 8, 2010)
Transparency 14 (December 10, 2010)
Transparency 15 (January 11, 2011)
Transparency 16 (January 18, 2011)
Transparency 17 (January 25, 2011)
Transparency 18 (January 25, 2011)

Disclaimer

Research Group Computer Science 2

Dept. of Computer Science