Théorème fondamental du calcul

Le théorème fondamental du calcul

Partie 1

• Si $g(x) = \int_{a}^{x} f(t) dt$, alors $g'(x) = f(x)$.
• La dérivée d'une fonction d'aire est la fonction originale.

Partie 2

• $\int_{a}^{b} F'(x) dx = F(b) - F(a)$
• L'intégrale d'un taux de variation est la variation nette.

Exemple 1

• Trouver $\frac{d}{dx} \int_{0}^{x} \sqrt{1 + t^2} dt$
• Solution: $\frac{d}{dx} \int_{0}^{x} \sqrt{1 + t^2} dt = \sqrt{1 + x^2}$

Exemple 2

• Trouver $\frac{d}{dx} \int_{2}^{x^4} \sqrt{1 + t^2} dt$
• Solution: $\frac{d}{dx} \int_{2}^{x^4} \sqrt{1 + t^2} dt = \sqrt{1 + (x^4)^2} \cdot 4x^3 = 4x^3 \sqrt{1 + x^8}$

Exemple 3

• Trouver $\frac{d}{dx} \int_{x}^{3} \cos(t^2) dt$
• Solution: $\frac{d}{dx} \int_{x}^{3} \cos(t^2) dt = \frac{d}{dx} [-\int_{3}^{x} \cos(t^2) dt] = -\cos(x^2)$

Exemple 4

• Evaluer $\int_{1}^{3} (x^2 + 4x - 3) dx$
• Solution: $\int_{1}^{3} (x^2 + 4x - 3) dx = [\frac{1}{3}x^3 + 2x^2 - 3x]_{1}^{3} = (\frac{1}{3}(3)^3 + 2(3)^2 - 3(3)) - (\frac{1}{3}(1)^3 + 2(1)^2 - 3(1)) = (9 + 18 - 9) - (\frac{1}{3} + 2 - 3) = 18 - (-\frac{2}{3}) = 18 + \frac{2}{3} = \frac{56}{3}$

Algorithme du plus court chemin de Dijkstra

Graphes pondérés

• Un graphe pondéré est un graphe où chaque arête a un poids ou un coût associé.
• Le coût d'un chemin dans un graphe pondéré est la somme des poids des arêtes dans le chemin.

Problème du plus court chemin

• Étant donné un graphe pondéré $G = (V, E)$ et deux sommets $s$ et $t$, il faut trouver le chemin de $s$ à $t$ avec le coût minimum.

Algorithme de Dijkstra

• L'algorithme de Dijkstra est un algorithme glouton qui résout le problème du plus court chemin à source unique pour un graphe pondéré avec des poids d'arête non négatifs.

Hypothèses:

• Le graphe est pondéré.
• Tous les poids d'arête sont non négatifs.
• Le graphe est dirigé.

Algorithme :

• Initialiser la distance au sommet source à 0 et la distance à tous les autres sommets à l'infini.
• Maintenir un ensemble de sommets visités et une file d'attente prioritaire des sommets non visités, classés par ordre de distance de la source.
• Tant que la file d'attente prioritaire n'est pas vide :
  • Extraire le sommet avec la distance minimale de la file d'attente prioritaire.
  • Marquer le sommet comme visité.
  • Pour chaque voisin du sommet :
    • Calculer la distance au voisin à travers le sommet actuel.
    • Si cette distance est inférieure à la distance actuelle au voisin, mettre à jour la distance au voisin et l'ajouter à la file d'attente prioritaire.

Exemple :

• Le document montre un graphe pondéré dirigé avec 6 sommets (A, B, C, D, E, F) et leurs arêtes et poids correspondants.
• Le but est de trouver le plus court chemin du sommet A au sommet F.
• L'algorithme est appliqué étape par étape, en mettant à jour les distances de chaque sommet à partir du sommet source A.
• Un tableau est utilisé pour suivre les distances de A à chaque autre sommet.

• Répétition 1: L'algorithme commence au sommet A. Les distances aux voisins B et C sont mises à jour respectivement à 2 et 4.
• Répétition 2: Le sommet B est visité (car il a la distance minimale de 2). La distance au voisin D est mise à jour à 7 (2 + 5).
• Répétition 3: Le sommet C est visité (car il a la distance minimale de 4). La distance au voisin D est mise à jour à 6 (4 + 2).
• Répétition 4: Le sommet D est visité (car il a la distance minimale de 6). Les distances aux voisins E et F sont mises à jour respectivement à 11 (6 + 5) et 13 (6 + 7).
• Répétition 5: Le sommet E est visité (car il a la distance minimale de 11). Il n'y a pas de voisins non-visités.
• Répétition 6: Le sommet F est visité (car il a la distance minimale de 13). L'algorithme se termine.
• Par conséquent, le plus court chemin de A à F est 13.

Exactitude

• L'algorithme de Dijkstra fonctionne en maintenant un ensemble de sommets dont les poids finaux du plus court chemin à partir de s ont déjà été déterminés.
• L'algorithme sélectionne de manière répétée le sommet $u \in (V - S)$ avec l'estimation minimale du plus court chemin, ajoute u à S et met à jour les estimations du plus court chemin de tous les voisins v de u qui sont toujours dans $V - S$.

Complexité temporelle

• La complexité temporelle de l'algorithme de Dijkstra dépend de l'implémentation de la file d'attente prioritaire.
  • Avec un tas binaire, la complexité temporelle est $O((|V| + |E|) \log |V|)$.
  • Avec un tas de Fibonacci, la complexité temporelle est $O(|E| + |V| \log |V|)$.
• L'algorithme de Dijkstra ne fonctionne pas pour les graphes avec des poids d'arêtes négatives.
• Pour les graphes avec des poids d'arêtes négatives, l'algorithme de Bellman-Ford peut être utilisé.

Physique

Vecteurs

Qu'est-ce qu'un vecteur?

• Un vecteur est un outil mathématique qui représente une grandeur physique qui a à la fois une magnitude et une direction.

Représentation graphique d'un vecteur

• Un vecteur est représenté graphiquement comme une flèche.
  • La longueur de la flèche représente la magnitude du vecteur.
  • La direction de la flèche représente la direction du vecteur.
  • Le point où commence la flèche s'appelle le point d'application du vecteur.

Composantes d'un vecteur

• Un vecteur dans le plan peut être décomposé en deux composantes:
  • La composante x, qui est la projection du vecteur sur l'axe x.
  • La composante y, qui est la projection du vecteur sur l'axe y.
• Les composantes d'un vecteur peuvent être calculées en utilisant les formules suivantes: $V_x = V \cos \theta$ $V_y = V \sin \theta$

Où :

• $V$ est la magnitude du vecteur
• $\theta$ est l'angle que forme le vecteur avec l'axe x.

Somme de vecteurs

• Il existe différentes méthodes pour additionner des vecteurs :
  • Méthode graphique: Les vecteurs sont placés l'un après l'autre, en conservant leur magnitude et leur direction. Le vecteur résultant est la flèche qui relie le point d'application du premier vecteur à l'extrémité du dernier vecteur.
  • Méthode analytique: Les composantes des vecteurs sont additionnées. La composante x du vecteur résultant est la somme des composantes x des vecteurs d'origine, et la composante y du vecteur résultant est la somme des composantes y des vecteurs d'origine.

Produit d'un vecteur par un scalaire

• Le produit d'un vecteur par un scalaire est un nouveau vecteur qui a la même direction que le vecteur d'origine, mais sa magnitude est multipliée par le scalaire.

Produit scalaire de deux vecteurs

• Le produit scalaire de deux vecteurs est un nombre qui est obtenu en multipliant les magnitudes des deux vecteurs par le cosinus de l'angle qu'ils forment. $\vec{V} \cdot \vec{W} = |\vec{V}| |\vec{W}| \cos \theta$

Produit vectoriel de deux vecteurs

• Le produit vectoriel de deux vecteurs est un nouveau vecteur qui est perpendiculaire aux deux vecteurs d'origine. Sa magnitude est égale au produit des magnitudes des deux vecteurs par le sinus de l'angle qu'ils forment. $|\vec{V} \times \vec{W}| = |\vec{V}| |\vec{W}| \sin \theta$
• La direction du vecteur résultant peut être déterminée en utilisant la règle de la main droite.

Labo 6 : Algèbre booléenne et cartes de Karnaugh

1. Objectifs

• Acquérir les connaissances de base de l'algèbre booléenne.
• Apprendre à utiliser les cartes de Karnaugh pour minimiser les fonctions booléennes.
• Apprendre à construire des circuits logiques numériques à partir de fonctions booléennes minimisées.

2. Préparation

2.1. Matériels

• Ordinateur personnel ;
• Logiciel Quartus II.

2.2. Contexte

2.2.1. Algèbre booléenne

• L'algèbre booléenne est une branche de l'algèbre qui traite des valeurs booléennes (VRAI et FAUX) et des opérations logiques.
• Les opérations logiques de base sont AND, OR et NOT.
  • AND : l'opération ET (notée par .) renvoie TRUE uniquement si les deux opérandes sont TRUE. Sinon, elle renvoie FALSE.
    • $A \cdot B = VRAI$ uniquement si $A = VRAI$ et $B = VRAI$.
  • OR : l'opération OU (notée par +) renvoie TRUE si l'un des opérandes est TRUE. Elle renvoie FALSE uniquement si les deux opérandes sont FALSE.
    • $A + B = VRAI$ si $A = VRAI$ ou $B = VRAI$.
  • NOT : l'opération NON (notée par ') renvoie l'inverse de l'opérande. Si l'opérande est TRUE, elle renvoie FALSE, et vice versa.
    • $A' = VRAI$ si $A = FAUX$.
• Les lois de DeMorgan sont deux théorèmes importants de l'algèbre booléenne :
  • $(A + B)' = A' \cdot B'$
  • $(A \cdot B)' = A' + B'$

2.2.2. Cartes de Karnaugh

• Une carte de Karnaugh (carte K) est une méthode graphique utilisée pour simplifier les expressions de l'algèbre booléenne.
• Une carte K est un diagramme de type tableau qui représente la table de vérité d'une fonction booléenne.
• La carte K est construite de telle sorte que les cellules adjacentes ne diffèrent que d'une seule variable.
• Par exemple, la carte K suivante représente une fonction booléenne avec trois variables : | | $A'B'$ | $A'B$ | $AB$ | $AB'$ | | :----------------- | :----- | :---- | :--- | :---- | | $C'$ | 0 | 1 | 1 | 0 | | $C$ | 0 | 1 | 1 | 0 |
• Chaque cellule de la carte K représente un terme minimal de la fonction booléenne.
• Un terme minimal est un terme produit qui contient toutes les variables de la fonction, soit sous leur forme vraie, soit sous leur forme complémentée.
• Par exemple, le terme minimal $A'B'C'$ représente la cellule dans le coin supérieur gauche de la carte K.
• Pour simplifier une fonction booléenne à l'aide d'une carte K, nous regroupons les cellules adjacentes qui contiennent des 1.
• Les groupes doivent être rectangulaires ou carrés, et le nombre de cellules dans chaque groupe doit être une puissance de 2 (1, 2, 4, 8, etc.).
• Plus le groupe est grand, plus le terme résultant est simple.
• Pour la carte K ci-dessus, nous pouvons identifier deux groupes de deux 1 :
  • Le premier groupe est constitué des cellules $A'BC'$ et $A'BC$. Ce groupe correspond au terme $A'B$.
  • Le deuxième groupe est constitué des cellules $ABC'$ et $ABC$. Ce groupe correspond au terme $AB$.
• Par conséquent, la fonction booléenne simplifiée est $F = A'B + AB$.

3. Procédure de l'expérience

3.1. Algèbre booléenne

1. Simplifier les fonctions booléennes suivantes à l'aide de l'algèbre booléenne :
   • $F_1 = A'B + AB$
   • $F_2 = (A + B)(A + C)$
   • $F_3 = A'BC + AB'C' + ABC + A'B'C'$
2. Vérifier vos réponses en construisant les circuits dans Quartus II et en les simulant.

3.2. Cartes de Karnaugh

1. Simplifier les fonctions booléennes suivantes à l'aide des cartes de Karnaugh :
   • $F_4(A, B, C) = A'B'C' + A'BC' + AB'C' + ABC'$
   • $F_5(A, B, C) = A'B'C + A'BC + AB'C + ABC$
   • $F_6(A, B, C, D) = A'B'C'D' + A'B'CD' + A'BC'D' + A'BCD' + AB'C'D' + AB'CD' + ABC'D' + ABCD'$
2. Vérifier vos réponses en construisant les circuits dans Quartus II et en les simulant.

3.3. Mise en œuvre de circuits numériques

1. Mettre en œuvre la fonction booléenne suivante à l'aide des portes ET, OU et NON :
   • $F_7(A, B, C) = A'B + AC' + BC$
2. Minimiser la fonction à l'aide d'une carte de Karnaugh.
3. Mettre en œuvre la fonction minimisée à l'aide des portes ET, OU et NON.
4. Comparer les deux circuits en termes de nombre de portes et de délai de propagation.

4. Rapport de l'expérience

Le rapport de l'expérience doit comprendre les éléments suivants :

• Objectifs et préparation (10 %)
• Procédure et résultats (60 %)
  • Enregistrer en détail les étapes et les résultats de vos expériences, y compris les fonctions booléennes simplifiées, les cartes K, les schémas de Quartus II et les résultats de la simulation.
  • Inclure des instantanés des schémas de Quartus II et des résultats de la simulation.
• Conclusions (30 %)
  • Résumer ce que vous avez appris dans ce laboratoire.
  • Discuter des avantages et des inconvénients de l'utilisation de l'algèbre booléenne et des cartes de Karnaugh pour simplifier les fonctions booléennes.
  • Discuter des compromis entre le nombre de portes et le délai de propagation dans la mise en œuvre des circuits numériques.

Chapitre 14 : Graphiques

14.1 Introduction

• Le but central d'un graphique statistique est d'afficher les données de manière précise, claire et efficace.
• Les graphiques peuvent être utilisés pour l'exploration, la présentation ou le stockage des données.

14.2 Les utilisations des graphiques

14.2.1 Pour l'exploration

• Les graphiques permettent de mieux comprendre l'ensemble de données afin de formuler des hypothèses.
• Exemples :
• Les nuages de points peuvent aider à visualiser la relation entre deux variables.
• Les histogrammes peuvent afficher la distribution d'une seule variable.

14.2.2 Pour la présentation

• Les graphiques permettent de communiquer les résultats à un public.
• Exemples :
• Les diagrammes à barres peuvent comparer les moyennes de différents groupes.
• Les graphiques linéaires peuvent montrer les tendances au fil du temps.

14.2.3 Pour le stockage des données

• Les graphiques peuvent être utilisés pour stocker les données dans un format visuel.
• Exemples :
• Les cartes peuvent stocker des données géographiques.
• Les diagrammes de réseau peuvent stocker les relations entre les entités.

14.3 Les éléments d'un graphique

14.3.1 La zone de données

• La zone de données est la zone du graphique où les données sont affichées.
• Elle doit être clairement définie et facile à interpréter.

14.3.2 Les axes

• Les axes sont les lignes horizontales et verticales qui définissent la zone de données.
• Ils doivent être étiquetés clairement et avec précision.

14.3.3 Les échelles

• Les échelles sont les unités de mesure utilisées sur les axes.
• Elles doivent être choisies avec soin pour éviter de fausser les données.

14.3.4 Les étiquettes

• Les étiquettes sont le texte qui identifie les différents éléments du graphique.
• Elles doivent être claires, concises et précises.

14.3.5 La légende

• La légende est une clé qui explique les symboles et les couleurs utilisés dans le graphique.
• Elle doit être placée dans un endroit bien en vu et compréhensible.

14.4 Types courants de graphiques

14.4.1 Nuages de points

• Les nuages de points servent à afficher la relation entre deux variables.
• Chaque point du graphique représente une seule observation.

14.4.2 Graphiques linéaires

• Les graphiques linéaires permettent de montrer les tendances au fil du temps.
• L'axe des x représente le temps et l'axe des y représente la variable d'intérêt.

14.4.3 Diagrammes à barres

• Les diagrammes à barres servent à comparer les moyennes de différents groupes.
• La hauteur de chaque barre représente la moyenne du groupe.

14.4.4 Histogrammes

• Les histogrammes servent à afficher la distribution d'une seule variable.
• L'axe des x représente les valeurs de la variable et l'axe des y représente la fréquence de chaque valeur.

14.4.5 Boîtes à moustaches

• Les boîtes à moustaches servent à comparer les distributions de différents groupes.
• La boîte représente l'intervalle interquartile (IQR) et les moustaches représentent l'intervalle des données.

14.5 Autres types de graphiques

14.5.1 Graphiques à points

• Les graphiques à points sont semblables aux diagrammes à barres, mais ils utilisent des points au lieu de barres.
• Les graphiques à points peuvent être utiles pour comparer les moyennes de différents groupes lorsqu'il y a de nombreux groupes.

14.5.2 Graphiques de tournesols

• Les graphiques de tournesols servent à afficher la relation entre deux variables lorsqu'il y a de nombreux points qui se chevauchent.
• Chaque "pétale" du tournesol représente une seule observation.

14.5.3 Graphiques de variables ajoutées

• Les graphiques de variables ajoutées servent à évaluer la relation entre une variable prédictive et une variable de réponse, après avoir ajusté les effets des autres variables prédictives.

14.5.4 Graphiques Q-Q

• Les graphiques Q-Q servent à comparer la distribution d'un échantillon à une distribution théorique.

14.6 Perception graphique

14.6.1 La perception graphique en tant que science

• La perception graphique est l'étude de la façon dont les gens perçoivent et interprètent les graphiques statistiques.
• C'est un processus complexe qui est influencé par de nombreux facteurs, y compris le type de graphique, les couleurs utilisées et les connaissances antérieures de l'individu.

14.6.2 Tâches de la perception graphique

• Il existe de nombreuses tâches différentes que les gens effectuent lorsqu'ils regardent un graphique statistique.
• Ces tâches comprennent :
• Identifier les variables affichées.
• Interpréter les échelles sur les axes.
• Identifier les tendances dans les données.
• Comparer les valeurs des différentes variables.
• Faire des inférences sur la population sous-jacente.

14.6.3 Expériences relatives à la perception graphique

• De nombreuses expériences ont été menées pour étudier la perception graphique.
• Ces expériences ont montré que certains types de graphiques sont plus faciles à comprendre que d'autres.
• Par exemple, les diagrammes à barres sont généralement plus faciles à comprendre que les diagrammes circulaires.

14.6.4 La façon dont nous jugeons les éléments graphiques élémentaires

• Les jugements sur les éléments graphiques sont plus précis lorsqu'ils sont basés sur la position le long d'une échelle commune.
• Les jugements sur la longueur sont plus précis que les jugements sur la superficie ou le volume.
• Les jugements sur l'angle sont plus précis que les jugements sur la couleur ou l'ombrage.

14.6.5 Conséquences pour les graphiques statistiques

• Les graphiques statistiques doivent être conçus pour permettre aux gens d'effectuer facilement les tâches