Jean-Jacques BOURDIN
Le dernier partiel écrit aura lieu le 2/9/2020 en amphi B1. Entre 14h
et 16h. Tout étudiant qui n'a pas encore rendu son propre projet doit
prendre contact au plus vite avec l'enseignant sauf à accepter
d'être compté absent. À partir du 19 août, 14h, de nouvelles séances de révision
seront données sur le serveur Discord (ou sur un BBB). Les liens
seront donnés sur cette page. Dans tous les cas je reste disponible par mail pour toute question. Attention, compte tenu de ce que vous avez fait au second semestre,
le partiel ne contiendra pas de questions sur C ni Prolog.
Une note va donc être affichée sur votre ENT. Elle tient compte de
votre second partiel pour ceux qui l'ont passé ou simplement du
premier. Dans tous les cas, il sera possible de passer un "second partiel" à
la fin des cours de second semestre, à une date que nous fixerons
via un sondage en ligne. Ce nouveau partiel ne pourra pas comprendre de
questions sur C, Prolog ou Java, puisque les cours de programmations
impérative et logique vous auront fait progresser dans ces
domaines. Il y aura donc des questions concernant les langages
suivants :
Dans tout ce cours il faudra, souvent, m'envoyer des messages par email. Vous devrez utiliser votre compte étudiant (etud.univ-paris8.fr), de façon à ce que je puisse vous répondre facilement. Les pièces jointes sont autorisées à condition que les fichiers portent un suffixe cohérent ("exo.l" si c'est du lisp par exemple). Les messages sans sujet peuvent ne pas être lus.
Une série de raccourcis est disponible sous emacs, vous en trouverez quelques exemples soit ici , soit en tapant Esc x puis "describe-bindings" sous emacs.
Pour "lancer emacs" faire :$ emacs prog.l &où $ est le prompt que le système vous adresse.
(function parameter_1 parameter_2 parameter_3 ... parameter_n)
(+ 3 2) => 5
Avec Drracket il suffit de lancer DrRacket, donc de choisir
l'application racket dans le menu application.
Dans la fenêtre qui s'ouvre, deux parties, en haut doit être écrit
#lang racketet dans celle du bas, vous pouvez demander des évaluations et racket les exécute.
>(- 5 2) 3 > (+ 5 (* 2 6)) 17 >
(define (foisquatre n)
(* n 4))
(define (carre n)
(* n n))
(define (cube n)
(* n (* n n)))
Faites maintenant :
(load "premprog.l")Lisp répond par son promopt >. Vous pouvez alors vous servir de tout ce qui est défini dans le fichier. Par exemple pour demander un calcul (+ 3 5) ou l'évaluation d'une fonction :
>(carre 5) 25 >(carre 6) 36 >(cube 5) 125 >Plus tard, vous devrez quitter racket en choisissant "quit" dans le menu.
Plus grand de deux valeurs
(define (plgd2 a b)
(if (< a b)
b
a))
Exercices à faire et à valider sur ordinateur.
Plus grand de trois valeurs
(define (plgd3 a b c) (if (< a b) (if (< b c) c b) (if (< a c) c a)))Exemples :
Plus grand de quatre valeurs
(define (plgd4 a b c d) (if (< a b) (if (< b c) (if (< c d) d c) (if (< b d) d b)) (if (< a c) (if (< c d) d c) (if (< a d) d a))))
Plus grand de quatre valeurs, again...
(define (plg4 a b c d) (plgd2 (plgd2 a b) (plgd2 c d)))
(define (som n)
(if (= n 0)
0
(+ n (som (- n 1)))))
(define (fac n)
(if (< n 2)
1
(* n (fac (- n 1)))))
Vous devrez ensuite faire une série d'exercices :
0^0+1^1+2^2+3^3+...+n^n
0^n+1^n+2^n+3^n+...+n^n
0^p+1^p+2^p+3^p+...+n^p
(define (div a b)
(if (= a b)
1
(+ 1 (div (sous a b) b))))
> (div 10 5)
2
> (div 11 5)
. Interactions disabled; out of memory
Vous l'avez essayé et ça vous a plu. Je l'ai testé et détesté !
(define (somme n)
(somrt n 0))
(define (somrt n acc)
(if (= n 0)
acc
(somrt (- n 1) (+ n acc))))
Reprendre en récursivité terminale tous les exercices faits jusqu'ici.
;Multiplication de deux valeurs en récursivite terminale
(define (mulrtaux a b acc)
(if (= a 0)
(* b acc) ; ceci n est pas une addition, Hors Sujet
(mulrtaux (- a 1) b (+ acc 1))))
(define (mulrt a b)
(mulrtaux a b 0))
Et pourtant ça commençait bien, non ?Reste à refaire tous les exercices récursifs en récursivité terminale, y compris Fibonacci.
(define (multrt a b)
(multrtaux a b 0))
; il faut bien 0 puisqu on va faire des additions
(define (multrtaux a b acc)
(if (= a 0)
acc
(multrtaux (- a 1) b (+ b acc))))
; et où est la difficulté ?
Voici un programme qui affiche des traits qui forment un visage.
(define (ee) (load "Prog/Lisp/gra.l")) (require graphics/graphics) (define (findu port) (close-viewport port) ; viewport disappears (close-graphics) ; again, nothing appears to happen, but ; unclosed viewports (if any) would disappear ) (define (dessine_vis port) ((draw-polygon port) (list (make-posn -120 -120)(make-posn 120 -120)(make-posn 120 120)(make-posn -120 120)) (make-posn 140 130)) ((draw-ellipse port) (make-posn 50 30) 150 180) ((draw-ellipse port) (make-posn 70 90) 45 20 "magenta") ((draw-solid-ellipse port) (make-posn 80 90) 15 15 "blue") ((draw-ellipse port) (make-posn 130 90) 45 20 "magenta") ((draw-solid-ellipse port) (make-posn 140 90) 15 15 "blue") ((draw-line port) (make-posn 90 160) (make-posn 150 160) "red") ((draw-line port) (make-posn 120 100) (make-posn 120 150)) ) (define (face) (open-graphics) ; nothing appears to happen, but the library is initialized... (define viz (open-viewport "visage" 300 300)) (dessine_vis viz) (sleep 20) (findu viz) ) |
def fact(n):
if n==0:
return 1
else:
return n*fact(n-1)
print fact(5)
print fact(6)
print fact(7)
|
Pour s'en servir, une fois ce programme sera mis dans un fichier exo.py
, on se place dans un terminal et on tape :
dhcp17.ai.univ-paris8.fr: python prog.py 120 720 5040Où dhcp17.ai.univ-paris8.fr: est le prompt donné par la machine.
Comme vous le voyez, pour l'utiliser il suffit de demander l'exécution de python fact.py.
Vous avez quelques exercices à faire avec python, il suffit de reprendre tout ce que nous avons fait jusqu'ici !
def restediv (a, b):
if (a < b):
return a
else:
return restediv (a - b, b)
|
def somt(n):
if (n < 0):
return 0
return somrt(n,0)
def somrt (n, acc):
if (n == 0):
return acc
return somrt(n - 1, acc + n)
|
def som(n):
s = 0
i = 0
while (i <= n):
i = i + 1
s = i + s
return s
print 5,som(5)
|
Exercices : Vous devez maintenant reprendre toutes vos fonctions récursives
(surtout sous la forme récursive terminale) et en faire des
fonctions itératives.
Dès que vous aurez écrit la fonction fib, vous pourrez facilement faire une petite fonction pour s'en servir :
def essai_fib (n):
i = 0
while (i <= n):
print i,fib(i)
i = i + 1
essai_fib(10)
|
On appelle vecteur un objet qui est soit vide [], soit la construction d'un élément et d'un vecteur [3,5].
Première fonction
def affiche (V):
for i in V:
print i
affiche([7,4,3,2])
|
JJBook : python aff.py 7 4 3 2 |
def soml (L):
nb = len(L)
i = 0
s = 0
while (i < nb):
s = s + L[i]
i = i + 1
return s
print soml([3, 2, 5, 4, 1])
|
def longueur (L): nb = 0 for v in L: nb = nb + 1 return nb print longueur([9,2,3]) |
def remplirt (n):
i = 0
T = []
while (i <= n):
T.insert(i)
i = i + 1
return T
print remplirt(10)
def somt (n,L):
i = 0
s = 0
while i < n:
s = s + L[i]
i = i + 1
return s
print somt(6,remplirt(6))
print somt(7,remplirt(7))
|
def creer (n):
T = []
T.append(1)
T.append(1)
i=2
while (i <= n):
j=(T[i-1] + T[i-2])%27
T.append(j)
i = i + 1
return T
|
def repcar (L):
nb = long(L)
i = 0
while i < nb:
L[i] = L[i] * L[i]
i = i + 1
return L
print "repcar ([1,9,-5,3,2]) == ", repcar ([1,9,-5,3,2])
#repcar ([1,9,-5,3,2]) == [1, 81, 25, 9, 4]
|
(define (pgdg l)
(if (vide l) l
(if (vide (cdr l)) l
(if (vide (cddr l)) (inv2 l)
(cons (car (pgdg (cdr l)))
(pgdg (cons (car l)
(pgdg (cdr (pgdg (cdr l)))))))))))
|
from turtle import * import time import math |
def dessin3():
ht()
color("red","green") #choix de couleurs
fd(100) #avancer
left(90) #tourner
fd(100)
left(135)
fd(141)
print("fini")
time.sleep(2.5) #laisser l'affichage quelques secondes
dessin3()
|
fill(True)et après la forme finir avec :
fill(False)
/* voici un exemple tres simple */
/* D abord une fonction elementaire */
int som (int n) {
if (n < 1) {
return 0;
}
return som (n - 1);
}
|
main () {
printf("som (5) == %d\n",som(5));
printf("som (6) == %d\n",som(6));
printf("som (7) == %d\n",som(7));
}
|
mu.ai.univ-paris8.fr: gcc exo1.c mu.ai.univ-paris8.fr: a.out som(5) == 15 som(6) == 21 som(7) == 28 mu.ai.univ-paris8.fr: |
Faire en C toutes les fonctions vues précédemment.
void remplirt (int tab [100], int nb) {
/* void à la place de int pour signifier qu'il n'y a rien à renvoyer*/
int pred, ante, i;
if (nb > 99)
return;
pred = 13;
ante = 8;
tab [0] = 8;
tab [1] = 13;
i = 2;
while ( i < nb) {
tab [i] = (ante + pred) % 23;
/* % est le modulo, le reste de la division entière */
ante = pred;
pred = tab [i];
i = i + 1;
}
}
main () {
int nb, t [100];
nb = 20;
remplirt (t, nb);
affichet (t, nb);
}
|
Dans la suite, nous utilisons parfois le terme de "suite" pour désigner "tableau" ou "vecteur", le lecteur corrigera de lui-même.
0^0+1^1+2^2+3^3+...+n^n
0^p+1^p+2^p+3^p+...+n^p
0^n+1^n+2^n+3^n+...+n^n
* (somodd '(2 4 1 2 5 6 2)) = 10
Cette procédure est nommée "tri par insertion".
lesgrands ([13, 7, 15, 2], 8) donne [13, 15]
public class big {
public static void main(String[] args) {
int i, som, fac, fi;
int n;
n = 10;
int tab[] = new int[100];
System.out.println(" ");
i = 1;
som = 0;
fac = 1;
while (i <= n) {
som = som + i;
fac = fac * i;
i = i + 1;
}
System.out.println(" som iteratif " + som + " recursif " + somme(n));
System.out.println(" produit iteratif " + fac + " recursif " + fact(n));
i = 0;
n = 10;
while (i <= n) {
System.out.println("fib " + i + " => " + fib (i));
i = i + 1;
}
i = 2;
tab[0] = 1;
tab[1] = 1;
while (i < n) {
tab[i] = tab[i - 1] + tab[i - 2];
i = i + 1;
}
i = n - 1;
while (i >= 0) {
System.out.println("tab " + i + " => " + tab [i]);
i = i - 1;
}
/* vecteurs dans d'autres fonctions*/
remplir(n, tab);
voir (n, tab);
}
public static int somme (int n) {
if (n < 1)
return 0;
return n + somme (n - 1);
}
public static int fact (int n) {
if (n < 1) {
return 1;
}
else {
return n + fact (n - 1);
}
}
public static int fib (int n) {
if (n < 2)
return 1;
return fib (n - 1) + fib (n - 2);
}
public static void remplir (int nb, int [] vec) {
int i, j, tmp;
i = 0;
j = nb - 1;
tmp = 5;
while (i < nb) {
vec[i] = j;
j = j - tmp;
if (j < 0) {
tmp = - tmp;
tmp++;
}
if (j > 30) {
tmp = - tmp;
tmp--;
}
i = i + 1;
}
}
public static void voir (int nb, int [] vec) {
int i;
i = 0;
while (i < nb) {
System.out.println("vec ( "+i+" ) == " + vec[i]);
i++;
}
}
}
|
$ javac big.java $ java big Il faut compter jusqu a : 10 Somme recursive => 3628800 Somme vecteur => 55 Recursive terminale => 55 Produit recursif => 3628800 vec ( 0 ) == 9 vec ( 1 ) == 4 vec ( 2 ) == -1 vec ( 3 ) == 3 vec ( 4 ) == 7 vec ( 5 ) == 11 vec ( 6 ) == 15 vec ( 7 ) == 19 vec ( 8 ) == 23 vec ( 9 ) == 27 vec ( 0 ) == 27 vec ( 1 ) == 23 vec ( 2 ) == 19 vec ( 3 ) == 15 vec ( 4 ) == 11 vec ( 5 ) == 7 vec ( 6 ) == 3 vec ( 7 ) == -1 vec ( 8 ) == 4 vec ( 9 ) == 9 Fib 1 = 1 Fib 2 = 2 Fib 3 = 3 Fib 4 = 5 Fib 5 = 8 Fib 6 = 13 Fib 7 = 21 Fib 8 = 34 Fib 9 = 55 Fib direct 10 = 89 Fib recur 10 = 89 $ |
carre(N,C):- C is N * N.
somme(0,0).
somme(N,S):- N1 is N - 1,
somme(N1,S1),
S is S1 + N.
|
$ swipl Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.2.3) Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions. Please visit http://www.swi-prolog.org for details. For help, use ?- help(Topic). or ?- apropos(Word). ?- consult(exo). true. ?- carre(5,N). N = 25 Yes ?- carre(5,7). No ?- somme(3,Z). Z = 6 Yes ?- |
Emacs et Prolog
Pour que emacs respecte l'indentation prolog, il convient de rajouter deux lignes au fichier .emacs (qui se trouve dans votre répertoire "home").
(autoload 'prolog-mode "prolog" "Major mode for editing Prolog programs." t)
(add-to-list 'auto-mode-alist '("\\.pl\\'" . prolog-mode))
on pourra par exemple, sous terminal taper les lignes
suivantes en finissant par "contrôle-d" :
JJBook : cat >> ~/.emacs
(autoload 'prolog-mode "prolog" "Major mode for editing Prolog programs." t)
(add-to-list 'auto-mode-alist '("\\.pl\\'" . prolog-mode))
Il vous reste à faire un certain nombre de fonctions numériques
(jusqu'à la suite de Fibonacci, par exemple).
pere(chuck, eddie). pere(chuck, elvis). pere(elvis,john). pere(elvis,mick). pere(john,janis). pere(john,nico). |
$ swipl Welcome to SWI-Prolog (Version 3.3.4) Copyright (c) 1990-2000 University of Amsterdam. Copy policy: GPL-2 (see www.gnu.org) For help, use ?- help(Topic). or ?- apropos(Word). 1 ?- consult(rock). % rock compiled 0.01 sec, 9,868 bytes Yes 2 ?- pere(X,janis). X = john Yes 3 ?- pere(janis,X). No 4 ?- |
/* famille du rock, due a J-J Bourdin */ /* les pères */ pere(chuck, eddie). pere(chuck, elvis). pere(elvis,john). pere(elvis,mick). pere(john,janis). pere(john,nico). pere(john,lou). pere(mick,pete). pere(mick,robert). pere(mick,david). pere(lou,vanessa). pere(lou,marianne). /* les mères */ mere(ella,eddie). mere(ella,elvis). mere(edith,john). mere(edith,mick). mere(janis, sinead). mere(nico, joan). feminin(janis). feminin(nico). feminin(vanessa). feminin(marianne). feminin(sinead). feminin(joan). masculin(chuck). masculin(eddie). masculin(elvis). masculin(john). masculin(mick). masculin(lou). masculin(david). masculin(pete). masculin(robert). fils(X,Y):-pere(Y,X),masculin(X). fils(X,Y):-mere(Y,X),masculin(X). fille(X,Y):-pere(Y,X),feminin(X). fille(X,Y):-mere(Y,X),feminin(X). /* quelques primitives généralistes */ /* admirez les variables */ parent(X,Y):-pere(X,Y). parent(X,Y):-mere(X,Y). enfant(X,Y):-parent(Y,X). gdparent(X,Y) :- parent(X,Z),parent(Z,Y). |
egal(A,B):-A==B.cela fonctionne :
?- egal(5,5). Yes ?- egal(4,5). NoPar contre pour la différence, il faut écrire =\= pour les valeurs numériques (et pas les textes) :
diffe(A,B):-A=\=B.Pour les autres cas, l'inverse d'une valeur logique est sa négation:
egal(A,B):-A==B. different(A,B):-not(egal(A,B)).Il faut maintenant faire les prédicats :
long([],0).
long([A|As],L):-long(As,T),
L is T + 1.
|
$ latex ilp10_p.tex ...$ latex ilp10_p.tex ... Overfull \hbox (5.3039pt too wide) in paragraph at lines 131--135 []\T1/cmr/bx/n/10.95 SomCar : \T1/cmr/m/n/10.95 ?cri-vez une fonc-tion qui pren d [1] Overfull \hbox (7.47572pt too wide) in paragraph at lines 149--153 \T1/cmr/m/n/10.95 en pa-ra-m?tre une liste et ren-voie la somme [2] (./ilp07_p.aux) ) (see the transcript file for additional information) Output written on 12_ilp_p.dvi (8 pages, 7144 bytes). Transcript written on ilp10_p.log.Ensuite on le passe en ps ou en pdf, selon l'usage souhaité.$ dvips -o 12_ilp_p.ps 12_ilp_p.dvi |
white.home: dvipdf 12_ilp_p.dvi white.home: open 12_ilp_p.pdf white.home: |
\documentclass{article}
\pagestyle{empty}
\usepackage{ifthen}
\newcounter{mula}
\newcounter{mulb}
\newcounter{prod}
\newcounter{compt}
\newcounter{fv}
\newcounter{fi}
\newcommand{\mul}[2]{
\setcounter{mula}{#1}
\setcounter{mulb}{#2}
\setcounter{prod}{0}
\setcounter{compt}{0}
\mulaux{#1}
}
\newcommand{\mulaux}[1]{
\ifthenelse{#1 > \thecompt}{\mulo{#1}}{}
}
\newcommand{\mulo}[1]{
\stepcounter{compt}
\addtocounter{prod}{\themulb}
\mulaux{#1}
}
\newcommand{\fac}[1]{
\setcounter{fv}{1}
\setcounter{fi}{1}
\facaux{#1}
La factorielle de #1 est \thefv ~\\~\\
}
\newcommand{\facaux}[1]{
\ifthenelse{#1 > \thefi}{\faco{#1}}{}
}
\newcommand{\faco}[1]{
\stepcounter{fi}
\mul{\thefi}{\thefv}
\setcounter{fv}{\theprod}
\facaux{#1}
}
\begin{document}
\underline{\Huge\bf I.L.I. LaTeX}\\~\\
on affiche pour 3 et 5 \\~\\
\fac{3}
\fac{5}
\end{document}
|
Enfin, un rapport
Voici, ici un exemple de rapport écrit en LaTeX. Le fichier de bibliographie (si vous en avez besoin) est donné là de même que le résultat de la compilation de l'ensemble vers un fichier pdf: projet.pdf .PATH=$PATH'./:'Premier programme
#!/bin/sh # affiche les arguments echo $1 echo $2 echo $3 echo $4Utilisons-le :
Vous mettez ce code dans un fichier, par exemple de nom voir.sh.
Vous rendez ce fichier exécutable, par exemple par :
$chmod 755 voir.sh
Il en ira de même à chaque nouveau shellscript : il doit être
exécutable et on doit y avoir accès pour pouvoir l'exécuter.
$ voir.sh Je fais souvent ce reve etrange Je fais souvent ce $
#!/bin/sh # affiche les arguments echo $1 shift echo $1 shift echo $1 shift echo $1 shiftUtilisons-le :
$ voir.sh Je fais souvent ce reve etrange Je fais souvent ce $Continuons avec le double d'un nombre :
if test $# -eq 1 then expr $1 + $1 else echo "usage: $0 n" fiJe mets ceci dans un fichier carre.sh et cela donne à l'usage :
otake: chmod +x carre.sh otake: carre.sh 5 10 otake: carre.sh 6 12
Comme à notre habitude, nous verrons la fonction somme.
Fichier som.sh
#!/bin/sh
#juste la somme
if test $# -lt 1
then
echo "usage: $0 nb"
else
if test $1 -le 0
then
echo 0
else
n=`expr $1 - 1`
f=`som.sh $n`
expr $f + $1
fi
fi
#jj@aqua$ chmod +x som.sh
#jj@aqua$ som.sh 5
#15
Notez que j'ai modifié mon fichier .bashrc en ajoutant la ligne
suivante :
PATH=$PATH'~/bin/:./:'pour y rajouter mon répertoire bin (où je mets mes exécutables) et le répertoire courant.
source ~/.bashrc
Fibonacci récursif
Ce script est dans un fichier fibr.sh dans un répertoire qui fait partie de mon PATH.
#!/bin/sh
if test $# -ne 1
then echo "usage: $0 nb"
else
case $1 in
0) echo 1;;
1) echo 1;;
*)
s=`expr $1 - 1`
t=`expr $1 - 2`
u=`fibr.sh $s`
v=`fibr.sh $t`
expr $u + $v;;
esac
fi
|
#!/bin/bash n=$# i=1 while test $i -lt $n do echo $1 shift i=`expr $i + 1` done |
#!/bin/bash while test $# -gt 0 do echo $1 shift done |
jj@sunfire$ cat essai.sh case $# in 1) echo $1;; 2) echo $1 $2;; 3) echo $1 $2 $3;; *) echo "trop de parametres" esac jj@sunfire$ essai.sh 1 2 1 2
Fichier faciter.sh
#!/bin/sh
if test $# -eq 1
then
n=$1
f=1
while test $n -ge 1
do
f=`expr $f \* $n`
n=`expr $n - 1`
done
echo $f
else
echo "un argument, un !"
fi
#jj@aqua$ chmod 755 faciter.sh
#jj@aqua$ faciter.sh 6
#720
Refaites tous les exercices numériques en
shell itératif.
D'abord prendre et afficher tous les arguments :
| Fichier louque.sh |
for i do echo $i done |
| Fichier ici.sh |
for i in * do echo $i done |
| Fichier tiens.sh |
f=1 for i in 1 2 3 4 5 6 do f=`expr $f \* $i` echo $i $f done |
Dernière mise à jour de ce document :