MAT120 - Mathématiques discrètes

Cible(s) de formation

Maîtriser le langage de base dans lequel s'expriment les mathématiques; utiliser les concepts fondamentaux associés au discret; se servir d'un logiciel de calcul symbolique pour explorer des hypothèses et vérifier ou obtenir des résultats reliés au discret.

Contenu

Logique : calcul propositionnel et calcul des prédicats. Techniques de preuve : preuve directe, preuve indirecte (contraposition et absurde), récurrence simple et généralisée. Ensembles. Entiers, divisibilité, décomposition en nombres premiers, arithmétique modulaire. Principe de Dirichlet. Aperçu de la théorie des graphes : graphes orientés et non orientés, sous-graphes, circuits et cycles, connexité, graphes complets et coloriage, matrice associée à un graphe, graphes isomorphes; arbre et arbre générateur.Automates finis déterministes et non déterministes, traduction d'un automate non déterministe en un automate déterministe, minimisation d'un automate.

Équivalente(s)

(MAT114)

(MAT115)

* Sujet à changement