CM de structures discrètes (DUT 1 Informatique)

Voici les thèmes abordés, séance par séance :

• CM 1, 17 septembre 2013 : notions de base sur les ensembles ; éléments ; appartenance ; ensembles finis et infinis ; cardinal ; ensembles usuels de nombres ; notations ensemblistes (extension, compréhension, formule, intervalle).


• CM 2, 1^er octobre 2013 : les entiers de von Neumann ; formules du calcul propositionnel ; booléens ; affectations ; évaluation d'une formule sous une affectation ; tables de vérité ; formules satisfiables, falsifiables, valides, contradictoires ; tables de vérité sur deux formules atomiques ; formules de la logique du 1^er ordre.


• CM 3, 8 octobre 2013 : formules closes ; interprétations de formules closes ; évaluations de formules closes ; notion de démonstration, de raisonnement, de contre-exemple ; inclusion d'ensembles.


• CM 4, 15 octobre 2013 : théorème de la double inclusion ; schéma de démonstration d'égalité de deux ensembles par double inclusion ; diagrammes de Venn ; détection de sophismes par utilisation de diagrammes de Venn ; opérations sur les ensembles : union, intersection, différence ensembliste, différence symétrique, complémentaire, ensemble des parties.


• CM 5, 22 octobre 2013 : la notion de couple d'éléments ; produit cartésien de deux ensembles ; opérations commutatives ; opérations associatives ; théorème de distributivité ; théorème de De Morgan ; partitions ensemblistes ; relations binaires, définition et premiers exemples.


• CM 6, 5 novembre 2013 : l'inclusion ensembliste en tant que relation binaire ; relations binaires remarquables ; représentations de relations binaires (sagittale, matricielle, graphe orienté) ; propriétés des relations binaires (réflexivité, irréflexivité, symétrie, antisymétrie, transitivité) ; relations d'ordre ; démontrer qu'une relation binaire est une relation d'ordre.


• CM 7, 12 novembre 2013 : examen de mi-semestre.


• CM 8, 19 novembre 2013 : relations d'équivalence ; démontrer qu'une relation binaire est une relation d'équivalence ; classes d'équivalence ; constructions : relations d'équivalence vers partitions ensemblistes et partitions ensemblistes vers relations d'équivalence ; opérations sur les relations binaires (inverse, complémentaire, composée) ; notion de fonction ; domaine et définition d'une fonction ; image d'une fonction.


• CM 9, 26 novembre 2013 : image et image réciproque d'un ensemble par une fonction ; notion d'application ; injectivité d'une application (et technique de démonstration) ; surjectivité d'une application (et technique de démonstration) ; bijectivité d'une application.


• CM 10, 3 décembre 2013 : injectivité, surjectivité, bijectivité et cardinaux d'ensembles finis ; composition d'applications ; inversion d'applications bijectives ; composition d'une application avec son inverse ; théorème de l'inversion ; structures récursives ; les listes ; les arbres ; représentations graphiques des arbres.


• CM 11, 10 décembre 2013 : langages ; arbre syntaxique d'une formule ; occurrences libres/liées de variables dans une formule ; interprétation d'un langage ; évaluation d'une formule sous une interprétation et une valuation ; équivalence de formules ; calcul de la négation d'une formule ; contraposée.


• CM 12, 17 décembre 2013 : examen final.