• FR
  • EN

Fundamentals of computer science

Code: S1214, ECTS: 1


The aims of this course of introduction to the fundamental principles of computer science are:

  • to introduce students to knowledge that will still be valid 10 years from now;
  • to relate mathematical formalism and programming languages;
  • to show the intrinsic limitations of the computer as a tool;
  • to link categories of problems to groups of technical solutions;
  • to provide keys to help engineers choose among existing formal tools;
  • and, above all, to have fun and be surprised.


Most of the subjects presented will not require any particular specific knowledge, apart from a minimum of interest in the formalization of concepts, a knowledge of the basic principles of programming dealt with in first year courses and a fair amount of curiosity...


  • introduction: limitations of computer science, notion of problems, logical systems, mathematical formalisms and applications to computer science,  notion of effective resolution (incompleteness, decidability), languages and operating models;
  • calculation models: Turing machines, notion of calculation, lambda-calculus, rewriting systems, Diophantine equations, Turing/Church thesis, equivalences; application to programming paradigms (imperative, functional object-oriented and logic);
  • definitions of programming languages: syntax, typing, fixed-point notion, operational semantics (McCarthy, 1963), axiomatic semantics (Hoare, 1969), denotational semantics (Milne and Strachey, 1976);
  • complexity: types of complexity, non-determinism, temporal complexity, NP-complete problems, Cook theorem, spatial complexity, hierarchy theorems;
  • advanced aspects: randomization, quantum computation, DNA computing.

Teaching team


Teaching staff

Code S1214
Year 2nd year
Level Graduate 1st year
ECTS Credits 1
Coefficient 1
Nb. of hours 12
Nb. of lessons 10
Course type Specialized courses
Semester 4
Period Spring
  • Informatique
Last update:
20 Jun 2017 11:21 by julien