Passer au contenu de cette vue

Vers les limites ultimes de l'informatique
Université de Montréal

À 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.
  1. Numéro du cours

    IFT-Limites
  2. Institution

    Université de Montréal
  3. Début du cours

    26 févr 2017
  4. Fin des cours

    25 mai 2017
  5. Effort estimé

    5 heures par semaine
  6. Pré-requis

    Mathématiques
S'inscrire