École polytechnique learning platform

Ce cours présente les fondements de l'informatique en tant que science. Si l'idée d'utiliser des machines pour effectuer des calculs est ancienne, c'est dans les années 30 que les travaux d'Alan Turing, Alonzo Church, Kurt Goedel et d'autres ont posé les bases de ce qui allait devenir l'informatique que nous connaissons aujourd'hui.

Leurs travaux ont révélé que le raisonnement et le calcul sont intimement liés et ces bases doivent donc se comprendre dans la tradition, plus ancienne, de la logique et des fondements des mathématiques, de Peano à Zermelo en passant par Hilbert et bien d'autres. Il est remarquable que ces bases sont toujours d'actualité, malgré les progrès technologiques spectaculaires.

Alors que d'autres cours montrent comment programmer, on explicite ici le cadre de ce qui est faisable, en termes
- de calculabilité : certains problèmes ne peuvent pas être résolus par une machine ;
- de complexité : certains problèmes ne peuvent être résolus en un temps raisonnable.

C'est par exemple sur ces points que reposent les technologies cryptographiques et le fameux problème "P=NP" à $1.000.000.


Pas de pré requis. En revanche, ce cours est un pré-requis pour les thématiques "Algorithmique et optimisation" et "Langages, preuves, calcul" du PA Info en 3ème année.

Modalités d'évaluation : Examen sur table.

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