🕸️

Mathématiques discrètes : graphes et structures

60 cards · 🇫🇷 Français

Graphes, chemins, arbres et les structures discrètes qui sous-tendent l'informatique.

logicdiscrete-mathgraphs

Study all 60 cards for free

Flashcards, quizzes, pixel-art games and a daily review that remembers for you.

Study this deck free

Try the first 10 cards

1 / 10
Question

Mathématiques discrètes

Knew itLearning

Tap the card for the answer · swipe right if you knew it, left if not

Already have an account? Sign in

Cards

  1. 1Mathématiques discrètes
    L'étude des structures mathématiques fondamentalement discrètes (valeurs dénombrables et séparées) plutôt que continues, incluant les entiers, les graphes et les énoncés logiques.
  2. 2En quoi les mathématiques discrètes diffèrent-elles des mathématiques continues ?
    Les mathématiques discrètes traitent d'objets dénombrables et séparés (entiers, graphes) ; les mathématiques continues traitent de phénomènes lisses et connexes (nombres réels, calcul infinitésimal, géométrie).
  3. 3Pourquoi les mathématiques discrètes sont-elles importantes pour l'informatique ?
    Les ordinateurs fonctionnent par étapes discrètes et stockent des bits discrets. Les mathématiques discrètes fournissent les bases des algorithmes, des structures de données, des bases de données, de la cryptographie et de la théorie de la calculabilité.
  4. 4Graphe en mathématiques discrètes
    Une structure constituée de sommets (nœuds) reliés par des arêtes (liens). Utilisé pour modéliser des relations, des réseaux et des connexions.
  5. 5Un graphe orienté vs non orienté
    Non orienté : les arêtes n'ont pas de direction (relation symétrique). Orienté (digraphe) : les arêtes ont une direction indiquée par des flèches (relation asymétrique).
  6. 6Chemin dans un graphe
    Une séquence de sommets où chaque paire adjacente est reliée par une arête. Un chemin simple visite chaque sommet au plus une fois.
  7. 7Cycle dans un graphe
    Un chemin qui commence et se termine au même sommet. Un cycle simple ne répète aucun sommet, à part le premier/dernier.
  8. 8Graphe connexe
    Un graphe où il existe un chemin entre chaque paire de sommets. Aucune composante isolée.
  9. 9Arbre en théorie des graphes
    Un graphe non orienté connexe et acyclique (sans cycle). Un arbre à n sommets possède exactement n-1 arêtes.
  10. 10Arbre couvrant (arbre recouvrant)
    Un sous-graphe qui inclut tous les sommets du graphe original et qui est un arbre (connexe, acyclique). Utilisé dans la conception de réseaux.
  11. 11Énonce le théorème des quatre couleurs.
    Toute carte peut être coloriée avec au plus quatre couleurs de sorte qu'aucune région adjacente n'ait la même couleur. Démontré en 1976 par Appel et Haken à l'aide d'ordinateurs.
  12. 12Coloration de graphe
    Attribuer des couleurs aux sommets de sorte qu'aucun sommet adjacent n'ait la même couleur. Le nombre chromatique est le nombre minimal de couleurs nécessaires.
  13. 13Graphe complet Kₙ
    Un graphe où chaque paire de sommets distincts est reliée par une arête. Kₙ possède n sommets et n(n-1)/2 arêtes.
  14. 14Graphe biparti
    Un graphe dont les sommets peuvent être répartis en deux ensembles disjoints tels que chaque arête relie un sommet d'un ensemble à un sommet de l'autre. Aucune arête à l'intérieur d'un ensemble.
  15. 15Formule d'Euler pour les graphes planaires
    V - E + F = 2, où V = sommets, E = arêtes, F = faces (régions). S'applique aux graphes planaires connexes.
  16. 16Chemin eulérien
    Un chemin qui passe par chaque arête exactement une fois. Il existe si un graphe a exactement 0 ou 2 sommets de degré impair.
  17. 17Chemin hamiltonien
    Un chemin qui passe par chaque sommet exactement une fois. En trouver un est NP-complet (difficile sur le plan calculatoire).
  18. 18Combinatoire
    L'étude du dénombrement, de l'arrangement et de la combinaison d'objets discrets. Inclut les permutations, les combinaisons et les techniques d'énumération.
  19. 19Permutation
    Un arrangement ordonné d'objets. Le nombre de permutations de n objets est n! = n × (n-1) × ... × 2 × 1.
  20. 20Combinaison
    Une sélection d'objets où l'ordre n'a pas d'importance. Le nombre de façons de choisir k objets parmi n est C(n,k) = n!/(k!(n-k)!).
  21. 21Coefficient binomial C(n,k)
    Le nombre de façons de choisir k éléments parmi n éléments sans tenir compte de l'ordre. Aussi noté (n parmi k) ou ₙCₖ.
  22. 22Énonce le principe des tiroirs (principe de Dirichlet).
    Si n objets sont répartis dans m tiroirs avec n > m, alors au moins un tiroir contient plus d'un objet.
  23. 23Principe d'inclusion-exclusion
    Pour dénombrer les éléments d'unions d'ensembles : |A∪B| = |A| + |B| - |A∩B|. Se généralise à plus d'ensembles en alternant additions et soustractions.
  24. 24Fonction génératrice
    Une série entière formelle utilisée pour encoder des suites de nombres (comme des dénombrements combinatoires). Le coefficient de xⁿ donne le n-ième terme.
  25. 25Triangle de Pascal
    Un tableau triangulaire où chaque nombre est la somme des deux nombres au-dessus. La ligne n contient les coefficients binomiaux C(n,k) pour k=0 à n.
  26. 26Relation de récurrence
    Une équation définissant une suite de façon récursive à partir des termes précédents. Exemple : Fibonacci Fₙ = Fₙ₋₁ + Fₙ₋₂.
  27. 27Suite de Fibonacci
    F₀=0, F₁=1, Fₙ = Fₙ₋₁ + Fₙ₋₂. Suite : 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Apparaît partout dans la nature et les mathématiques.
  28. 28Logique mathématique
    L'étude des systèmes formels de raisonnement, incluant la logique propositionnelle, la logique des prédicats et les règles d'inférence.
  29. 29Proposition
    Un énoncé déclaratif qui est soit vrai, soit faux (mais pas les deux). Exemple : « 5 est premier » (vrai), « 2+2=5 » (faux).
  30. 30Connecteurs logiques de base
    ET (∧), OU (∨), NON (¬), IMPLIQUE (→), SI ET SEULEMENT SI (↔). Utilisés pour construire des propositions composées à partir de propositions simples.

And 30 more cards. Study the whole deck free

More Mathematics decks

See all
Study all 60 cards free