Exercice corrigé concernant la vérification du théorème de Fermat

Informatique théorique

Travail demandé:

Qu’arrive-t-il quand on exécute un programme qui vérifie le grand théorème de Fermat ?           

Réponse:

Rappel de l’hypothèse de Fermat :

Pour n entier, n ≥ 3, il n’existe pas d’entiers positifs a, b, c  tels que :

aⁿ + bⁿ = cⁿ

Programme en C++ :

Afin de constater ce qui se passe quand on essaie de vérifier ce théorème, on a réalisé un programme en C++ dont voici le code :

Quand on exécute le programme, celui-ci nous demande d’introduire des valeurs de a, b et c pour vérifier l’hypothèse de Fermat.

Lorsqu’on clique sur « Entrer », le programme s’exécute et ne s’arrête que lorsqu’une valeur ( aⁿ , bⁿ , cⁿ ou n) arrive à la valeur correspondante à la taille limite du type de la variable ( la valeur limite dans notre cas est  +ou- 1073741824 égale à  2*2³⁰), résultat logique sachant que le compilateur utilisé alloue 4 octets aux variables de type entier. Afin de concrétiser ceci le programme affiche n à chaque exécution de la boucle.

Commentaire :

D’après l’exécution du programme on constate  qu’en aucun cas celui-ci arrive à trouver une valeur de « n » vérifiant un contre exemple. Cependant, ce résultat ne peut pas confirmer la vérification de l’hypothèse puisqu’il est pratiquement impossible de vérifier tous les cas. Alors on peut dire que ce programme (algorithme) est indécidable.

            En effet, une proposition est, logiquement, dite décidable dans une théorie axiomatique, si on peut la démontrer ou démontrer sa négation dans le cadre de cette théorie. Un énoncé mathématique est donc indécidable dans une théorie s'il est impossible de le déduire, ou de déduire sa négation, à partir des axiomes ; ceci d’une part.

            D’autre part, un algorithme consiste en un ensemble fini d'instructions simples et précises qui sont décrites avec un nombre limité de symboles. Un algorithme doit toujours produire le résultat en un nombre fini d'étapes. L’exécution d’un algorithme ne requiert pas d'intelligence de l'humain sauf celle qui est nécessaire pour comprendre et exécuter les instructions.

            Ainsi, on peut dire que le problème est décidable s'il existe un algorithme ou une procédure mécanique qui termine en un nombre fini d'étapes, qui le décide, c'est-à-dire qui réponde par  « oui »  ou par « non » à la question posée par le problème. S'il n'existe pas de tels algorithmes, le problème est dit indécidable. En outre, le problème décidable réfère à la notion de calculabilité en cherchant un algorithme qui s’arrête à un temps fini et fournit la réponse OUI ou NON à la question posée. Dans ce sens, dire qu'un problème est indécidable ne veut pas dire que les questions posées sont insolubles mais seulement qu'il n'existe pas de méthode unique et bien définie, applicable d'une façon mécanique, pour répondre à toutes les questions, en nombre infini, rassemblées dans un même problème ; et ceci correspond exactement à l’hypothèse de Fermat.

            Pour conclure, On peut dire que l’hypothèse de Fermat ne peut être vérifiée ni démontrée à travers un algorithme exécuté sur une machine de Turing universelle.

Read More

Exercice corrigé du système MIU

Informatique théorique

Exercice 3:

Système MIU :

        Nous avons le système MIU est une suite de ‘M’,’I’ et ’U’;  L₀=MU étant son axiome. L’évolution du système étant basée sur 4 règles qui gèrent l’extension et la limitation du système. On obtient alors :

-         L₀ = {MI}

-         L₁ = {MI , MIU , MII}

-         L₂ = {MI , MIU , MII , MIUIU , MIIU , MIIII}

-         L₃ =  {MI , MIU , MII , MIUIU , MIIU , MIIII , MIUIUIUIU , MIIUIIU , MIIIIU , MIIIIIIII , MUI , MIU}

-         L₄={MI, MII, MIU, MIUIU, MIIU, MIIII, MIUIUIUIU, MIIUIIU, MIIIIU, MIIIIIIII, MUI, MIUIUIIUIUIIUIUIIUIUI, MIIUIIUIIUIIU, MIIIIUIIIIU, MUIU, MIUU, MIIIIIIIIU, MIIIIIIIIIIIIIIII, MUUII, MIIUU, MIUUI, MUIIU, MUIUI}

-         Etc. …

        Le jeu du système MIU consiste à vérifier, à partir des règles de dérivation d’un coté et de l’axiome MI de l’autre, si tous les assemblages de lettres effectuées à partir de MIU existent. Autrement dit, il s’agit de savoir si les mots que l’on peut obtenir à partir de ‘M’ , ’I’ et ‘U’ sont des théorèmes du système.

        Après quelques tentatives pour trouver ‘MU’ ; on n’est pas arrivé à le trouver. Cependant, on ne peut donner une preuve formelle sur l’absence de celui-ci. Mais logiquement, ou plutôt intuitivement, on constate que ‘MU’ ne peut pas être théorème du système pour les raisons qui suivent :

a-  L’assemblage « MU » comporte zéro « I ». Or, zéro est un multiple de 3.

b- R1 et R2 laissent intact le nombre de « I » autorisé. C’est R3 qui diminue le nombre de

« I » de 3, sans le changer quant à la divisibilité par 3. R2, quant à elle, double le nombre de « I ». Et, comme 2n ne peut être divisible par 3 que si « n » est divisible par 3, R2 ne produit pas de multiple de 3. Alors, aucune règle ne produit de multiple de 3.

c-L’axiome « MI » contient un nombre non multiple de 3 de « I », c’est-à-dire un seul « I ». Par conséquent, aucun théorème ne peut contenir de multiple de 3 de « I », donc en particulier zéro « I ».

d- Il est clair que, pour produire la preuve formelle de « MU » dans le système MIU, il faut supprimer tous les « I ».

         Toutes ces constatations, intuitives, ne constituent pas de preuves formelles, toutefois elles nous donnent une vision plus claire sur l’existence ou l’inexistence d’un tel ou tel phénomène.

Read More

Exercice corrigé de la fonction d'Ackermann

Informatique théorique

Exercice :

La Fonction d’Ackermann : Calcul de A(4,4)

Vu la complexité du calcul, on a procédé à la réalisation d’un programme sur C, dont voici le code :

                   

Donc on constate que le A(4,4) a causé une saturation du système. Ce phénomène étant tout à fait normal, vu le comportement de la fonction d’Ackermann. Celle-ci croit d’une manière extrêmement rapide, passant initialement d’une adition, à une multiplication, ensuite à une exponentiation, et par la suite à une réitération de l’exponentiel, ainsi de suite :

-         A( m , 1 ) = 2 + (m+3) – 3                 Adition

-         A( m , 2 ) = 2 * (m+3) – 3                 Multiplication

-         A( m , 3 ) = 2(m+3) – 3                     Exponentiation

-         A( m , 4 ) = (…(2)2)…)2 – 3             Réitération de l’exponentiel

                                            

         Alors A(4,4) ne peut être calculée via un ordinateur simple, du moment que l’unité de calcul (UC) de celui-ci ne peut supporter le nombre d’opérations que demande le calcul de A(4,4).

Read More

Exercice corrigé fonction définie

Informatique théorique

Exercice :

Démontrer est ce que f(n) est bien définie ? (calculer f(97) et f(0))

Pour  pouvoir calculer ces valeurs et observer la nature de la fonction, on a vu utile de réaliser un programme en C :

Après compilation et exécution du programme on obtient le résultat suivant :

Cette fonction reste constante pour n<100 et croissante pour n>100.voila quelques tests :

Donc on constate que f(0)=f(97)=91, ceci étant valable jusqu’à la valeur de 101 à partir de laquelle la fonction commence à suivre un comportement croissant jusqu’à l’infini. Ainsi, on peut observer le comportement de f qui est bien définie.

Read More