Key Information
About the content
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.
Syllabus
Ce cours s’adresse à des étudiants motivés et curieux qui s’intéressent aux aspects fondamentaux de l’informatique. 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.
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.
À 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.
Instructors
lain 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.
Content Designer
The Université de Montréal (UdeM) is a public research university in Montreal, Quebec, Canada. The francophone institution comprises thirteen faculties, more than sixty departments and two affiliated schools: the École Polytechnique (School of Engineering) and HEC Montréal (School of Business). It offers more than 650 undergraduate programmes and graduate programmes, including 71 doctoral programmes. The Times Higher Education World University Rankings of 2014-2015 ranks the Université de Montréal at 113th place globally.
The university has Quebec's largest sponsored research income and the third largest in Canada, allocating close to $524.1 million to research conducted in more than 150 research centres as of 2011. It is also part of the U15 universities. More than 55,000 students are enrolled in undergraduate and graduate programs, making it the second-largest university in Canada in terms of student enrolment.
Platform
EDUlib was launched by HEC Montreal in October 2012 with the aim of making it available to as many people a high quality university education in French in the field of management. EDUlib is now a joint initiative of the University of Montreal and its two affiliated schools, HEC Montreal and Ecole Polytechnique Montreal. The goal remains to offer the greatest number of people a high quality university education in French but in different areas of knowledge of the three partners. EDUlib courses are modeled on those offered-face. They are taught by the same faculty and academic knowledge is transmitted caliber. Course format and frequency change, of course, but not the quality of teaching.
EDUlib is a public education initiative that does not lead to obtaining a university degree. However, it is expected that a statement will crown the efforts of participants who pass quizzes or tests covered in the course. The courses have been designed to be widely accessible, in a concerted effort to spread knowledge.
Pas la technologie des limites finales de l'informatique
Pas la technologie des limites finales de l'informatique
