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

Réalisation d'un éditeur de texte en utilisant les listes chaînées

I- Le cadre général :

a.      But du Mini-projet:

Ce projet consiste à concevoir un éditeur de texte contenant les fonctionnalités de base communes à tous les éditeur en utilisant les listes  chaînées.

b.      Présentation du sujet :

Un éditeur de texte est un logiciel destiné à la création et l'édition de fichiers textes. Chaque système d'exploitation fournit un éditeur, tant son usage est courant, voire incontournable pour certaines tâches (souvent informatiques (administration de système et développement logiciel)).

                      

Les éditeurs de texte se divisent en deux catégories:

·         Les éditeurs plein écran (ou full-screen),

·         Les éditeurs en mode caractère.

Un éditeur plein écran n'interagit avec l'unité centrale que lorsqu'elle est pressée une touche comme Entrée ou l'une des touches de fonction (Fn) ou d'action (PAn) du terminal. Le reste du temps, ce sont les capacités d'insertion native fournies par l'unité de contrôle du terminal qui permettent l'ajout, la suppression ou l'insertion de caractères dans toutes les lignes affichées sur l'écran.

c.      Quelques opérations de base :

Les fonctionnalités les plus élémentaires d'un éditeur sont:

      

-          Ouvrir un fichier (en proposant parfois une liste de fichiers récemment ouverts, ou déjà existants, voire en permettant de restreindre cette liste par un filtre)

-          Ajouter du texte dans une ligne, ou des lignes dans un fichier

-          Ôter des caractères dans une ligne, ou des lignes d'un fichier

-          Rechercher/remplacer une chaîne texte (la recherche n'est pas toujours disponible).

-       Sauvegarder le fichier, ou au contraire sortir en renonçant aux modifications (en cas de grosse erreur comme un effacement involontaire de texte).    

d.     Analyse générale :

Editer un texte semble très intuitif à toute personne sachant utiliser un ordinateur et un éditeur. Du point de vue d’un programmeur, il faut penser à toutes les fonctionnalités que doit proposer un tel programme. De l’ouverture d’un fichier à sa sauvegarde, en passant par les différentes opérations possibles sur le texte et l’annulation de celles-ci. Toutes ces fonctionnalités s’appliquent à des données.

Les fonctionnalités de l'éditeur à réaliser :

Parmi celles-ci certaines sont « indispensables » au bon fonctionnement de l'éditeur et au respect du cahier des charges. En voici une synthèse :

·    Ouvrir ou créer un fichier ;

·         Sauvegarde du fichier sous ;

·         Sauvegarde du fichier si le fichier existe déjà ;

·         Insertion du texte à la position courante ;

·         Suppression du texte à la position courante ;

·         Ajouter du texte après la ligne courante ;

·         Donner la position du curseur ;

·         Faire la recherche ;

·     Et d’autres fonctionnalités….

Un éditeur de texte porte bien son nom : son rôle est en effet d’éditer du texte… La donnée fondamentale est donc un texte. Texte qui peut provenir d’un fichier chargé en mémoire, ou qui peut également être créé de « toute pièce » dans l’éditeur.

                        

Afin que cet éditeur puisse servir de manière effective,il faut disposer de données persistantes qui permettent de stocker de manière définitive ce texte (dans un fichier). Lors de son chargement en mémoire, le texte est placé ligne par ligne dans une liste chaînée et devient une donnée résidente jusqu’à un nouvel enregistrement.

En dehors du texte, des données relatives aux opérations que l’on veut effectuer sont indispensables : les coordonnées x et y de la position courante par exemple. Nombre de lignes et nombre de caractères dans la ligne courante sont également des données q'on aura besoin d’extraire du texte.

Un dernier type de données est utilisé, il s’agit de la liste des commandes acceptées et reconnues par l’interpréteur de commande. Ces données sont réunies dans une liste les faisant correspondre aux fonctions voulues. On traite ces données en les comparants à une saisie de l’utilisateur.

II- Architecture de l'application :

Lors du lancement du programme, on obtient la fenêtre suivante qui demande soit d’ouvrir un fichier existant soit la création d’un nouveau fichier. Cette opération aboutira à la création d’une liste doublement chaînée contenant le texte en cours d’édition, chaque ligne étant rattachée à celle la précédant et à celle la suivant.

Une fois cette opération effectuée, Une fenêtre de saisie s’ouvre, permettant de d’éditer le texte avec toutes les fonctionnalités habituelles de déplacement du curseur ou des lignes, de la saisie du texte ou encore sa suppression.

Lorsqu’on clique sur ECHAP,  un prompt «  EDITEUR> » s’affiche nous permettant de saisir la fonctionnalité qu’on veut  effectuer. La plus simple étant « help » ; l’aide nous permet de consulter les différentes commandes relatives à chaque fonctionnalité disponible sur notre éditeur.

Ainsi, l’utilisateur peut saisir les commandes qu’il désire suivies éventuellement de leurs paramètres. Ces commandes appelleront les fonctions voulues afin qu’elles s’exécutent et laissent à nouveau la place à l’interpréteur de commande, déjà prêt pour la commande suivante. 

Les fonctions réalisant des opérations sur le texte reçoivent toutes un pointeur sur la liste doublement chaînée. Elles peuvent être appelées les unes à la suite des autres. 

En fin d’édition, il pourra être utile de sauvegarder les modifications du texte dans un fichier.

Lire  la  suite    

Read More

Réalisation d'un éditeur de texte en utilisant les listes chaînées(suite)

III- Analyse détaillée:

3.1 - Présentation et justification de la structure :

Afin de stocker le texte en mémoire, on a utilisé deux structures représentant respectivement les caractères et les lignes:

Les caractères :

Les lignes : 

    Différentes structures de données auraient pu être utilisées mais la plus simple s’est avérée être deux listes doublement chaînées, permettant d’accéder à tous les caractères stockés via un compteur tout en restant liés aux caractères précédents et suivants.

3.2 – Présentation et justification des fichiers :

Les fichiers que peut ouvrir cet éditeur n’obéissent à aucun format particulier. Il est cependant logique d’ouvrir des fichiers ASCII, qui contiennent du texte brut. Cependant nous n’avons pas fixé de barrières : avec ou sans extension, d’un *.txt à un *.c ou *.exe, tous les fichiers peuvent être chargés. Il suffit d’en indiquer le nom complet accompagné de l’extension éventuelle.

3.3 – Architecture détaillée :

On a séparé le code source du projet en plusieurs modules, réunis autour d’une fonction principale « main ». On va ici vous présenter l’architecture de ce découpage modulaire :

3.4  – Description des modules :

a.      main :

Le rôle de la fonction main est axé essentiellement sur l’initialisation des différents modules composant cet éditeur, en plus de l’ouverture du fichier directement à partir du système d’exploitation ou le chargement du fichier si on l’ouvre à partir de l’application proprement dite.

b.      Structure de donnée :

Ce module comporte les structures qui mettent en place les listes doublement chaînées déjà citées.

c.     Opérations élémentaires   :

Ce module assure la gestion élémentaire de l’éditeur du texte, ceci via la gestion du fichier et celle des structures

·         Gestion du fichier : Cette opération consiste au chargement du fichier et l’enregistrement des caractères dans la structure d’une part. Et, lors d’une opération de sauvegarde, enregistrer les caractères dans le fichier à partir de la structure, d’autre part.

·         Gestion des structures : Ce fichier comprend :

o    une fonction qui assure l’ajout des lignes ajouterLigne(ptr_ligne *ligneEnCour),

o    une autre fonction qui assure leur surpression supprimerLigne(ptr_ligne *ligneEncour )

o   Une troisième qui permet l’insertion du caractère avant le caractère en cours ajouterCaractere(ptr_ligne *LigneEnCour, ptr_charLigne *charEncour,long val),

o    une qui  libère l’espace du caractère en cour de la structure et renvoi au caractère suivant supprimerCaractere(ptr_ligne *premiereLigne, ptr_ligne *LigneEnCour, ptr_charLigne *charEncour) ;

 o   Une fonction qui effectue la recherche d’un mot depuis le 1^er caractère jusqu’au dernier, rechercherMot(ptr_charLigne *charDebut, ptr_charLigne charFin, ptr_ligne *r *mot),

o   Et une dernière qui permet de remplacer un mot donné par l’utilisateur par un autre au choix, remplacerMot(ptr_ligne *premierLigne,ptr_ligne *ligneEnCour, ptr_charLigne *CharEnCour, char *mot, char *mot2,ptr_charLigne dernierChar,ptr_buffer *lebuffer).

d.      Module pleine page :

En plus du sous modèle qui permet de gérer le curseur en fonction des flèches et autres, Ce module comprend :

·         Module pleine page : qui contient 4 fonctions qui gèrent les actions propres aux touches:

o   ‘ del’ qui permet de supprimer le caractère où est basé le curseur ;

o   ‘retour’ ou ‘ß’ qui permet de supprimer le caractère à gauche du curseur avec le même principe de la touche ‘del’ seulement avec des conditions différentes ;

o   ‘ajouter caractère’ qui permet d’ajouter le caractère saisie su r l’emplacement de celui-ci tout en le déplaçant vers la droite ;

o   ‘entrée’ qui permet de créer une nouvelle ligne et de faire passer les caractères après le curseur à la ligne.

e.        Module commande :

Ce module permet de gérer les fonctionnalité basées sur un jeu de commandes (relatées dans le help), et ceci grâce au :

·         Menu commande  qui comprend une fonction Menucommande( ) qui permet, après récupération de la commande , d’assurer sa traduction, avant de passer à l’exécution en cas d’absence d’une erreur de syntaxe.

·         Module commande :qui contient les différentes fonctions traitant chaque commande à part. dont voici la liste :

Ce module joue un rôle essentiel quand à la sauvegarde temporaire de la saisie avant que l’utilisateur décide d’enregistrer lui-même. En effet, on a représenté ce buffer sous forme d’une structure de pile :

h.      Module Conio :

Ce module, comporte les différentes fonctions assurant des fonctionnalités techniques dont on a eu besoin pour la bonne exécution de notre éditeur ;

Exemple: la fonction gotoxy( ).

Pour télécharger le code source de l'application

Read More