<- Archives UCL - Programme d'études ->



Discrete mathematics: logical foundations of computing science [ LINGI1101A ]


5.0 crédits ECTS  30.0 h + 30.0 h   1q 

Teacher(s) Van Roy Peter ;
Language French
Place
of the course
Louvain-la-Neuve
Online resources

> https://icampus.uclouvain.be/claroline/course/index.php?cid=ingi1101

Prerequisites

Within SINF1BA : LSINF1250

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

Part II: Discrete structures

  • 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

Given the learning outcomes of the "Bachelor in Engineering" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:

  • AA1.1, AA1.2
  • AA2.4

Given the learning outcomes of the "Bachelor in Engineering" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:

  • S1.I1, S1.G1
  • S2.2

Students completing this course successfully will be able to

  • convert ordinary language statements into logical expressions using the syntax and semantics of propositional or predicate logic
  • use rules of inference to construct proofs in propositional or predicate logic
  • describe how symbolic logic can model real-life situations , such as those encountered in the context of computing ( eg analysis algorithms )
  • identify and define precisely the basic concepts of graphs and trees providing contextualized examples that highlight these concepts
  • explain various methods of graph paths
  • model various real-world problems encountered in computer using the appropriate forms of graphs and trees, such as social networks and the Web
  • explain the key concepts of the theory of games ( game type, the type of policy agents ) using appropriate examples

Students will have developed skills and operational methodology. In particular, they have developed their ability to

  •     define and interpret concepts with rigor and precision
  •     avoid misinterpretation and detect errors in reasoning .
Evaluation methods
  • short test during the semester
  • written exam
Teaching methods
  • 2h of lecture / week
  • 2h of exercise sessions / week
Content
  • 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.
  • 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.

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

Bibliography

Slides on icampus

Books :

  • Introductory Logic and Sets for Computer Scientists by Nimal Nissanke
  • Networks, Crowds and Markets: Reasoning About a Highly Connected World by David Easley and Jon Kleinberg,
Other information

Background :

  • Elementary discrete mathematics (functions, sets, ...)
  • Use of different techniques of mathematical proof
Cycle et année
d'étude
> Preparatory year for Master in Computer science
Faculty or entity
in charge
> INFO


<<< Page précédente