Note : aucun document autorisé.
[Corrigé du partiel]
On considère le plan affine et l'on s'intéresse aux objets géométriques suivants : les points, les vecteurs et les droites. Un point est défini par ses deux coordonnées dans le plan, un vecteur est également défini par deux coordonnées, et une droite est définie par un point et un vecteur directeur.
1. Spécifier les types abstraits point et vecteur. Pour le type point, les opérations sont la translation d'un point par un vecteur v, la distance entre deux points et le test d'égalité de deux points. Pour le type vecteur, les opérations sont le calcul de la norme d'un vecteur, la multiplication d'un vecteur par un scalaire, le calcul du vecteur orthogonal à un vecteur V et de même norme que V, le calcul du produit scalaire de deux vecteurs, et le test pour calculer si deux vecteurs sont colinéaires. Vous devez définir les constructeurs qui vous semblent nécessaires. Il n'est pas demandé de réaliser ces types abstraits.
2. A l'aide des types abstraits point et vecteur, spécifier et réaliser un type abstrait droite muni des opérations suivantes :
3. Une droite D définie par un point P et un vecteur V définit deux demi-plans : le demi-plan à droite de D et le demi-plan à gauche de D. Pour savoir dans quel demi-plan se trouve un point M, on calcule le produit scalaire du vecteur orthogonal à V et du vecteur PM. S'il est négatif, M est dans le demi-plan de droite, s'il est positif, M est dans le demi-plan de gauche, s'il est nul, M est sur la droite D. Spécifier et réaliser une fonction qui calcule où se trouve un point M par rapport à une droite D.
4.a On définit un polygone comme une suite d'au moins 3 points. Le i-ème point d'un polygone est Pi, et le i-ème segment est (Pi Pi+1) si 0 <= i < n et (Pn P0) si i = n. Spécifier le type abstrait polygone : les opérations sont l'ajout d'un point à la fin de la séquence (P0, P1, ... Pn), l'opération qui retourne le i-ème point et l'opération qui retourne le i-ème segment.
4.b Réaliser le type polygone en utilisant comme type concret un tableau pour stocker les points (P0 ... Pn).
5. Pour savoir si un polygone est convexe (c'est-à-dire s'il n'a pas de "creux"), on peut utiliser la méthode suivante : pour chaque segment du polygone, il faut que tous les autres points du polygone soient du même côté de la droite qui supporte le segment. Spécifier et réaliser un fonction qui teste si un polygone est convexe.
Dans les langages de programmation comme Pascal, le type prédéfini entier est en réalité un sous-ensemble fini des entiers, qui dépend de la taille des mots mémoire utilisés pour représenter les entiers. Ainsi, si les entiers sont représentés sur 16 bits, l'intervalle est [-32768 .. +32767].
Le but de cet exercice est de définir un type GrandNombre permettant de calculer avec des entiers positifs ou nuls de taille arbitrairement grande. On suppose que l'on dispose du type prédéfini "entier". On se donne le type abstrait suivant :
type chiffre = [0..9];
type GrandNombre
{ constructeurs }
{ le nombre 0 }
zéro : GrandNombre
{ opérations }
{ retourne le ième chiffre d'un nombre
(le rang 0 correspond au chiffre des unités) }
ième : GrandNombre x entier -> chiffre
{ affecte un chiffre du nombre : affecter(gn, r, c)
affecte c au chiffre de rang r de gn.
Le rang 0 correspond au chiffre des unités }
action affecter : DR GrandNombre x entier x chiffre
{ nombre de chiffres d'un nombre }
nbChiffres : GrandNombre -> entier
{ multiplie le nombre par 10n (n > 0) : }
mul10n : GrandNombre x entier -> GrandNombre
fin
1. A l'aide des constructeurs et opérations du type abstrait, spécifier et réaliser la fonction permettant d'additionner deux GrandNombre, en s'inspirant de la façon dont on additionne deux nombres "à la main".
2. A l'aide des opérations du type abstrait, spécifier et réaliser une fonction qui multiplie un GrandNombre par un chiffre de 0 à 9. Spécifier et réaliser ensuite une fonction qui multiplie deux GrandNombre. Comme pour l'addition, on s'inspirera de la façon dont on effectue une multiplication à la main.
3. Pour réaliser le type abstrait GrandNombre, on utilise un tableau dont chaque élément représente un chiffre du nombre. Si le tableau a 100 éléments, on peut donc représenter des nombres de 100 chiffres. Réaliser les constructeurs et opérations du type abstrait GrandNombre spécifié à la question 1.
Expliquer la différence entre le lexique et la syntaxe d'un langage de programmation. Donner un exemple de programme Pascal contenant au moins une erreur lexicale et une erreur syntaxique.