INF3100 Structures discrètes (3 crédits)

Théorie des ensembles. Eléments de combinatoire : énumération, permutations et combinaisons. Principes de base du dénombrement. Introduction à la logique : calcul propositionnel, calcul des prédicats, méthodes de preuve et algèbre de Boole, preuve par récurrence, suites définies par récurrence. Algorithmes : définition, analyse, récursivité. Preuves par récurrence et relations de récurrence, règles d’inférence et de déduction. Comportement asymptotique des fonctions et complexité temporelle des algorithmes. Théorie des nombres : nombres premiers, algorithme d’Euclide, arithmétique modulaire et applications. Relations et fonctions. Théorie des graphes : terminologie, représentations, chemins et circuits, fonctions génératrices. Langages et grammaires, automates finis, machines de Turing.