Mathématiques pour l’informatique (2018) [PDF]

• 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

[GN⁺]

Avis sur Hacker News

• Mentionne que Thomson Leighton est le fondateur d’Akamai, et recommande la série de cours qu’il a animée
  C’était l’un des contenus les plus marquants qu’il ait vus sur Internet

  • Présente aussi comme ressources complémentaires les vidéos de cours les plus récentes du MIT OCW, ainsi qu’un cours de l’Open Learning Library donné par Albert Meyer, l’un des auteurs du manuel
  • Ajoute qu’il aimerait qu’Akamai s’occupe davantage des problèmes liés aux plages IPv4 utilisées par les scanners ou les script kiddies

• La structure de chaque section est assez classique, mais il apprécie que chaque citation comporte des renvois vers toutes les sources
  Il aimerait voir davantage de livres conçus de cette manière

  • Le choix du contenu était au contraire peu standard, ce qui le rendait intéressant, avec l’humour caractéristique du MIT
    Il regrette cependant que la rédaction se soit arrêtée après 2018

• Il adore vraiment ce livre. Le niveau est élevé, mais il arrivait quand même à comprendre 1 à 2 pages par paragraphe
  Il y a trouvé l’intuition que les fonctions sont des listes infinies d’entrées et de sorties, et l’humour dans la notation mathématique l’a aussi marqué
  Il aimerait le comprendre entièrement avant de mourir

  • La formule « comprendre 1 à 2 pages par paragraphe » l’a fait rire en lui rappelant les longues phrases à la Victor Hugo
  • « 1 à 2 pages », plaisante quelqu’un, ce serait plutôt « -1 page »

• Pose la question de savoir s’il est possible de ne retenir que 5 livres indispensables en informatique

  • Répond que c’est impossible avec seulement 5, et partage sa propre liste Top 10
    Elle comprend Brookshear, Forta, Stallings, CLRS, Kurose & Ross, Sipser, Aumasson, Russell & Norvig, entre autres
    Python est en pratique devenu une langue commune, et Python Crash Course 3rd Edition de Matthes est aussi recommandé
  • Recommande TeachYourselfCS.com si l’on n’est pas issu d’un cursus d’informatique
    Le site indique aussi les 2 livres essentiels à lire quand on manque de temps
  • Dit que cela dépend du domaine visé, un peu comme la question « quel langage faut-il apprendre ? »
  • Estime que ce livre met moins l’accent sur les relations que sur les nombres, et recommande aussi d’étudier la type theory ou la category theory
  • Ajoute qu’il n’existe pas de liste qui fasse consensus. L’important est d’explorer par soi-même et de trouver les livres qui conviennent à chacun en algorithmes, automates, langages, systèmes d’exploitation, machine learning, etc.

• Il a particulièrement apprécié la partie sur les probabilités de ce livre
  Le problème de Monty Hall y est expliqué clairement avec une « méthode en 4 étapes », bien plus facile à comprendre que dans le film

  • A découvert que l’édition 2017 est disponible au Royaume-Uni en impression à la demande
    C’est pratique pour étudier certaines parties en version papier

• En voyant la table des matières, il a été surpris que le chapitre 2 porte sur le Well-Ordering Principle
  Contrairement au théorème de Zermelo, cette manière de partir de l’ordre des nombres naturels lui paraissait inhabituelle
  D’ordinaire, il avait appris qu’on définissait l’ordre à partir des axiomes de Peano avant de démontrer ensuite le principe

  • Explique que le Well-Ordering Principle, l’Axiom of Choice et le Zorn’s Lemma sont équivalents
    Il est intéressant de noter qu’il existe aussi un bon ordre sur les réels, même qu’on ne peut pas exprimer concrètement cet ordre
    Cite aussi la plaisanterie : « l’axiome du choix est évidemment vrai, le principe du bon ordre est évidemment faux, et le lemme de Zorn, je ne sais pas »
  • En informatique, on l’aborde surtout comme base de l’induction mathématique, puis il n’est presque plus mentionné dans les cours d’algorithmes

• Réexplique le principe des tiroirs de la section 15.8 en suivant l’approche de Dijkstra
  Si 500 000 habitants de Boston ont entre 1 et 200 000 cheveux, alors comme la moyenne est de 2,5 personnes par valeur possible, on peut prouver qu’au moins 3 personnes ont le même nombre de cheveux
  Il trouve intéressant que cela se résolve à partir du simple fait qu’une moyenne ne peut pas dépasser la valeur maximale

• Dit que c’est la première fois qu’il voit un livre sous forme de cahier d’exercices, et se demande s’il existe des corrigés
  Il a essayé de résoudre quelques problèmes, mais n’a pas pu vérifier ses réponses

  • Le cours de maths discrètes de Math Academy montre la solution après soumission d’une réponse, et propose aussi une fonctionnalité de révision espacée
  • Sans corrigés, il trouve l’auto-apprentissage difficile. Discrete Mathematics With Applications de Susanna Epp est aussi une bonne alternative
  • Quelqu’un dit que ce type de problèmes est facile à résoudre avec un LLM
  • Un autre partage avoir réellement utilisé un LLM pour repérer des erreurs dans des démonstrations. Gemini lui a signalé une preuve incorrecte, ce qui lui a été utile
  • Si les universités ne publient pas leurs recueils de solutions, c’est parce qu’elles réutilisent les exercices d’une année sur l’autre avec un stock limité de problèmes

• Remercie pour cette ressource, qu’il juge très utile

• Se réjouit d’avoir trouvé grâce à Hacker News le PDF qu’il cherchait
  Demande des recommandations de lecteurs d’écran capables de lire des PDF

  • Se demande s’il existe des lecteurs capables de lire des PDF contenant des formules LaTeX
    Il précise qu’il ne sait pas non plus lire la plupart des symboles mathématiques