Ce cours introduira des éléments théoriques fondamentaux en informatique.
En particulier, on se penchera sur la notion de calcul en évoquant divers modèles de calcul dont celui de Turing. On verra que certains problèmes ne peuvent pas être calculés, en particulier la célèbre question de l'arrêt.
Dans un second temps on verra que même parmi ceux qui peuvent être calculés, il convient de mesurer les ressources nécessaires (comme le temps de calcul ou l'espace de calcul) et de classer les problèmes selon la quantité de ressource nécessaire pour calculer la réponse à un problème. Cette seconde partie est liée au cours d'algorithmique du S1 et sera illustrée par des exemples de problèmes concrets autour des graphes.
La suite du cours permettra d'évoquer d'autres aspects fondamentaux par exemple en lien avec la théorie de l'information (cryptographie, codes détecteurs et correcteurs d'erreurs).
Le cours s'organisera tout d'abord sous une forme classique CM+TD puis prendra progressivement la forme d'un groupe de travail / séminaire, pendant lequel on creusera certains sujets préparés en avance et présentés par les étudiants.
Mots clé. Informatique fondamentale, Calculabilité, Complexité, Machine de Turing, Théorie de l'information.
Attendus. Appréhender les notions vus en cours comme les limites théoriques de ce qu'on peut espérer calculer. S'approprier une question fondamentale concrète proposée par l'enseignant ou par l'étudiant en faisant des recherches dans la littérature, et la présenter à la promotion (probablement sous la forme d'une vidéo de 15 minutes préparée en avance).
Dans l'immédiat le cours est en distantiel. Je vais utiliser zoom (Meeting ID: 937 5711 7226, mot de passe par mail) et enregistrer la vidéo du cours auxquelles je vais vous donner accès ultérieurement.
