Main Lecture: Theory of Computer Science

Course Number 10948-01
Lecturers Gabriele Röger
Tutors Guillem Francès Medina
Manuel Heusner
Time and Location Mon 14:15 - 16:00; Seminarraum 05.002, Spiegelgasse 5
Wed 16:15 - 18:00; Seminarraum 05.002, Spiegelgasse 5
Start 26-02-2018
Exercises Mon 16:15 - 18:00; Seminarraum 00.003, Spiegelgasse 1
Mon 16:15 - 18:00; Computer-Labor U1.001, Spiegelgasse 1
Group assignment (Requires login)
Prerequisites None.
Objectives The participants should be able to formulate statements and situations in logical systems and to formally derive logical consequences. They should develop a precise understanding of initially intuitive concepts such as computability and complexity. This will enable them to determine the fundamental hardness of computer science problems and to infer consequences for practical approaches.
Contents The course gives an introduction to the theory of computer science.

Topics are: logic, automata theory and formal languages, computability and complexity theory
Literature German textbooks:
U. Schöning: "Theoretische Informatik - kurz gefasst", 5. Auflage, Spektrum Verlag, 2008.
U. Schöning: "Logik für Informatiker", 5. Auflage, Spektrum Verlag, 2000.

English textbooks:
M. Sipser: "Introduction to the Theory of Computation", 3. edition, Cengage Learning, 2012.
U. Schöning: "Logic for Computer Scientists", 1. edition, Birkhäuser Verlag, 2008.
Assessment Examen

Please note: Written exam, 2 hours.
The written exam will take place on Friday, 15 June, 2-4 p.m., at Spiegelgasse 1, room 00.003.
Further information regarding exams of main lectures (Hauptvorlesungen): https://philnat.unibas.ch/examen

Credit Points 8
Grades 1-6 0,5
Registration Services (Requires login)