date_range Débute le 12 septembre 2017
event_note Se termine le 31 janvier 2018
list 6 séquences
assignment Niveau : Introductif
label Informatique & Programmation
chat_bubble_outline Langue : Français
card_giftcard 18 points
2.5 /5
Avis de la communauté
2 avis

Les infos clés

credit_card Formation gratuite
verified_user Certification gratuite
timer 30 heures de cours

En résumé

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.

more_horiz Lire plus
more_horiz Lire moins
dns

Le programme

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.

record_voice_over

Les intervenants

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

Le concepteur

L'Université de Montréal (UdeM) est l'un des quatre établissements d'enseignement supérieur de Montréal au Québec. Elle est l'une des dix grandes universités du Canada (la deuxième en terme du nombre d'étudiants) et parallèlement la plus importante au Québec pour le nombre d'étudiants ainsi que pour la recherche.

assistant

La plateforme

EDUlib a été lancé par HEC Montréal en octobre 2012 avec comme objectif de rendre disponible au plus grand nombre de personnes une formation universitaire de haute qualité en français dans le domaine de la gestion. EDUlib est maintenant une initiative conjointe de l’Université de Montréal et de ses deux Écoles affiliées, HEC Montréal et Polytechnique Montréal. L’objectif demeure d'offrir au plus grand nombre de personnes une formation universitaire de haute qualité en français mais dans les différents domaines de connaissances des trois partenaires. Les cours d’EDUlib sont calqués sur ceux offerts en présentiel. Ils sont donnés par les mêmes professeurs et les connaissances transmises sont de calibre universitaire. Le format du cours et la périodicité changent, évidemment, mais pas la qualité d’enseignement.

EDUlib est une initiative d’éducation populaire qui ne mène pas à l’obtention d’un diplôme universitaire. Toutefois, il est prévu qu’une attestation couronnera les efforts des participants qui auront réussi les quiz ou tests prévus dans le cours. Les cours ont été conçus pour être largement accessibles, dans un effort concerté de diffusion de la connaissance.

Avis de la communauté
2.5 /5 Moyenne
1
0
0
0
1
Contenu
2.5/5
Plateforme
2.5/5
Animation
2.5/5
Le meilleur avis

Pas la technologie des limites finales de l'informatique

le 1 janvier 2018
Quelle note donnez-vous à cette ressource ?
Contenu
0/5
Plateforme
0/5
Animation
0/5
le 1 janvier 2018

Pas la technologie des limites finales de l'informatique

Vous pourriez être intéressé par...