Campus Informatique Tout-en-un Mp2i-mpi

Par (auteur) Becker, Florent; Par (auteur) Bournez, Olivier; Par (auteur) Carré, Jean-Loup; Par (auteur) Liedloff, Mathieu; Par (auteur) Reichert, Julien; Par (auteur) Rozsavolgyi, Gérard
Description:
LE COURS

• Les notions du programme indispensables à connaître  sont abordées dans le respect des textes officiels.
• Les principales difficultés et erreurs sont mises en avant.
• Des méthodes expliquent la démarche attendue.

LES EXERCICES

• Des QCM et des Vrai/Faux pour valider ses connaissances.
• Des exercices d’entraînement, dont certains tirés d’annales  de concours, de difficulté variée pour appliquer le cours et  se préparer aux épreuves.
• Tous les corrigés détaillés et expliqués.

Table of contents:
Bases de l’informatique.  Notion d’algorithme.  Notion de machine.  Le langage OCaml. Compléments. Le langage C.  Processus de compilation et interprétation. 
Codage de l’information.  Mémoire - Méthodologie algorithmique.  Compléments sur la gestion mémoire en C.  Langage C et gestion mémoire.  Notions fondamentales en algorithmie.  Complexité et structures de données  séquentielles.  Analyse de complexité.  Algorithmes de tris simples.  Structures de données abstraites.  Complexité temporelle amortie.  Tableaux associatifs - Hachage.  Structures de données hiérarchiques et récursivité.  Données hiérarchiques.  Structures de données hiérarchiques efficaces.  Algorithmes utilisant des arborescences.  Bases de données.  Vocabulaire des bases de données. 
Associations.  Requêtes en SQL.  Paradigmes algorithmiques.  Introduction. Stratégies gloutonnes.  Diviser pour régner.  Programmation dynamique.  Graphes et algorithmes de graphes.  Vocabulaire.  Représentation.  Accessibilité et parcours de graphes.  Plus courts chemins.  Arbre couvrant de poids minimum. 
Algorithmique avancée.  Algorithmique des textes.  Algorithmique pour l’intelligence artificielle et l’étude des jeux.  Algorithmes probabilistes.  Algorithmes d’approximation.  Concurrence et synchronisation.  Fil d’exécution.  Exclusion mutuelle.  Logique, preuves et déduction naturelle.  Syntaxe du calcul des prédicats.  Sémantique.  Satisfaisabilité et complexité.  Déduction naturelle. Quantificateurs.  Langages - Automates - Grammaires.  Alphabets et mots. Langages.  Expressions régulières.  Automates.  Grammaires.  Décidabilité et classes de complexité.  Machines universelles.  Un programme universel en Ocaml.  Problèmes et langages décidables.  Modèles de calculs.  Indécidabilité.  La notion de temps raisonnable.  Comparer les problèmes.  La classe NP.  Quelques problèmes NP-complets.  Preuve du théorème de Cook-Levin