• contact@mooc-francophone.com

Vers les limites ultimes de l’informatique

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.

Organisateur :

Université de Montréal

* MOOC Francophone est un service de mise en relation sans inscription et sans intermédiaire. Nous n’organisons aucun cours, le lien « Suivre le cours » vous redirige vers la page web des organisateurs. Les participants peuvent également évaluer ce cours en cliquant ici
  • icon

    Intervenant

    Alain Tapp

    Professeur, Département d’informatique et de recherche opérationnelle, Université de Montréal

     

    Rébecca Lapointe

    Chargée de cours, Institut Grasset

  • icon

    Durée

    16 semaines
    Du 12 Septembre 2017 au 31 Janvier 2018

  • icon

    Prérequis

    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.

  • icon

    Charge de travail

    5h / semaine

  • icon

    Coût

    Gratuit

  • icon

    Certification

    À 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.

  • icon

    Déroulement

    Non communiqué

  • icon

    Programme

    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.

  • icon

    Plateforme

    EDUlib
    La Plate-forme est basée sur la technologie Open edX du MIT et de Harvard. Initialement lancée en octobre 2012 par HEC Montréal sur le LMS Sakai, EDUlib est aujourd’hui une initiative conjointe de l’Université de Montréal et de ses deux Écoles affiliées, HEC Montréal et Polytechnique Montréal.

Pin It on Pinterest

Share This