Ingénieur 2A

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.

Programme
Logique des propositions et des prédicats : Formules, modèles, satisfiabilité, validité, prouvabilité
Exemples de théories: arithmétique et théorie des ensembles
Modèle de calcul : machines de Turing, calculabilité, décidabilité, théorème de l'arrêt, machine universelle
Classes de complexité : P, NP, réduction de problème, NP-complétude, problèmes SAT

Niveau requis : 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.

Langue du cours : Français

Algorithms are the heart of all computation. This course, building on the algorithmic foundations laid in the first computer science courses (INF321 or INF311+INF411), equips the student with a solid background in modern algorithmics. Having followed this course, the student will have a profound knowledge of the most central algorithms, both understanding how and why they work and being able to solve a wide range of computational problems with these building blocks. This is material that everyone aiming to work in a computer science or computing related context needs to know, let it be in a research or industrial environment. In addition to this, we shall also give a brief introduction to several more recent topics like randomized algorithms, evolutionary algorithms, online algorithms, or algorithmic game theory, which had a significant impact on how we understand computing today.The course is taught in English (amphis, poly), for all the rest including the exam both French and English are offered.