Spécialisation Introduction aux mathématiques discrètes pour l'informatique

Le comptage est l'une des tâches mathématiques de base que nous rencontrons au quotidien. La principale question qui se pose ici est la suivante : si nous devons compter quelque chose, pouvons-nous faire mieux que de compter tous les objets un par un ? Si nous devons compter quelque chose, pouvons-nous faire mieux que de compter tous les objets un par un ? Devons-nous créer une liste de tous les numéros de téléphone pour nous assurer qu'il y a suffisamment de numéros de téléphone pour tout le monde ? Existe-t-il un moyen de savoir si notre algorithme s'exécutera en un temps raisonnable avant de l'implémenter et de l'exécuter réellement ? Toutes ces questions sont abordées dans un domaine mathématique appelé Combinatoire. Dans ce cours en ligne, nous discutons de la plupart des paramètres combinatoires standard qui peuvent aider à répondre à des questions de ce type. Nous nous concentrerons particulièrement sur le développement de la capacité à distinguer ces paramètres dans la vie réelle et les problèmes algorithmiques. Cela aidera l'apprenant à mettre en œuvre ses nouvelles connaissances. En outre, nous discuterons de la technique récursive pour le comptage qui est importante pour les implémentations algorithmiques. L'un des principaux "consommateurs" de la combinatoire est la théorie des probabilités. Ce domaine est lié à de nombreux aspects de la vie, d'une part en tant que concept important dans la vie quotidienne et d'autre part en tant qu'outil indispensable dans des domaines aussi modernes et importants que les statistiques et l'apprentissage automatique. Dans ce cours, nous nous concentrerons sur l'acquisition d'une connaissance pratique des bases de la probabilité et d'une bonne intuition dans ce domaine. La pratique montre qu'une telle intuition n'est pas facile à développer. A la fin du cours, nous créerons un programme qui jouera avec succès à un jeu de dés délicat et très contre-intuitif. Comme prérequis, nous supposons seulement des mathématiques de base (par exemple, nous nous attendons à ce que vous sachiez ce qu'est un carré ou comment additionner des fractions), une programmation de base en python (fonctions, boucles, récursion), du bon sens et de la curiosité. Notre public cible est constitué de toutes les personnes qui travaillent ou envisagent de travailler dans le domaine des technologies de l'information, à commencer par les lycéens motivés.

Nous vous invitons à un voyage fascinant dans la théorie des graphes - un domaine qui allie l'élégance de la peinture et la rigueur des mathématiques ; il est simple, mais non dépourvu de sophistication. La théorie des graphes nous offre à la fois un moyen facile de représenter picturalement de nombreux résultats mathématiques majeurs et un aperçu des théories profondes qui les sous-tendent.

Dans ce cours en ligne, parmi d'autres applications fascinantes, nous verrons comment les systèmes GPS trouvent les itinéraires les plus courts, comment les ingénieurs conçoivent les circuits intégrés, comment les biologistes assemblent les génomes, pourquoi une carte politique peut toujours être colorée en utilisant quelques couleurs. Nous étudierons la théorie de Ramsey qui prouve que dans un grand système, le désordre complet est impossible ! À la fin du cours, nous mettrons en œuvre un algorithme qui trouve une affectation optimale des élèves aux écoles. Cet algorithme, développé par David Gale et Lloyd S. Shapley, a été reconnu plus tard par l'attribution du prix Nobel d'économie. Comme prérequis, nous supposons seulement des mathématiques de base (par exemple, nous nous attendons à ce que vous sachiez ce qu'est un carré ou comment additionner des fractions), une programmation de base en python (fonctions, boucles, récursion), du bon sens et de la curiosité. Notre public cible est constitué de toutes les personnes qui travaillent ou envisagent de travailler dans le domaine des technologies de l'information, à commencer par les lycéens motivés.

Au début du XXe siècle, Godfrey Hardy, éminent spécialiste de la théorie des nombres, la décrivait comme l'une des branches les plus manifestement inutiles des mathématiques pures. Trente ans seulement après sa mort, un algorithme de cryptage de messages secrets a été mis au point en s'appuyant sur les acquis de la théorie des nombres. Il a été baptisé RSA, du nom de ses auteurs, et sa mise en œuvre est probablement le programme informatique le plus utilisé dans le monde aujourd'hui. Sans lui, personne ne serait en mesure d'effectuer des paiements sécurisés sur l'internet, ni même de se connecter en toute sécurité à son courrier électronique ou à d'autres services personnels. Dans ce cours, nous commencerons par les bases de la théorie des nombres et nous aborderons les protocoles cryptographiques basés sur cette théorie. À la fin du cours, vous serez capable d'appliquer les bases de la théorie des nombres pour crypter et décrypter des messages, et de casser le code si l'on applique RSA sans précaution. Comme prérequis, nous supposons seulement des mathématiques de base (par exemple, nous nous attendons à ce que vous sachiez ce qu'est un carré ou comment additionner des fractions), une programmation de base en python (fonctions, boucles, récursion), du bon sens et de la curiosité. Notre public cible est constitué de toutes les personnes qui travaillent ou envisagent de travailler dans le domaine des technologies de l'information, à commencer par les lycéens motivés.

Dans ce cours en ligne, nous mettrons en œuvre (en Python) des programmes efficaces pour un problème dont les entreprises de livraison du monde entier ont besoin des millions de fois par jour - le problème du voyageur de commerce. L'objectif de ce problème est de visiter tous les lieux donnés le plus rapidement possible. Comment trouver rapidement une solution optimale à ce problème ? Nous ne disposons toujours pas d'algorithmes efficaces prouvés pour ce problème informatique difficile et c'est l'essence même du problème P versus NP, la question ouverte la plus importante de l'informatique. Néanmoins, nous allons implémenter plusieurs solutions pour des instances réelles du problème du voyageur de commerce, en nous appuyant fortement sur la matière apprise dans les cours de la spécialisation : techniques de preuve, combinatoire, probabilités, théorie des graphes. Nous verrons plusieurs exemples d'utilisation d'idées de mathématiques discrètes pour obtenir des solutions de plus en plus efficaces.