Obligement - L'Amiga au maximum

Jeudi 29 juin 2017 - 05:49  

Translate

En De Nl Nl
Es Pt It Nl


Rubriques

 · Accueil
 · A Propos
 · Articles
 · Galeries
 · Glossaire
 · Hit Parade
 · Liens
 · Liste jeux Amiga
 · Quizz
 · Téléchargements
 · Trucs et astuces


Articles

 · Actualité (récente)
 · Actualité (archive)
 · Comparatifs
 · Dossiers
 · Entrevues
 · Matériel (tests)
 · Matériel (bidouilles)
 · Points de vue
 · En pratique
 · Programmation
 · Reportages
 · Tests de jeux
 · Tests de logiciels
 · Tests de compilations
 · Articles divers

 · Articles in english
 · Articles in other languages


Twitter

Suivez-nous sur Twitter




Liens

 · Sites de téléchargements
 · Associations
 · Pages Personnelles
 · Moteurs de recherche
 · Pages de liens
 · Constructeurs matériels
 · Matériel
 · Autres sites de matériel
 · Réparateurs
 · Revendeurs
 · Presse et médias
 · Programmation
 · Développeurs logiciels
 · Logiciels
 · Développeurs de jeux
 · Jeux
 · Autres sites de jeux
 · Scène démo
 · Divers
 · Informatique générale


Jeux Amiga

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Trucs et astuces

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Glossaire

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Partenaires

Annuaire Amiga

Amedia Computer

Relec

Hit Parade


Soutien

N'hésitez pas à soutenir le projet Obligement



Contact

David Brunet

Courriel

 


Programmation : Scheme - les données
(Article écrit par Damien Guichard - avril 2004)


Scheme, ça donne - Partie 2

Rappel des bases du langage Scheme

Scheme est un langage de programmation élégant et expressif qui trouve de nombreuses applications dans l'intelligence artificielle. L'Amiga est depuis très longtemps équipé d'interpréteurs Scheme évolués et d'une étonnante compacité comme Scheme.lha et SIOD.lha qui conviendront à merveille pour tester les exemples qui suivent.

Un rapide rappel des commandes :

(define (succ n) (+ n 1))            ;; la définition de fonction "define"
(succ 0)                             ;; l'appel de fonction "(..)"
(define start 0)                     ;; la définition de variable "define"
(set! start 1)                       ;; l'affectation de variable "set!"
(define (min a b) (if (< a b) a b))  ;; la conditionnelle "if"
(begin (set! a b) (set! b c) c)      ;; la séquence "begin"

Pour plus d'informations voir l'article précédent dans Obligement n°43.

Plus de commandes

#t                     ;; le vrai
#f                     ;; le faux
(or a b)               ;; le "ou" logique
(and a b)              ;; le "et" logique
(abs x)                ;; la valeur absolue
(quotient a b)         ;; division entière: le quotient
(remainder a b)        ;; division entière: le reste
(display "hello")      ;; affiche un texte
(newline)              ;; affiche un retour à la ligne   

Par exemple la somme des "n" premiers entiers :

(define (integers-sum n)
  (quotient (* n (+ n 1)) 2)
)

Les tableaux

(make-vector n)        ;; renvoie un nouveau tableau indicé de 0 à n-1
(vector-ref a i)       ;; renvoie l'élément d'indice "i" du tableau "a"
(vector-set! a i val)  ;; affecte "val" à l'élément "i" du tableau "a"
(display a)            ;; affiche le tableau "a"

Voici en plus une fonction qui permute les deux éléments "i" et "j" d'un tableau "a" :

(define (swap! a i j)
  (define tmp 0)
  (set! tmp (vector-ref a j))
  (vector-set! a j (vector-ref a i))
  (vector-set! a i tmp)
)

Et aussi une qui crée un tableau-interval qui contient tous les entiers de "a" à "b" :

(define (vector-interval a b)
  (set! b (+ b 1))
  (define result (make-vector (- b a)))
  (define i 0)
  (define (loop)
    (if (< a b)
      (begin
        (vector-set! result i a)
        (set! i (+ i 1))
        (set! a (+ a 1))
        (loop)
      )
    )
  )
  (loop)
  result
)

Le moteur d'intelligence artificielle

C'est en fait une routine qui teste toutes les permutations possibles sur un ensemble d'éléments. De nombreux problèmes mettent en jeu un échantillon d'éléments et une règle qui indique quelles permutations sont valides. Ce qu'il nous faut c'est donc une routine qui, étant donnés un échantillon et une règle, affiche toutes les permutations valides. L'échantillon est représenté par le tableau "the-array". La règle est représentée par la fonction "partial-solution?".

(define (total-solution the-array partial-solution?)
  (define (found-solution)
    (display the-array)
    (newline)
  )
 (define (search-solution) 
    (define i top)
    (define (loop)
      (if (< i (vector-length the-array))
        (begin
          (swap! the-array i top)
          (if (partial-solution? the-array top)
            (begin
              (set! top (+ top 1))
              (if (= top (vector-length the-array))
                (found-solution)
                (search-solution)
              )
              (set! top (- top 1))
            )
          )
          (swap! the-array i top)
          (set! i (+ i 1))
          (loop)
        )
      )
    )
    (loop)
  )
  (define top 0)
  (search-solution)
)

Comment procède cette routine ?

C'est en fait plus simple qu'il n'y paraît :
  1. On "swap!" deux éléments, et on teste la règle.
  2. Si la règle est encore vérifiée, alors on cherche l'élément suivant.
  3. Sinon on "swap!" à nouveau les deux éléments pour restaurer l'état antérieur, puis on retourne à l'étape 1.
  4. Quand on a trouvé tous les éléments on affiche le tableau avec "found-solution".
Ce moteur peut maintenant être réutilisé pour toutes sortes de problèmes de permutation.

Le problème des 8 reines

Il consiste à placer 8 reines sur un échiquier sans qu'aucune soit menacée de prise. La règle qui valide une permutation des reines est donc une fonction qui renvoie vrai seulement si aucune reine est menacée. L'échantillon est le tableau "the-array" qui contient la rangée de chaque reine, "top" est le nombre de colonnes à examiner :

(define (partial-queens-solution? the-array top)
  (define q 0)
  (define x 0)
  (define dy 0)
  (define result #t)
  (set!  q (vector-ref the-array top))
  (set!  x (- top 1))
  (define (loop)
    (if (>= x 0)
      (begin
        (set! dy (- q (vector-ref the-array x)))
        (if (or (= (- x top) dy) (= (- top x) dy))
          (set! result #f)
          (begin (set! x (- x 1)) (loop))
        )
      )
    )
  )
  (loop)
  result
)

La fonction "queens-solutions" appelle le moteur de recherche avec l'échantillon et la règle appropriés au problème des "n" reines :

(define (queens-solutions n)
  (total-solution
    (vector-interval 1 n) partial-queens-solution?)
)

Le problème des 8 reines a 92 solutions :

:=> (queens-solutions 8)

Le problème de la pyramide

Il s'agit de créer une pyramide de chiffres consécutifs telle que chaque chiffre est la différence de ses deux chiffres inférieurs, voici par exemple une pyramide à 4 étages :
   3
  2 5
 7 9 4
8 1 10 6

Et maintenant la définition de la règle adéquate :

(define (partial-pyramid-solution? a top)
  (define level 1)
  (define (loop)
    (if (<= (integers-sum level) top)
      (begin (set! level (+ level 1)) (loop))
    ) 
  )
  (loop)
  (if (= top (integers-sum (- level 1)))
    #t
    (=
      (vector-ref a (- top level))
      (abs
        (- (vector-ref a top)
           (vector-ref a (- top 1))))
    )
  )
)

Il ne reste plus qu'à créer l'échantillon et appeler le moteur de recherche "total-solution" :

(define (pyramid-solutions n)
  (total-solution
    (vector-interval 1 (integers-sum n))
    partial-pyramid-solution?)
)

Voyons ce que ça donne à 5 étages, ça peut prendre quelques longues minutes de calcul, mais ça vaut le coup :

:=> (pyramid-solutions 5)
#(5 4 9 7 11 2 8 1 12 10 6 14 15 3 13)
#(5 9 4 2 11 7 10 12 1 8 13 3 15 14 6)
()

Il y n'a qu'une seule solution (et son symétrique bien sûr) :
     5
    4 9
   7 11 2
  8 1 12 10
6 14 15 3 13

En fait, à partir de 6 étages le problème de la pyramide n'a plus de solution.

Pour aller plus loin

Les interpréteurs "Scheme.lha", "SIOD.lha", "scm.lha" et "UMBScheme212.lha", sont tous disponibles sur Aminet dans le répertoire /Dev/Lang.

Deux bons textes d'introduction à Scheme :

mitpress.mit.edu/sicp/
www.scheme.com/tspl2d/index.html

Plus de documentations sur Scheme :

www.schemers.org
www.cs.indiana.edu/scheme-repository/home.html
www.swiss.ai.mit.edu/projects/scheme


[Retour en haut] / [Retour aux articles] [Article précédent]