Examen Corrigé de Complexité et Calculabilité - Master Info Lyon 1

Présentation de l'examen final de complexité et calculabilité

Ce document est le corrigé détaillé de l'examen final de l'unité d'enseignement de complexité et calculabilité, dispensée dans le cadre du Master Informatique de l'université Lyon 1 pour l'année universitaire 2015-2016. Conçu pour une durée d'une heure et trente minutes, ce sujet aborde plusieurs piliers de l'informatique théorique à travers des exercices pratiques et des démonstrations mathématiques rigoureuses.

Les notes de cours et de travaux dirigés étaient autorisées lors de cette épreuve, tandis que les livres et les appareils électroniques étaient interdits. Le texte fournit non seulement les réponses aux différents problèmes posés, mais détaille également les étapes de raisonnement et les constructions formelles attendues des étudiants.

Thèmes et notions abordés dans le sujet

Le contenu de l'examen est divisé en plusieurs parties distinctes, chacune explorant un domaine fondamental de la théorie de la calculabilité et de la complexité des algorithmes :

• Machines de Turing : La conception d'une machine de Turing déterministe capable de reconnaître un langage spécifique, en l'occurrence les palindromes sur l'alphabet formé par les lettres a et b. Le corrigé présente un diagramme d'états complet accompagné de la logique de déplacement de la tête de lecture.
• Fonctions primitives récursives : L'étude de la construction de fonctions par récursion et composition. Les étudiants devaient prouver qu'une fonction spécifique liant les diviseurs d'un entier est primitive récursive, puis mener une démonstration formelle sur une fonction définie par récurrence imbriquée faisant intervenir la fonction puissance de deux.
• Indécidabilité : Une démonstration par réduction à partir du problème de l'arrêt pour prouver qu'un problème portant sur le caractère infini du langage accepté par une machine de Turing est indécidable.
• NP-complétude : Une exploration approfondie du problème Clique. Cela comprend la construction d'un exemple concret de graphe contenant une clique de taille quatre, la réduction polynomiale depuis le problème SAT vers le problème Clique, l'évaluation de la taille du graphe résultant par un polynôme, et l'écriture d'un algorithme non déterministe pour attester de l'appartenance de Clique à la classe NP.

Utilisation recommandée pour les révisions

Ce sujet corrigé constitue un support de travail particulièrement formateur pour les étudiants en informatique avancée. Il est conseillé de chercher à résoudre chaque exercice de manière autonome avant de consulter la solution rédigée par Paul Brunet et Laure Gonnord. L'analyse des démonstrations relatives à la récursivité primitive et aux réductions polynomiales permet de s'imprégner de la rigueur exigée dans les épreuves universitaires de ce niveau.

Les étudiants peuvent ainsi s'entraîner à formaliser des machines de Turing, à manipuler les opérateurs de composition et de récursion, et à rédiger des preuves de NP-complétude en suivant la méthodologie rigoureuse présentée dans le document.

Questions fréquentes

Quel est le niveau académique de cet examen ?

Cet examen est destiné aux étudiants inscrits en première année de Master Informatique (Master Info), dans le cadre du cours de complexité et calculabilité de l'université Lyon 1 pour l'année 2015-2016.

Quels sont les principaux chapitres évalués dans ce sujet ?

L'évaluation porte sur quatre grands thèmes de l'informatique théorique : les machines de Turing, les fonctions primitives récursives, l'indécidabilité par réduction et la théorie de la NP-complétude avec le problème de la clique.

Le document contient-il des corrigés détaillés ?

Oui, le document fournit les corrigés rédigés de toutes les questions, incluant les diagrammes d'états pour les machines de Turing, les définitions formelles par récurrence et les étapes détaillées des preuves de complexité.

Testez vos connaissances

Télécharger Examen Corrigé de Complexité et Calculabilité - Master Info Lyon 1 pdf