Physique

Optimisations pour les langages orientés objet

• La dévirtualisation transforme les appels virtuels en appels directs, améliorant ainsi les performances.
• L'inlining réduit la surcharge des appels de fonctions et permet d'autres optimisations.
• D'autres optimisations incluent l'analyse d'échappement, le grossissement de verrou et l'élision de verrou.

Appels virtuels et dévirtualisation

• Un appel virtuel, comme x.foo(), consulte la méthode foo dans la classe de x.
• Il est difficile de déterminer quel code sera appelé en raison de la possibilité que x soit null, de ses différents types potentiels et de l'extensibilité de la hiérarchie des classes.
• La dévirtualisation vise à transformer les appels virtuels en appels directs vers la méthode cible en prouvant que le récepteur x a un type connu.

Approches de la dévirtualisation

• Analyse de la hiérarchie des classes (CHA)
  • Calcule l'ensemble des types possibles pour le récepteur x.
  • Remplace l'appel virtuel par un appel direct s'il existe une seule méthode cible possible.
• Analyse rapide des types (RTA)
  • Similaire à CHA, mais ne prend en compte que les classes réellement instanciées.
• Profilage des sites d'appels virtuels
  • Enregistre les types réels de récepteurs observés au runtime pour un site d'appel virtuel.
  • Remplace l'appel virtuel par un appel direct gardé, basé sur le type observé.

Analyse de la hiérarchie des classes (CHA) en détail

• Détermine tous les types possibles pour le récepteur x en examinant l'ensemble du programme.
• Remplace l'appel virtuel par un appel direct s'il existe une seule méthode cible possible, ce qui peut nécessiter l'examen de l'héritage des méthodes.
• Exemple:
  • Si une classe A a une méthode foo(), et les classes B et C héritent de A et redéfinissent foo(), un appel virtuel à foo() avec un récepteur de type A ne peut pas être dévirtualisé.
• Limitation : Nécessite l'analyse de l'ensemble du programme, ne fonctionne pas avec le code de la bibliothèque et de nombreux appels virtuels ne peuvent pas être dévirtualisés en raison de l'héritage.

Analyse rapide des types (RTA) en détail

• Similaire à CHA mais ne prend en compte que les classes réellement instanciées (celles avec l'opérateur new).
• Plus précis que CHA, permettant de dévirtualiser plus d'appels.
• Exemple:
  • Si seules les instances de la classe A sont créées dans le programme, un appel virtuel à foo() avec un récepteur de type A, B ou C (où B et C héritent de A) peut être dévirtualisé avec RTA.
• Limitations : Nécessite toujours une analyse de l'ensemble du programme, ne gère pas bien la réflexion ou le chargement dynamique de classes, ne tient pas compte du contexte et ne voit pas le comportement au runtime.

Profilage des sites d'appels virtuels en détail

• Enregistre les types réels de récepteurs observés au runtime pour un site d'appel virtuel en insérant du code pour enregistrer les types.
• Remplace l'appel virtuel par un appel direct gardé, basé sur le type observé.
• Exemple:
  • Si x est toujours de type A, l'appel virtuel x.foo() peut être remplacé par un appel direct gardé : if (x instanceof A) { ((A) x).foo(); } else { x.foo(); }.
• Les gardes peuvent être déplacées hors des boucles et combinées pour améliorer les performances.

Inlining

• Les petites méthodes sont de bonnes candidates à l'inlining car cela réduit les frais généraux d'appel.
• L'inlining des méthodes virtuelles est également bénéfique car il permet d'autres optimisations telles que la propagation de constantes et l'élimination du code mort.
• Inliner trop de code est préjudiciable car cela augmente la taille du code, ce qui entraîne des défauts de cache d'instructions et un temps de compilation accru.
• Types d'inlining :
  • Si la méthode cible exacte est connue, alors inline-la.
  • Si un appel direct est gardé, alors inline l'appel direct.
  • S'il y a un appel virtuel, alors spéculer et inline la cible la plus courante. Si cela ne va pas, alors désoptimiser.

Exemple d'inlining

• Dans le code où la méthode x.foo() a été dévirtualisée à un appel direct à A.foo(), A.foo() peut être inline en remplaçant l'appel de la méthode par le corps de la méthode.

Désoptimisation dynamique

• Pour une spéculation incorrecte:
  • Revenir au code d'origine
  • Suivre tout le code inline
  • Restaurer le code d'origine et continuer l'exécution lors d'une violation d'hypothèse
  • Peut être couteux.

Autres optimisations

• L'analyse d'échappement détermine si un objet est utilisé uniquement dans une méthode, ce qui permet de l'allouer sur la pile au lieu du tas.
• Le grossissement de verrou combine plusieurs verrous en un seul pour réduire la surcharge de l'acquisition et de la libération des verrous.
• L'élimination de verrou supprime les verrous inutiles si un objet est utilisé par un seul thread.

Résumé

• Les langages orientés objet présentent des défis d'optimisation uniques tels que des appels virtuels et des envois dynamiques.
• Les techniques visant à améliorer les performances comprennent la dévirtualisation, l'inlining, l'analyse d'échappement, le grossissement de verrou et l'élision de verrou.

Vecteurs

• La somme vectorielle peut être déterminée graphiquement en plaçant les vecteurs bout à bout ou analytiquement en additionnant leurs composantes.

Composantes rectangulaires d'un vecteur

• Un vecteur $\vec{A}$ peut être décomposé en composantes rectangulaires $\vec{A_x}$ et $\vec{A_y}$ telles que $\vec{A} = \vec{A_x} + \vec{A_y}$.
• Le calcul des composantes se fait via $A_x = A \cdot \cos{\alpha}$ et $A_y = A \cdot \sin{\alpha}$.
• Le module d'un vecteur peut être calculé à partir de ses composantes: $A = \sqrt{A_x^2 + A_y^2}$.
• La direction d'un vecteur peut être calculée à partir de ses composantes: $\alpha = \arctan{\frac{A_y}{A_x}}$.

Somme analytique des vecteurs

• Pour additionner des vecteurs analytiquement, il faut additionner leurs composantes respectives.
• Soit $\vec{R} = \vec{A} + \vec{B} + \vec{C} +...$, alors $R_x = A_x + B_x + C_x +...$ et $R_y = A_y + B_y + C_y +...$.
• Le vecteur résultant est $R = \sqrt{R_x^2 + R_y^2}$ à un angle de $\alpha = \arctan{\frac{R_y}{R_x}}$.

Produit de vecteurs

• Le produit scalaire de deux vecteurs est un scalaire donné par $\vec{A} \cdot \vec{B} = A \cdot B \cdot \cos{\alpha}$ ou $\vec{A} \cdot \vec{B} = A_x \cdot B_x + A_y \cdot B_y$.
• Le module du produit vectoriel de deux vecteurs est donné par $|\vec{A} \times \vec{B}| = A \cdot B \cdot \sin{\alpha}$. La direction du vecteur résultant est perpendiculaire au plan formé par les vecteurs $\vec{A}$ et $\vec{B}$ et peut être trouvé par la règle de la main droite. Soit $\vec{A} \times \vec{B} = (A_y \cdot B_z - A_z \cdot B_y)\hat{i} + (A_z \cdot B_x - A_x \cdot B_z)\hat{j} + (A_x \cdot B_y - A_y \cdot B_x)\hat{k}$.

Définition d'un espace vectoriel

• Un espace vectoriel sur un corps K est un ensemble E avec une addition vectorielle et une multiplication scalaire qui satisfont huit axiomes.
• Les axiomes incluent l'associativité et la commutativité de l'addition, l'existence d'un élément neutre et d'un inverse additif, ainsi que des propriétés de distributivité et d'associativité pour la multiplication scalaire.

Exemples courants d'espaces vectoriels

• $\mathbb{R}^n$ : l'ensemble des n-uplets de nombres réels.
• $\mathbb{C}^n$ : l'ensemble des n-uplets de nombres complexes.
• $\mathbb{K}[X]$ : l'ensemble des polynômes à coefficients dans $\mathbb{K}$.
• $\mathcal{F}(X, \mathbb{K})$ : l'ensemble des fonctions de X vers $\mathbb{K}$.

Sous-espace vectoriel

• Un sous-ensemble F d'un espace vectoriel E est un sous-espace vectoriel si F est non vide, fermé sous l'addition vectorielle et fermé sous la multiplication scalaire.

Combinaison linéaire

• Une combinaison linéaire des vecteurs $v_1, v_2, \dots, v_n$ est une expression de la forme $\lambda_1 v_1 + \lambda_2 v_2 + \dots + \lambda_n v_n$, où $\lambda_i$ sont des scalaires.

Indépendance linéaire

• Les vecteurs $v_1, v_2, \dots, v_n$ sont linéairement indépendants si $\lambda_1 v_1 + \lambda_2 v_2 + \dots + \lambda_n v_n = 0$ implique que tous les $\lambda_i$ doivent être nuls.

Base d'un espace vectoriel

• Une base d'un espace vectoriel est un ensemble de vecteurs qui est à la fois linéairement indépendant et générateur de cet espace vectoriel.

Dimension d'un espace vectoriel

• Définit le nombre de vecteurs dans une base est ce que l'on définit en terme de dimension

Applications linéaires

• Une application linéaire est une fonction $f : E \rightarrow F$ entre deux espaces vectoriels qui préserve l'addition vectorielle et la multiplication scalaire.

Noyau et image

• Le noyau d'une application linéaire f est l'ensemble des vecteurs qui sont envoyés sur le vecteur nul.
• L'image d'une application linéaire f est l'ensemble des vecteurs qui sont l'image d'au moins un vecteur.

Théorème du rang

• Pour une application linéaire $f : E \rightarrow F$ où $E$ est de dimension finie, on a : $\text{dim}(E) = \text{dim}(\text{Ker}(f)) + \text{dim}(\text{Im}(f))$

Matrices

• Une matrice est un tableau de nombres ayant des lignes et colonnes

Transposition, inverse et déterminant

• La transposée d'une matrice est obtenue en échangeant les lignes et les colonnes de la matrice.
• Une matrice carrée est inversible s'il existe une autre matrice donnant la matrice identité lorsque les deux sont multipliées.
• Le déterminant d'une matrice carrée fournit des informations sur les propriétés de la matrice, comme son inversibilité.

Valeurs propres et vecteurs propres

• Un vecteur propre v d'une matrice A satisfait l'équation Av = λv, où λ est la valeur propre.

Diagonalisation

• Une matrice A est diagonalisable s'il existe une matrice inversible P et une matrice diagonale D telles que A = PDP⁻¹.

Qu'est-ce que la statistique descriptive ?

• Branche des mathématiques permettant de collecter et d'organiser de grandes quantités de données
• Permet d'identifier des groupes, communiquer des informations complexes de manière concise

Types de données

• Quantitative: Données qui peuvent être mesurées numériquement
• Qualitative: Données qui ne peuvent pas être mesurées numériquement

Mesures de la tendance centrale

• Les valeurs représentant le centre d'un ensemble de données qui inclut des moyennes, des médianes et un nombre qui apparaissent avec plus fréquentes fréquences dans les données.
• Moyens:
  • Moyenne des données
  • Calculé en sommant toutes les valeurs et en divisant le résultat par le nombre de valeurs
• Médiane:
• Valeur située au centre des données lorsqu'elles sont organisées de la plus petite à la plus grande
• Mode:
  • Valeur qui apparaît le plus souvent dans les données

Mesures de dispersion

• Ces mesures indiquent le degré de disparité des données autour de la mesure d'inductance centrale:
  • Intervalle: Différence entre la valeur maximale et la valeur minimale des données
  • Variance: Mesurer la distance entre les données et la moyenne
  • Écart type: Racine carrée de la variance

Graphiques et tableaux

• Outils efficaces pour visualiser et transmettre les données efficacement
• Histogramme, diagramme à bandes, diagramme à secteurs
• Les tableaux sont une excellente façon d'organiser et de présenter les données qui contiennent des variables et des mesures de tendance centrale

Logiciel statistique

• Programmes qui effectuent des analyses statistiques descriptives comme Microsoft Excel, SPSS et Python

Vecteurs

• Addition vectorielle:
• Graphiquement:
  • Placer les vecteurs en succession en maintenant l'ordre de grandeur de la direction et du sens
  • Le vecteur résultant doit commencer à partir de l'endroit où le premier vecteur commence et doit finir là où le dernier vecteur finit.
• Analytiquement:
• Décomposer chaque vecteur en composantes rectangulaires
• Ajouter toutes les composantes horizontales des vecteurs à la composante horizontale
• Ajouter toutes les composantes verticales des vecteurs à la composante verticale
• Le théorème de Pythagore calcule la direction du vecteur résultant à l'aide de la tangente

Produit de vecteurs

• Produit scalaire:
• $\vec{a} \cdot \vec{b} = |\vec{a}| \cdot |\vec{b}| \cdot \cos \alpha$
• Produit vectoriel:
  • $\vec{a} \times \vec{b} = |\vec{a}| \cdot |\vec{b}| \cdot \sin \alpha \cdot \hat{n}$

Cinématique

• MRUV
  • Accélération uniforme $a = \frac{\Delta v}{\Delta t} = \frac{v_f - v_i}{t_f - t_i}$
  • Vitesse uniforme $v = \frac{\Delta x}{\Delta t} = \frac{x_f - x_i}{t_f - t_i}$

Lois de Newton

• Première loi:
  • Tout corps reste dans son état de repos ou de mouvement uniforme à moins d'être contraint de changer son état par des forces qui lui sont imprimées.
• Deuxième loi:
  • L'accélération d'un objet est directement proportionnelle à la force nette qui agit sur lui, prend la même direction et est inversement proportionnelle à la masse de l'objet.
  • $\sum \vec{F} = m \cdot \vec{a}$
• Troisième loi:
• A chaque action s'oppose une réaction toujours égale mais de sens opposé.

Chaleur

• Le coefficient d'état décrit comment le volume d'une substance change en fonction de la température
• $P = \frac{RT}{V-b} - \frac{a}{V^2 + cbV + d b^2}$

Algorithme de Fleury

• Algorithme de la théorie des graphes utilisé pour déterminer le chemin Eulerien dans un graphe
• Cet algorithme ne peut être appliqué qu'aux graphes:
  • Connectée
  • Tout au plus 2 nœuds de degré inégal
• Étapes:
  • Sélectionnez un nœud de départ et un bord qui n'a pas été visité
  • Déplacez et supprimez le fil de bord dans le graphique
  • Répétez et réorganisez la liste des nœuds visités comme un chemin Eulerien