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.
Graduate 1st year
|Nb. of hours
|Nb. of lessons
02 Apr 2015 13:03 by p.jouvelot