Mathématiques discrètes – Open Introduction, 4e édition
(discrete.openmathbooks.org)- La 4e édition de Discrete Mathematics: An Open Introduction, utilisable directement dans un cours universitaire introductif de mathématiques discrètes, est disponible en manuel gratuit en ligne et en PDF
- Cette nouvelle édition renforce une progression qui commence par la logique et les démonstrations, fait pratiquer les preuves via la théorie des graphes, puis enchaîne avec le dénombrement et les suites
- Depuis le printemps 2013, l’ouvrage a été utilisé comme manuel principal ou support complémentaire dans plus de 200 universités à travers le monde, a été recommandé par l’AIM Open Textbook Initiative et a reçu une critique dans l’Open Textbook Library
- Ebook en ligne, PDF, version imprimée, sources GitHub, et même ensembles de devoirs pour Runestone Academy, Edfinity et WeBWorK sont fournis, ce qui réduit la barrière à l’adoption en cours
- La version en ligne restera gratuite, et la 4e édition est publiée sous licence CC BY-NC-SA 4.0, autorisant l’usage, l’impression et la modification à des fins non commerciales
Publication de la 4e édition et nature du manuel
- La 4e édition de Discrete Mathematics: An Open Introduction est disponible en ligne et sur Runestone Academy
- La 3e édition reste également disponible
- Il s’agit d’un manuel open source gratuit conçu pour les cours de mathématiques discrètes de 1re et 2e année en mathématiques et informatique
- Il convient particulièrement bien aux cours intégrant l’apprentissage par exploration
- Depuis le printemps 2013, il est utilisé comme manuel principal ou ressource complémentaire dans plus de 200 universités dans le monde
- Il a été recommandé par l’Open Textbook Initiative de l’American Institute of Mathematics, et fait aussi l’objet d’une critique dans l’Open Textbook Library
Ce qui change dans la 4e édition
- La nouvelle édition réorganise en profondeur l’ordre des contenus
- Elle commence par la logique et les démonstrations
- Elle poursuit avec la théorie des graphes pour s’exercer aux preuves
- Elle place le dénombrement et les suites dans la seconde partie
- Le chapitre sur le dénombrement inclut une nouvelle section d’applications en probabilités
- Ce choix reflète l’expérience récente selon laquelle les étudiants ont obtenu de meilleurs résultats avec cette organisation
- L’accent est aussi renforcé sur les structures discrètes
- ensembles, fonctions et relations sont couverts
- avec une approche plus utile aux étudiants en informatique, tout en conservant la compréhension des concepts mathématiques nécessaire aux étudiants en mathématiques et aux futurs enseignants
Interactivité et support pour les devoirs
- La 4e édition ajoute davantage d’éléments interactifs
- en créant un cours basé sur le manuel dans Runestone Academy, il est possible d’utiliser des exercices interactifs notés pour les étudiants
- du code interactif Sage et Python est inclus pour explorer certains sujets
- Des ensembles de devoirs en ligne sont proposés par plusieurs voies
- Runestone Academy est gratuit
- Edfinity est une option peu coûteuse
- les ensembles WeBWorK peuvent être demandés à l’auteur et sont aussi inclus dans le dossier Contrib de l’OPL
- Les erreurs et coquilles peuvent être signalées via une issue GitHub
Formats disponibles et accessibilité
- L’ensemble du manuel est proposé comme ebook interactif en ligne gratuit
- conçu pour bien fonctionner sur toutes les tailles d’écran, y compris les smartphones
- avec prise en compte de l’usage des lecteurs d’écran pour les étudiants malvoyants
- les indices et corrigés des exemples et exercices sont masqués et accessibles en cliquant sur des liens
- certains exercices permettent de saisir une réponse et de la vérifier, afin de faire plusieurs tentatives sans voir immédiatement la solution
- Un PDF gratuit est également proposé pour un usage hors ligne
- adapté à la lecture sur tablette ou ordinateur
- avec recherche et navigation via liens intégrés
- les indices et corrigés sont accessibles en cliquant sur le numéro de l’exercice, et un clic sur le numéro de l’indice ou du corrigé permet de revenir à l’exercice correspondant
- La version imprimée est publiée chez CRC Press
- La version en ligne continuera d’être disponible gratuitement
Sources, ressources pédagogiques et communauté
- Les fichiers sources PreTeXt et LaTeX du manuel sont disponibles sur GitHub
- Des ressources vidéo basées sur le manuel sont également proposées
- Mathematical Visual Proofs : vidéos montrant les idées du manuel sous forme d’animations
- Dr. Trevor Bazett's Course : cours complet fondé sur ce manuel
- Les enseignants qui utilisent le manuel en cours peuvent demander des ressources pédagogiques
- Si vous avez accès à un serveur WeBWorK, vous pouvez aussi demander les ensembles de devoirs WeBWorK
- Un Google Group existe pour les enseignants de mathématiques discrètes
Contenu du manuel et usage en cours
- Le manuel est né des notes de cours d’un enseignement de mathématiques discrètes à l’University of Northern Colorado
- Ce cours sert à la fois d’introduction aux thèmes des mathématiques discrètes et d’initiation à la démonstration pour les étudiants en mathématiques
- Le cours inclut une forte dimension d’exploration par les étudiants, et le manuel a été rédigé pour la soutenir
- Il a été conçu à l’origine pour accompagner de futurs enseignants de mathématiques, avec un ton accessible et informel
- Il met l’accent sur la compréhension des concepts plutôt que sur la mémorisation de procédures
- Il a aussi été utilisé dans des cours destinés aux étudiants en informatique, en mettant l’accent sur une compréhension plus approfondie
- Les quatre grands thèmes sont la logique, la théorie des graphes, le dénombrement et les suites
- Parmi les méthodes de preuve couvertes figurent la preuve par contradiction, la preuve par récurrence et les preuves combinatoires
- Des sujets supplémentaires comme les fonctions génératrices et la théorie des nombres sont également inclus
- Le manuel comporte aussi des fonctions utiles pour un usage comme support principal de cours
- plus de 750 exercices
- de nombreux problèmes avec corrigés et indices
- des exercices allant de très simples à très complexes
- de nombreux problèmes adaptés aux devoirs
- des activités Investigate! et des activités d’introduction soutenant un apprentissage actif et fondé sur l’exploration
- un index complet et une liste des symboles
- une mise en page et un formatage cohérents, avec repérage des exemples, encadrés de définitions et de théorèmes, etc.
Licence
- Discrete Mathematics: an Open Introduction, 4th edition est diffusé sous licence CC BY-NC-SA 4.0
- Le téléchargement, l’utilisation et l’impression sont autorisés à des fins non commerciales
- La modification du texte est également autorisée
- vous pouvez créer une version personnalisée pour vos étudiants
- vous devez attribuer les auteurs des parties utilisées
- la version modifiée doit être diffusée sous une licence compatible
- Pour combiner ce texte avec d’autres sous une licence similaire mais différente, comme la GFDL, il est possible de demander une autorisation de modification de licence
1 commentaires
Avis sur Hacker News
En autodidacte sans diplôme « officiel » en informatique, les mathématiques discrètes m’ont semblé être la clé pour aborder des sujets plus avancés et résoudre des problèmes pratiques de programmation, et elles m’ont effectivement aidé à plusieurs reprises
J’aime aussi “A Primer of Discrete Mathematics” de Finkbeiner II et Lindstrom, paru en 1987 : https://archive.org/details/isbn_0716718154. C’est un peu ancien et ce n’est pas gratuit, mais cela reste bon, avec de bons exercices et quelques solutions
Je compte aussi jeter un œil à ce livre ; son approche plus moderne, avec des exercices interactifs, et le fait qu’il soit entièrement gratuit, le rendent prometteur
Le livre est assez épais, mais le contenu reste plutôt accessible. Je viens moi aussi de l’autoformation, et maintenant que j’ai la trentaine, je suis des cours formels de maths/physique pour combler mes lacunes
Les California Community Colleges ont aussi été une excellente ressource. Tous les professeurs de maths que j’ai rencontrés jusqu’ici étaient étonnamment passionnés, et comme la plupart des cours de maths proposent des sections asynchrones/en ligne, il est courant que des adultes les suivent pour le plaisir ou le développement personnel
La section « logique » m’a attiré, et elle n’a pas déçu. On peut le télécharger gratuitement sur le site
Vous disiez « un peu ancien et malheureusement pas gratuit » ; si quelqu’un le cherche, il se trouve aussi sur Anna’s Archive
J’aimerais que davantage de manuels, surtout les gratuits comme celui en lien, proposent plus de solutions. Les livres qui en manquent me créent un problème circulaire
Pour savoir si ma solution est correcte, il faut que je comprenne vraiment le concept. Mais si je comprenais vraiment le concept, je n’aurais pas eu besoin de résoudre le problème au départ. Je ne vois pas comment on est censé apprendre sans retour
Grâce à PreTeXt, j’ai beaucoup utilisé des exercices interactifs faciles à intégrer au texte, afin que l’étudiant puisse saisir une réponse et recevoir un retour indiquant si elle est correcte. Cela fonctionne bien pour les exercices de calcul
Pour les problèmes fondés sur des démonstrations ou plus théoriques, j’ai essayé de fournir suffisamment d’exemples entièrement corrigés, ainsi que quelques exercices avec solution. En même temps, je voulais laisser de la place à ceux qui souhaitent des problèmes plus ouverts sans solution
Pour que d’autres enseignants puissent utiliser ce livre utilement en cours, il est aussi important d’avoir des problèmes sans solution pouvant être notés dans le cadre de l’évaluation. Quoi qu’il en soit, j’espère que cette ressource sera utile
Pour apprendre avec un manuel hors d’une salle de classe, sans retour extérieur, il faut lire la ressource de manière beaucoup plus active
On peut considérer chaque énoncé du texte comme un exercice informel. Dès qu’une proposition apparaît, qu’il s’agisse d’un théorème ou d’une affirmation dans une explication, il faut essayer de la démontrer ou de la justifier soi-même avant de continuer
Par exemple, les théorèmes 2.3.1 et 2.3.2 sont très similaires. Si vous avez compris la démonstration de 2.3.1, vous pouvez essayer 2.3.2 par vous-même. Si vous bloquez, lisez quelques phrases de la démonstration incluse comme indices, puis, une fois votre démonstration terminée, comparez-la à celle du texte
En lisant de façon suffisamment active, on peut apprendre assez bien le contenu sans résoudre de problèmes. On dit souvent qu’apprendre les maths nécessite de faire des exercices formels, mais ce n’est pas vrai. Parmi les manuels de mathématiques de niveau plus avancé, beaucoup n’ont aucun exercice ou problème formel, et les gens apprennent quand même très bien
Bien sûr, lire des mathématiques est une compétence à part entière, donc il ne faut pas s’attendre à ce que ce soit facile dès le début. L’idéal est d’avoir un enseignant en tête-à-tête, mais peu de gens ont cette chance
Commencez par le faire à la main, puis modélisez-le avec un outil comme Mathematica ou OR-Tools pour vérifier que vous obtenez la même solution
Cela marche encore mieux pour des mathématiques de niveau plus élémentaire comme l’algèbre ou l’analyse. Pour beaucoup de problèmes, utiliser la fonction
Solve[]de Mathematica permet de savoir si l’on a juste ou fauxOn peut adopter la même approche dans un cours d’algorithmique. Écrivez vous-même un programme naïf qui résout les cas de test de manière simple mais sûre, puis comparez ses résultats à ceux d’un algorithme plus sophistiqué. Ou bien utilisez l’implémentation de référence d’une autre bibliothèque. Par exemple, vous pouvez comparer la solution de votre propre algorithme de graphe avec les résultats renvoyés par Neo4j
En dessous de cela, cela ne sert guère que de référence pour l’enseignant. Car l’enseignant doit vérifier que les solutions sont vraiment complètes et correctes
Il y a des décennies, quand j’étudiais l’ingénierie et l’économie, sans corrigés, mes solutions auraient souvent été incomplètes et auraient omis des détails ou certains cas particuliers
La technologie basée sur XML utilisée pour produire ce livre, PreTeXt, pourrait aussi vous intéresser : https://pretextbook.org/
Cela fait plaisir de voir une ressource d’une telle qualité. Je suis particulièrement reconnaissant à tous les auteurs qui, y compris ceux de ce manuel, mettent leur travail gratuitement en ligne
Leur engagement est évident. Grâce à ce type de ressources gratuites, ou presque, beaucoup de personnes peuvent poursuivre leur formation, y compris les autodidactes et celles qui disposent de moyens limités
J’espère que les auteurs savent à quel point leurs efforts sont appréciés
Avec un peu de retard, je recommande vivement Discrete mathematics with applications de Susanna Epp
Il existe quelques livres au titre similaire, mais celui d’Epp est remarquablement bien écrit. C’est un manuel dans lequel on sent un énorme soin et une grande attention aux détails. Il est aussi excellent pour l’auto-apprentissage
The Math Sorcerer a aussi une vidéo sur une ancienne édition, qui ressemble presque à une charmante ode au livre. Il semble vraiment conquis : https://www.youtube.com/watch?v=FPr5-X9nZc4
Comme beaucoup de manuels de mathématiques discrètes, la section sur la méthode des racines caractéristiques pour les racines multiples ne donne pas de démonstration de la formule
r, on développex^2 - 2r + r^2et, en identifiant les termes, on obtienta = 2r,b = -r^2. La récurrence devient donca(n) = 2r a(n-1) - r^2 a(n-2)En divisant par
r^n, on obtient de façon équivalentec(n) = 2c(n-1) - c(n-2), oùc(n) = a(n)/r^nC’est une récurrence à différences constantes :
c(n) - c(n-1) = c(n-1) - c(n-2)Donc
c(n)est une suite arithmétiquec(n) = x*n + ypour certainsxetydéterminés par les conditions initiales. La suite d’origine esta(n) = c(n) r^n = (x*n + y) r^nPar exemple, avec de l’algèbre linéaire, on obtient une démonstration assez concise ; en voici une partie. Je l’aime bien parce qu’elle ne part pas de la forme supposée, mais dérive la formule à partir des premiers principes
Supposons qu’on ait une suite
x_ndéfinie par la récurrencex_{n+1} = a * x_{n-1} + b * x_nSi l’on définit la suite de vecteurs formés de deux éléments consécutifs
[x_0; x_1],[x_1; x_2],[x_2; x_3], ..., on peut exprimer la relation par un produit matrice/vecteur[x_1; x_2] = [[0 1], [a b]] [x_0; x_1]Si l’on appelle la suite de vecteurs
y_net la matriceM, alorsy_1 = M * y_0Le terme suivant s’obtient par
y_2 = M * y_1 = M * (M * y_0) = M^2 * y_0, et par récurrence on ay_n = M^n * y_0Le polynôme caractéristique de
Mestr^2 - br - a = 0, et ses racines sontr_1 = (b - c)/2,r_2 = (b + c)/2, avecc = √(b^2 + 4a)Par diagonalisation, on obtient donc
y_n = S * [[r_1^n 0], [0 r_2^n]] * S^(-1) * y_0. Ici,Sest la matrice des vecteurs propresÀ partir de là, on peut conclure la démonstration de l’existence et de l’unicité grâce à l’existence et l’unicité des valeurs propres de
MKnuth trouvait les formes fermées des suites récursives avec des fonctions génératrices et, si ma mémoire est bonne, il ne traitait presque pas d’autres méthodes. Le cours que j’avais suivi n’abordait pas les fonctions génératrices, et la plupart des autres manuels que j’avais lus non plus
C’est intéressant que ce livre traite ce sujet. Les « mathématiques discrètes » peuvent vraiment recouvrir beaucoup de choses différentes
J’aimerais aimer mon domaine autant que les personnes qui écrivent ces manuels gratuits semblent aimer le leur
C’était mon cours préféré à l’université. J’ai tellement aimé les mathématiques discrètes en première année que j’ai fini par faire une double spécialisation en maths et en IA, et j’ai choisi les maths à cause de la vérification formelle
Il est indiqué que « le PDF sera disponible jusqu’au 15 août », mais dans la barre latérale il est seulement écrit « PDF coming soon » :(
Si l’on s’intéresse à la cryptographie, les mathématiques discrètes sont-elles un bon point de départ ? C’est sûrement mieux que l’analyse, non ?