Le MOOC Vers les limites ultimes de l’informatique propose l’étude d’un langage de programmation très simple n’ayant que 3 instructions. Malgré les apparences, ce langage peut 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.
* 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
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 GrassetRé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.
Durée
7 semaines
Du 26 février au 25 mai 2017Pré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.
Charge de travail
5 heures / semaine
Coût
Gratuit
Certification
Attestation de réussite
Déroulement
N.C
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.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.
