UCL - Studies

Version française

Study programmes
First cycle
Second cycle
Third cycle
Faculties and entities
Access to studies
Academic calendar
Search
Simple
Detailed
Per course

Discrete mathematics: logical foundations of computing science [INGI1101]
[30h+30h exercises] 4 credits

Version française

Printable version

This course is taught in the 1st semester

Teacher(s):

Chantal Poncin (supplée Axel Van Lamsweerde), Axel Van Lamsweerde

Language:

French

Level:

First cycle

>> Aims
>> Main themes
>> Content and teaching methods
>> Other information (prerequisite, evaluation (assessment methods), course materials recommended readings, ...)
>> Other credits in programs

Aims

- To acquire the mathematical foundations of a variety of concepts and techniques used in computing science.

- To make the appropriate connections between such foundations and various application domains in programming, data structures, artificial intelligence, software engineering, databases, robotics, etc.).

- To apply rigorous approaches for formalizing structures found in computing science and for reasoning about such structures.

Main themes

- Introduction to mathematical logic: propositional logic, predicate logic; first-order theories.

- Reasoning mechanisms: resolution, rewriting, induction on well-founded sets.

- Discrete structures as first-order theories: equality, partial orders, lattices; nonnegative integers, tuples, lists, trees, sets, multisets, sequences, etc.

Content and teaching methods

- Preliminaries: sets, relations, and functions; formal systems.

- Mathematical logic: proposition calculus -- syntax, semantics, proof theory; first-order predicate calculus -- syntax, semantics, proof theory ; resolution and refutation; first-order theories --models, consistency, inclusion, extension, etc.

- Equational theories: equality, partial orders, lattices, groups.

- Inductive theories: well-founded relations and the general induction principle. Basic inductive theories : nonnegative integers, tuples, lists, trees, sets, multisets, sequences, etc. Structure generators, systematic construction of axiomatisations, and inductive proofs of typical properties according to various induction rules (recurrence, complete induction, etc.).

Applications to various domains : program verification, specification of abstract data types, automated reasoning, expert systems, robotics, databases, parsing, etc.

Implementation with declarative programming languages such as PROLOG or ML.

Other information (prerequisite, evaluation (assessment methods), course materials recommended readings, ...)

- Weekly exercise sessions require students to come prepared and be actively involved -questions/answers, and resolution, by small groups, of problems submitted during the previous week. Quizzes are organized regularly to make sure that students follow and work properly.

- Prerequisite:
Elementary maths (assumed to be acquired after the first two bachelor years).

- References:
(1) Course lecture notes (available at " SICI ").

(2) Z. Manna and R. Waldinger, The Deductive Foundations of Computer Programming, Addison-Wesley, 1993.

(3) D. Gries, F. Schneider, A Logical Approach to Discrete Mathematics, Springer-Verlag, 1994.

- Evaluation :
Quizzes throughout the quadrimester, and written exam at the end.

Other credits in programs

FSA13BA

Troisième année de bachelier en sciences de l'ingénieur, orientation ingénieur civil

(4 credits)

INFO22

Deuxième année du programme conduisant au grade d'ingénieur civil informaticien

(4 credits)

INFO23

Troisième année du programme conduisant au grade d'ingénieur civil informaticien

(4 credits)

SINF12BA

Deuxième année d'études de bachelier en sciences informatiques

(4 credits)

SINF13BA

Troisième année d'études de bachelier en sciences informatiques

(4 credits)

SINF1PM

Année d'études préparatoires au master en sciences informatiques (60 et 120)

(4 credits)

Mandatory



This site was created in collaboration with ADCP, ADEF, CIO et SGSI
Person in charge : Jean-Louis Marchand - Information : secretaire@fsa.ucl.ac.be
Last update :13/03/2007