Université Côte d'azur
/ Formation / Syllabus SLUIN603
Français English

UE Grands concepts d'informatique fondamentale

Code de l'ECUE : SLUIN603

Ce cours donne droit à 6.0 ECTS.
PORTAIL SCIENCES ET TECHNOLOGIES
Informatique
Campus Valrose
Licence 3
Semestre pair
Français

PRESENTATION

Le cours aborde trois limites fondamentales des mathématiques et de l'informatique: l'impossibilité de dénombrer certains ensembles (Cantor), l'impossibilité de calculer certaines fonctions (Turing) et l'impossibilité de démontrer certains théorèmes (Gödel). Nous démontrerons ces trois théorèmes d'impossibilité et nous discuterons l'impact des limites qu'ils posent dans ces deux disciplines.

Responsable(s) du cours

Christophe Crespelle

Présentiel

  • 24h de cours magistral
  • 36h de travaux dirigés
  • 30h de Travail personnel

PREREQUIS

Avant le début du cours, je dois ...

OBJECTIFS

A la fin de ce cours, je devrais être capable de...
  • distinguer les ensembles dénombrables des ensembles indénombrables
  • concevoir des procédés d’énumération d'un ensemble dénombrable
  • construire une machine de Turing pour décider un langage
  • montrer qu'un langage est indécidable
  • montrer qu'il existe des théorèmes vrais qui n'admettent pas de preuve

CONTENU

  • Le concept d'infini nous est devenu naturel, mais en saisissons nous réellement le sens profond? Dans ce chapitre, nous tenterons de répondre à la question de savoir si tous les infinis se valent ou s'il y en a de plus grands que d'autres.

  • Peut-on tout calculer? Pour éclaircir cette question, il nous faudra définir ce qu'est un calcul. Au passage, nous nous demanderons si les ordinateurs dont nous disposons à l'heure actuelle sont la forme de calculateur la plus aboutie possible.

  • Derrière le titre opaque de ce chapitre, se cache une question d'apparence simple à la réponse déconcertante: suffit-il qu'un énoncé mathématique soit vrai pour qu'il admette une preuve? La question fut tranchée en 1931 par un jeune Autrichien de 25 ans, Kurt Gödel, qui marqua les mathématiques à jamais.

  • Aucune description
Accéder au Syllabus complet (Authentification requise)
Important
Ce syllabus n’a aucune valeur contractuelle. Son contenu est susceptible d’évoluer en cours d’année : soyez attentifs aux dernières modifications.