Theoretical Computer Science (Bridging Course) - WS 2014/15

Aims of the lecture

The participants should get a foundational knowledge of the theoretical aspects of computer science.

Contents of the lecture

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 how efficiently, as well as what cannot. More specifically, the following topics will be included:

• Automata
• Formal languages
• Formal grammars
• Turing machines
• Decidability
• Complexity theory
• Logic

People

• Lecturer: Gian Diego Tipaldi
• Tutor: Federico Boniardi

Rooms and Times

There will be no classical face to face lectures. Instead, the participants are supposed to follow the video recordings themselves. We provide exercise sheets and tutorials every week, to make sure the material is understood properly.

• Lecture:
  • Mon 20 April 2015, 10-12 in building 52, SR 02-017: Introduction
• Tutorials:
  • Mon, 10-12 in building 52, SR 02-017: By appointment
• Final Exam:
  • Mon 31st August 2015, 10-12 in building 101, SR 01-016

Language

Lectures are held in English, course material and exercise sheets are in English. Students may ask questions and submit exercise sheets in English.

Credit Points

6 ECTS points

Course Book

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

Additional Information

• There is a QnA forum from the last semester for questions.
• Teaching is done in English.

Material

Topic	Slides	Videos	Homework Assignment	Solutions
Introduction	00.pdf	n/a	---	---
Mathematical Preliminiaries	02.pdf	MP4	Sheet0	Sheet0
DFA, NFA, Regular Languages	03.pdf	MP4	Sheet1	Sheet1
Regular Languages and closure wrt elementary operations			---	---
Regular expressions		MP4	Sheet2	Sheet2
Non-regular languages		MP4	---	---
Context Free Grammars	04.pdf	MP4	Sheet3	Sheet3
Context Free Grammars		MP4	---	---
Pushdown Automata		MP4	Sheet4	Sheet4
Pumping Lemma for Context Free Grammars		MP4	Sheet5	Sheet5
Turing Machines	05.pdf	MP4	---	---
Turing Machines		MP4	Sheet6	Sheet6
Decidability and decidable languages.	06.pdf	MP4	---	---
Decidability, mathematical backgrounds on cardinality, Cantor's diagonal argument		MP4	Sheet7	Sheet7
Decidability and the halting problems.		MP4	---	---
Complexity	07.pdf	MP4	Sheet8	Sheet8
Complexity		MP4	---	---
Complexity		MP4	Sheet9	Sheet9
Complexity		MP4	Sheet10	Sheet10
Propositional Logic and basic definitions, CNF/DNF, logical entailment.	08.pdf	MP4	---	---
Propositional Logic. Deduction/Contraposition/Contradiction Theorems and Derivations.		MP4	Sheet11	Sheet11
Propositional Logic. Derivations, Soundness and Completeness of calculi.		MP4	---	---
Propositional Logic. Refutation-completeness and Resolution.		MP4	Sheet12	Sheet12
First Order Logic. Derivations.	09.pdf	MP4	---	---
First Order Logic. Satisfaction, closed formulae and brief overview on Normal Forms.		MP4	---	---
Review of some old exam questions. QnA.	Revision Sheet	n/a	---	Solutions