On commence par étudier quelques structure de données supplémentaires, en complément du cours précédent.
Ensuite, on prépare le terrain pour le Devoir à la Maison n°3 qui nécessite quelques bases en algèbre que l'on se propose de revoir.
Vous allez implémenter cette fonction dans le cadre du prochain TP.
En revanche, nous ne chercherons pas à construire une telle liste chaînée immutable dans le cadre de ce cours.
Une liste doublement chaînée conserve une référence vers le noeud précédent.
File d'attente de l'Empire State Building à New York.
Source : Wikipedia (C)
Il s'agit ici d'une implémentation basée sur une liste chaînée.
D'autres implémentations existent.
Au début, on a initial = None et final = None.
Lorsque le 1er noeud est inséré, initial et final pointent tous les 2 dessus.
On conserve une référence vers le dernier élément car on sait que chaque empilement se fait à la fin.
Par conséquent, il faut pouvoir ajouter rapidement un élément à la fin.
Nous avons vu que l'ajout à la fin d'une liste chaînée simple nécessite de traverser tous les éléments, ce qui n'est pas nécessairement rapide.
Nous verrons lors du prochain cours des outils mathématiques pour évaluer la vitesse d'exécution d'un algorithme.
Vous allez implémenter cet algorithme dans le prochain TP.
Il s'agit d'une implémentation alternative basée sur une `list`.
Cette implémentation est plus simple et probablement plus performante que celle avec notre liste chaînée.
Il existe une meilleure structure de données que `list` pour représenter une file d'attente.
Il s'agit de la collection `deque`.
Cette collection offre un profil de performances bien plus intéressant que `list` pour de grandes tailles de données.
Un empilement de pièces.
On ne peut pas retirer les pièces intermédiares sans faire tomber une pièce supérieure.
En tout cas, pas facilement.
Cela montre un problème plus mécanique appelé "Empilement de bloc".
Le surplomb maximal à chaque niveau est proportionnel à la moitié de la série harmonique.
Source : Wikipedia
Il s'agit ici d'une implémentation basée sur une liste chaînée.
D'autres implémentations existent.
Exactement identique à une liste chaînée.
Vous allez implémenter cet algorithme dans le prochain TP.
Il s'agit d'une implémentation alternative basée sur une list.
De la même manière que l'on peut implémenter une queue avec une list, la même chose est possible pour une pile.
On peut aussi bien utiliser un deque pour représenter une queue ou une pile.
Cela peut sembler contre-intuitif, mais c'est pratique.
A ne pas confondre avec FIFA...
A gauche : FIFO (queue).
A droite : LIFO (stack).
Il s'agit d'un diagramme de Venn.
On l'appelle vulgairement un patatoïde.
Vous avez déjà vu ces définitions dans le TD n°3.
Nous repartons de ces définitions avant d'introduire de nouveaux concepts.
Le calcul du déterminant d'une matrice à 2 lignes et 2 colonnes est simplement un produit en croix.
On prend la première ligne de la matrice M.
Chaque élément de la première ligne est multiplié par le déterminant de la matrice 2x2 "opposée".
On ajoute ou soustrait alternativement ces produits.
Le fait de définir un déterminant d'une matrice 3x3 en fonction de déterminants 2x2 en fait une définition récursive.
La condition de fin de la récursion est l'arrivée sur une matrice 2x2.
Le calcul d'un mineur d'une matrice est précisé sur la diapositive suivante.
C'est dans cette définition que se retrouve la nature récursive de ce mode de calcul.
Un système d'équations est dit "linéaire" si ses inconnues n'ont pas d'exposant.
Tout système d'équations linéaires peut s'écrire sous forme matricielle.
Ici, on donne un exemple pour 3 équations à 3 inconnues.
On reviendra plus tard sur l'inversion matricielle.
Il existe d'autres méthodes pour résoudre ce système d'équations sous forme matricielle.
La règle de Cramer nous permet de résoudre ce système d'équations en calculant uniquement des déterminants.
Le dénominateur est le déterminant de la matrice M qui représente les coefficients du système d'équations.
Le nominateur est la matrice M à laquelle on a remplacé une colonne par le vecteur D(d1, d2, d3).
La règle de Cramer permet de résoudre les systèmes de N équations linéaires à N inconnues, si le déterminant de M est non nul.
Nous allons voir d'autres méthodes pour résoudre ce système, certaines plus efficaces.
On va commencer par quelques définitions supplémentaires
A priori, une matrice diagonale est très facile à inverser.
Si on diagonalise une matrice, est-ce que cela nous aide à l'inverser ?
Une matrice n'est pas forcément diagonalisable.
Il faut que le nombre de valeurs propres soit égal au rang de la matrice pour qu'elle soit diagonalisable.
Vous verrez tout ceci plus en détails en cours de mathématiques.
Cette méthodologie peut être automatisée.
Cela étant, il faut calculer P^{-1} pour revenir à la matrice initiale.
Donc la diagonalisation n'est pas le bon procédé pour inverser une matrice.
En pratique, il existe d'autres approches.
L'une de ces approches consiste à utiliser la transposée de la co-matrice, mais cela entraine trop de calculs dans le cas général.
Nous allons voir une approche efficace : le pivôt de Gauss, ou plus généralement l'élimination de Gauss-Jordan.
Autrement dit, il s'agit d'une simple concaténation des matrices M et D.
Cette définition est utile pour l'élimination de Gauss-Jordan.
Il s'agit des étapes clés de l'algorithme.
Cet algorithme est illustré dans les diapositives suivantes.
Vous aurez à l'implémenter dans le DM n°3.