Last modified: 04 Jul 2017 10:08
This course provides a basic-level introduction to some areas of Discrete Mathematics that are of particular relevance to Computing. The course starts with a simple introduction to formal languages (starting from Regular Expressions and Finite-State Automata); it continues with an introduction to Predicate Logic (assuming basic familiarity with Propositional Logic); it concludes with an introduction to probability, focussing on Bayesian reasoning.
|Session||First Sub Session||Credit Points||15 credits (7.5 ECTS credits)|
Three main topics will be covered: 1. Introduction to formal languages: finite-state machines, regular expressions, Kleene's theorem, pushdown automata, context-free languages. 2. Introductory statistics for computing: Probability, Combinations, Permutations, Bayes' rule; the noisy channel model; principles of descriptive and inferential statistics; principles of hypothesis testing (null hypothesis, type-1 and type-2 errors, etc). 3. Topics in logic and set theory, including and introduction to predicate logic; the cardinality of Infinite sets; Cantor's diagonal argument; simple abstract applications to computability. Throughout the course, there will be an emphasis on proof methods, including methods such as proof by mathematical induction, and proof by contradiction.
Even though this course does not replace any now-existing course, it does teach elements of earlier courses on Formal Languages and Discrete Methods. It will allow other existing courses, such as the present CS3518 (Languages and Computatibility), to be substantially upgraded. The course will build on the new course in Principles of Programming (CS1022).
This is the total time spent in lectures, tutorials and other class teaching.