Note from June 29, 2020
Although we do not yet know how long the social distancing related to the Covid-19 pandemic will last, and regardless of the changes that had to be made in the evaluation of the June 2020 session in relation to what is provided for in this learning unit description, new learnig unit evaluation methods may still be adopted by the teachers; details of these methods have been - or will be - communicated to the students by the teachers, as soon as possible.
Although we do not yet know how long the social distancing related to the Covid-19 pandemic will last, and regardless of the changes that had to be made in the evaluation of the June 2020 session in relation to what is provided for in this learning unit description, new learnig unit evaluation methods may still be adopted by the teachers; details of these methods have been - or will be - communicated to the students by the teachers, as soon as possible.
5 credits
30.0 h + 30.0 h
Q1
Teacher(s)
Van Roy Peter;
Language
French
Prerequisites
Within SINF1BA : LSINF1250
Within FSA1BA : LFSAB1101, LFSAB1102, LFSAB1401, (LFSAB1301, LFSAB1201, LFSAB1202)
Within FSA1BA : LFSAB1101, LFSAB1102, LFSAB1401, (LFSAB1301, LFSAB1201, LFSAB1202)
Main themes
Part I: Propositional logic and predicate logic
- Propositional logic (syntax, semantics, proofs)
- Predicate logic (quantifiers, bound and free variables, proofs) and application to algorithm analysis
- Set theory and application to formal system specification (Z notation)
- Relations and applications in computer science (relational databases, overriding, binary relations, ')
- Functions and lambda calculus
- Graphs (basic concepts, paths and connectivity)
- Applications of graphs, e.g., to model social networks (ties, homophily, closure)
- Graphs and properties of graphs used to model Internet-based networks
- Introduction to game theory
Aims
At the end of this learning unit, the student is able to : | |
| 1 |
Given the learning outcomes of the "Bachelor in Engineering" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:
|
The contribution of this Teaching Unit to the development and command of the skills and learning outcomes of the programme(s) can be accessed at the end of this sheet, in the section entitled “Programmes/courses offering this Teaching Unit”.
Content
- Preliminaries: sets, relations, and functions; formal systems; deduction, induction, abduction; scientific method.
- Mathematical logic:
- propositional calculus -- syntax, semantics, proof theory, proof algorithm;
- first-order predicate calculus -- syntax, semantics, proof theory, proof algorithm;
- Prolog programming language and its proof algorithm;
- first-order theories -- models, consistency, inclusion, extension, etc.
- Equational theories: equality, partial orders, lattices, groups.
- Discrete structures on the Internet: graphs and graph properties, giant components, strong and weak links, triadic closure, structural balance, balance theorem, structure of the Web, PageRank, power laws, the long tail.
Teaching methods
- 2h of lecture / week
- 2h of exercise sessions / week
Evaluation methods
- short test during the semester
- written exam
Other information
Background :
- Elementary discrete mathematics (functions, sets, ...)
- Use of different techniques of mathematical proof
Online resources
LINGI1101 Moodle: https://moodleucl.uclouvain.be/course/view.php?id=8199
Bibliography
- LINGI1101: Logique et Structures Discrètes par Peter Van Roy
- Networks, Crowds and Markets: Reasoning About a Highly Connected World par David Easley and Jon Kleinberg
Faculty or entity
INFO
