Expressions (cours 1-2)
Que valent les expressions (quotient 18 5) et (/ 18 5) ?
Quand utilise-t-on quotient plutôt que / ?
Traduire en Scheme la phrase : n-2 est divisible par 5
Comment écririez-vous une expression équivalente à (or (not a) b) avec un if ?
Quelle est la valeur de l'expression (number? (/ 1 0)) ?
Quelle est la valeur de l'expression (and (integer? pi) (number? (/ 1 0))) ?
Quelle est la valeur de l'expression (lambda (x) (+ 2 3)) ?
Quelle est la valeur de l'expression ((lambda (x) (+ 2 3)) 4) ?
Donnez une expression dont la valeur soit un entier impair aléatoire de l'intervalle [1,100].
Programmez une fonction (moy f g) prenant deux fonctions f et g : R --> R, et retournant la fonction réalisant la moyenne des deux. SOLUTION
Fonctions_élémentaires_1 (cours 1-2)
Programmez la fonction Scheme foo qui à deux réels x et y associe le minimum entre la moitié de x et la racine cubique de la moyenne de x et y. Par exemple, (foo 2.5 6) donne 1.25. SOLUTION
Fonctions_élémentaires_2 (cours 1-2)
Le lambda-calcul [ne pas lire ceci], cité en amphi, est une théorie mathématico-logique n'utilisant que les fonctions pures comme éléments de base pour construire l'arithmétique, et utilisée en informatique théorique. On trouve dans un manuel de lambda-calcul les deux définitions suivantes :
(define (foo a b) (lambda (k) (k a b))) (define (pi1 f) (f (lambda (x y) x)))
A votre avis, à quoi servent ces fonctions ? Quelle structure mathématique implémentent-elles ? Trouvez celle qui manque... SOLUTION
Structures (cours 1-2)
a) Une voiture a un modèle, un prix, et une puissance fiscale. Définissez le type voiture sous la forme d'une structure.
b) Quelles sont les fonctions automatiquement créées par Scheme suite à cette définition ?
c) Définissez la voiture de James Bond : c'est une Aston-Martin DB5 (de 1963), coûtant 217000 euros, et d'une puissance fiscale de 13 CV.
d) Comment demanderiez-vous le prix de cette voiture en Scheme ? SOLUTION.
Image_1 (cours 1-2-3)
Dessinez sur papier l'image suivante :
(define img
(local [(define c (circle 20 'solid "red"))]
(frame (rotate 45 (beside c (above c (scale 2 c) c) c)))))
Image_2 (cours 1-2-3)
Définissez en Scheme les deux images du cours 3 page 14. SOLUTION
Animation_à_une_variable_1 (cours 1-4)
Programmez une fonction (animation1) dont l’effet est le suivant. Dans une scène carrée de côté 300, une petite balle rouge de rayon 5 va du point A au point B puis au point C en suivant la diagonale en pointillé ci-dessous, et à vitesse raisonnable, qu’on ait le temps de voir… L’animation stoppe dès que la balle arrive au point C. SOLUTION.
Animation_à_une_variable_2 (cours 1-4)
Programmez l’animation suivante (animation2) dans une scène carrée jaune de côté 300. Une particule gonflable naît à un endroit quelconque de la scène [pas trop près des bords !], sous la forme d’un cercle de rayon 0 et de bord rouge. A chaque top d’horloge, le rayon du cercle augmente d’un pixel. L’animation stoppe dès que le cercle touche l’un quelconque des bords de la scène. SOLUTION.
Animation_à_une_variable_3 (cours 1-4)
Programmez une animation (pendule angle). Dans un canvas jaune carré de côté 300, un pendule
de longueur 100 est accroché à un clou situé au centre du canvas. A son extrémité se trouve une balle
rouge de rayon 15. Ce pendule a pour période 1 seconde, et l'animation se déroule à la fréquence par
défaut de 28 images/secondes. Elle ne stoppe pas.
Indication : Il ne s'agit pas de résoudre les équations différentielles de la physique (brrr)
mais de faire de la simulation vidéo. Pour exprimer la périodicité du mouvement, on supposera que le
mouvement du pendule est sinusoïdal. Si l'on note theta l'angle avec la verticale,
il varie donc entre angle et -angle, où angle est exprimé en radians.
Il suffit d'exprimer que theta est une fonction sinusoïdale du nombre de tops d'horloge, de la
forme theta = a sin(k t), et nous vous laissons calculer k pour avoir la bonne période...
Le Monde sera donc le numéro t du top d'horloge.
Voici l'animation (pendule (/ pi 6)).
SOLUTION.
Animation_Struct_1 (cours 1-4)
Programmez une fonction (animation4) dont l'effet est le même que (animation1), mais la balle fait des aller-retours entre A et C en passant par B ! L'animation ne s'arrête jamais. SOLUTION.
Animation_Struct_2 (cours 1-4)
Programmez une fonction (animation5 n) affichant exactement n petits carrés rouges de côté 20 à des endroits aléatoires d'une scène noire de dimension 200 x 200. On verra apparaître un rectangle par seconde, et on n'effacera pas les rectangles déjà affichés. Voici l'animation avec n=10 :
N.B. Il se peut que dans la structure du Monde, vous ayez un champ qui soit une image [ce qu'il faut en principe éviter]. Pour éviter d'avoir une image comme champ de la structure, utilisez la liste des rectangles déjà obtenus [et du coup il n'y a plus besoin de structure, comme dans animation3]. SOLUTION.
Animation_Struct_3 (cours 1-4)
Dans un canvas 400 x 400, programmez l'animation d'une balle rouge de rayon 20 se promenant sans stopper sur la courbe de Lissajou [utilisée en électronique], dont les équations paramétriques sont pour t ≥ 0 :
x(t) = 200 + 150 sin(3t), y(t) = 200 + 150 sin(2t)
On veut voir la trajectoire, et la balle continue à la parcourir indéfiniment. Ne regardez pas la SOLUTION avant d'avoir passé les difficultés (il y en a)...
Animation_Struct_4 (cours 1-4)
Allez, un peu de physique (très important pour les jeux vidéo !)... Petits veinards, vous allez programmer une animation (ressort k F) illustrant le mouvement oscillant d'un ressort de longueur au repos L = 150 dans un canvas 300 x 100 jaune. Le ressort est dessiné sous la forme d'un rectangle horizontal rouge de hauteur 20 qui va à chaque top d'horloge se comprimer ou se dilater suivant sa distance à sa position de repos. La physique (loi de Hooke) donne l'accélération de l'extrémité libre (droite) du ressort : a = -k*x où x est la distance (positive ou négative) à la position de repos. La technique est régulière : l'abscisse de l'extrémité libre avance du vecteur vitesse à chaque top d'horloge et la vitesse se prend une accélération. Un ressort est caractérisé par sa raideur k proche de 0 (raide). On ajoute de plus un coefficient de frottement F entre 0 et 1 (aucun frottement) qui va être multiplié à la vitesse pour amortir l'oscillation et éviter un mouvement perpétuel. A vous ! SOLUTION.
Récurrence_Nombres_1 (cours 1-5)
On considère la fonction mystere définie ci dessous. Quelles sont les valeurs retournées par (mystère 1) ? (mystère 11) ? (mystère 157) ? Plus généralement, expliquez ce que retourne (mystère n) pour un nombre entier n > 0. SOLUTION.
(define (mystère n)
(if (< n 2 )
n
(+ (modulo n 2) (* (mystère (quotient n 2)) 10))))
Récurrence_Nombres_2 (cours 1-5)
a) Programmez une fonction récursive (sommePuissance x n) qui retourne la somme 1+x+x2+…+xn-1+xn.
b) Ecrire une fonction non récursive (sommePuissance2 x n) qui fasse le même travail. On utilisera une formule remarquable sur les suites géométriques.
c) Ecrire une variante (fonctionSommePuissance n) de telle sorte que l’appel à ((fonctionSommePuissance n) x) retourne la même valeur que (sommePuissance x n). SOLUTION.
Récurrence_Nombres_3 (cours 1-5)
Programmez une fonction (binomial n p) prenant deux entiers n et p tels que 0 ≤ p ≤ n, et retournant la valeur du coefficient du binôme C(n,p) situé en ligne numéro n et colonne numéro p du triangle de Pascal. Les lignes et colonnes sont numérotées à partir de 0. On n'effectuera aucune multiplication, uniquement des additions et soustractions ! SOLUTION.
1
1 1
1 2 1 ; par exemple C(3,1) = 3 et C(4,2) = 6
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
.......
Récurrence_Images_1 (cours 1-5)
a) Vous n'avez pas vu en cours la primitive (triangle c). Soit T l'image produite par (triangle 16). Consultez la doc en ligne sur cette fonction, puis visualisez l'image T au toplevel.
b) Certains livres sur les fractales montrent le
triangle de Sierpinsky.
Montrez qu'il est très facile (3 lignes) de le construire par récurrence en Scheme, avec des images, en définissant une
fonction récursive (sierpinsky n).
On remarquera qu'un triangle de Sierpinsky de niveau n est constitué :
- si n = 0, du triangle T tout seul.
- si n > 0, de trois triangles de Sierpinsky de niveau n-1, bien disposés.
d'où la récurrence, comme ils disent... Voici par exemple les triangles de Sierpinsky de niveau 3 puis 4 :
> (sierpinsky 3)
> (sierpinsky 4) ; Non, ne regardez pas la SOLUTION, vous POUVEZ le faire !
Cette structure fractale se retrouve dans la nature, et les spécialistes des automates cellulaires la connaissent bien...
Récurrence_Images_2 (cours 1-5)
Programmez une fonction (rectangles n) dont le résultat est l'image finale produite par l'animation ci-dessus, formée de n carrés rouges aléatoires dans une scène noire. On n'utilisera pas d'animation (donc aucun big-bang), mais une fonction récursive locale pour calculer l'image. SOLUTION.
Récurrence_Images_3 (cours 1-5)
Programmez une fonction (cercles n r) retournant une image constituée de n cercles tangents sur leur bord gauche, comme dans la figure ci-dessous. Le plus petit cercle est de rayon r, et les rayons augmentent de 5 en 5. Par exemple, avec (define C (cercles 6 30)), la valeur de C serait l’image : SOLUTION
Récurrence_Listes_1 (cours 1-6)
Ecrivez une fonction (entiers n x) qui retourne la liste des n premiers entiers à partir de l’entier x.
a) En une ligne en utilisant la fonction build-list
b) De manière récursive enveloppée sans utiliser la primitive build-list. SOLUTION.
Récurrence_Listes_2 (cours 1-6)
Ecrivez une fonction (bégaie L) qui fait bégayer une liste L :
(begaie ’(je suis un peu affamé)) --> (je je suis suis un un peu peu affamé affamé)
puis une fonction (débégaie LB) qui prend une liste LB résultat d'un appel à bégaie, et qui rend la liste avant le bégaiement : SOLUTION
(débégaie ’(je je suis suis un un peu peu affamé affamé)) --> (je suis un peu affamé)
Récurrence_Listes_3 (cours 1-6)
Ecrivez une fonction (insérer x L n) prenant un entier n dans [0, length(L)], et retournant une liste obtenue en insérant x dans L, de sorte que x soit en position n dans le résultat. SOLUTION
(insérer '? '(a b c d e f) 4) --> (a b c d ? e f) (insérer '? '(a b c d e f) 6) --> (a b c d e f ?) (insérer '? '(a b c d e f) 0) --> (? a b c d e f)
Récurrence_Listes_4 (cours 1-6)
a) Ecrivez une fonction (diviseurs n) prenant un entier n > 0 et retournant la liste des diviseurs de n dans [1,n]. Exemple :
(diviseurs 20) --> (1 2 4 5 10 20)
b) En déduire un prédicat (premier? n) exprimant que l'entier n est un nombre premier. On rappelle qu'un entier n est premier s'il est > 1 et si ses seuls diviseurs sont 1 et n.
(list (premier? 21) (premier? 23)) --> (#f #t)
c) Que pensez-vous de l'efficacité de la fonction premier? ainsi définie ? SOLUTION
Récurrence_Listes_5 (cours 1-6)
Programmez une fonction (dégraisser n L) prenant un entier n et une liste L d'entiers, et retournant deux résultats sous la forme d'une liste (L1 k) où L1 est une liste obtenue à partir de L en supprimant tous les multiples de n, et où k est le nombre de multiples supprimés. On utilisera une récurrence enveloppée, donc non itérative ! SOLUTION
(dégraisser 3 '(8 9 4 3 6 1 0 7 12)) --> ((8 4 1 7) 5)
Récurrence_Listes_6 (cours 1-6)
Vous connaissez le Triangle de Pascal, dans lequel chaque élément est la somme des deux éléments qui sont juste au-dessus de lui :
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
etc.
Montrez qu'il est très facile de programmer une fonction (ligne-suiv L) retournant la ligne suivant la ligne L, si chaque ligne est représentée par une liste. SOLUTION
> (ligne-suiv '(1)) (1 1) > (ligne-suiv '(1 4 6 4 1)) (1 5 10 10 5 1)
Récurrence_Listes_7 (cours 1-6)
Programmez de manière récursive enveloppée la fonction (compacter L) prenant une liste L et retournant une copie de cette liste dans laquelle les suites d'éléments consécutifs identiques seront remplacés par une liste à deux éléments contenant l'élément et le nombre de ses apparitions consécutives. SOLUTION
> (compacter '(a a a b b a c c c c a a c)) ((a 3) (b 2) (a 1) (c 4) (a 2) (c 1))
Système_de_Particules_1 (cours 1-7)
Programmez l'animation du système de particules suivant. Une particule (aiguille) est un segment de taille aléatoire mais fixe joignant deux points du canvas graphique jaune 300 x 300. A chaque top d'horloge, les extrémités de chaque segment vont subir une même petite translation d'un vecteur (dx,dy) dont les composantes sont dans [-3,3], donnant ainsi l'impression d'une vibration des aiguilles. Attention, les aiguilles ne changent pas de longueur. L'animation stoppe au bout de 15 secondes. FAITES-VOUS PLAISIR, NE LISEZ PAS LA SOLUTION !
Système_de_Particules_2 (cours 1-7)
Aucune indication, il s'agit de balles soumises à la gravitation, avec un effet plutôt visqueux illustrant l'action du GC (Garbage Collector) chargé d'évacuer régulièrement tous les objets devenus inutiles et qui encombrent la mémoire de Scheme (ou de Java, Python, etc)... Brodez là-dessus, entraînez-vous ! SOLUTION
Système_de_Particules_3 (cours 1-7)
Téléchargez le fichier arbre_nu.png qui vous servira de fond pour l'animation suivante. Il s'agit de placer des feuilles dans l'arbre (voir la vidéo) puis de les faire tomber lentement avec de légers mouvements de rotation lors de la chute. Une feuille sera définie par une structure :
(define-struct feuille (x y img)) ; img est l'image de la feuille, rotation d'une petite ellipse marron fixe
Vous allez commencer par programmer une petite animation préliminaire vous permettant de cliquer à la souris sur tous les endroits de l'arbre où vous souhaitez placer une feuille (j'en ai pris 165 dans la vidéo). Cette première animation (qui ne servira plus dans la suite) vous permet de récupérer la liste de tous les points (x,y) de l'arbre où vous avez cliqué. Vous programmez ensuite l'animation d'un système de particules dont les particules ne sont autres que les feuilles qui tombent en partant des positions choisies à la souris.
SOLUTION.
Animation_à_une_variable_avec_liste_et_souris (cours 1-7)
Programmez l'animation suivante (animation3 n). Dans une scène carrée de côté 200, l'utilisateur va choisir n points avec la souris. A chaque point cliqué, un petit disque rouge de rayon 2 est dessiné. Lorsque les n points auront été choisis, l'animation stoppe et le résultat du big-bang est le monde final : la liste des n points choisis, sous la forme (p1 p2 ...) où chaque point pi sera représenté au choix par une liste à deux éléments (x y) ou par une structure de type posn comme ci-dessous. Attention, le premier point cliqué sera le premier élément de la liste. SOLUTION.
BONUS : reliez aussi les points dans l'ordre où ils ont été cliqués, pour voir le polygone choisi [qui ne se referme pas]...
Programmation Audio (cours 1-7+Audio)
Les premiers hackers américains des années 1960 (LA référence : Levy avec un prolongement ici) ont inventé le phreaking : piratage des téléphones. La pression d'une touche sur un clavier de téléphone produisait un son à une fréquence spécifique. A condition d'avoir mis une pièce ! Mais si l'on savait produire les sons à l'exacte fréquence sans mettre de pièce, on pouvait téléphoner gratuitement... On en trouve un exemple à l'écran dans l'excellent film War Games. Et Wozniak lui-même, génial créateur du premier ordinateur Apple-I avait inventé sa blue box à 16 touches pour téléphoner. N'essayez même pas, le cryptage a bien changé depuis l'époque des hackers du MIT ! Nous utilisons ci-dessous le code DTMF. Techniquement, chaque touche d'un téléphone correspond à un couple de deux fréquences audibles qui sont superposées. DTMF utilise huit fréquences bien distinctes (pas d'harmoniques) permettant de coder les seize touches. Voici les paires de fréquences DTMF pour chaque chiffre de 0..9 :
(define DTMF '((1 697 1209) (2 697 1336) (3 697 1477) (4 770 1209)
(5 770 1336) (6 770 1477) (7 852 1209) (8 852 1336)
(9 852 1477) (0 941 1336))) ; Pourquoi ? Voir la page Web DTMF
a) Programmez une fonction (chercher k DTMF) retournant la liste (f1 f2) des deux fréquences associées au chiffre k dans la table DTMF. Par exemple : (chercher 3 DTMF) --> (697 1477).
b) Programmez une fonction (chiffres->sons L) prenant une liste L d'entiers de 0..9, et retournant la liste des sons correspondants à chacun de ces entiers. Chaque son sera obtenu en superposant les deux fréquences et les sons seront séparés par un petit silence de 3000 échantillons. Pour générer les tonalités sinusoïdales, vous chercherez dans la doc de rsound la fonction make-tone. Exemple :
> (chiffres->sons '(2 5 0)) (#(struct:rsound #0 11000 #i44100.0) #(struct:rsound # 0 3000 44100) #(struct:rsound # 0 11000 #i44100.0) #(struct:rsound # 0 3000 44100) #(struct:rsound # 0 11000 #i44100.0) #(struct:rsound # 0 3000 44100))
c) Vous pouvez maintenant en déduire en une ligne une fonction (phone L) jouant la suite des sons nécessaires à l'obtention du numéro de téléphone contenu dans la liste L. Hey dude, just hack it, it's magic ! Looking at the SOLUTION ? No way !
> (phone '(6 1 7 2 5 3 5 8 5 1)) ; MIT Artificial Intelligence Lab phone number, what else ? "played sound"
Itération_Nombres_1 (cours 1-8)
La fonction locale iter ci-dessous est-elle itérative ? Expliquez pourquoi. SOLUTION
(define (mystère x) ; on suppose x entier > 0
(local [(define (iter x acc)
(cond ((= x 0) acc)
((even? x) (iter (- x 1) (+ acc 1)))
(else (+ 1 (iter (- x 1) acc)))))]
(iter x 0)))
Itération_Nombres_2 (cours 1-8)
Programmez une fonction itérative ($exp x n) retournant l'approximation suivante de la fonction exponentielle au point x, par un développement limité à l'ordre n. Il est interdit d'utiliser une fonction factorielle séparée [ce serait en effet peu efficace, pourquoi ?]. SOLUTION
1 + 1/1! + 1/2! + 1/3! + 1/4! + ... + 1/n!
> ($exp 1 12) ; approximation par des nombres rationnels 260412269/95800320 > ($exp #i1 12) #i2.7182818282861687 > (exp 1) #i2.718281828459045
Itération_Images_1 (cours 1-8)
Programmez une fonction (image2 n) dont le résultat est l'image finale produite par animation5, formée de n carrés rouges aléatoires dans une scène noire. On n'utilisera pas d'animation [donc aucun big-bang], mais une itération locale pour calculer l'image. SOLUTION
Itération_Images_2 (cours 1-8)
Définissez une variable RECT-DEGRAD dont la valeur soit un rectangle de longueur 256 ayant une couleur variant du bleu pur à droite au rouge pur à gauche, avec les 256 nuances intermédiaires. SOLUTION
> RECT-DEGRAD
Itération_Images_3 (cours 1-8)
Programmez une fonction (image3 N) dont le résultat est l'image d'un canvas bleu de taille 200 x 200, et contenant N cercles blancs aléatoires mais NE SE COUPANT PAS ! SOLUTION
> (image3 10) ; 10 cercles aléatoires ne se coupant pas !
Itération_Listes_1 (cours 1-8)
Programmez les fonctions (bégaie L) et (débégaie LB) de Récurrence_Listes_3 mais avec des fonctions locales itératives, avec un accumulateur. SOLUTION
Itération_Listes_2 (cours 1-8)
On s'intéresse à des listes de points du plan sous la forme ((x y) ...). Programmez itérativement une fonction (moyx&maxy LP) prenant une liste de points LP et retournant une liste (mx ymax) où mx est la moyenne des abscisses de tous les points de L, et ymax le maximum des ordonnées. Attention, on calculera ces deux quantités en un seul passage sur la liste ! SOLUTION
(moyx&maxy ’((5 8) (3 -2) (7 10) (3 6))) --> (9/2 10)
Itération_Listes_3 (cours 1-8)
Résoudre l'exercice (dégraisser n L) de Récurrence_Listes_5 mais avec une fonction locale itérative, avec deux accumulateurs. SOLUTION
Itération_Listes_4 (cours 1-8)
Résoudre l'exercice (compacter L) de Récurrence_Listes_7 mais avec une fonction locale itérative. SOLUTION
> (compacter-iter '(a a a b b a c c c c a a c)) ((a 3) (b 2) (a 1) (c 4) (a 2) (c 1))
Itération_Listes_5 (cours 1-8)
LA DECOMPOSITION EN FACTEURS PREMIERS. On se propose de programmer une fonction (factor n) retournant la liste des diviseurs premiers d'un entier n. Dans l'algorithme utilisé, on cherchera les facteurs premiers de 1 en 1. En considérant le facteur 2 à part, on pourrait aller de 2 en 2 mais bon... Il y a beaucoup d'optimisations possibles, qui ne modifient pas ou peu la [mauvaise] complexité !
VERSION 1
Le résultat est une liste plate [aucun élément n'est lui-même une liste]. On rédige une itération avec 3 variables de boucle : n qui décroit, p qui est le candidat diviseur en cours d'examen, et L qui est la liste déjà produite [et qui contient peut-être déjà p]. SOLUTION
> (factor_v1 1214840) (2 2 2 5 11 11 251)
VERSION 2
Cette fois on regroupe les facteurs premiers identiques en donnant leur exposant. Plutôt que de retravailler le résultat de factor_v1, on va produire directement une liste de couples [ce que l'on nomme une A-liste]. On introduira une 4ème variable de boucle e représentant le nombre de fois que le facteur premier p a été déjà rencontré. SOLUTION
> (factor_v2 1214840) ((2 3) (5 1) (11 2) (251 1))
N.B. Ces algorithmes ne sont pas efficaces pour de grands nombres. Les méthodes pour attaquer des nombres à plusieurs dizaines de chiffres utilisent des mathématiques un peu plus sophistiquées [exercice 6.8.13 du livre de cours PCPS]...
OrdreSup_Listes_1 (cours 1-9)
Calculez en une ligne le produit des nombres impairs de [1,50]. SOLUTION
Réponse : 58435841445947272053455474390625
OrdreSup_Listes_2 (cours 1-9)
Programmez un prédicat (every? pred L) prenant un prédicat unaire pred et une liste L, et retournant true si et seulement si tous les éléments de L vérifient pred. SOLUTION
(every? number? '(3 6 2 1 8)) --> #t (every? number? '(3 6 2 toto 8)) --> #f (every? (lambda (x) (> x 0)) '(3 6 2 1 8)) --> #t
N.B. La fonction primitive andmap de Racket peut remplacer every?. Regardez dans la doc en ligne...
Arbres_1 (cours 1-10)
Programmez une fonction (sous-arbre? A1 A2) retournant #t si et seulement si l'arbre A1 est un sous-arbre de l'arbre A2 : SOLUTION
(sous-arbre? '(+ x 1) '(* (- (+ x 1) 3) (/ z 2))) --> #t (sous-arbre? '(+ x (* y 2)) (+ x (* y 2))) --> #t (sous-arbre? 'x '(+ (* x 2) 3)) --> #t (sous-arbre? '(+ x 1) '(* (+ x 2) 3)) --> #f
Arbres_2 (cours 1-10)
On s’intéresse aux arbres troués. Un tel arbre est un arbre binaire d’expression dont certaines feuilles sont des trous, des symboles ’?. Exemple d'arbre troué :
(+ (* ? x) (- ? (* 2 ?)))
a) Programmez une fonction (nb-trous A) prenant un arbre troué A, et retournant le nombre de trous.
(nb-trous '(+ (* ? x) (- ? (* 2 ?)))) --> 3
b) Programmez une fonction (remplir A) prenant un arbre troué A, et retournant le même arbre, mais dans lequel chaque trou aura été remplacé par un entier aléatoire de [-5,5]. SOLUTION
(remplir '(+ (* ? x) (- ? (* 2 ?)))) --> (+ (* 0 x) (- 4 (* 2 –1)))
Arbres_3 (cours 1-10)
D'après l'idée d'un étudiant... Etant donné un arbre A et une feuille x, trouver le premier chemin menant de la racine de A à la feuille x. Par chemin, on entend la liste de tous les objets recontrés. On retournera #f si un tel chemin n'existe pas ! Programmez la fonction (chemin x A). SOLUTION
(chemin 3 '(+ (* x (- y 3)) (/ 3 z))) --> (+ * - 3) (chemin 'b '(+ (* x (- y 3)) (/ 3 z))) --> #f
Arbres_4 (cours 1-10)
Programmez une fonction (bilan A) prenant un arbre A et retournant une A-liste dont les clefs sont les opérateurs et les valeurs le nombre d'apparitions de chaque opérateur. SOLUTION
(bilan '(+ (* x (+ y 3)) (/ (- x 2) (- x y)))) --> ((+ 2) (* 1) (/ 1) (- 2))
Calcul_Formel_1 (cours 1-10)
Calculez par programme la liste des coefficients exacts [rationnels] du développement en série de Taylor de l'expression (x+3)/(2x+5) en x=0 à l'ordre 5. Vous programmerez donc une fonction (taylor A x x0 n) retournant la liste des n+1 premiers termes de la série de Taylor en 0, en utilisant les fonctions diff, valeur et fac vues en TP.
• Avec Scheme :
> (taylor '(/ (+ x 3) (+ (* 2 x) 5)) 'x 0 5) ;SOLUTION (3/5 -1/25 2/125 -4/625 8/3125 -16/15625)
• Avec Maxima :
