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

UE Grands concepts d'informatique fondamentale

ECUE's code : SLUIN603

This course give 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.

Course's manager(s)

Christophe Crespelle

In class

  • 24h of lectures
  • 36h of directed studies
  • 30h of Travail personnel

PREREQUISITES

Before the start of the course, I must ...

OBJECTIVES

By the end of this course, I should be able to...
  • 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

CONTENT

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

  • No description
Access to complete Syllabus (Authentification required)
Important
This syllabus has no contractual value. Its content is subject to change throughout this year: be aware to the last updates