Analyse et implémentation en Java du flocon de koch et vérificateur d'orthographe

Résumé du document

Document présentant l'analyse et l'implémentation en Java du flocon de koch et le vérificateur d'orthographe, l'analyse concerne ainsi la description du problème, la complexité, l'exactitude, la terminaison de l'algorithme.

Extraits

[...] Le grand problèmes résiderait donc à déterminer à chaque fois que cela est nécessaire les coordonnées des points qui forment le nouveau triangle (cas de C et D pour la figure connaissant les coordonnées des points de départ (cas de A et E pour la figure Figure a La détermination des coordonnées des points C et D sera valable pour tous les triangles générés et s'effectuera à l'aide de certaines formules de vecteur et de rotation: Coordonnées de B Vecteur (AB)=vecteur / 3 Abscisse de B : [(abscisse(E)- abscisse / + abscisse Ordonnée de B :[(ordonnée(E)- ordonnée / + ordonnée Coordonnées de D Vecteur = X vecteur / 3 Abscisse de D : X (abscisse(E) abscisse / 3 +abscisse Ordonnée de D : [2X (ordonnée(E) ordonnée / 3 + ordonnée Coordonnées de C La détermination des coordonnées de C s'effectueront à l'aide des formules de rotation compte tenue du fait que BC est l'image de BD par la rotation de centre B et d'angle 60°. [...]

[...] L'ensemble des solutions est : t(n)=a*4exp Détermination de a est réel) ; t(1)=30 ( conditions initiales) ,on obtient l'équation : a=7,5 On a donc l'ensemble solution égale à t(n)=7,5*4exp(n) On conclut donc que notre procédure fonctionne en (7,5*4exp d'où elle est exponentielle. 3-4 Complexité de l'algorithme principal du flocon L'algorithme utilise trois fois la procédure dessinfloc chaque procédure dessinfloc ayant une complexité exponentielle nous allons utiliser la règle du maximum et nous nous rendrons compte que la complexité de notre algorithme fonctionne en (10*4exp donc exponentielle. [...]

[...] Terminaison de l'algorithme du flocon Nous allons montrer d'abord que la procédure dessinfloc se termine et déduire que l'algorithme flocon se termine également. SI N=0 on trace juste le segment d'un point de coordonnée donné vers un autre de la procédure dessinfloc, nous pouvons conclure que l'algorithme se termine pour N=0. [...]

[...] Figure 1 dessinfloc abscisse(A),ordonnée(A), abscisse(E),ordonnée(E)) Se positionner en A Si alors tracer une ligne allant de A à E Sinon { on va construire le niveau suivant sur les segment AB,BC,CD,DE } déterminer les coordonnées de B { point au tiers de AE } déterminer les coordonnées de D { point au deux tiers de AE } déterminer les coordonnées de C { sommet du triangle généré sur le tiers central de AE } {Nous allons réitérer cette procédure au segment AB, BC, CD, DE à l'ordre dessinfloc (N-1,abscisse ordonnée abscisse(B),ordonnée(B)) {on recommence la procédure sur AB} dessinfloc (N-1,abscisse (B),ordonnée(B), abscisse(C),ordonnée(C)) {on recommence la procédure sur BC} dessinfloc (N-1,abscisse(C), ordonnée(C), abscisse(D),ordonnée(D)) {on recommence la procédure sur CD} dessinfloc (N-1,abscisse(D),ordonnée(D), abscisse(E),ordonnée(E)) {on recommence la procédure sur DE} FINSI 2-2 L'algorithme principale Nous allons supposer que nous avons les coordonnées des trois points appelés E et F au départ, nous allons appelé notre algorithme flocon Algorithme flocon Début Entrer les coordonnées de A Entrer les coordonnées de E Entrer les coordonnées de F Entrer le niveau N dessinfloc (N,abscisse(A),ordonnée(A), abscisse(E),ordonnée(E)) dessinfloc (N,abscisse(A),ordonnée(A), abscisse(F),ordonnée(F)) dessinfloc (N,abscisse(F),ordonnée(F), abscisse(E),ordonnée(E)) Fin 3-Complexité de l'algorithme le flocon 3-1 Opérations élémentaires Les opérations les plus utilisées dans le cadre de la mise sur pied de l'algorithme du flocon en général et de la procédure dessinfloc en particulier sont les opérations effectuées dans le cadre du calcul des cordonnées des nouveaux points générés d'un niveau à un autre, nous avons ainsi comme opération : L'addition (somme et différence) La multiplication La division Fonctions usuelles cosinus et sinus 3-2 Complexité des trois points générés d'un niveau de récursivité à un autre Nous allons exploiter la figure ci-dessous pour illustrer cette complexité Rappelons les coordonnées des points C et D Abscisse ( C ) : [ [abscisse (D)-abscisse (B)]cos(60°)-[ordonnée ordonnée(B)]sin(60°)] + abscisse Ordonnée : [ [abscisse abscisse (B)]sin(60°)-[ordonnée ordonnée(B)]cos(60°)] ] +ordonnée Abscisse de B : [(abscisse(E)- abscisse / + abscisse Ordonnée de B :[(ordonnée(E)- ordonnée / + ordonnée Abscisse de D : X (abscisse(E) abscisse / 3 +abscisse Ordonnée de D : [2X (ordonnée(E) ordonnée / 3 + ordonnée Nous pouvons donc dire que pour la détermination des points avant le passage d'un niveau de récursivité à un autre on effectuera 30 opérations. 3-3 Complexité de la fonction dessin La procédure dessinfloc au niveau n calcule les coordonnées des nouveaux points générés et s'appelle récursivement au niveau n-1 quatre fois d'où l'équation de partition : dessinfloc dessinfloc + 30 Nous obtenons l'équation de partition : =30 Nous résolvons l'équation linéaire : nous trouvons la solution égale à 4. [...]

[...] Rappelons donc qu'un vecteur de coordonnées qui subi une rotation d'angle q autour de l'origine se transforme en : V=X cos(q) Y sin(q) (en abscisse) S=X sin(q) + Y cos(q) (en ordonnée) Nous aurons donc : Abscisse de C Abscisse ( C ) : [ [abscisse (D)-abscisse (B)]cos(60°)-[ordonnée ordonnée(B)]sin(60°)] + abscisse Ordonnée : [ [abscisse abscisse (B)]sin(60°)-[ordonnée ordonnée(B)]cos(60°)] ] +ordonnée 2-Analyse 2-1 Algorithme Nous présenterons ici la procédure récursive de l'algorithme qui permet de générer les triangles équilatéraux à partir d'un segment et l'algorithme principal en vue de montrer comment cette procédure récursive sera appelée. 2-1-1 Procédure récursive de l'algorithme du flocon Nous allons appeler cette procédure dessinfloc qui va prendre en paramètre : les coordonnées des deux points qui forment le segment le paramètre n qui indique le niveau que l'on veut utiliser pour tracer le flocon Nous allons utiliser la figure1 pour bien illustrer cette fonction. [...]