This course introduces the fundamentals of IT as science. The idea of using machines to make calculations is an old one, it was in the 1930s that the work of Alan Turing, Alonzo Church, Kurt Goedel and others laid the foundations for what would become the computer science we know today.
Their work revealed that reasoning and calculation are closely linked, and these foundations must therefore be understood in the older tradition, in logic and in the foundations of mathematics, from Peano to Zermelo passing by Hilbert and many others. We can note that these foundations are still relevant today, despite spectacular technological advances.
While other courses show how to program, here we clarify the framework of what is doable, in terms of
- calculability: some problems cannot be solved by a machine;
- complexity: some problems cannot be solved in a reasonable time.
It is on these points, for example, that cryptographic technologies and the famous "P=NP" problem to $1,000,000 are based.
There are no prerequisites. However, this course is a prerequisite for "Algorithms and Optimization" and "Languages, Proofs, Calculus" in the 3rd-year PA Info.
Evaluation: written exam
- Profesor: Bournez Olivier
- Profesor: Mimram Samuel
- Profesor: Wu Jui-Hsuan
- Profesor: Zeilberger Noam