Mathematics for computer science

lsinf1250  2017-2018  Louvain-la-Neuve

Mathematics for computer science
7 credits
30.0 h + 15.0 h
Q1
Teacher(s)
Saerens Marco;
Language
French
Prerequisites
LMAT1111E, LSINF1101

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
1 . Logic , sets and functions
  • Equivalence ,
  • Predicates and quantifiers ,
  • Sets and set operations ,
  • Sequences and summations ,
  • Growth of functions
2 . Algorithms, integers and matrix
  • Algorithmic complexity ,
  • Integers and divisions ,
  • Rudiments of the theory of numbers,
  • Recalls of matrix calculation ,
  • Application to Markov chains
3 . Logical and mathematical reasoning
  • Methods of proof ,
  • Mathematical induction ,
  • Recursion and recursive algorithms ,
  • Correctness of a program
4 . Combinatorial mathematics
  • Counting
  • Permutations,
  • Arrangements
  • Recurrence relations ,
  • Solving recurrence equations
5 . graphs
  • Representation of graphs and graph isomorphism ,
  • Connectivity
  • Hamiltonian paths ,
  • Problems of the shortest path
6 . Trees
  • Introduction
  • Applications trees,
  • Tree paths,
  • Trees and sorting,
  • Minimum spanning trees
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:

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

Students completing successfully this course will be able to

  • use of the terminology related to functions, relations and all associated operations and realize where the context requires
  • explain the basic structure of the main proof techniques ( direct proof , counterexample , proof by contradiction , induction, recursion)
  • apply the different proof techniques convincingly by selecting the most suitable to the problem
  • analyze a problem to determine the relationships underlying recurrence
  • determine counts , permutations , arrangements sets within an application.
  • apply various methods of graphs and trees path ( including the prefix , postfix and infix tree path )
  • model various real-world problems encountered in computer science using the appropriate forms of graphs and trees, eg the representation of network topology , the hierarchical organization of files, ...
  • explain the problem of the shortest path in a graph and apply on simple graphs Dijkstra's algorithm and Bellman- Ford's algorithm
  • explain how to construct the minimum spanning tree of a graph
  • eetermine if two graphs are isomorphic
 

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
The course is constructed around the following basic topics:
- Mathematical structures: finite and infinite sets, relations, functions - Proof techniques: induction, elementary logic
- Enumeration: binomial coefficients, recurrences, generating functions - Algebraic structures: monoids, groups, morphisms, lattice, Boolean algebras
- Graph theory: trees, paths, matchings, tours
- Analysis of algorithms, plynomial algorithms, etc.
Teaching methods
  • 30 hours of magistral courses.
  • A project / case study on the implementation of an algorithm.
Evaluation methods
  • A project / case study accounting for 2 on 20 points.
  • A written exam held in session accounting for 18 points on 20.
Other information
Background:
  • Good knowledge of general mathematics (especially linear algebra) and of basic concepts in programming is required to start this course in good conditions.
Online resources
http://icampus.uclouvain.be/claroline/course/index.php?cid=SINF1250
Bibliography
Support de cours :
  • transparents de l'enseignant
  • Ouvrage conseille : K. Rosen, "Mathématiques discrètes". 2006.
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
7
LSINF1101 AND LSINF1112
Master [120] in data Science: Statistic
DATS2M
7