MAT6080 Mathématiques discrètes (1 crédit)

Théorie naïve des ensembles. Opérations sur les ensembles, cardinalité d'un ensemble, ensembles dénombrables, relations : fonctions, relations d'ordre, relations d'équivalence et partitions. Algèbre relationnelle. Logique propositionnelle et calcul des prédicats. Preuves par induction. Écriture de boucles simples à partir d'invariants. Introduction à la vérification de programmes. Preuves de boucles à l'aide d'invariants. Notions élémentaires sur la complexité temporelle et spatiale des algorithmes. Notation asymptotique. Algorithmes de fouille et de tri. Analyse de la complexité d'algorithmes récursifs. Équations de récurrence. Théorie des graphes et combinatoire. Graphes orientés, graphes non orientés, arbres, arborescences. Chemins dans un graphe, hauteur d'une arborescence et exemples d'applications à l'analyse d'algorithmes. Parcours de graphes.