- Manuel de mathématiques destiné aux étudiants en informatique proposé par le MIT, couvrant de façon structurée les concepts mathématiques essentiels, de la logique et des preuves jusqu’aux probabilités, aux récurrences et à la théorie des graphes
- Organisé en cinq parties — preuves, structures, dénombrement, probabilités, récurrences —, chacune traitant à la fois des bases théoriques et des applications à l’informatique
- Inclut des sujets indispensables à la programmation et à l’analyse d’algorithmes, comme les formules logiques, l’induction mathématique, les machines à états, les graphes, les variables aléatoires
- Montre l’usage des concepts mathématiques à travers des cas concrets et des problèmes appliqués, comme le chiffrement RSA, le code de Turing ou le problème de Monty Hall
- Rédigé conjointement par des chercheurs du MIT et de Google, l’ouvrage est publié sous licence Creative Commons BY-SA 3.0, ce qui permet l’apprentissage et la réutilisation libres
Présentation du manuel
- Mathematics for Computer Science (MCS) est le manuel du cours de premier cycle en informatique et génie électrique du MIT (6.042), conçu pour développer la pensée logique et la capacité de modélisation mathématique
- Les auteurs sont Eric Lehman (Google Inc.), F. Thomson Leighton (MIT, Akamai Technologies), Albert R. Meyer (MIT)
- Il s’agit de l’édition révisée du 6 juin 2018, distribuée sous licence Creative Commons Attribution-ShareAlike 3.0
I. Proofs (preuves)
- Présente les principes fondamentaux de la preuve mathématique, dont les propositions, prédicats, méthode axiomatique, preuve par contradiction, preuve par cas
- Explique la relation entre le Well Ordering Principle (principe du bon ordre) et l’induction, avec des applications sur des exemples comme la décomposition en facteurs premiers
- Inclut les formules logiques et la logique propositionnelle, le problème SAT, ainsi que les types de données mathématiques (ensembles, fonctions, relations)
II. Structures
- Présente les fondements mathématiques de l’informatique autour de la théorie des nombres, de la théorie des graphes et des structures de réseau
- Applications de théorie des nombres comme les nombres premiers, le plus grand commun diviseur, l’arithmétique modulaire, le chiffrement RSA
- Description de modèles structurels tels que les graphes orientés, ordres partiels, routage réseau, graphes simples, graphes planaires
- Aborde le code de Turing et son lien avec le problème SAT, montrant la connexion entre théorie de la calculabilité et cryptographie
III. Counting (dénombrement et combinatoire)
- Couvre les sommes, produits, notation asymptotique, règles de combinatoire, fonctions génératrices et d’autres techniques de calcul combinatoire
- Inclut des exemples pratiques comme le principe des tiroirs, le principe d’inclusion-exclusion et les mains de poker
- Applique les fonctions génératrices et les méthodes de résolution des récurrences linéaires à l’analyse d’algorithmes et au calcul de suites
IV. Probability (probabilités)
- Couvre l’ensemble de la théorie des probabilités, dont les espaces probabilisés, probabilités conditionnelles, variables aléatoires, variance, estimation par échantillonnage, marches aléatoires
- Comprend des cas mettant à l’épreuve l’intuition, comme le problème de Monty Hall, le paradoxe de Simpson, le problème des anniversaires
- Fournit les bases de l’analyse de données via les inégalités de Markov et de Chebyshev et l’échantillonnage aléatoire
V. Recurrences (récurrences)
- Traite des thèmes clés de l’analyse d’algorithmes comme les tours de Hanoï, le tri par fusion, les récurrences de diviser pour régner
- Explique des structures de calcul efficaces à travers les méthodes de résolution des récurrences linéaires et la pensée récursive
Annexe
- Inclut les références bibliographiques, explications des symboles, index, utiles pour l’apprentissage et la consultation
- Le manuel complet est disponible gratuitement en PDF sur le site web du MIT CSAIL
Aucun commentaire pour le moment.