Data ScienceDécouvrir Coursera Plus
Data Science · Année 2 · Informatique théorique et statistique
S3 Mathématiques discrètes et algorithmique
Savoir prouver, compter et raisonner sur des graphes, puis concevoir et analyser des algorithmes efficaces.
173heures de cours
18semaines à 10 h
2étapes
9nouveaux cours
2universités
Compétences visées
- Preuve par récurrence, par l'absurde, invariants
- Combinatoire, probabilités discrètes, théorie des graphes
- Arithmétique modulaire et cryptographie RSA
- Diviser pour régner, graphes, gloutons, programmation dynamique, NP-complétude
Projet du semestre
Le projet Delivery Problem de UCSD : résoudre un problème de voyageur de commerce et comparer des heuristiques.
Cours du semestre
- 1University of California San DiegoDébutantPython
Prérequis annoncés : Basic math (fractions, squares), basic Python (functions, loops, recursion)
Voir les 5 cours
Cours Niveau Durée Note (avis) Mathematical Thinking in Computer Science Débutant 42 h 4,4 (2 289) Combinatorics and Probability Débutant 23 h 4,6 (874) Introduction to Graph Theory Débutant 21 h 4,5 (1 073) Number Theory and Cryptography Débutant 17 h 4,5 (610) Delivery Problem Débutant 13 h 4,7 (376) - 2Stanford University (Stanford Online)IntermédiaireC, Java, Python
Prérequis annoncés : Programming in at least one language (C, Java or Python); familiarity with proofs (induction, contradiction); discrete probability
Voir les 4 cours
Cours Niveau Durée Note (avis) Divide and Conquer, Sorting and Searching, and Randomized Algorithms Intermédiaire 15 h 4,8 (5 342) Graph Search, Shortest Paths, and Data Structures Intermédiaire 14 h 4,8 (2 002) Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming Intermédiaire 15 h 4,8 (1 279) Shortest Paths Revisited, NP-Complete Problems and What To Do About Them Intermédiaire 13 h 4,8 (832)
Lectures
Mathematics for Computer ScienceE. Lehman, F. T. Leighton, A. R. Meyer (MIT)La référence pour les preuves, la combinatoire et les graphes ; couvre tout le cours de UCSD et davantage.Gratuit, CC BY-SA
AlgorithmsJeff EricksonAccompagne Stanford Algorithms : récursivité, programmation dynamique, graphes, réductions, avec de nombreux exercices.Gratuit, CC BY 4.0
Points d’attention
- Stanford Algorithms suppose la lecture de preuves : le faire après Discrete Mathematics.
- Pour aller plus loin en pratique : Data Structures and Algorithms (UCSD, 182 h), disponible dans le fichier Computer Science.
Avec Coursera Plus
Ce semestre représente 173 heures, soit environ 4 mois à 10 heures par semaine. L’abonnement Coursera Plus donne accès à la plupart de ses cours pendant cette période.