INF115 - Logique et structures discrètes

Cible(s) de formation

Acquérir la capacité d'abstraction jugée suffisante pour la poursuite d'études universitaires en informatique; être apte à formaliser des idées exprimées dans une langue naturelle.

Contenu

Calcul propositionnel; calcul des prédicats, quantificateurs. Ensemble, relation, fonction, suite et séquence. Techniques de preuve : preuve par l'absurde (contradiction, contraposée), induction (mathématique, généralisée, constructive). Méthodes élémentaires de dénombrement : arrangement, combinaison, coefficients binomiaux. Éléments de la théorie des graphes et des arbres. Automates finis déterministes et non déterministes; déterminisation et minimisation d'un automate.