Mathematics for computer science [ LSINF1250 ]

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

LMAT1111E, LSINF1101

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

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

• A project / case study accounting for 3 on 20 points.
• A written exam held in session accounting for 17 points on 20.

• 30 hours of magistral courses.
• A project / case study on the implementation of an algorithm.

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.

Background:

• Good knowledge of general mathematics (especially linear algebra) and of basic concepts in programming is required to start this course in good conditions.