-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathindex.html
More file actions
169 lines (168 loc) · 10.1 KB
/
index.html
File metadata and controls
169 lines (168 loc) · 10.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
<!DOCTYPE html>
<html lang="fr">
<head>
<meta charset="utf-8">
<title>B1 - Laboratoire n°3</title>
<!-- Latest compiled and minified CSS -->
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css" integrity="sha384-BVYiiSIFeK1dGmJRAkycuHAHRg32OmUcww7on3RYdg4Va+PmSTsz/K68vbdEjh4u" crossorigin="anonymous">
<link rel="stylesheet" href="style.css" >
</head>
<body>
<div class="container">
<div class="page-header">
<h1>2231.3 - Algorithmes numériques : Laboratoire n°3</h1>
<i>Groupe B1</i>
<p>Auteurs :</p>
<ul>
<li>Raphael Margueron</li>
<li>Damian Petroff</li>
<li>Bastien Wermeille</li>
</ul>
</div>
<div class="row">
<div class="col-md-12 col-sm-12">
<h2>Utilisation</h2>
<p>2 possibilités de chargement du fichier. Première, utilisation du drag and drop du fichier à lire dans la zone prévue à cette effet.
Second option, copier directement le contenu du fichier dans la zone prévue à cet effet.
Nous avons implémenter une 3ème solution mais celle-ci ne fonctionne pas avec tous les navigateurs à cause de restrictions de ceux-ci.
Cette méthode permet de sélectionner directement le fichier JSON à charger à gauche de zone de drag and drop, cliquer sur le nom du fcihier à charger.
Chrome et Safari ne permettent pas d'utiliser cette solution.
</p>
</div>
</div>
<hr>
<div class="row">
<div class="col-md-8 col-sm-12">
<textarea id="holder">Drag your file HERE!</textarea>
<button id="solve" class="btn btn-primary">Calculer</button>
<div id="chronotime"></div>
</div>
<div class="col-md-4 col-sm-12">
<h2>Charger un fichier</h2>
<p>Cliquez sur le fichier voulu, attention fonctionnalité disponible uniquement avec Firefox et Edge.</p>
<ul id="files">
<li>matrice_0x0.json</li>
<li>matrice_2x2.json</li>
<li>matrice_3x3.json</li>
<li>matrice_50x50.json</li>
<li>matrice_250x250.json</li>
<li>matrice_300x300.json</li>
<li>matrice_avecPB_0x0.json</li>
<li>matrice_avecPB_3x3_avec_A_a_0.json</li>
<li>matrice_avecPB_3x3_avec_SwapObligatoire.json</li>
</ul>
</div>
<div class="col-md-12 col-sm-12">
<h2>Résultats</h2>
<div id="result"></div>
</div>
</div>
<hr>
<div class="row">
<div class="col-md-12">
<h1>Rapport</h1>
<h2>Contextualisation</h2>
<p>Le but de ce labo est la résolution d'un système d'équations linéaires avec la méthode de Gauss. L'utilisateur a la possibilité de choisir un fichier ou de directement entrer une matrice dans la zone prévue à cet effet au format JSON.</p>
<p>La matrice devra cependant être carrée et valide. Notre algorithme ne permet pas de trouver des solutions non constantes ou une infinité de solutions. Si un tel cas se présente, un message d'erreur est affiché.</p>
<p>Notre programme permet de visualiser les résultats trouvés s'ils sont de nature constante.</p>
<h2>Méthodologie de développement</h2>
<div>
<p>
Nous avons séparé le chargement du système d'équations linéaires et la résolution de l'équation en deux classes : Matrix et Solver.
</p>
<h3>Système d'équations linéaires (Matrix)</h3>
<p>
Les systèmes d'équations linéaires sont représentés de la manière suivante : AX = B
</p>
<p>
Les équations linéaires nous sont données sous la forme de fichiers JSON.
Les trois attributs suivants sont chargés et doivent être présents dans le fichier JSON.
</p>
<ul>
<li>n : Correspond à la taille du vecteur X et B ainsi qu'aux dimensions de la matrice A</li>
<li>A : Correspond à la matrice A</li>
<li>B : Correspond au vecteur B</li>
</ul>
<p>
Les valeurs des trois attributs doivent être sous la forme d'un tableau 1D dans le fichier JSON.
Quand nous chargeons le système d'équations linéaires, nous importons la matrice A dans un tableau 2D et nous ajoutons à cette matrice A une nouvelle colonne contenant le vecteur B (à la fin de chaque ligne du tableau 2D, on ajoute la valeur de la matrice B du même numéro de ligne). Cela nous permet de n'avoir qu'un "grand" tableau 2D. Qui est de taille N x (N+1). => Principe de la matrice augmentée (Augmented matrix).
</p>
<p>
Une fois la matrice chargée, il est possible d'effectuer les opérations de matrice suivante :
</p>
<dl>
<dt>swapRows(i, j)</dt>
<dd>Échange les deux lignes des indices passés en paramètre</dd>
<dt>indiceMaxColumn(iColumn, iRowStart=0)</dt>
<dd>Retourne l'indice de ligne où la valeur est maximale pour l'indice de la colonne spécifiée (il est possible de passer un indice pour la chercher à partir d'une ligne spécifique)</dd>
<dt>substractLineFactor(iRowRef, iRowSub, factor, iColumnStart=0)</dt>
<dd>Soustrais la ligne de référence (ligne d'indice iRowRef) par la ligne de soustraction (ligne d'indice iRowSub) multipliée par un facteur (factor).
Il est également possible de passer un numéro de colonne à partir duquel on commence l'opération (optimisation).</dd>
</dl>
</div>
<h3>Solutionneur (Solver)</h3>
<div>
<p>
Cette classe possède uniquement un attribut qui stockera le vecteur de solutions, une fois la fonction de résolutions appelées.
</p>
<p>
Voici la liste des fonctions de la classe :
</p>
<dl>
<dt>gaussTransform(matrix)</dt>
<dd>
Réalise une élimination de Gauss-Jordan de la matrice (Méthode de Gauss).
Il en est l'implémentation du pseudocode de l'algorithme qui se trouve sur la page Wikipédia anglaise d'élimination Gauss-Jordan. (Voir les références de développement).
Son fonctionnement est le suivant :
<ul>
<li>
On initialise des variables qui représentent le pivot à 0.
Celui pour les lignes est appelé h. Et celui des colonnes est appelé k.
</li>
<li>
On recherche l'indice de la plus grande valeur(en absolue), avec notre fonction indiceMaxColumn à la colonne du pivot (k) et à partir de la ligne du pivot (h). <i>Si notre pivot vaut 0, il ne vaut plus la peine de chercher continuer. Le système d'équations n'a pas de solution. Évidemment cela impliquerait une division par zéro dans l'étape suivante.</i>
</li>
<li>
Si l'indice de ligne du pivot n'est pas égal à l'indice de la valeur max, on inverse les lignes pour avoir la ligne d'indice max sur la ligne sur laquelle on "travaille" (ligne du pivot).
</li>
<li>
Pour toutes les lignes en dessous de notre pivot : On soustrait à la ligne courante la ligne du pivot de telle sorte à annuler la valeur du pivot (En multipliant la ligne un facteur).
<i>A noter que nous avons optimisé la soustraction en ne soustrayant qu'à partir de la position du pivot(colonne)+1 car le pivot va de toute façon être annulé (On le met donc 'manuellement' à 0, par une affectation.)</i>
</li>
<li>
Puis on déplace le pivot de 1 en horizontale et de 1 en vertical puis on recommence jusqu'à être à la fin de la matrice.
</li>
</ul>
</dd>
<dt>resolveX(matrix)</dt>
<dd>Va parcourir la matrice triangulaire (droite à gauche puis de bas en haut) pour résoudre le système d'équations (générer le vecteur X de la classe). Elle fonctionne selon la méthode vue en cours. C'est-à-dire qu'on trouve la solution dans la ligne qui n'a qu'une inconnue puis on remplace cette inconnue dans la ligne qui en a deux, etc, etc...</dd>
<dt>displayX()</dt>
<dd>Affiche le vecteur de solution (l'attribut x de classe) dans la balise HTML prévu à cet effet.
Affiche également des messages d'erreur en cas d'impossibilité de trouver des solutions.</dd>
<dt>solve(matrix)</dt>
<dd>Reçois une référence sur l'objet Matrix, chronomètre le temps pour : effectuer la transformation de gausss (gaussTransform) et résoudre le système (resolveX).
L'affichage du résultat (DisplayX) n'est pas appelé dans cette classe et n'est ainsi pas chronométré.
Cette fonction est la fonction principale de la classe.</dd>
</dl>
</div>
<h2>Tests</h2>
<p>Nous avons testé notre code avec toutes les matrices mises à notre disposition par notre responsable. Tous les tests effectués ont été concluants!</p>
<h2>Conclusion et perspective</h2>
<p>Nous sommes satisfaits de notre résultat, notre code permet de résoudre une matrice de 300x300 en ~13ms avec Firefox Quantum 59.0.2 (64 bits) + Lenovo Thinkpad P50.</p>
<p>Finalement, en ce qui concerne les perspectives, il serait intéressant de pouvoir comparer notre algorithmes avec d'autres tels que ceux utilisés par Mathematica par exemple.</p>
</div>
</div>
<hr>
<footer>
<h2>Références de développement</h2>
<ul class="a-autoFill">
<li><a href="https://stackoverflow.com/questions/11313414/html5-drag-and-drop-load-text-file-in-a-textbox-with-javascript"></a></li>
<li><a href="https://en.wikipedia.org/wiki/Gaussian_elimination#Pseudocode"></a></li>
<li><a href="http://html5demos.com/file-api"></a></li>
<li><a href="https://developer.chrome.com/apps/xhr"></a></li>
</ul>
</footer>
</div>
<script src="script.min.js"></script>
</body>
</html>