logo Insalogo Insa

Theoretical tools for computer science


Programme (detailed contents):


Complexité :

-       O notation

-       Master theorem

-       P, NP, NP-hard classes


Calculability and combinatorics :

-       Decidability

-       Turing machine

-       Discrete mathematics



-       Modelling

-       Simplex algorithm

-       Duality


At the end of this module, the student will have understood and be able to explain (main concepts):


-       Regular expressions

-       Algorithm and problem complexity

-       Calculability

-       Information encoding

-       Linear programming


The student will be able to:



- Students are able to recognize a problem that can be solved using regular expressions, choose the appropriate tool, and apply quickly the solution.

- Students are able to identify the complexity (temporal, spatial) of an algorithm

- Students are able to determine and prove the class of complexity of a problem (P, NP, NP-hard)

- Students undertands the basis of information theory

- Students are able to determine if a problem can be solve by a computer

- Students are able to model a problem as a linear program and solve it using the simplex algorithm through a software

Needed prerequisite

Basic mathematics (linear algebra), algorithmics, Unix Shell

Form of assessment

The evaluation of outcome prior learning is made as a continuous training during the semester. According ot the teaching, the assessment will be different: as a written exam, an oral exam, a record, a written report, peers review...

Additional information

Regular expressions, information theory, linear programming, calculability