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.
The course "Hoger Wiskunde" is a preresiquite as well as familiarity with logic.
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, ...
trees: definitions and properties
minmal spanning trees
maximal flow/minmal cut
matching networks and Hall's theorem
Fixed point theory (5h)
monotone and continuous functions on (complete) lattices
theorems of Tarski and Kleene
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.
Complexity theory (8 hours)
the concept language and the decision of a language
regular languages and their decision by FSA
Turing machines - deterministic and non-deterministic
calculating with TM
formulation of Church's hypothesis
complexity definition of an algorythm and the big O notation
design of a recurrency comparison for the time complexity of an algorythm
techniques for solving recurrency comparisons
P, NP and NP-C: definitions and links
Graphs theory (13 hours)
definitions: graph, path
trees: definitions and qualities
minimal stretching trees
passing through trees
matching networks and Hal's theorem
Fixed points theory (5 hours)
monotonous and continuous afbeeldingen
closed books for theory.
open books for exercises.