À propos de ce cours
De nos jours, l’informatique arrive à accomplir de véritables
miracles. Suite à quelques cours d’informatique, un étudiant peut croire
avoir une bonne intuition concernant ce qu’il est possible d’accomplir
avec un ordinateur. Cette intuition est parfois trompeuse. En fait,
quelles sont les limites ultimes de l’informatique? Existe-t-il des
problèmes impossibles à résoudre sur un ordinateur? Cela dépend-il du type
d’ordinateur? Quels sont les problèmes qui sont réellement difficiles en
pratique? Nous allons dans ce cours répondre à certaine de ces questions,
mais aussi aborder les raisons qui rendent certaines d’entre elles
particulièrement difficiles.
Une des tâches de l’informatique théorique est d’étudier la notion de
calculabilité. Nous allons débuter le cours par l’étude d’un langage de
programmation très simple n’ayant que 3 instructions. Nous allons voir que
malgré les apparences on peut avec ce langage résoudre des problèmes
arbitrairement complexes. Nous allons aussi étudier la Machine de Turing,
le modèle de calcul par excellence en informatique théorique qui nous
permet de formaliser précisément la notion de temps de calcul et d’espace
mémoire dans un contexte de classification de problème.
Une des tâches principales de l’informatique théorique est effectivement
de classer les problèmes en fonction des ressources nécessaires à leur
résolution. Dans le cours, nous allons étudier une dizaine de classes de
complexité qui chacune formalise un contexte de ressource spécifique.
Préalables
Des connaissances de base en informatique et en programmation sont
nécessaires. De plus, nous supposons que l'étudiant possède la formation
mathématique préalable à des études dans un programme scientifique.
Équipe pédagogique
Alain Tapp
Professeur, Département d'informatique et de recherche opérationnelle, Université de Montréal
Alain Tapp est professeur au département d’informatique et de recherche
opérationnelle de l’Université de Montréal depuis 2001. Alain a reçu son
doctorat en 1999 sous la supervision de Gilles Brassard et Pierre
McKenzie. Alain a exploré au cours de sa carrière de chercheur certains
aspects de l’informatique théorique dans le cadre de la cryptographie et
de l’informatique quantique. Il enseigne sur une base régulière le cours
d’introduction à l'informatique théorique pour les étudiants de deuxième
année du DIRO. Le présent cours est en fait une version adaptée au
contexte MOOC de ce cours.
Rébecca Lapointe
Chargée de cours, Institut Grasset
Rébecca Lapointe a obtenu un diplôme de maîtrise en au DIRO en 2012 sous la
supervision d’Alain Tapp. Rébecca se spécialise en cryptographie quantique et
a une longue expérience dans l'accompagnement d’étudiant en info
théorique. Elle enseigne en ce moment au CÉGEP de Grasset à la technique en
informatique.
Le cours contient plusieurs entrevues avec d’autres membres du DIRO:
- Gilles Brassard, chercheur en cryptographie et informatique quantique;
- Marc Feeley, chercheur en parallélisme et en théorie des langages de programmation;
- Sylvie Hamel, chercheure en bio-informatique;
- Pierre Mckenzie, chercheur en informatique théorique;
- Stéfan Monnier, chercheur en théorie des langages de programmation;
- Pascal Vincent, chercheur en intelligence artificielle.
Préalables
Des connaissances de base en informatique et en programmation sont nécessaires. De plus, nous supposons que l’étudiant possède la formation mathématique préalable à des études dans un programme scientifique.
Effort
Nous anticipons un effort de 5 heures de travail par semaine. Bien qu’étant un cours MOOC s’adressant à un public très varié, le cours est sans aucun doute d’un niveau universitaire et nécessitera, pour donner de bon résultat, une quantité d’effort significative.
Public cible
Ce cours s’adresse à des étudiants motivés et curieux qui s’intéressent aux aspects fondamentaux de l’informatique.
Structure du cours
- Module 0: prérequis, technique de preuve et notation asymptotique;
- Module 1: La classe des primitifs récursifs;
- Module 2: Les langages réguliers et les automates;
- Module 3: Les langages hors contexte et les grammaires;
- Module 4: La machine de Turing;
- Module 5: Les classes de complexité P, NP et la NP-complétude;
- Module 6: Les problèmes indécidables.
Attestation
À la fin du cours, les participants qui auront obtenu la note de passage moyenne de 60 % aux évaluations pourront télécharger une attestation de réussite sur la plateforme EDUlib.
Domaine du cours
- Informatique théorique;
- Mathématique discrète et logique;
- Calculabilité et complexité du calcul.
