Discrete mathematics: logical foundations of computing science

lingi1101  2017-2018  Louvain-la-Neuve

Discrete mathematics: logical foundations of computing science
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)

The prerequisite(s) for this Teaching Unit (Unité d’enseignement – UE) for the programmes/courses that offer this Teaching Unit are specified at the end of this sheet.
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

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:

  • 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 .
 

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.
  • 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.
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
http://icampus.uclouvain.be/claroline/course/index.php?cid=ingi1101
Bibliography
Transparents en ligne sur icampus
Livres :
  • Introductory Logic and Sets for Computer Scientists par Nimal Nissanke
  • Networks, Crowds and Markets: Reasoning About a Highly Connected World par David Easley and Jon Kleinberg,
Faculty or entity
INFO


Programmes / formations proposant cette unité d'enseignement (UE)

Title of the programme
Sigle
Credits
Prerequisites
Aims
Bachelor in Computer Science
SINF1BA
5
LSINF1250 AND LSINF1101 AND LSINF1102 AND LSINF1103
Minor in Computer Sciences
LINFO100I
5
LSINF1103
Additionnal module in Mathematics
LMATH100P
5
Additionnal module in Mathematics
TMATH100P
5