Cours-deug-Logique

Description

èmeDEUG MIAS – 3 période — Informatique Cours Septembre 2004 p. 1/ 23Table des matières1 Administration 22 Rappels 32.1 Le langage Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 Paires et Listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4 Fonctions d’orde supérieur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.5 Manipulation symbolique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Types Abstraits de Données 83.1 Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83.2 Arbres Binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.2.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.2.2 Quelques fonctions opérant sur le type ArbreBin . . . . . . . . . . . . . . . . . . . . . 113.2.3 Représentation en Scheme des AB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.2.4 Arbres Binaires de Recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 Objets mutables 134.1 Effets de bord – Rappels. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134.2 Représentation des objets en mémoire . . ...

Sujets

• informatique
• informatique cours

Informations

• Publié par: Enna
• Nombre de lectures: 44
• Langue: Français

Extrait

DEUG MIAS – 3 ème période — Informatique Cours Septembre 2004 p. 1/ 23 Table des matières 1 Administration 2 Rappels 2.1 Le langage Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Paires et Listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Fonctions d’orde supérieur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Manipulation symbolique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Types Abstraits de Données 3.1 Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Arbres Binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Quelques fonctions opérant sur le type ArbreBin . . . . . . . . . . . . . . . . . . . . . 3.2.3 Représentation en Scheme des AB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.4 Arbres Binaires de Recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Objets mutables 4.1 Effets de bord – Rappels. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Représentation des objets en mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Effets de bords : Opérations de mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Egalite vs identité. Partage et miettes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Applications et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Complexité des algorithmes 6 Logique des Propositions 6.1 Syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Sémantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Mise en forme normale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Conséquence sémantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Insatisfiabilité et forme clausale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 Insatisfiabilité et arbre sémantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.7 Méthode de résolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 3 3 7 7 7 8 8 8 10 10 11 12 12 13 13 14 14 15 15 16 18 18 18 19 20 21 21 22

DEUG MIAS – 3 ème période — Informatique Cours Septembre 2004 1 Administration Emploi du temps 20 h de cours (7 semaines) ; 25h de TD (9 semaines) ; 15h de TP (5 semaines) gr A jfv ; gr B pja

p. 2/ 23

SEMAINE COURS TD TP ------------------------------------------------------- 6 sept scheme: syntaxe sémantique, récursivité listes, ordre sup. (2 cours) pas de td pas de tp C1,2 ------------------------------------------------------- 13 sept manip symbolique. tad ensembles (2 cours) 2 td (feuille 1) réc listes pas de tp C3,4 TD1,2 ------------------------------------------------------- 20 sept 1 seul cours (arbres) 2 td (feuille 2) ordre sup manip symb pas de tp C5, TD3,4 ------------------------------------------------------- 27 sept pas de cours 2td (feuille 3) ensembles arbre bin tp (ens) TD5,6 TP1 ------------------------------------------------------- 4 oct 1 cours mutable 1 td (feuille3) arbre bin C6, TD7 ------------------------------------------------------- 11 oct 1 cours complexité 2 td (feuille 4) mutable complexité tp (lourd) arbres mutables C7, TD8,9 TP2 ------------------------------------------------------- 18 oct pas de cours pas de td 1/2 tp mutables (fin du tp2) TP3 ------------------------------------------------------- attention congés Toussaint du 27 Oct (mercredi) inclus au 1er Nov (lundi) inclus 25 oct partiel le 3 nov (rentrée vacances) ------------------------------------------------------- 1 nov 2cours mots et langages et ... pas de td pas de tp C8,9 ------------------------------------------------------- 8 nov 2 td (feuille 5) mots et langages TD10,11 ------------------------------------------------------- 15 nov 2 cours automates et 2 td (feuille 5) tp automates mots et langages C10,11 TD12,13 TP4 ------------------------------------------------------- 22 nov 2 cours automates 2 td (feuille 6) automates tp automates (minimisation) C12,13 TD14,15 TP5 ------------------------------------------------------- 9 déc FIN 2 td (feuille 6) tp automates (équivalences) TD16,17 TP6 ------------------------------------------------------- Cours Répartition : 20 h C, 25 h TD, 15h TP. Par semaine. Alternance des TP. Inscriptions salles machines. Contenu : Scheme - Arbres - Mutables - Complexité / Langages rationnels et automates. Barême Barême exam = 60 = sup( note exam sur 60 ; note exam sur 40 + note partiel sur 20) Partiel 2 heures le 3 Novembre (fin Scheme) Exam 2 heures en fin de semestre ( Scheme + langages ) Attention, certaines semaines 0 ou 1 ou 2 Cours.

DEUG MIAS – 3 ème période — Informatique Cours Septembre 2004 p. 3/ 23 2 Rappels 2.1 Le langage Scheme 1. Le cycle Lecture Évaluation Impression 2. Types de Données en Scheme. Rappel : Type de donnée = Domaine + Fonction de manipulation. Notation : Objet = Union de tous les domaines. (a) Nombres Nombre a pour domaine les flottants sur 64 bits, dans l’intervalle [ − 10 − 40000 ; 10 +40000 ] . Le sous–type Entier est implémenté. +  −  ∗   : N ombre × N ombre −→ N ombre sqrt,abs,exp,log,sin,cos : N ombre −→ N ombre sqrt est la racine carrée abs – la valeur absolue . floor,ceiling : N ombre −→ Entier Parties entières par valeurs in- férieure, supérieure truncate,round : N ombre −→ Entier troncature, arrondi < > < =  > =  =  <> : N ombre −→ Booleen opérations classiques de com- paraison quotient,remainder : Entier × Entier −→ Entier Quotient et reste de la division entière number ?,integer ?, float ? : Objet −→ Booleen Test d’appartenance au type Nombre, au sous–type Entier, Flottant number-> string : N ombre −→ Chaine Conversion de type (b) Paires et Listes Paire a pour domaine l’ensemble des « objets » construits à partir de la fonction cons appliquée à deux objets quelconques. Liste est définie récursivement par : liste ::= null | ( cons objet liste ) . L’identificateur primitif null est la liste vide qu’on peut aussi définir par ′ () . Une liste non vide est une paire. null : −→ Liste La liste vide cons : Objet × Objet −→ P aire cons : Objet × Liste −→ Liste list : Objet ×    × Objet −→ Liste Une abréviation pour cons ( o 1  ( conso 2     cons ( o n  nil )    )) en notation préfixée. append : Liste × Liste −→ Liste Concaténation de listes length : Liste −→ Entier Nombre d’éléments d’une liste car,cdr : P aire −→ Objet Premier, deuxième élément d’une paire car : Liste − { null }−→ Objet Premier élément d’une liste non vide cdr : Liste − { null }−→ Liste Liste extraite d’une liste non vide en ôtant le premier élément caar,cadr,...,cdar,cddr,.. :  −→  Imbrication à 4 niveaux maximum des fonctions car et cdr : cadar = (car ( cdr (car ...))) null ? : Objet −→ Booleen Renvoie vrai si l’argument est null, faux sinon pair ?, list ? : Objet −→ Booleen Teste si l’argument est une paire, une liste atom ? : Objet −→ Booleen Teste si l’argument est « atomique » cad non construit. Le seul constructeur, pour nous, étant cons, atom ? est identique à (not pair ?) ... enfin, dans notre version simplifiée.

(c) Booléens Booleen a pour domaine { # T  # F } . and,or : Booleen × Booleen −→ Booleen not : Booleen −→ Booleen boolean ? : Objet −→ Booleen Teste si l’argument est un booléen

DEUG MIAS – 3 ème période — Informatique Cours Septembre 2004 p. 4/ 23

(d) Caractères et Chaînes de caractères Les caractères sont notés en Scheme #  a    #  Z . Les chaînes de caractères sont notées "ceci est une chaîne" . char ?, string ? : Objet −→ Booleen Teste si son argument est un caractère, une chaîne Il existe de nombreuses fonctions de manipulation de chaînes – string-ref, substring ... – que nous n’utiliserons pas. (e) Divers Un « littéral » ou expression littérale est soit une expression Scheme dont la valeur est elle–même comme les constantes numériques, booléennes, caractères ou chaînes, soit le résultat de l’application de la fonction dite de citation quote ou ’ , qui, appliquée à une expression Scheme renvoie littéralement l’expression argument. quote : Objet −→ Objet Ex. (quote a) renvoie a, (quote (a b )) renvoie (a b), (quote +) renvoie +, (quote 4) renvoie 4 Un identificateur est une suite de caractères. symbol ? : Objet −→ Booleen Teste si l’argument est un identi- ficateur. (f) Égalité L’égalité la plus générale. Attention le prédicat = est réservé au type Nombre equal ? : Objet × Objet −→ Booleen (g) Entrées – Sorties read :

display : Objet

newline :

−→

−→

−→

Objet

Lit une expression Scheme au clavier par défaut, renvoie l’expression lue, sans éva- luation. Affiche à l’écran la valeur de l’argument. Ne renvoie rien. C’est une des fonctions à « effet de bord» Affiche à l’écran un caractère qui fait pas- ser le curseur en début de ligne suivante

DEUG MIAS – 3 ème période — Informatique Cours Septembre 2004 p. 5/ 23 3. Expressions Scheme : La syntaxe . La grammaire qui suit est formée d’un ensemble de règles de réécriture qui spécifient la syntaxe : « Comment doit–on écrire un mot du langage ». Une règle s’écrit < symbole non terminal > ::= < symbole 1 > | < symbole 2 > | . . . La phrase qui précède se lit « symbole non terminal » se réécrit en « symbole 1 » ou en « symbole 2 » ou en . . . . On applique – récursivement – ces règles de réécriture jusqu’à ne plus avoir que des symboles terminaux dans le mot du langage. ( Un symbole terminal ne se réécrit pas ). Notations ǫ désigne le mot vide. < symbole > * signifie une suite, éventuellement vide de < symbole > et < symbole > + signifie une suite non vide de < symbole > . Dans la grammaire du langage Scheme, les symboles terminaux sont les identificateurs primitifs du langage.

< X > * < X > + < expression > < identificateur > < ident. primitif > < ident. non primitif > < appel de fonction > < opérateur > < opérande > < définition > < lambda–expression > < corps > < paramètres formels > < conditionnelle > < forme cond > < forme if > < clause > < prédicat > < expression-alors > < expression-sinon > < forme let > < liaisons >

: := ǫ | < X >< X > * : := < X > | < X >< X > + : := < identificateur > | < appel de fonction > | < définition > | < lambda– expression > | < conditionnelle > | < forme let > | < forme let* > : := < ident. primitif > | < ident. non primitif > : := les constantes du langage (nombres, booléens, caractères) les fonctions de base du langage (+,*,define, car, ....) : := un symbole (suite de caractères) non ident. primitif : := ( < opérateur > < opérande > * ) : := < expression > : := < expression > : := ( define < ident. non primitif > < expression > ) : := ( lambda < paramètres formels > < corps > ) : := < expression > : := ( < ident. non primitif > * ) : := < forme cond > | < forme if > : := ( cond < clause > + ) | (cond < clause > * (else < expression > )) : := (if < prédicat > < expression-alors > ) | (if < prédicat > < expression-alors > < expression-sinon > ) : := ( < prédicat > < expression > ) : := < expression > : := < expression > : := < expression > : := ( let < liaisons > < corps > ) : := ( ( < ident. non primitif > < expression > )* )

DEUG MIAS – 3 ème période — Informatique Cours Septembre 2004 p. 6/ 23 4. Expressions Scheme : la sémantique La grammaire du lanage définit récursivement la syntaxe d’une expression Scheme. La sémantique définit la valeur d’une expression. Attention, une expression peut parfaitement être évaluée sans qu’une valeur soit renvoyée ! C’est le cas des fonctions à effet de bord ( define , set , . . . ) Soit V al la fonction d’évaluation de l’interpréteur Scheme. Toute expression Scheme s’évalue dans un environnement . Un environnement est un ensemble de couples ( < identificateur > , < valeur > ). On débute Scheme avec un environnement global classique – ie valuant les identificateurs primitifs comme 1, #t, + ... V al : < expression > 7−→ < valeur > est définie comme suit :

Au cas où < expression > est ( define < ident. non primitif > Calculer v = V al ( expression 1) , modifier l’environnement courant < expression1 > ) en ajoutant la liaison ( < ident. non primitif > , v ), ne renvoie rien. < identificateur > Renvoyer la valeur de l’identificateur, dans l’environnement cou- rant, que celle–ci soit primitive ou liée à l’identificateur par la forme spéciale define < lambda–expression > Renvoyer la fonction ( < paramètres formels > 7−→ < corps > ) as- sociée ainsi que l’environnement de cette fonction. ( cond ( p 1 e 1 )    ( p n e n ) ) Évaluer successivement V al ( p 1 )  V al ( p 2 )    V al ( p i ) jusqu’à trou- ver un indice i tel que V al ( p i ) = # t , renvoyer alors V al ( e i ) . Si pour chaque 1 6 i 6 n : V al ( p i ) = # f alors renvoyer une valeur indéterminée. ( cond ( p 1 e 1 )    ( p n e n ) Évaluer successivement V al ( p 1 )  V al ( p 2 )    V al ( p i ) jusqu’à trou- else e n +1 ) ver un indice i telque V al ( p i ) = # t , renvoyer alors V al ( e i ) . Si pour chaque 1 6 i 6 n : V al ( p i ) = # f alors renvoyer V al ( e n +1 ) . ( if < predicat > < expression- Calculer V al ( predicat ) . Si cette valeur est #t alors renvoyer alors > ) V al ( expression-alors ) , sinon renvoyer une valeur non spécifiée ( if < predicat > < expression- Calculer V al ( predicat ) . Si cette valeur est #t alors renvoyer alors > < expression-sinon > ) V al ( expression-alors ) , sinon renvoyer V al ( expression-sinon ) ( exp 0 exp 1    exp n ) Calculer, dans l’environnement courant, v 0 = V al ( exp 0 )  v 1 = V al ( exp 1 )    v n = V al ( exp n ) . Si v 0 est une fonction primitive d’arité n , appliquer cette fonction aux paramètres v 1    v n et ren- voyer la valeur obtenue. Si v 0 est une fonction associée à une lambda–expression ( par 1    par n 7−→ corps ) , calculer corps–substitué obtenu par sub- stitution de v i à chaque occurrence de par i dans corps , pour chaque 1 6 i 6 n . Retourner V al ( corps–substitué ), calculé dans l’environ- nement de la lambda–expression. Dans chaque cas où l’arité de la fonction ne correspond pas au nombre n de paramètres de l’appel, renvoyer Erreur ( let (( x 1 exp 1 )    ( x n exp n )) S’évalue à : V al ( (( lambda ( x 1    x n ) exp 0 ) exp 1    exp n ) ) exp 0 ) Autres cas Renvoyer Erreur ... pour cette version simplifiée de Scheme.

DEUG MIAS – 3 ème période — Informatique Cours Septembre 2004 p. 7/ 23 2.2 Récursivité Définition récurrente de fonction f = Domaine D + équations de récurrence (cas de base et récurrence) + preuve de la terminaison du calcul de f ( n ) ∀ n ∈ D . Exemple : exponentiation rapide. D = N . Soit a un nombre . exp ( n a ) = si n est pair alors exp ( n 2  a ) ∗ exp ( n 2  a ) sinon a ∗ exp ( n − 1  a ) . Définition incorrecte avec comme cas de base exp (0  a ) = 1 . Preuve par induction avec les 2 cas de base. P ( k ) = ∀ j 6 2 ∗ k + 1 : le calcul de exp ( j a ) termine. P ( k ) ⇒ P ( k + 1) , or P (0) . On peut d’ailleurs utiliser ce schéma de récurrence, pour prouver que l’exponentiation rapide coïncide avec l’exponentiation usuelle. Code Scheme. Exemples mathématiques usuels : suite arithmétique, géométrique. 2.3 Paires et Listes 1. Une paire ou couple est définie par le constructeur du type cons : <Paire> : := ( cons <Objet> <Objet>) Le type a deux fonctions d’accès car et cdr . Le prédicat associé est pair ? . Notation Scheme : (cons 1 2) renvoie (1 . 2) 2. Une liste est définie par récurrence . Le type a un élément de base null , un constructeur cons , deux fonctions d’accès car et cdr , et des prédicats associés null ? et list ? . <Liste> : := <liste vide> | ( cons <Objet> <Liste>) Notation Scheme : (cons 1 (cons 2 (cons 3 null))) renvoie (1 2 3) On parle des éléments de la liste, et on abrège syntaxiquement en Scheme avec les notations (list o1 o2 ... on) et cadr, ... 3. Schéma de récurrence f : Liste −→ T L 7−→  si L estlistevide s a i l n or o s n . . . . . . f ( cdr ( L )) ... Attention au domaine liste vide ou non ... le calcul se termine car la longueur de la liste décroit à chaque appel et f ( null ) est défini. 4. Exemples – length – append exhiber la faute (cons L1 L2) – reverse – fausse (cons (reverse (cdr L)) (list (car L))) – juste mais ... (append (reverse (cdr L)) (list (car L))) – juste et efficace revbis : Liste × Liste −→ Liste ( L 1  L 2 ) 7−→ concaténation de reverse ( L 2 ) et L 1 2.4 Fonctions d’orde supérieur Rien de spécial : pas de syntaxe ou sémantique particulière. Simplement, lorsque f est une fonction de E 1 ×    × E n dans F rien n’interdit E i = B A ou F = B A . Pour une fonction en résultat : nécessité de la lambda –expression. Abstraction Sigma P a b f ( k ) Composition f ◦ g puis f n = f ◦    ◦ f

DEUG MIAS – 3 ème période — Informatique Cours Septembre 2004 p. 8/ 23 2.5 Manipulation symbolique Type symbole ou identificateur. quote : Objet → Objet . La valeur de quote x est littéralement x . Ceci permet de définir des symboles, mais aussi des expressions symboliques. Exemples : – (define L ’(lambda (x) 1)) – Tester si une liste est une lambda–expression. 1. écrire la fonction liste-symboles ? qui teste si son paramètre liste est une liste de symboles. 2. une lambda–expression est une liste de taille 3, telle que le deuxième élément est une liste de symboles. – Tester si une liste est une expression let. 1. écrire la fonction liste-liaisons ? qui teste si son paramètre liste est une liste non vide de liaisons ((x1 e1) ... (xn en)) . 2. une expression–let est une liste de taille 3 ...

3 Types Abstraits de Données Motivation : besoin de construire de nouveaux types de données à partir des types de base, pour modéli- ser/traiter un problème. Exemple : ensembles, formules logiques, tableaux ... Un TA a : une unique définition Domaine (les valeurs du type) + Fonctions « de base » (manipulation, construc- teurs, fonctions d’accès, ...) spécifiées (prédicats). plusieurs implémentations possibles Programmation des fonctions de la définition en utilisant les types – de base ou abstraits déjà définis – existants. On utilise (manipule) un TA uniquement à l’aide des fonctions de sa définition, jamais en utilisant une de ses implémentations – qui peuvent changer. Ceci réalise une barrière d’abstraction. Exemple : les listes/ On ne sait pas comment elles sont implémentées. Peu importe.

3.1 Ensembles En réalité « Ensemble fini d’Objet » 1. Une définition : Domaine = P f ( Objet ) , Fonctions = vide vide ?  adjoindre oter app ?  choix . adjoindre est le constructeur, choix n’est pas nécessairement déterministe (expliquer). Spécifications : les règles « usuelles » de la théorie des ensembles – finis. E ∈ Objet x y ∈ E ∀ E 6 = vide : app ?( choix ( E )  E ) ∀ x : non ( app ?( x vide )) ∀ x E : app ?( x E ) ⇔ adjoindre ( x E ) = E ∀ x ∀ E ∈ Objet − { vide } : adjoindre ( x oter ( x E )) = E ⇔ app ?( x E ) ∀ x E : oter ( x adjoindre ( x E )) = E ⇔ non ( app ?( x E )) ∀ x y E : adjoindre ( x ( adjoindre ( y E )) = ( adjoindre ( y ( adjoindre ( x E ))

2. Utilisation : – E = { 1  2  3 } est construit par adjoindre (  ) comme par ... – union inclus ?  egal − ens ?  intersection NB : attention au non déterminisme qui impose la syntaxe soit x = (choix(E)), soit alors E’ = oter(x,E), ... abrégée let* en Scheme. 3. Implémentations – Par des listes sans répétition, en supposant que le prédicat equal ? assure l’égalité de 2 éléments : (define vide null) (define vide? null?) (define choix car) (define oter (lambda (x E) (cond ((vide? E) E) ((equal? x (car E)) (cdr E)) (else (cons (car E)

Septembre 2004

p. 9/ 23

DEUG MIAS – 3 ème période — Informatique Cours (oter x (cdr E))))))) (define app? (lambda (x E) (cond ((vide? E) #f) ((equal? x (car E)) #t) (else (app? x (cdr E)))))) (define adjoindre (lambda ( x E ) (cond ((app? x E) E) (else (cons x E))))) Remarque : Un même ensemble peut avoir plusieurs représentations. – Par des listes éventuellement avec répétitions, en supposant que le prédicat equal ? assure l’égalité de 2 éléments : Recoder oter adjoindre – Par des listes triées et sans répétition, en supposant que le prédicat equal ? assure l’égalité de 2 éléments et que l’ordre est total avec le prédicat inf ? . Recoder app ?  oter et adjoindre . Gains ? ATTENTION : oter est ... ((inf ? (car E) x) (cons (car E) (oter x (cdr E)))) ((equal ? (car E) x) E) (else (cons x E)) ... Dans ce cas, on peut inclure des opérations qui n’appartiennent pas à la définition stricte du type, comme union ou intersection pour des raisons d’efficacité. A faire. – Le problème lié à l’égalité sur Objet . Exemple Objet est Partie finie de N . Comment coder adjoindre app ?  oter ? Exemple : (define A (adjoindre 1 (adjoindre 2 vide))) et (define B (adjoindre 2 (adjoindre 1 vide))) . Puis (define E (adjoindre A (adjoindre B vide))) . Problème. En fait le type Ensemblef inideObjet est paramétré par le prédicat définissant l’égalité sur Objet . ( On a supposé dans un premier temps que le prédicat général equal ? faisait l’affaire ). – Exemple : "Ensembles généralisés de symboles" représentés par des "Listes généralisées" ;; ordre sur le type Big defini par Big := Base | esemble de Big ;; Base a pour ordre inf? et pour predicat d’egalite egal? ;; ainsi que pour predicat d’appartenance au type base? ;; on represente les elements de Big par ;; ou bien une representation de Base ou une liste ordonnee ;; par infB? et sans repetition. ;; l’ordre, infB?, est lexicographique, induit par inf? ;; on decide que infB?(x,y) pour tout x dans Base, y dans Big-Base ;; ici Base = Symbole (define base? symbol?) (define inf? (lambda (a b) (string<? (symbol->string a) (symbol->string b)))) (define egal? equal?) (define egalB? (lambda (A B) ;; ce sont des Bases ou des listes ordonnes croissantes (cond ((base? A) (cond ((base? B) (egal? A B)) (else #f))) ((base? B) #f) (else (equal? A B)))))

(define infB? ;; strict (lambda ( A B ) (cond ((base? A) (cond ((base? B) (inf? A B)) (else #t))) ((base? B) #f)

DEUG MIAS – 3 ème période — Informatique Cours Septembre 2004 ((null? A) (not (null? B))) ((null? B) #f) (else (let ((a (car A)) (b (car B)) (A1 (cdr A)) (B1 (cdr B))) (cond ((infB? a b) #t) ((egalB? a b) (infB? A1 B1)) (else #f))))))) (define ajouter ;; defini sur ensemble de Big (lambda (x E) (cond ((null? E) (cons x null)) (else (let ((y (car E)) (E1 (cdr E))) (cond ((infB? x y) (cons x E)) (else (cons y (ajouter x E1))))))))) (define aj ajouter)

(define A ’(a b () (a b))) (define A (aj ’a (aj null (aj (aj ’a (aj ’b null)) (aj ’b null)))))

(define B ’(a b c)) (define C ’((a))) (define D ’(a b () (a ())))

p. 10/ 23

3.2 Arbres Binaires 3.2.1 Généralités 1. Présentation : omniprésence du type arbre en informatique, mais aussi ailleurs. – Arbres généalogiques (une feuille sans frère) – Arbre tournoi – Système de fichier – Expression arithmétique avec op binaires seulement – Expression logique, avec opérateur unaire Un arbre est un graphe « orienté » du haut vers le bas (conventionnellement). Chaque sommet, a 0 ou plusieurs flèches partantes (vers le bas) et au plus 1 flèche entrante. Quelques définitions. Pour un arbre donné : (a) Un sommet ou noeud a une information attachée ou étiquette . (b) Le sommet du haut est dit la racine de l’arbre. (Tête en bas donc). (c) Un sommet a au plus un père et des fils (de 0 à n ). (d) Un sommet qui n’a pas de fils est dit feuille de l’arbre. (e) On définit récursivement les descendants d’un noeud : ses fils et les descendants de ceux–ci. Symétriquement, on définit les ascendants . (f) La relation est un descendant de est un ordre partiel sur les noeuds d’un arbre. Un descendant du noeud racine est dit sous–arbre de l’arbre considéré. (g) Il existe un arbre particulier, l’ arbre vide , qui n’est pas un sommet ou noeud, qui n’a pas d’éti- quette. (h) Un arbre binaire est un arbre dont les noeuds ont au plus 2 fils. 2. Définition des arbres binaires. Le type Arbre Binaire noté ArbreBin est : ArbreBin ::= ArbreV ide | consAB ( Objet ArbreBin ArbreBin ) Le type abstrait est défini par :

DEUG MIAS – 3 ème période — Informatique Cours Septembre 2004 p. 11/ 23 – Ses constructeurs ABvide : −→ ArbreBin consAB : Objet × ArbreBin × ArbreBin −→ ArbreBin – Ses fonctions d’accès etiq : ArbreBin − { Abvide }−→ Objet ABgauche ABdroit : ArbreBin −→ ArbreBin – Un prédicat : ABvide ? : ArbreBin −→ Booleen 3. Sémantique : – ABvide ?( A ) ⇔ A = ABvide – etiq ( consAB ( x G D )) = x – ABgauche ( consAB ( x G D )) = G resp. ... 4. Exemples : (a) (* (+ a b ) 5 ) donner la représentation complète, puis sans les ABvides. (b) (* (+ a (- b)) 5) Idem : un seul fils. Insister sur différences étiquette, noeud, arbre. Pour moi arbre est ABvide ou noeud. cad noeud = arbre non vide. attention à l’orientation du dessin ! ! ! 5. Propriétés (a) Définition : Soit A un arbre non vide, et n un noeud de A . prof ondeur A ( n ) = 0 si n est la racine de A , 1 + prof ondeur A ( pere ( n )) sinon. (b) Définition : Soit A un arbre non vide. hauteur ( A ) = max ( prof ondeur A ( n ); n ∈ A ) . (c) Définition : Soit A un arbre non vide. Un chemin de A est une suite ( n 1      n k ) telle que n i est le père de n i +1 ∀ i ∈ [1  ( k − 1)] . Une branche de A est un chemin ( n 1      n k ) tel que n 1 est la racine de A et n k est une feuille de A . Donner des exemples. (d) Relation entre hauteur, type des branches et nombre de noeuds. Soit h la hauteur d’un arbre et n son nombre de noeuds. i. Arbre filiforme (ou peigne) : n = h + 1 ii. Arbre binaire complet : toutes les branches ont la même longueur. carcatérisé par : tout noeud non feuille a 2 fils, toutes les feuilles sont à la même profondeur. n = 2 h +1 − 1 iii. Pour tout arbre, on a h + 1 6 n 6 2 h +1 − 1 . Faire la preuve :Induction structurelle directe

3.2.2 Quelques fonctions opérant sur le type ArbreBin 1. feuille ? 2. nbnoeuds DIRECT 3. ens-etiq 4. hauteur : hauteurbis avec hauteurbis(ABvide)=0 et ... 5. Opérations de parcours Parcourir un arbre, c’est « visiter » chaque noeud, et effectuer un certain traitement lors de la visite. L’ordre dans lequel on traite les noeuds a une influence sur le résultat. – Parcours préfixe(A) = si A est vide, terminer sinon ; ; A = consAB ( x G D ) 1. traiter(A) ; 2. parcours préfixe(G) ; parcours préfixe(D) – Parcours infixe, suffixe – Exemple : liste des étiquettes préfixe, infixe, suffixe. – Contre–exemple : peut–on reconstruire un arbre sachant que ses étiquettes sont 2 à 2 disjointes (il y a une bijection entre noeuds et étiquettes) et qu’on a la liste des étiquettes dans un des 3 parcours ? Évidemment non. Donner un exemple. Effleurer le fait que d’un coté on a un ordre total et de l’autre un ordre partiel. Effleurer le fait qu’on peut reconstruire l’arbre si on a 2 listes d’étiquettes dans 2 parcours différents (donc c’est un ordre partiel de dimension 2). – Évaluation d’un arbre expression numérique. Un AEB est un arbre binaire dont les feuilles sont étiquetées par des nombres et les noeuds interne ont pour étiquette un opérateur binaire ou unaire (+,- ... sin, log ...). Il faut utiliser eval .