	Home
	Events
	People
	Research
	Publications
	Teaching
	Job and Students
	Opportunities
	Tools and Data
	Miscellanous
	Contact

Applied Computer Science II

Prof. Dr. Luc De Raedt

Co-organizer : Dipl.-Inf. Kristian Kersting

Wednesday 9-11 o'clock, Friday 9-10 o'clock, Room: SR 00-010/14, Bulding 101

Final Exam: 21.02.03 (Friday), 10-12 o'clock, Room: HS 101 00-026

Repetition Exam: 25.04.03 (Friday), 10-12 o'clock, Room: 101 01-009/013

* NEW: The exam has been marked. You can obtain your marks by personally contacting the secretariat of the Machine Learning Lab in Building 79 or by phone +49 761 203 8006.

Exercices: Friday 10-11 o'clock, Room: SR 00-010/014, Building 101

Credit points (Kreditpunkte): 6

Exercise sheets

Slides

Fun

This course will address theoretical aspects of computer science. It comprises the fundamental mathematical properties of computer hard and software. We will see what can be computed, and what not, and if it can be computed, how hard (efficient) it is to compute it. More specifically, we will study automata, languages, grammars, turing machines, decidability, complexity theory and logic.

It is likely (but not 100% certain) that we will use the following books :

Michael Sipser. "Introduction to the theory of computation". PWS Publishing Co., Boston, MA, 1996.

J. D. Ullman, J. E. Hopcroft, R. Motwani. "Introduction to Automata Theory, Languages, and Computation". Addison Wesley, second edition, 2001.

The course is entirely in English!

Consultation Hours

Time: every Tuesday, 11:00 to 13:00
Venue: Building 079, Room 1018 or 1019 (downstairs, at the end of the corridor on the right)
Extra session on Monday, 9th December, 2002, at 14:00 p.m.

Exercise sheets

Exercise 1 (Deadline: 30.10.2002) [gzipped Postscript (43kb)] [PDF (55kb)]
Exercise 2 (Deadline: 15.11.2002) [gzipped Postscript (43kb)] [PDF (54kb)]
Exercise 3 (Deadline: 22.11.2002) [gzipped Postscript (44kb)] [PDF (61kb)]
Exercise 4 (Deadline: 29.11.2002) [gzipped Postscript (57kb)] [PDF (93kb)]
Exercise 5 (Deadline: 06.12.2002) [gzipped Postscript (48kb)] [PDF (65kb)]
Exercise 6 (Deadline: 20.12.2002) [gzipped Postscript (48kb)] [PDF (65kb)]
No exercises during Christmas and New Year holidays! :-D
Exercise 7 (Deadline: 17.01.2003) [gzipped Postscript (34kb)] [PDF (48kb)]
Exercise 8 (Deadline: 24.01.2003) [gzipped Postscript (48kb)] [PDF (77kb)]

Example Grammar for 8.2 (a).

Exercise 9 (Deadline: 31.01.2003) [gzipped Postscript (41kb)] [PDF (50kb)]
Exercise 10 (Deadline: 07.02.2003) [gzipped Postscript (51kb)] [PDF (60kb)]

That's all for the exercises. But please note the date and time for the exam! (It has been revised.)

Slides

Logic [gzipped Postscript (54kb)]
Predicate Calculus --- First Order Logic [gzipped Postscript (547kb)]
Resolution in FOL [MS Powerpoint (1.28Mb)] [gzipped Postscript (1.63Mb)] [environmental gzipped Postscript (1.63Mb)]
Chapter 0: Introduction [MS Powerpoint (212kb)] [gzipped Postscript (312kb)] [environmental gzipped Postscript (315kb)]
Chapter 1: Regular Languages [MS Powerpoint (1.86Mb)] [gzipped Postscript (4.75Mb)] [environmental gzipped Postscript (4.77Mb)]
Chapter 2: Context-free Languages [MS Powerpoint (1.06Mb)] [gzipped Postscript (2.94Mb)]
Chapter 3: Turing Machines [MS Powerpoint (1.49Mb)][gzipped Postscript (4.37Mb)] [environmental gzipped Postscript (4.37Mb)]
Chapter S1: Programs and Turing Machines [MS Powerpoint (260kb)] [gzipped Postscript (24.5kb)] [environmental gzipped Postscript (25.8kb)]
Chapter 4: Decidability [MS Powerpoint (1.03Mb)] [gzipped Postscript (3.36Mb)] [environmental gzipped Postscript (3.37Mb)]
Chapter 5: Reducability [MS Powerpoint (1.26Mb)] [gzipped Postscript (2.68Mb)] [environmental gzipped Postscript (2.69Mb)]
Chapter S2: Grammars [MS Powerpoint (304kb)] [gzipped Postscript (626kb)] [environmental gzipped Postscript (629kb)]
Chapter 7: Time Complexity [MS Powerpoint (1.69Mb)] [gzipped Postscript (3.49Mb)] [environmental gzipped Postscript (3.50Mb)]
Chapter 8: Space Complexity [MS Powerpoint (179kb)] [gzipped Postscript (292kb)] [environmental gzipped Postscript (293b)]

Fun

You may find this poem helpful for memorizing the pumping lemma for regular languages.

Last modified: $Date: 2003-02-07 09:52:18+01 $