Micro Med 2

Trading Algorithmique et à Haute Fréquence

• Le trading algorithmique utilise des instructions informatiques préprogrammées pour l'exécution des ordres.
• Le trading à haute fréquence (THF) est un sous-ensemble du trading algorithmique avec des taux de rotation élevés, des ratios ordre/transaction élevés, la co-location et des horizons d'investissement à très court terme.

Définitions

Trading Algorithmique

• Exécution ou ordres d'instruments financiers utilisant des instructions informatiques préprogrammées.
• Ces instructions prennent en compte des variables telles que le prix, le timing et le volume.
• D'autres noms incluent le trading automatisé, le trading « boîte noire » et le trading systématique.

Trading à Haute Fréquence

• Sous-ensemble du trading algorithmique caractérisé par des taux de rotation élevés, des ratios ordre/transaction élevés.
• Caractérisé aussi par la co-location dans les centres de données boursiers et des horizons d'investissement très courts.

Motivation

Avantages du négotiation Algorithmique

• Réduction des coûts de transaction et amélioration de l'exécution des ordres.
• Accès à la liquidité et anonymat.
• Exploitation des opportunités d'arbitrage.
• Rétro-test et automatisation.

Inconvénients de la négociation Algorithmique

• Risque de modèle et les événements imprévus.
• Problèmes avec la qualité des données et la sur-optimisation.
• Erreurs du système et surveillance.
• Risque de manipulation du marché.

Mise en œuvre

Stratégies de negociation Algorithmique

• Suivi de tendance et retour à la moyenne.
• Arbitrage et tenue de marché.
• Rééquilibrage des fonds indiciels et négociation de portefeuille.
• Algorithmes d'exécution (par exemple, TWAP, VWAP, etc.).

Comment mettre en œuvre:

• Recherche, collecte et nettoyage des données.
• Simulation de la stratégie sur les données historiques.
• Simulation de la stratégie sur des données réelles sans argent réel.
• Déploiement de la stratégie avec de l'argent réel
• Surveillance continue de la performance de la stratégie.

Réglementation

• Le trading algorithmique fait l'objet d'un examen réglementaire, en particulier après des événements tels que le Flash Crash de 2010.
• Exigences réglementaires : contrôles des risques, tests et surveillance, transparence et conformité.

Matrices - Concepts de Base

• Une matrice m x n est un tableau rectangulaire de nombres réels ou complexes avec m lignes et n colonnes.
• Les éléments de la matrice sont notés aij, où i est le numéro de la ligne et j est le numéro de la colonne.
• Si m = n, la matrice A est une matrice carrée.

Exemples

• A = [ [1, 2, -1], [0, -2, 3] ] est une matrice 2 x 3.
• B = [ [-1, 5], [0, -2] ] est une matrice 2 x 2, c'est-à-dire une matrice carrée.
• C = [ [1], [2], [-1] ] est une matrice 3 x 1, c'est-à-dire un vecteur colonne.
• D = [ [1, 2, -1] ] est une matrice 1 x 3, c'est-à-dire un vecteur ligne.

Égalité des matrices

• Deux matrices A=(aij)m x n et B=(bij)p x q sont égales si m=p, n=q et aij=bij pour tout i et j.

Transposition de matrices

• La transposée AT d'une matrice A=(aij)m x n est obtenue en échangeant les lignes et les colonnes.
• La taille de la transposée est n x m.

Exemples

• Si A = [ [1, 2, -1], [0, -2, 3] ], alors AT = [ [1, 0], [2, -2], [-1, 3] ].

Matrices carrées

• Une matrice carrée A est symétrique si AT = A.

Exemples

• La matrice A = [ [1, 2, -1], [2, 0, 3], [-1, 3, 5] ] est symétrique.

Cinétique Chimique

• La cinétique chimique étudie les vitesses de réactions et les facteurs qui les influencent.

Vitesse de réaction

• La vitesse de réaction mesure le changement de concentration d'un réactif ou d'un produit par unité de temps.
• Unités : mol dm-3 s-1.

Loi de vitesse

• L'équation de vitesse exprime la vitesse d'une réaction en fonction des concentrations des réactifs.
• Pour aA + bB → cC + dD, la vitesse peut être exprimée comme Vitesse = k[A]x[B]y.
• k est la constante de vitesse.
• x est l'ordre de la réaction par rapport à A.
• y est l'ordre de la réaction par rapport à B.
• x+y est l'ordre global de la réaction.
• La loi de vitesse ne peut être déterminée qu'expérimentalement.

Ordre de réaction

• L'ordre d'une réaction est la puissance à laquelle la concentration d'un réactif est élevée dans la loi de vitesse.
• Ordre zéro : la vitesse de réaction est indépendante de la concentration du réactif.
• Premier ordre : La vitesse de réaction est directement proportionnelle à la concentration du réactif.
• Ordre deux : La vitesse de réaction est proportionnelle au carré de la concentration du réactif.

Constante de vitesse

• La constante de vitesse (k) est la constante de proportionnalité dans la loi de vitesse.
• les unités de k dépendent de l'ordre général de la réaction.

Demi-vie

• La demi-vie (t1/2) d'une réaction est le temps nécessaire pour que la concentration d'un réactif diminue jusqu'à la moitié de sa valeur initiale.
• Premier ordre : t1/2 = 0.693/k
• Deuxième ordre : t1/2 = 1/(k[A]0)
• Ordre zéro : t1/2 = [A]0/(2k)
• [A]0 est la concentration initiale de A.

La distribution de Maxwell-Boltzmann

• La distribution décrit les vitesses des particules dans un gaz.
• La distribution se décale vers la droite et s'élargit lorsque la température augmente.
• Plus de molécules ont suffisamment d'énergie pour surmonter l'énergie d'activation (Ea) à des températures plus élevées.

Énergie d'activation

• L'énergie d'activation (Ea) est l'énergie minimale nécessaire pour qu'une réaction se produise.
• Les réactions avec des énergies d'activation plus faibles se produisent plus rapidement.
• L'énergie d'activation est la différence entre l'énergie du complexe activé et l'énergie des réactifs.

L'équation d'Arrhenius

• L'équation d'Arrhenius relie la constante de vitesse à l'énergie d'activation et à la température.
• k = Ae-Ea/RT, ln(k) = (-Ea/R)(1/T) + ln(A)
• Une représentation graphique de ln(k) en fonction de 1/T donne une ligne droite dont la pente est -Ea/R.
• k est la constante de vitesse, A est le facteur de fréquence, Ea est l'énergie d'activation, R est la constante des gaz et T est la température en Kelvin.

Catalyseur

• Un catalyseur augmente le taux de réaction sans être consommé.
• Les catalyseurs fournissent un autre processus de réaction avec une énergie d'activation inférieure.
• Les catalyseurs ne modifient pas la constante d'équilibre.
• Un catalyseur homogène est dans la même phase que les réactifs.
• Un catalyseur hétérogène est dans une phase différente de celles des réactifs.

Relations

• Les relations sont utilisées pour décrire les associations entre des ensembles.

Définition

• Étant donné des ensembles A et B, une relation entre A et B est un sous-ensemble R ⊆ A x B.
• Pour (a, b) ∈ R, on dit que "a est en relation R avec b" ou simplement "a R b".

Exemple

• Soient A = {chiens} et B = {personnes}.
• R = {(a, b) ∈ A x B | b est le propriétaire de a}

Relations sur un Ensemble

• Une relation sur un ensemble A est un sous-ensemble R ⊆ A x A.

Exemple

• Soient A = ℕ et R = {(a, b) ∈ ℕ x ℕ | a < b}

Propriétés des Relations

Soit R ⊆ A x A une relation sur A. R est dite :

• réflexive si ∀ a ∈ A : (a, a) ∈ R.
• symétrique si ∀ a, b ∈ A : (a, b) ∈ R ⇒ (b, a) ∈ R.
• transitive si ∀ a, b, c ∈ A : (a, b) ∈ R et (b, c) ∈ R ⇒ (a, c) ∈ R.

Exemples

1. Soient A = ℤ et R = {(a, b) ∈ ℤ x ℤ | a ≤ b}.
   • réflexive : ∀ a ∈ ℤ : a ≤ a.
   • non symétrique : 1 ≤ 2 mais 2 ≰ 1.
   • transitive : a ≤ b et b ≤ c ⇒ a ≤ c.
2. Soient A = {ensembles} et R = {(a, b) ∈ A x A | a ⊆ b}.
   • réflexive : ∀ a ∈ A : a ⊆ a.
   • non symétrique : a ⊆ b mais b ⊈ a.
   • transitive : a ⊆ b et b ⊆ c ⇒ a ⊆ c.

Relations d'Équivalence

• Une relation R ⊆ A x A sur A est une relation d'équivalence si R est réflexive, symétrique et transitive.

Exemples

1. Soient A = ℤ et n ∈ ℕ.

   • R = {(a, b) ∈ ℤ x ℤ | a ≡ b (mod n)}, c'est-à-dire que a - b est divisible par n.
     • réflexive : a ≡ a (mod n) car a - a = 0 est divisible par n.
     • symétrique : a ≡ b (mod n) ⇒ a - b = k · n pour un k ∈ ℤ. Donc b - a = -k · n, c'est-à-dire b ≡ a (mod n).
     • transitive : a ≡ b (mod n) et b ≡ c (mod n) ⇒ a - b = k · n et b - c = l · n pour k, l ∈ ℤ. Donc a - c = (a - b) + (b - c) = k · n + l · n = (k + l) · n, c'est-à-dire a ≡ c (mod n).

2. Soient A = {lignes droites dans le plan} et R = {(a, b) ∈ A x A | a || b}.

   • réflexive : a || a.
   • symétrique : a || b ⇒ b || a.
   • transitive : a || b et b || c ⇒ a || c.

Classe d'Équivalence

• Soit R ⊆ A x A une relation d'équivalence sur A. Pour a ∈ A, la classe d'équivalence de a est définie comme :
  • [a] = {b ∈ A | (a, b) ∈ R} = {b ∈ A | a R b}

Exemple

• Soient A = ℤ, n ∈ ℕ et R = {(a, b) ∈ ℤ x ℤ | a ≡ b (mod n)}.
  • [0] = {b ∈ ℤ | 0 ≡ b (mod n)} = {b ∈ ℤ | b est divisible par n} = {k · n | k ∈ ℤ}.
  • [1] = {b ∈ ℤ | 1 ≡ b (mod n)} = {b ∈ ℤ | b - 1 est divisible par n} = {1 + k · n | k ∈ ℤ}.
  • En général : [a] = {a + k · n | k ∈ ℤ}

Théorème

• Soit R ⊆ A x A une relation d'équivalence sur A. Alors :
  1. ∀ a ∈ A : a ∈ [a]
  2. ∀ a, b ∈ A : [a] = [b] ⇔ (a, b) ∈ R
  3. ∀ a, b ∈ A : [a] ≠ [b] ⇒ [a] ∩ [b] = ∅

Implication

• Les classes d'équivalence d'une relation d'équivalence forment une partition de A, c'est-à-dire que A est l'union disjointe des classes d'équivalence.

Définition

• L'ensemble de toutes les classes d'équivalence de A par rapport à R est appelé l'espace quotient de A par rapport à R :
  • A/R = {[a] | a ∈ A}

Théorème de Bayes

• Le théorème de Bayes décrit la probabilité d'un événement, sur la base d'une connaissance préalable des conditions qui peuvent être liées à l'événement.

Formulation

• La formule de Bayes est : $P(A|B) = \frac{P(B|A)P(A)}{P(B)}$
• $P(A|B)$ est la probabilité conditionnelle que A se produise, étant donné que B est vrai.
• $P(B|A)$ est la probabilité conditionnelle que B se produise, étant donné que A est vrai.
• $P(A)$ et $P(B)$ sont les probabilités de A et B se produisent indépendamment (probabilités marginales).

Déduction

• Le théorème de Bayes peut être déduit des définitions de base de la probabilité conditionnelle :
• $P(A|B) = \frac{P(A \cap B)}{P(B)}$
• $P(A|B) = \frac{P(A \cap B)}{P(A)}$
• En résolvant $P(A \cap B)$ dans les deux équations et en les mettant à égalité, on obtient : $P(A|B)P(B) = P(B|A)P(A)$
• En divisant les deux membres par $P(B)$, étant donné que $P(B) \neq 0$, on aboutit au théorème de Bayes : $P(A|B) = \frac{P(B|A)P(A)}{P(B)}$

Exemple

• Supposons qu'un test de dépistage d'une maladie ait une précision de 99%. Si une personne est testée positive, quelle est la probabilité réelle qu'elle ait la maladie ?
• Définissons les variables :
• $A$ = a la maladie
• $B$ = test positif
• Nous avons:
• $P(A)$ = 0,001 (la prévalence de la maladie dans la population est de 0,1 %)
• $P(B|A)$ = 0,99 (vrai positif)
• $P(B|\neg A)$ = 0,01 (faux positif)
• Nous voulons trouver $P(A|B)$ : $P(B) = P(B|A)P(A) + P(B|\neg A)P(\neg A) = 0,99 \times 0,001 + 0,01 \times 0,999 = 0,01098$
• $P(A|B) = \frac{0. 99 \times 0,001}{0.01098} \approx 0,08998$
• => Même avec un test dont la précision est de 99 %, la probabilité qu'une personne ait réellement la maladie après un test positif n'est que d'environ 9 %.

U1: Structure Atomique

Théorie Atomique de Dalton

• La matière est composée d’atomes indivisibles et destructibles.
• Les atomes du même élément sont identiques en masse et en propriétés.
• Les atomes d’éléments différents ont des masses et des propriétés différentes.
• Les composés sont formés par la combinaison de deux ou plusieurs atomes différents.
• Dans une réaction chimique, les atomes sont réorganisés, mais ne sont ni créés ni détruits.

L'atome

• Particules subatomiques
  • Électrons (e-) : Charge négative, masse ≈ 0.
  • Protons (p+) : Charge positive, masse ≈ 1 amu.
  • Neutrons (n0) : Pas de charge, masse ≈ 1 amu.
• Numéro atomique (Z) : Nombre de protons dans le noyau.
• Nombre massique (A) : Nombre de protons + nombre de neutrons dans le noyau.
  • A = Z + N
• Isotopes : Atomes du même élément avec un nombre différent de neutrons.

Modèles Atomiques

• Modèle de Thomson : « Pudding aux raisins », électrons intégrés dans une sphère de charge positive.
• Modèle Rutherford : Noyau petit et dense avec une charge positive, et des électrons orbitant autour.
• Modèle Bohr : Électrons dans des orbites circulaires avec des niveaux d’énergie quantifiés.
  • En = -RH/n2
  • RH est la constante de Rydberg (constante physique reliant le spectre électromagnétique d’un atome aux niveaux d’énergie).
• Modèle de Schrödinger (Mécanique Quantique)
  • Décrit la probabilité de trouver un électron dans une région de l’espace (orbitale).
  • Introduit les nombres quantiques.
    • Principal (n) : Niveau d’énergie (n = 1, 2, 3,...).
    • Azimutal ou angulaire (l) : Forme de l’orbitale (l = 0, 1, 2,..., n-1).
      • l = 0 : Orbitale s (sphérique)
      • l = 1 : Orbitale p (forme en haltère)
      • l = 2 : Orbitale d (formes plus complexes)
      • l = 3 : Orbitale f (formes très complexes)
  • Magnétique (ml) : Orientation de l’orbitale dans l’espace (ml = -l, -l+1,..., 0,..., l-1, l).
  • Spin (ms) : Rotation de l’électron (+1/2 ou -1/2).

Configuration Electronique

• Distribution des électrons dans les différentes orbitales d’un atome.
• Principe d’Aufbau : Les électrons remplissent les orbitales dans un ordre croissant d’énergie.
• Règle de Hund : Les électrons sont distribués individuellement dans chaque orbitale d’un sous-niveau avant d’être appariés.
• Principe d’exclusion de Pauli : Deux électrons dans un même atome ne peuvent pas avoir les mêmes quatre nombres quantiques.

Tableau Périodique

• Organisation des éléments en fonction de leur numéro atomique et de leurs propriétés chimiques.
• Groupes (colonnes) : Éléments ayant des propriétés chimiques similaires du fait de la même configuration électronique dans la couche de valence.
• Périodes (lignes) : Éléments ayant le même nombre de couches électroniques.
• Blocs : s, p, d, f (selon l’orbitale qui est remplie).
• Métaux, non-métaux et métalloïdes : Classification des éléments selon leurs propriétés physiques et chimiques.

Propriétés Périodiques

• Rayon atomique : Distance moyenne entre le noyau et les électrons les plus externes.
  • Diminue à mesure qu’on avance dans une période (charge nucléaire effective plus élevée).
  • Augmente à mesure que l’on descend dans un groupe (nombre de couches plus élevé).
• Énergie d’ionisation : Énergie nécessaire pour enlever un électron d’un atome en phase gazeuse.
  • Augmente à mesure qu’on avance dans une période (charge nucléaire effective plus élevée).
  • Diminue à mesure que l’on descend dans un groupe (distance plus élevée de l’électron au noyau).
• Affinité électronique : Variation d’énergie lorsqu’un atome en phase gazeuse accepte un électron.
  • Augmente généralement à mesure qu’on avance dans une période (attraction plus élevée pour les électrons).
  • Diminue généralement à mesure que l’on descend dans un groupe (attraction plus faible pour les électrons).
• Électronégativité : Mesure de la capacité d’un atome à attirer les électrons dans une liaison chimique.
  • Augmente à mesure qu’on avance dans une période.
  • Diminue à mesure que l’on descend dans un groupe.

Toutes ces propriétés périodiques influencent le comportement chimique des éléments et la formation des liaisons chimiques.

U4 : Vecteurs dans l’Espace

Vecteurs dans l’espace à trois dimensions

• Coordonnées dans l’espace à trois dimensions

  • Pour représenter des points dans l’espace à trois dimensions, on choisit un point fixe O (origine) et trois lignes de coordonnées qui sont perpendiculaires entre elles, appelées axe des x, axe des y et axe des z.
  • Tout point P dans l’espace peut être représenté par un triple ordonné de nombres réels (a, b, c), où a est la coordonnée x, b est la coordonnée y et c est la coordonnée z.
  • Le triple (a, b, c) est appelé coordonnées de P.

Exemple

• Graphique des points (3, 2, 5), (-2, 3, 1), (-1, 2, -4), (2, -3, 3).

Distance entre deux points dans l’espace

La distance |P1 P2| entre les points $P1(x_1, y_1, z_1)$ et $P2(x_2, y_2, z_2)$ est : $|P_1 P_2| = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2 + (z_2 - z_1)^2}$

Exemple

La distance entre les points (3, -2, 3) et (-1, 4, 0) est : $d = \sqrt{(-1 - 3)^2 + (4 + 2)^2 + (0 - 3)^2} = \sqrt{16 + 36 + 9} = \sqrt{61}$

L’équation d’une sphère

• Une sphère avec son centre $C(x_0, y_0, z_0)$ et son rayon r est l’ensemble de tous les points P(x, y, z) dans l’espace dont la distance à C est r.
• L’équation est : $(x - x_0)^2 + (y - y_0)^2 + (z - z_0)^2 = r^2$

Exemple

L’équation d’une sphère avec un centre en (4, -3, 1) et rayon 5 est : $(x - 4)^2 + (y + 3)^2 + (z - 1)^2 = 25$

4.2 Vecteurs

• Étant donné deux points A et B dans l’espace, le vecteur $\overrightarrow{AB}$ est le vecteur qui va de A à B.
• Si $A(x_1, y_1, z_1)$ et $B(x_2, y_2, z_2)$ , alors $\overrightarrow{AB} = \langle x_2 - x_1, y_2 - y_1, z_2 - z_1 \rangle$

Exemple

• Le vecteur représenté par le segment de droite allant du point A(2, -3, 4) au point B(-2, 1, 1) est : $\overrightarrow{AB} = \langle -2 - 2, 1 - (-3), 1 - 4 \rangle = \langle -4, 4, -3 \rangle$

La Longueur d’un Vecteur

• La longueur ou la magnitude d’un vecteur $\overrightarrow{a} = \langle a_1, a_2, a_3 \rangle$ est donnée par : $||\overrightarrow{a}|| = \sqrt{a_1^2 + a_2^2 + a_3^2}$

Exemple

La longueur du vecteur $\overrightarrow{a} = \langle -4, 4, -3 \rangle$est : $||\overrightarrow{a}|| = \sqrt{(-4)^2 + (4)^2 + (-3)^2} = \sqrt{16 + 16 + 9} = \sqrt{41}$

Somme de Vecteurs

• Si $\overrightarrow{a} = \langle a_1, a_2, a_3 \rangle$ et $\overrightarrow{b} = \langle b_1, b_2, b_3 \rangle$, alors la somme vectorielle $\overrightarrow{a} + \overrightarrow{b}$ est le vecteur $\overrightarrow{a} + \overrightarrow{b} = \langle a_1 + b_1, a_2 + b_2, a_3 + b_3 \rangle$

Exemple

• $\langle 2, 4, 0 \rangle + \langle -1, 3, 2 \rangle = \langle 1, 7, 2 \rangle$

Multiplication scalaire de vecteurs

• Si c est un scalaire et $\overrightarrow{a} = \langle a_1, a_2, a_3 \rangle$, le multiple scalaire $c\overrightarrow{a}$ est le vecteur $c\overrightarrow{a} = \langle ca_1, ca_2, ca_3 \rangle$

Exemple

• Si $\overrightarrow{a} = \langle 4, 0, -2 \rangle$, le vecteur $3\overrightarrow{a}= \langle 12, 0, -6 \rangle$

Propriétés des vecteurs

Si $\overrightarrow{a}$, $\overrightarrow{b}$ et $\overrightarrow{c}$ sont des vecteurs à un espace $V_3$ et c et d sont des scalaires, alors :

1. $\overrightarrow{a} + \overrightarrow{b} = \overrightarrow{b} + \overrightarrow{a}$
2. $\overrightarrow{a} + (\overrightarrow{b} + \overrightarrow{c}) = (\overrightarrow{a} + \overrightarrow{b}) + \overrightarrow{c}$
3. $\overrightarrow{a} + \overrightarrow{0} = \overrightarrow{a}$
4. $\overrightarrow{a} + (-\overrightarrow{a}) = \overrightarrow{0}$
5. $c(\overrightarrow{a} + \overrightarrow{b}) = c\overrightarrow{a} + c\overrightarrow{b}$
6. $(c + d)\overrightarrow{a} = c\overrightarrow{a} + d\overrightarrow{a}$
7. $(cd)\overrightarrow{a} = c(d\overrightarrow{a})$
8. $1\overrightarrow{a} = \overrightarrow{a}$

Vecteurs Unitaires Standard

$\overrightarrow{i} = \langle 1, 0, 0 \rangle$, $\overrightarrow{j} = \langle 0, 1, 0 \rangle$, $\overrightarrow{k} = \langle 0, 0, 1 \rangle$. ont une longueur 1 et pointent dans la direction des axes x, y et z positifs.

Composantes d’un Vecteur

$\overrightarrow{a} = \langle a_1, a_2, a_3 \rangle = a_1\overrightarrow{i} + a_2\overrightarrow{j} + a_3\overrightarrow{k}$

Exemple

$\langle 3, -2, 5 \rangle = 3\overrightarrow{i} - 2\overrightarrow{j} + 5\overrightarrow{k}$

Direction d’un Vecteur

• Un vecteur unitaire $\overrightarrow{u}$ est défini comme un vecteur d’une longueur de 1, $||\overrightarrow{u}|| = 1$

• Étant donné tout vecteur non nul $\overrightarrow{a}$, la direction de $\overrightarrow{a}$ est le vecteur unitaire $\overrightarrow{u}$ ayant la même direction que $\overrightarrow{a}$ : $\overrightarrow{u} = \frac{1}{||\overrightarrow{a}||} \overrightarrow{a}$

Exemple

Le vecteur unitaire dans la direction du vecteur $\overrightarrow{a} = \langle -2, 4, 2 \rangle$ est : $||\overrightarrow{a}|| = \sqrt{(-2)^2 + 4^2 + 2^2} = \sqrt{4 + 16 + 4} = \sqrt{24} = 2\sqrt{6}$, donc $\overrightarrow{u} = \frac{1}{2\sqrt{6}} \langle -2, 4, 2 \rangle = \langle -\frac{1}{\sqrt{6}}, \frac{2}{\sqrt{6}}, \frac{1}{\sqrt{6}} \rangle$

Angles de Direction et Cosinus de Direction

• Les angles $\alpha$, $\beta$ et $\gamma$ que $\overrightarrow{a}$ forme avec les axes de coordonnées positifs sont appelés angles de direction de $\overrightarrow{a}$.

• Les cosinus de ces angles de direction sont appelés cosinus directeurs de $\overrightarrow{a}$. $cos \alpha = \frac{a_1}{||\overrightarrow{a}||}$, $cos \beta = \frac{a_2}{||\overrightarrow{a}||}$, $cos \gamma = \frac{a_3}{||\overrightarrow{a}||}$ $cos^2 \alpha + cos^2 \beta + cos^2 \gamma = 1$

Exemple

Les angles de direction du vecteur $\overrightarrow{a} = \langle 1, 2, 3 \rangle$ sont : $||\overrightarrow{a}|| = \sqrt{1^2 + 2^2 + 3^2} = \sqrt{14}$, $cos \alpha = \frac{1}{\sqrt{14}}$, $cos \beta = \frac{2}{\sqrt{14}}$, $cos \gamma = \frac{3}{\sqrt{14}}$ $\alpha = cos^{-1}(\frac{1}{\sqrt{14}}) \approx 74.5^\circ, \beta = cos^{-1}(\frac{2}{\sqrt{14}}) \approx 57.7^\circ, \gamma = cos^{-1}(\frac{3}{\sqrt{14}}) \approx 36.7^\circ$

Théorie Algorithmique des Jeux - Introduction

• Étude des problèmes de décision multi-agents, où les utilités des agents sont affectées par les actions des autres.
• Initialement en économie, maintenant utilisé en informatique.

Exemples

• Routage de réseau
• Enchères de recherche sponsorisée
• Élections
• Réseaux peer-to-peer
• Réseaux sociaux

Routage égoïste

• Un réseau de n nœuds et m arêtes.
• Chaque arête e a une fonction de coût $\mathcal{l}_e(x)$, où x est la fraction de flux sur e.
• Les fonctions de coût sont non négatives, continues et non décroissantes.
• Un ensemble de k paires source-destination $(s_i, t_i)$, chacune avec un débit (quantité de flux) $r_i$.

Définition :

• Un flux f est une fonction qui attribue un débit de flux non négatif fp à chaque chemin p tel que :
  • Le débit de fluide ne dépasse pas le taux de chemin : $\sum_{p: s_i \rightarrow t_i} f_p = r_i \quad \forall i$
  • Le débit sur chaque arête est la somme des débits sur les chemins contenant cette arête : $f_e = \sum_{p: e \in p} f_p \quad \forall e$

Définition :

• Le coût du chemin p est la somme des latences des arêtes dans p : $l_p(f) = \sum_{e \in p} l_e(f_e)$.
  • Le coût total (ou latence) du flux f est : $C(f) = \sum_{p} f_p \cdot l_p(f) = \sum_{e} f_e \cdot l_e(f_e)$.

Équilibre de Wardrop

• Définition : Un flux f est en équilibre de Wardrop si, pour chaque paire source-destination $(s_i, t_i)$ et chaque paire de chemins $p_1, p_2$ entre $s_i$ et $t_i$ avec $f_{p1} > 0$, il tient que $l_{p1}(f) \le l_{p2}(f)$.

Explication

• Dans un équilibre de Wardrop, tout le flux est acheminé sur des chemins de latence minimale.

Définition

• Un flux f est en équilibre de Nash si aucun agent ne peut dévier unilatéralement et diminuer son coût.

####### Paradoxe de Braess

• Exemple : Un réseau où l’ajout d’une arête augmente le coût pour tous les utilisateurs à l’ équilibre de Wardrop.

####### Illustration

• Réseau initial :
  • Nœud A au nœud B : 1 unité de flux
  • Chemin A -> C -> B : Coût = $x + 1$
  • Chemin A -> D -> B : Coût = $1 + x$
• L'équilibre de Wardrop est atteint lorsque la moitié des utilisateurs empruntent le chemin A->C->B et l'autre moitié le chemin A->D->B ; Les deux chemins ont un coût de 1,5. Le coût total est 1,5.

Réseau augmenté

• Ajouter une arête de latence zéro C -> D. Maintenant, tous les utilisateurs emprunteront le chemin A -> C -> D -> B car il a un coût de x + 0 + x = 2x, soit 0 lorsque x = 0. Mais, à mesure que le flux augmente, ce chemin devient plus coûteux. L’équilibre de Wardrop est atteint lorsque tous les utilisateurs empruntent le chemin A -> C -> D -> B.
• Chemin A -> C -> D -> B : Coût = $1 + 1 = 2$, donc le coût total est $2$.

conclusion

• Ajouter l’arête augmente le coût pour tous les utilisateurs à l’équilibre de Wardrop.

Conférence 14 : le 25 octobre.

• Plans Preuve

Réclamation 1

Si $f: A \rightarrow B$ et $g: B \rightarrow C$ sont injectifs, alors $g \circ f: A \rightarrow C$ est injectif.

Preuve

Soient $f: A \rightarrow B$ et $g: B \rightarrow C$ injectifs.

Soient $a