Informatique en MP

En MP, l'informatique approfondit l'algorithmique : complexité, tris, arbres, stratégies gloutonnes, programmation dynamique, méta-heuristiques, graphes, apprentissage automatique, théorie des jeux et bases de données relationnelles avec SQL.

MP : Mathématiques et Physique — 2e année de CPGE.

Les 10 séquences du programme

• Séquence 1

  Complexité algorithmique

  Mesurer l'efficacité d'un algorithme : compter les opérations, utiliser la notation asymptotique et calculer la complexité de programmes itératifs et récursifs.

• Séquence 2

  Algorithmes de tri

  Comprendre, programmer et comparer les principaux algorithmes de tri, des tris simples au tri rapide et au tri fusion.

• Séquence 3

  Arbres binaires

  Représenter, parcourir et exploiter les arbres binaires, les arbres binaires de recherche et les tas.

• Séquence 4

  Algorithmes gloutons

  Appliquer la stratégie gloutonne et savoir quand elle donne une solution optimale.

• Séquence 5

  Programmation dynamique

  Résoudre des problèmes d'optimisation en réutilisant les solutions de sous-problèmes, par mémoïsation ou de façon ascendante.

• Séquence 6

  Méta-heuristiques

  Approcher des problèmes d'optimisation difficiles avec des méthodes approchées comme le recuit simulé.

• Séquence 7

  Théorie des graphes

  Représenter des graphes en Python, les parcourir et calculer des plus courts chemins.

• Séquence 8

  Intelligence artificielle

  Découvrir l'apprentissage supervisé et non supervisé : k plus proches voisins, matrice de confusion et k-moyennes.

• Séquence 9

  Théorie des jeux

  Modéliser des jeux à deux joueurs, calculer les positions gagnantes et programmer l'algorithme Minimax.

• Séquence 10

  Bases de données relationnelles

  Modéliser des données et les interroger en SQL : sélections, jointures, agrégations et requêtes imbriquées.

Et ensuite ?

Ce programme s'appuie sur celui de première année : voir l'informatique en MPSI. Vue d'ensemble des thèmes : informatique en CPGE.