Méthodologie de la Programmation
Les Projets

Dernier trimestre 2019

Le projets sont à rendre par mail et sous format papier au plus tard le mercredi 4 décembre 2019 à 11h (heure de Paris). Ils seront remis au tout début du cours.

Il faut fournir :

• un rapport composé de l'énoncé, de l'explication des fonctions réalisées et des choix de programmation,
• un listing du programme (c'est-à-dire l'ensemble du code),
• dans la mesure du possible un jeu d'essais sur machine.

NB : lorsqu'une liste de questions est fournie, il est recommandé de les traiter dans l'ordre et surtout de les traiter toutes.

NB: le nombre d'étoiles correspond à la difficulté supposé du projet.

NB : puisque des fonctions ont été fournies en cours, c'est avec elles que votre projet doit être fait. Tout désir d'utiliser des fonctions ou commandes non vues en cours doit faire l'objet d'une demande d'autorisation à l'enseignant.

NBVoici les projets encore non pris à ce jour : 1 2 3 4 5 6 7 8 9 16 17 18 19 21 22 28 29 30 31

Métro

• Construisez des fonctions ou prédicats qui construisent les listes des stations de métro des différentes lignes (vous n'êtes pas obligés de les faire toutes dans un premier temps). On prendra comme exemple le métro de Taipei. Exemple, la ligne Wenhu sera une liste comme :

     '(taipei_zoo muzha wanfang_community wanfang_hospital...)
  

  (les points de suspension ne vous autorisent pas à suspendre).
• Vous pouvez associer les lignes à un numéro si cela s'avère plus pratique.
• Donnez une fonction qui trouve si une station appartient à une ligne.
• Donnez une fonction qui donne la sous-liste des stations d'une ligne entre deux stations données.
• Donnez une fonction de deux lignes L1 et L2 et qui renvoie la liste des stations qui appartiennent aux deux lignes (intersection).
• Donnez une fonction de deux lignes L1 et L2 n'ayant pas d'intersection et qui renvoie la liste des lignes qui les coupent toutes les deux.
• Donnez une fonction qui donne un trajet permettant de joindre deux stations données.
• Donnez une fonction qui donne le trajet le plus court permettant de joindre deux stations données.
• Donnez une fonction qui donne le trajet avec le moins de correspondances permettant de joindre deux stations données.
1. Lisp : métro (*) ( )
   Faire ce travail en Scheme. On prendra comme exemple le métro de Londres .

2. Prolog : métro (*)
   Faire tout ce travail en prolog. On prendra comme exemple le métro de Berlin. On considérera que le mot fonction peut être remplacé sans grand changement par le mot prédicat.

   Grands nombres

   Un grand nombre est un nombre formé de nombreux chiffres. Nous dirons, par exemple, une liste formée d'abord d'un signe et, ensuite, d'une série de chiffres, exemple : '(+ (1 2 3)) pour dire 123.
   
   • Faites un ensemble de fonctions ou prédicats permettant de travailler, de faire tous les calculs arithmétiques classiques, avec de tels grands nombres.
     Exemple en Scheme :

     ? (add_gd_nb '(+ (1 2 3)) '(- (5 0)))
     = (+ (7 3))
     

     (en effet 123 + (- 50) == 73)

     Il faudra sans doute intégrer des calculs comme l'inversion de liste.
     On peut changer la présentation (par exemple demander le premier opérande, puis le second, enfin l'opérateur et afficher le résultat).
     

   • Adaptez un algorithme rapide pour calculer la suite de Fibonacci avec de tels grands nombres (pas la récursivité exponentielle vue en début de semestre !).
     
   • Faites une fonction de sauvegarde permettant de conserver un résultat, comme résultat intermédiaire pour de futurs calculs.
   • Mettre en place une calculatrice de tels grands nombres, avec les opérations classiques mais aussi la sauvegarde, le rappel de valeurs déjà trouvées, etc. Il faut que, pour l'usager, mettre en place un calcul soit facile.

3. Lisp : Grands nombres (*) ( )
   Faire ce projet en Scheme.

4. C : Grands nombres(*)( )
   Faire ce projet en C.

5. Prolog : Grands nombres (*)
   Faire ce projet en Prolog.

   ?- somme([+,1,1,1,1,1,1,1,1,1,1,1,1,2,3],[+,5,5],Xs).
    X = [+,1,1,1,1,1,1,1,1,1,1,1,1,7,8]
    Yes
   ?-
   

6. Python : Grands nombres (*)

   Faire ce projet en python.

   Motif

   • Soit une liste motif et une liste l chercher motif dans l. Exemple scheme :

     ? (cherche '(1 a b) '(2 3 5 1 A b e 4 8 1 a c 9 1 a b 10)) 
     = t 
     

   • Améliorez maintenant votre travail pour compter le nombre d'occurences du motif dans la liste (le nombre de fois que le motif apparait dans la liste).
   • Cherchez le nombre d'occurences de l'inverse du motif.
   • Complétez votre travail pour compter le nombre de fois où le motif apparaît dans la liste, mais de façon discontinue (le 1 puis, un peu plus loin le a, puis un peu plus loin le b sur l'exemple ci-dessus). (chaque lettre ne sert qu'une fois).

     ? (compte '(1 a b) '(2 3 5 1 A a 7 8 b 8 1 a c 9 1 a b 10 b)) 
     = 3
     

   • Ajoutez une fonction qui compte le nombre de fois où tous les éléments du motif apparaissent dans le bon ordre dans la liste, même si, entretemps, il y a eu d'autres valeurs.

     ? (comptefin '(1 a b) '(2 3 5 1 A a 7 8 b 8 1 a c 9 1 a b 10 b)) 
     = 11
     

7. Python : Motif (*) ( )
   Faire le projet motif en Python.

8. Prolog : Motif (*)
   Faire le projet motif en Prolog.

9. Java : Motif (*)
   Faire le projet motif en Java.

   Suite du nombre 8

   Soit la suite suivante:

   	u(0)=8
   si u(i) est pair	u(i+1)=(3 * u(i))/2
   si u(i) est de la forme 4*n+1	u(i+1)=3*n + 1
   si u(i) est de la forme 4*n-1	u(i+1)=3*n - 1

   
   Est-ce que 0 est de la forme 4*n+1 ? Dans ce cas que vaut n ?
   
   Est-ce que 1 est de la forme 4*n+1 ? Dans ce cas que vaut n ?
   
   Est-ce que 2 est de la forme 4*n+1 ? Dans ce cas que vaut n ?
   
   Est-ce que 3 est de la forme 4*n+1 ? Dans ce cas que vaut n ?
   
   Est-ce que 4 est de la forme 4*n+1 ? Dans ce cas que vaut n ?
   
   Est-ce que 5 est de la forme 4*n+1 ? Dans ce cas que vaut n ?
   
   Est-ce que 6 est de la forme 4*n+1 ? Dans ce cas que vaut n ?
   
   Premières valeurs de la suite :
   
   U(0)=8
   
   U(1)=12
   
   U(2)=18
   
   U(3)=27
   
   U(4)=20
   
   U(5)=30
   
   U(6)=45
   
   U(7)=34
   
   1. Faire une fonction ou un prédicat permettant de donner la valeur suivante de la suite. Exemple prolog :

      ?- suivant(8,N).
        N = 12
        Yes.
      ?-
      

   2. Faire une fonction ou un prédicat qui construit la liste des valeurs déjà renontrées.
   3. Faire une fonction ou un prédicat permettant de dire, à propos de cette suite, et d'une valeur X, si X existe dans la suite.
   4. Faire une fonction qui remplit les valeurs de la suite tant qu'elles sont différentes et renvoie la suite ainsi créée dès qu'elles ne le sont plus.
   5. Essayer votre fonction avec différentes valeurs de départ, en particulier 4, puis 44. Quelle sont, dans ces cas, les longueurs de la liste produite ?

10. Lisp : Suite du nombre 8 (**). ( )
    Programmez ces fonctions en Scheme.

11. Java : Suite du nombre 8 (*).
    Programmez ces fonctions en Java.

12. Prolog : Suite du nombre 8 (***).
    Programmez ces fonctions en Prolog.

    Crible d'Eratosthène

    Le crible fonctionne ainsi :

    1. Fabriquer une liste de tous les nombres entiers positifs, sauf 1 (0 n'est pas positif).
    2. Prendre le premier élément de cette liste, p. C'est un nombre premier.
    3. Enlever de la liste tous les multiples de p.
    4. Recommencez les deux dernières opérations, tant que la liste n'est pas vide.
    On a ainsi fabriqué la liste des nombres premiers.
    NB "enlever de la liste" peut être fait sous la forme de "mettre 0 à la place", si cela vous aide.
    Attention au Hors Sujet !
    

13. C : Eratosthène (*) ( )
    Programmez en C le crible d'Eratosthène pour caculer la liste des nombres premiers à partir de la liste de tous les entiers (au moins jusqu'à un rang donné en paramètre).

    a.out
      pour 10 nous avons 2, 3, 5, 7.
    

14. Python : Eratosthène (**) ( )
    Programmez en Python le crible d'Eratosthène pour caculer la liste des nombres premiers à partir de la liste de tous les entiers (au moins jusqu'à un rang donné en paramètre).

    print crible(10)
    [2, 3, 5, 7]
    

15. Lisp : Eratosthène (**) ( )
    Programmez en Scheme le crible d'Eratosthène pour caculer la liste des nombres premiers à partir de la liste de tous les entiers (au moins jusqu'à un rang donné en paramètre).

    (crible 10)
    '(2 3 5 7)
    

    Très grand Fibonacci

    Un grand nombre est un nombre formé de nombreux chiffres. Nous dirons, par exemple, une liste formée d'abord d'un signe et, ensuite, d'une série de chiffres, exemple : '(+ (1 2 3))
    1. Faites la fonction ou le prédicat d'addition de tels nombres.
       Exemple Prolog :

       ?- somme([1,1,1,1,1,1,1,1,1,1,1,1,2,3],[5,5],X).
        X = [1,1,1,1,1,1,1,1,1,1,1,1,7,8]
        Yes
       ?-
       

    2. Faites la fonction ou le prédicat multiplication de tels nombres.
       Attention, la multiplication est à traiter comme une série d'additions.
       Quand on travaille sur la suite de Fibonacci, on se retrouve gérer de très grands nombres qu'il faut, en particulier, additionner ou multiplier.

    3. Écrivez une fonction ou prédicat prolog permettant de calculer valeurs de cette suite pour 30, 100, 1000 ou 100000.

       Il vous est conseillé de développer la méthode rapide ci-dessous :
       Vous avez remarqué que f(n) = f(0).f(n-1) + f(1).f(n-2)
       Donc que :f(n) = (f(0)+f(1)).f(n-2) + f(0).f(n-3)
       Donc que :f(n) = f(2).f(n-2) + f(0).f(n-3)
       Donc que :f(n) = f(3).f(n-3) + f(1).f(n-4)
       Continuez ce calcul jusqu'à arriver à n/2 et vous devriez trouver une méthode très rapide qui permet en particulier de calculer f(n) et f(n+1) en ne faisant qu'un seul appel récursif (de f(n/2) à peu près).

16. Prolog : Fibonacci avec des listes de chiffres(**) ( )
    Faites ce travail en Prolog.

    Shell

    Attention, en shell ne sont autorisées que les commandes vues explicitement en cours et pour lesquelles il n'a pas été dit qu'elles étaient interdites dans les projets.
    De même, les fonctions shell sont proscrites.
    Vos scripts peuvent être itératifs ou récursifs, mais ne peuvent pas contenir de fonction.
    

17. Shell : Vide (**)
    Parcours des répertoires à partir d'un argument. On recherche tous les fichiers vides et on les détruit. Attention, la commande find est proscrite de même que ses avatars.

    On pourra étendre le travail en affichant (et détruisant ?) les fichiers dont la taille est inférieure à une taille donnée.

18. Shell : Core (*)

    Parours des répertoires à partir d'un argument. On recherche tous les fichiers core (il y en a déjà dans vos répertoires:-) et on les détruit. Attention, la commande find est proscrite de même que ses avatars.

19. Shell : Save (* - **)
    Parcours des répertoires à partir d'un argument et recopie de tous les fichiers qu'on y trouve dans un répertoire "~/SAVE"
    

    Améliorez le travail en reproduisant la structure (sous-sous... répertoires) dans le répertoire SAVE.

    Attention, la commande find est proscrite de même que l'utilisation d'options de la commande cp.

20. Shell : Compression/Décompression (***) ( )
    Écrire un shellscript qui parcourt un répertoire donné en argument et ses sous-répertoires et recopie tous les fichiers qui le composent dans un même fichier que l'on pourra compresser grâce à gzip. Attention, les commandes find et tar sont proscrites.
    Faire maintenant le script qui permet de décompresser le fichier obtenu précédemment et de placer son contenu dans un sous-répertoire argument du script.
    

21. Shell : Sauvegarde incrémentale(***) ( )
    On veut parfois faire des sauvegardes incrémentales, c'est-à-dire sauvegarder tous les fichiers (et uniquement les fichiers) qui ont été modifiés depuis la dernière savegarde. Pour cela il faut établir une liste des fichiers qui ont été sauvegardés. Puis, à chaque utilisation, parcourir tous vos sous-répertoires, pour chaque fichier vérifier s'il fait partie de la liste et, sinon, le sauvegarder (c'est-à-dire, pour l'instant, le mettre dans un répertoire SAVE).
    

22. Shell  : Hanoï (**)
    Écrire un shellscript permettant d'afficher la liste des mouvements à faire pour résoudre le problème des Tours de Hanoï pour une valeur donnée en argument.
    On rajoutera la possibilité de définir les noms des trois tours, ou, si ces noms ne sont pas en argument, d'utiliser des noms par défaut.

    Images, animation

    Vous allez devoir présenter un projet dans lequel on verra marcher un pantin simplifié.

    1. Faites une fonction paramétrique pour chacun des membres, le corps et la tête.
    2. Améliorez les fonctions précédentes pour séparer les différentes parties des bras et des jambes.
    3. Faites une fonction mouvement des jambes qui permet de voir les différentes positions des jambes au cours de la marche.
    4. Faites une fonction mouvement des bras qui permet de voir les différentes positions des bras au cours de la marche.
    5. Faites une fonction qui montre le mouvement général de votre pantin marchant.
    6. Si vous avez le temps, vous pouvez dessiner l'arrière-plan de cette marche.

23. Lisp : Animation (**) ( )

24. Python : Animation (**) ( )

    Images, visages

    Vous allez devoir présenter un visage sous différentes formes : cheveux, barbe, lunettes, expression, maquillage...

    1. Donnez une fonction qui dessine un visage paramétrique (il faut pouvoir en changer l'échelle facilement).
    2. Adaptez votre fonction pour modifier chacun des éléments caractéristiques de l'apparence d'un visage.

25. Python : Visages (**) ( )

    Jeu du pendu

    Vous allez devoir présenter un jeu du pendu dans lequel à chaque coup perdu, le pendu s'affiche un peu plus.

    Il faudra que, non seulement l'utilisateur puisse jouer, mais qu'il puisse aussi faire jouer l'ordinateur : c'est, dans ce cas, votre programme qui cherche la solution.

    1. Donnez une fonction qui dessine un pendu, étape par étape.
    2. Mettez en place un jeu du pendu.
    3. Mettez en place un jeu du pendu dans lequel c'est votre programme qui joue et cherche le mot.

26. Python : jeu du pendu (**) ( )

27. Lisp : jeu du pendu (**) ( )

    Divers

28. Lisp : Dérivées (***) ( )
    Une fonction numérique peut être dérivée, n'est-ce pas ? Écrire la fonction derive qui dérive une fonction qui lui est donnée en paramètre. Exemple:

    ? (derive '(+ (* x x) (+ (* x 5) 3)))
    = (+ (* 2 x) 5)
    

    1. Commencer par écrire une fonction qui dérive des fonctions simples, c'est-à-dire dont le premier terme est un +.
       
    2. Améliorez votre fonction pour qu'elle traite également les fonctions dont l'opérateur est une multiplication.
       Il est important de traiter la question des "variables", par exemple de décider que l'on traite, d'abord, uniquement des fonctions à une seule variable et qu'elle se nomme (par exemple) x.
       Ensuite, il faut surtout tout écrire sous une forme générique.
    3. Généralisez votre fonction pour dériver toute fonction numérique.
    
    

29. Postscript : au choix(***)( )
    Faites en postscript l'un des projets ci-dessous (à l'exception des projets Métro, Motif, Shell). Faites-le tourner sur un simulateur ou sur le processeur de l'imprimante.
    La difficulté porte surtout sur le fait d'apprendre un tout nouveau langage non vu en cours...
    

30. LaTeX : Fibonacci (***) ( )
    Écrire un texte LaTeX contenant de nouvelles commandes permettant de :
    calculer la somme des n premiers entiers,
    calculer le produit des n premiers entiers,
    calculer la puissance p d'un entier n,
    calculer le reste de la division entière d'un entier p par un entier n,
    calculer une valeur de la suite de Fibonacci,
    remplacer le numéro de page par le nombre correspondant de la suite de Fibonacci.
    Afficher pour un certain nombre x (argument de la fonction) le nombre de valeurs de la suite de Fibonacci jusqu'à la x-ième incluse qui sont paires. (NB il faudra peut-être créer une fonction parité).

    Exemple :

    	  nbpf (5) = 2
    	

    puisqu'il y a deux nombres pairs parmi 1, 1, 2, 3, 5 et 8.
    

31. LaTeX  : Hanoï (*** à ****)
    Écrire un texte LaTeX contenant de nouvelles commandes permettant d'afficher la liste des mouvements à faire pour résoudre le problème des Tours de Hanoï.
    Pouvez-vous passer à une formulation itérative ?

32. Java  : Hanoï (**)

    Rien de plus facile que de résoudre le problème des Tours de Hanoï en Java
    de façon récursive. Mais ce n'est pas le but de ce projet.

    Écrivez la fonction qui prend un numéro de coup, le nombre de disques et les noms des trois emplacements et qui renvoie le coup à jouer, c'est-à-dire le numéro du disque à déplacer, son emplacement de départ et son emplacement d'arrivée.

    NB Votre fonction doit donner une solution rapidement même s'il s'agit du coup 350 d'un problème avec 15 disques.