Introduction

• Programme officiel
• Objectifs
• Plan

Programme officiel

• Ensembles: calcul ensembliste, cardinaux, ensembles dénombrables (argument de la diagonale de Cantor)
• Relations, Fonctions: relations, fonctions, fonctions partielles, opérations, compositions, relations d’équivalences, partitions, congruences
• Ordres: ordres et pré-ordres, applications monotones, ensembles totalement ordonnés, sous-ensembles, chaînes, majorants, minorants, ordres bien fondés, notion d’induction bien fondée, produits (lexicographique) de relations bien fondées, ensembles complets, treillis, points fixes de fonctions monotones
• Algèbre de Boole: définition algébrique, homomorphismes, anneaux de Boole, fonctions booléennes
• Algèbre combinatoire: permutations, arrangements, formule du binôme, suites récurrentes
• Eléments de probabilité discrète: espace de probabilité, probabilité conditionnelle, variable aléatoire, événements indépendants, chaînes de Markov

Objectifs

• Raisonner sur des structures utiles en informatique :
  • Objets syntaxiques (mots, listes, arbres, …)
  • Equivalence
  • Ordres
  • Dénombrement
• Construire des objets complexes à partir de briques de base
• Quelques éléments d’informatique théorique

Plan

1. Quelques éléments de logique
2. Théorie naive des ensembles
3. Le paysage syntaxique
4. Équivalence et Ordres
5. Algèbre de Boole
6. Combinatoire