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

Réalisation d'un programme de gestion d'un dictionnaire

 Introduction :

L’élaboration d’un dictionnaire se basant sur l’alphabet français peut se faire de différentes manières à savoir les tableaux simples, les tables associatives (Hash-code), les listes chaînées et les arbres. La dernière solution qui se base sur les arbres présente la meilleure  en terme d’optimisation de l’espace mémoire et de la rapidité de recherche et d’intervention et ceux dus à la notion de récursivité utilisée largement dans ce genre de manipulation.

Travail demandé :

Dans ce présent travail, on demande d’écrire un programme contenant un menu pour gérer un dictionnaire contenant  des mots de la langue française qui seront présentés par ordre alphabétique fournissant pour chacun une définition. Pour se faire, nous disposons d’un menu comportant des fonctions pour créer un dictionnaire, pour y ajouter des mots  , pour en supprimer, pour afficher tous les éléments, pour rechercher et enfin pour fermer et quitter le fichier.

Architecture utilisée :

On a opté pour l’utilisation des arbres, suivant l’architecture ci-dessus :

S_noeud *droite, *gauche: deux pointeurs pour la navigation dans l’arbre.

Char *info : pointe sur un espace dynamique pour recevoir le mot en question.

Char *def : pointe sur un espace dynamique pour recevoir la définition associée.

Les différentes étapes d’élaboration du menu sont expliquées ci-dessous:

1. Étapes de réalisation:

Pour élaborer ce mini projet, plusieurs étapes ont été suivies:

• L’ajout d’un mot au dictionnaire.
• La recherche d’un mot dans le dictionnaire.
• La suppression d’un mot du dictionnaire.
• La fermeture du dictionnaire.

Pour ce faire, un menu a été établi. Ce menu comporte toutes les fonctionnalités citées. Toutes ces fonctions sont décrites en détails dans les paragraphes qui suivent.

1.1. Élaboration du menu:

Le menu général de notre  programme se présente comme suit:

1- Ajouter un mot au dictionnaire.

2- Rechercher un mot dans le dictionnaire.

3- Supprimer un mot du dictionnaire.

4- Fermer le dictionnaire.

Donc un ensemble de fonction a été  élaboré  afin d’exécuter le menu ci-dessus tout en utilisant les arbres sous c afin d’optimiser l’espace mémoire et en s’appuyant sur la notion de récursivité.

1.2. Les fonctions principales du programme:

A- Fonction exprimant l’ajout d’un mot au dictionnaire :

Pour ajouter un élément au dictionnaire, on a recours à une fonction qui ne retourne rien et qui prend comme paramètre un pointeur de pointeur de type t_noeud. Le prototype de la fonction qui permet l’ajout est arbre * create(char nb[],arbre * prim,char d[]). Dans la fonction create, On fait entrer le mot à insérer et on teste s’il existe déjà ou pas. Si l’élément existe, le mot ne sera pas accepté, sinon il sera ajouté avec succès. 

B- Fonction vérifiant la recherche d’un mot dans le dictionnaire :

La fonction  Exist qui nous permettra de chercher un mot dans le dictionnaire, elle retourne void et reçoit comme paramètre un pointeur nœud de type t_noeud. Le prototype de cette fonction est void Exist(arbre *src ,char elt[]).

C- Pour supprimer un élément du dictionnaire :

Dès que l’utilisateur désire supprimer un élément du dictionnaire, on fait appel à la fonction   Supprimer dont le prototype est : void Supprimer(arbre**src, char *chaine). Cette fonction permet de vérifier si le mot entré existe dans le dictionnaire. Si c’est le cas elle permet de bien supprimer l’élément.

On trouve aussi la fonction Suppression dont le prototype est : void Suppression(arbre **src) qui permet de libérer le nœud à supprimer ainsi que sa définition.

2. Algorithmes:

       typedef struct tree{

     char mot[10];

    char def[1000];

     struct tree *droite;

     struct tree *gauche;

     }arbre;

   ajouter (&R, mot[30])

i=0;

D=R;

ptr prec, temp;

Tantque (i<m.lenght())

D=D->bas;

prec=Null;

  Tant que (D!=Null) et ((D->lettre)<mot[i])

    prec=D;

    D=D->suivant;

  fin tantque

si ((D->lettre)=mot[i]) alors D=D->bas;

i=i+1;

sinon

     temp=(ptr) malloc(size of(noeud));

     temp->lettre=mot[i];

    si (prec=!=Null) alors

prec->suivant=temp;

temp->suivant=D;

    sinon

         si (D=Null)

            D->bas=temp;

            temp->haut=D;

            temp->suivant=Null;

         sinon

             temp->suivant=D;

             D->haut=Null;

         finsi

      finsi

   finsi

fintantque

si i>=mot.lenght() alors D->bas=definition;

---------------------------------------------------------------------------------------------------------------------

rechercher(&R, mot[30])

D=R;

tantque (D->bas!=Null) et (i=<mot.lenght())

tantque (D!=Null) et (mot[i]>D->lettre)

D=D->suivant;

fintantque

si mot[i]=D->lettre alors

 D=D->bas;

i=i+1;

sinon return -1;

fintantque

si ( i=mot.lenght()) et (D->definition!=Null) alors

return D->definition;

sinon return -1

finsi

---------------------------------------------------------------------------------------------------------------------

supprimer(&R, mot[30])

D=recherche(&R, mot[30])

si (D!=Null)

alors

si  D->bas!=Null

    alors D->definition=Null;

sinon tantque ((D->haut->definition)!=Null) et ((D->haut->suivant)!=Null)

free(D); 

3. Ecrans de saisie:

Menu principal:

Ajout d’un mot:

Recherche d’un mot:

Suppression d’un mot:

Quitter le programme :

 Conclusion :

L’élaboration de ce programme permet d’étudier profondément les arbres comme structure et outil puissant dans la gestion de grandes tables de données. L’introduction de la gestion dynamique de la mémoire nous a permis de gérer d’une façon optimale l’occupation de la mémoire et mettre en évidence la force des pointeurs.

Pour télécharger le code source du programme

Read More

Exercice UML : publiphone

UML-Etude des cas

Cette étude de cas concerne un système simplifié de Publiphone à pièces.

1- le prix minimal d’une communication interurbaine est de 2 francs

2- après l’introduction de la monnaie, l’utilisateur a deux minutes pour composer son numéro (ce délai est décompté par le standard).

3- La ligne peut être libre ou occupée.

4- Le correspondant peut raccrocher le premier.

5- Le publiphone consomme de l’argent dès que l’appelé décroche et à chaque unité de temps (UT) générée par le standard.

6- On peut ajouter des pièces à tout moment.

7- Lors du raccrochage, le solde de monnaie est rendu.

Identification des acteurs:

- Utilisateur

- Standard

- Correspond

- Publiphone

- Appelé

Description graphique des cas d'utilisation:

Read More