Entry requirements

Algebra and geometry. Program design.

Aims

The course provides basic knowledge of the theory

of computation and formal languages and of the

theory of groups and fields, and it gives an

introduction to graph theory and coding theory.

Content

The course consists of two parts: Automata theory

and formal languages and Algebraic structures.

Automata theory and formal languages, 4.5 ECTS

credits:

Theory of automata: Deterministic and

non-deterministic finite automata, regular

languages, Kleene's theorem, pushdown automata,

context free languages, pumping theorems,

Chomsky's hierarchy of languages.

Turing machines: The universal machine and the

halting problem. A survey of complexity theory

(complexity classes P and NP). Recursive

functions. Rice's theorem and other

undecidability results. Church-Turing's thesis.

Logic: Propositional and predicate logic and

their semantics.

Algebraic structures, 6 ECTS credits:

The integers (especially divisibility and modulo

arithmetic), permutations, groups (subgroups,

cosets, group homomorphisms), rings (in

particular polynomial rings), partial orders,

lattices and boolean algebras, finite fields

(characteristic, prime fields, algebraic field

extensions). Coding theory: Linear and cyclic

codes. Combinatorics: Basic principles for

enumeration. Graph theory: Basic concepts,

optimisation in networks.

Instruction

Lectures, problem solving sessions and laboratory

sessions.

Assessment

Written and, possibly, an oral examination at

the end of each sub-course. Compulsory

assignments may be given during the course.