Aims

The course intends to offer insight in a number of formal aspects of computer science, in particular in complexity theory (which has been introduced informally in the first programming course), graph theory (which is important in many applications) and fixed point theory (important for the understanding of inductive definitions).The student must be able to reproduce proofs and to use theorems when solving new problems. The student must have a well founded critical attitude towards definitions and be able to understand and discover possibilities for the application of the theory.

Previous knowledge

The course "Hoger Wiskunde" is a preresiquite as well as familiarity with logic.

Content

Complexity theory (8h)
• notion of a language and to decide a languag
• regular languages and FSA
• Turing machines (det and nondet)
• computing with a TM
• the hypotheses of Church
• definition of complexity and big-O notation
• deriving a recurrence equation and solving it
• P, NP, NPC: definitions and relations 
 
Graph theory (13h)
• definitions: grahp, path, ...
• representing graphs
• graph isomorphism
• weighted graphs
• plane graphs
• graph coloring
• trees: definitions and properties
• spanning trees
• minmal spanning trees
• tree traversal
• game trees
• transport networks
• maximal flow/minmal cut
• matching networks and Hall's theorem
• Petri-nets 
 
Fixed point theory (5h)
• order
• monotone and continuous functions on (complete) lattices
• theorems of Tarski and Kleene

Course material

Syllabus

Order of Enrolment

This course unit is a prerequisite for taking the following course units:
H01Q3A : Problem solving and engineering design, computer science and engineering
H01Q3C : Problem Solving and Engineering Design: Computer Science

Is also included in other courses

• Bridging Programme: Master of Applied Informatics 59 ects.
• Bachelor of Biochemistry and Biotechnology (Minor Subject: Informatics) 180 ects.
• Bachelor of Informatics 180 ects.
• Bachelor of Mathematics (Minor Subject: Broadening) 180 ects.
• Bachelor of Mathematics (Minor Subject: Informatics) 180 ects.
• Bachelor of Physics (Minor Subject: Informatics) 180 ects.
• Bachelor of Informatics (Abridged Programme) 120 ects.