Contenu

Cours

Cours	Matière	Chapitres des notes de cours	Heures
1 - 2	Logique propositionnelle. Équivalences propositionnelles. Prédicats et quantificateurs. Règles d'inférence. Cohérence d’un ensemble de spécifications. Types de preuve.	1	6
3	Ensemble : opérations sur les ensembles. Fonctions.	1	1.5
3 - 4	Modélisation. Identification des variables, des contraintes et de la fonction-objectif dans un problème d'optimisation. Solution admissible, solution optimale.	2	3
4-5	Théorie des graphes : types de graphes, terminologie, représentation et utilisation. Matrice d’adjacence d’un graphe. Connectivité. Chemins eulériens et hamiltoniens d’un graphe, circuit et applications. Problème du plus court chemin (algorithme de Dijkstra).	3	4.5
6	Théorie des graphes (suite): tri topologique (algorithme de Kahn), chemin de poids maximal, chemin critique.	3	3
7	Examen intra portant sur les cours 1 à 6	4	3
8	Arbres: définitions de base, théorèmes sur les arbres, arbre couvrant de poids minimal (algorithme de Prim).	4	3
9	Introduction à la complexité des algorithmes: mesurer un temps de calcul à l’aide d’une fonction, notation grand-O et grand-Θ, résolution de sommations, fonction de complexité d’un algorithme.	5	4.5
10	Algorithmes récursifs. Fonctions récursives et relations de récurrence. Algorithmes de type diviser pour régner.	5	3
11	Preuves par récurrence. Principe de récurrence forte. Preuve de validité d’un algorithme récursif.	7	3
12 -13	Notions de base du dénombrement. Permutations et combinaisons. Dénombrement par relation de récurrence.	8	4.5
Total			39

Laboratoires et travaux pratiques

Trois heures de travail pratique par semaine seront consacrées à travailler les exercices hebdomadaires, à demander des éclaircissements sur les notions vues dans le cours, à compléter le cours magistral par certaines démonstrations ou certains exemples.

Utilisation d'outils d'ingénierie

Afin de permettre une participation active en classe, il est obligatoire que chaque étudiant·e possède une calculatrice TI-Nspire CX II CAS. Ces calculatrices sont en vente à la COOP. La calculatrice symbolique sera utilisée tout au long de la session pour illustrer des concepts mathématiques, pour effectuer des calculs, des manipulations algébriques et même pour implémenter certains algorithmes. L’utilisation efficace de cet outil sera vérifiée lors des examens. Pour de l’aide sur l’utilisation de cette calculatrice symbolique, visitez le site http://seg-apps.etsmtl.ca/nspire/.

Voici des objectifs spécifiques d’apprentissage concernant l’utilisation de la calculatrice TI-Nspire CAS CX:

Connaître la syntaxe des expressions logiques : and, or, not.
Connaître le fonctionnement de l’éditeur de programmes et de fonctions.
Savoir implémenter une fonction définie par récurrence.
Savoir implémenter une fonction récursive définie par une relation de type diviser pour régner.
Savoir implémenter une suite définie par récurrence, en tracer le graphique en obtenir un terme de rang donné ou une table de valeurs.
Savoir effectuer différentes opérations matricielles (par exemple : obtenir la 5e puissance d’une matrice M associée à un graphe afin d’établir le nombre de chemins de longueur 5 entre deux sommets donnés).

Le programme Excel sera utilisé pour trouver des solutions optimales à des problèmes de programmation linéaire dans le chapitre sur la modélisation. L'utilisation du solveur sera présentée.