Montréal, cégep, programmes d'informatique

Tuteur en mathématiques pour l'informatique 201-N11 à Montréal

Oui, je donne aussi des cours pour ce programme. Le tutorat au cégep à Montréal se résume trop souvent au calcul différentiel de Sciences de la nature, et les étudiants inscrits en Techniques de l'informatique ou en Sciences informatiques et mathématiques ne trouvent personne pour leur cours de mathématiques. J'accompagne ces étudiants sur le cours Mathématiques pour l'informatique, porté dans plusieurs cégeps par le code 201-N11 : logique booléenne, systèmes de numération, théorie des ensembles et relations, graphes et matrices.

Cours 201-N11Techniques de l'informatiqueLogique et algèbre de BooleBinaire et hexadécimalEnsembles, relations, graphes ★ 5,0 · 11 avis Google

Prendre contact WhatsApp

Le cours Mathématiques pour l'informatique : ce qu'il faut savoir

Les programmes d'informatique du cégep ont leur propre cours de mathématiques, distinct de la séquence 201-SN2-RE, 201-SN3-RE et 201-SN4-RE (anciens NYA, NYB, NYC) suivie en Sciences de la nature. Il porte selon les établissements le code 201-N11 ou un code voisin, et il s'appelle presque partout Mathématiques pour l'informatique ou Mathématiques discrètes. Un étudiant en Techniques de l'informatique le suit généralement dans sa première année, et un étudiant du programme intégré Sciences informatiques et mathématiques le retrouve comme cours de concentration à côté des cours de calcul.

La différence avec le calcul différentiel n'est pas une différence de difficulté, c'est une différence de nature. Il n'y a ici ni limite, ni dérivée, ni intégrale. Le cours travaille sur des objets finis et discrets : des propositions vraies ou fausses, des motifs de bits, des ensembles, des relations, des sommets reliés par des arêtes. C'est exactement la mathématique qui se cache derrière une condition dans un programme, une requête de base de données, un masque de bits ou un parcours de réseau.

C'est aussi un cours qui décide de la suite du programme. La logique booléenne se retrouve dans toutes les conditions écrites en programmation, les ensembles et les relations reviennent en base de données, la numération réapparaît dès qu'il faut comprendre un dépassement de capacité ou une comparaison de nombres à virgule flottante, et les graphes reviennent en structures de données. Un étudiant qui laisse passer ce cours le paie deux fois.

Les quatre grands blocs du programme 201-N11

Logique booléenne et mathématique

Connecteurs et tables de vérité
Lois de l'algèbre de Boole et De Morgan
Implication, contraposée, réciproque, négation
Quantificateurs et négation d'un énoncé quantifié
Formes normales et tableaux de Karnaugh
Circuits logiques, additionneur, porte NAND

Systèmes de numération

Poids positionnels, binaire, octal, hexadécimal
Conversions par divisions et multiplications successives
Arithmétique binaire posée
Complément à deux et plage asymétrique
Débordement contre retenue
Masques, opérations bit à bit, ASCII, BCD, Gray, IEEE 754

Ensembles et relations

Appartenance, inclusion, ensemble des parties
Opérations et produit cartésien
De Morgan par double inclusion
Diagrammes de Venn et inclusion-exclusion
Relations binaires, matrice, graphe sagittal
Relations d'ordre, d'équivalence, classes et partitions

Graphes et matrices

Sommets, arêtes, degrés, lemme des poignées de main
Matrice d'adjacence d'un graphe orienté
Opérations matricielles et non-commutativité
Puissances de la matrice et comptage de chemins
Connexité et matrice d'accessibilité
Déterminant, inverse, transformations du plan

Le découpage varie un peu d'un cégep à l'autre, et beaucoup de plans de cours ajoutent les techniques de démonstration, l'arithmétique modulaire, les fonctions, la récurrence et la récursivité, le dénombrement et les probabilités : ces chapitres ont aussi leur série et leur fiche sur le site. Envoyez-moi votre plan de cours, je m'aligne dessus.

Ce qui bloque réellement les étudiants

Le premier obstacle est le format de la réponse. Jusqu'au secondaire, une question de mathématiques se termine par un nombre. Ici, on demande de démontrer que deux ensembles sont égaux, de justifier qu'une relation est transitive, ou d'expliquer pourquoi une simplification est valide. Un étudiant qui a compris la notion peut perdre la moitié des points simplement parce qu'il a donné le résultat sans le raisonnement.

Le deuxième vient du profil des étudiants. Beaucoup arrivent en Techniques de l'informatique depuis une séquence CST ou TS, parfois après quelques années passées hors de l'école. Ils sont souvent très à l'aise avec un ordinateur et beaucoup moins avec une notation abstraite. Voir écrit l'ensemble des parties d'un ensemble, un cardinal d'union ou la négation d'une conjonction suffit à faire décrocher, alors que la même idée exprimée en code passerait sans difficulté. Une bonne partie du travail consiste à traduire dans les deux sens.

Le troisième est la vitesse. Le cours enchaîne quatre univers différents en une session : on passe des tables de vérité au complément à deux, puis aux relations d'équivalence, puis aux matrices, sans que rien ne semble relier ces chapitres. Un étudiant qui prend du retard sur un bloc n'a pas d'occasion de le rattraper, parce que le suivant commence sur un terrain neuf.

Et enfin les erreurs de détail, qui coûtent très cher en évaluation : lire les restes d'une division successive dans le mauvais sens, confondre un élément et l'ensemble qui le contient, oublier qu'une implication est vraie dès que son hypothèse est fausse, ou croire qu'un produit de matrices se lit dans n'importe quel ordre.

Tous les chapitres, avec leurs exercices corrigés et leurs fiches

Le programme chapitre par chapitre, dans l'ordre de l'année : chaque ligne mène à une série d'exercices entièrement corrigés et, quand elle existe, à la fiche de révision du chapitre. Tout est gratuit, sans inscription.

Mathématiques pour l'informatique, 201-N11 10 séries corrigées • 9 fiches de révision

Exercices corrigés du cours 201-N11

Une série par chapitre du cours, au format d'un examen réel, une partie sur les bases et une partie au niveau de l'évaluation finale, avec le corrigé complet de chaque exercice, et un examen de synthèse. Accès libre, sans inscription.

Logique booléenne et mathématique

Connecteurs et tables de vérité, lois de l'algèbre de Boole et De Morgan, implication avec contraposée et réciproque, quantificateurs et leur négation, formes normales lues sur une table. Puis une partie niveau examen : tableau de Karnaugh à quatre variables, demi-additionneur et porte NAND universelle, un contrôle d'accès à simplifier et la validation d'un raisonnement par le modus tollens.

10 exercices corrigés • /100 points

Techniques de démonstration

Les cinq techniques du devis, et surtout le choix de la structure avant la première ligne : preuve directe, contraposée qui n'est pas la réciproque, raisonnement par l'absurde avec l'irrationalité et l'infinité des premiers, disjonction de cas, réfutation par contre-exemple. Puis une partie niveau examen : le principe des tiroirs de Dirichlet démontré puis généralisé, la récurrence située parmi les cinq, l'impossibilité d'un compresseur sans perte universel et quatre rédactions d'une même preuve à départager.

10 exercices corrigés • /100 points

Systèmes de numération informatique

Poids positionnels et conversions entre binaire, octal, hexadécimal et décimal, divisions successives, arithmétique binaire posée, complément à deux et plage asymétrique, débordement contre retenue. Puis une partie niveau examen : masques et opérations bit à bit, codes ASCII, BCD, Gray et parité, un problème de couleurs et de mémoire, et le format IEEE 754 en simple précision. Deux laboratoires complets, en base 8 puis en base 16, prolongent les bases : notation développée, conversions dans les deux sens, additions, complément à 8 et à 16, soustractions, multiplications posées et aller-retour contrôlé en décimal.

12 exercices corrigés • /120 points

L'arithmétique modulaire

La division euclidienne et le reste toujours positif, avec la différence de convention entre Python et le langage C qui piège les programmeurs ; les congruences, leurs trois propriétés d'équivalence et la compatibilité avec la somme et le produit, démontrée puis utilisée pour réduire avant de multiplier ; les tables modulo 7 et modulo 6, où apparaissent les diviseurs de zéro et la raison pour laquelle un module premier change tout ; l'algorithme d'Euclide justifié en une ligne et illustré par un pavage de carrés, avec le pire cas des nombres de Fibonacci ; l'inverse modulaire, son critère d'existence et les équations de congruence à zéro, une ou plusieurs solutions. La partie B établit Bézout et l'algorithme d'Euclide étendu, le petit théorème de Fermat et l'exponentiation rapide avec son gain chiffré, puis traite les clés de contrôle ISBN et leur faiblesse sur les interversions, et enfin un chiffrement RSA complet sur de petits nombres premiers. En ouverture, deux exercices de calculs, neuf restes à calculer modulo n et un PGCD, puis huit inverses et congruences à résoudre.

12 exercices corrigés • /120 points

Théorie des ensembles et relations

Appartenance contre inclusion, ensemble des parties, opérations et produit cartésien, De Morgan par double inclusion et par table d'appartenance, diagrammes de Venn et inclusion-exclusion, relations binaires avec leur matrice et leur graphe sagittal. Puis une partie niveau examen : les quatre propriétés, relations d'équivalence et partitions, un sondage à trois ensembles et un problème d'ordre partiel avec fermeture transitive.

10 exercices corrigés • /100 points

Fonctions injectives, surjectives, bijectives

La fonction comme relation soumise à l'existence et à l'unicité, image et image réciproque d'une partie, fibres ; puis les trois natures lues sur un diagramme sagittal et sur la règle du carré posée entre quatre couples de départ et d'arrivée, les trois rédactions types, la composée et ce dont elle hérite. La partie B traite le chiffrement par substitution comme bijection et sa réciproque, le comptage des fonctions, des injections, des surjections et des bijections avec les trois inégalités de cardinal, une fonction de hachage lue comme fonction plutôt que comme calcul de probabilité, et l'énumération de Z par N.

10 exercices corrigés • /100 points

Récurrence et récursivité

Le principe de récurrence et ses deux étapes, avec les deux contre-exemples qui montrent qu'aucune n'est facultative, la propriété n égale n plus un dont l'hérédité est valide, et le polynôme d'Euler premier jusqu'à trente-neuf ; les trois familles de récurrences, sommes, inégalités et divisibilité, et le geste propre à chacune ; la récurrence forte appliquée à l'existence d'un diviseur premier, et la récurrence à deux crans qui exige deux initialisations ; la traduction en fonctions récursives, les deux conditions de terminaison et le rôle de la pile d'appels ; le coût de Fibonacci naïf, compté sur son arbre puis démontré égal à deux fois Fibonacci moins un. La partie B résout les récurrences linéaires par l'équation caractéristique jusqu'à la formule de Binet, analyse la dichotomie et le tri fusion, puis traite les tours de Hanoï, dont le coût exponentiel est cette fois inévitable, ce qui donne le critère pour distinguer un mauvais algorithme d'un problème difficile.

10 exercices corrigés • /100 points

Introduction aux graphes et aux matrices

Sommets, arêtes et lemme des poignées de main, matrice d'adjacence d'un graphe orienté, opérations matricielles et non-commutativité, puissances de la matrice et comptage de chemins, connexité et matrice d'accessibilité. Puis une partie niveau examen : transformations du plan et infographie, déterminant et matrice inverse, un réseau routier pondéré et la composition de transformations en coordonnées homogènes. En ouverture, un exercice de calculs : dix calculs directs sur les matrices, du produit au déterminant 3x3.

11 exercices corrigés • /110 points

Dénombrement et probabilités

Le principe multiplicatif appliqué aux adresses IPv4 et IPv6, aux couleurs sur vingt-quatre bits et aux identifiants ; les quatre modèles de tirage rangés en tableau, avec le constat contre-intuitif qu'interdire les répétitions affaiblit un mot de passe ; le triangle de Pascal démontré par un argument de partage, la somme d'une ligne égale à deux puissance n, et le calcul récursif naïf qui retombe sur le problème de mémoïsation du chapitre précédent ; le principe des tiroirs, de treize personnes et douze mois jusqu'à la preuve qu'aucune fonction de hachage ne peut éviter les collisions ; les probabilités uniformes et le réflexe de l'événement contraire. La partie B traite la formule de Bayes sur un test de dépistage, où un positif sur six seulement est malade, et sur un filtre antipourriel, où la même formule donne quatre-vingt-seize pour cent ; l'espérance et l'analyse en moyenne d'un algorithme ; puis deux problèmes complets, la force d'un mot de passe mesurée en bits d'entropie et le paradoxe des anniversaires appliqué au dimensionnement des empreintes cryptographiques. En ouverture, un exercice de calculs : dix dénombrements à calculer directement, des factorielles au binôme de Newton.

11 exercices corrigés • /110 points

Examen de synthèse 201-N11

L'examen final blanc qui reprend les sept grands thèmes du cours en dix exercices. Partie A : un tableau de Karnaugh simplifié en deux blocs, la forme normale disjonctive et la contraposée opposée à la réciproque ; conversions de bases, complément à deux et débordement signé lu sur la roue des seize codes ; relations d'équivalence, partitions et ordre partiel de la divisibilité ; matrice d'adjacence dont le carré compte les chemins de longueur deux ; congruences et chiffrement affine avec son inverse modulo vingt-six. Partie B : une démonstration par récurrence complète, dont la somme des cubes égale au carré de la somme des entiers et une suite qui se révèle être la méthode de Newton ; un arbre binaire de recherche, sa hauteur, sa dégénérescence sur des données triées et la probabilité de ce pire cas ; cinq affirmations transversales à corriger ; puis deux problèmes de synthèse, le stockage des mots de passe avec sel et le coût d'analyse d'un réseau.

10 exercices corrigés • /100 points

Voir toute la banque d'exercices corrigés →

Fiches de révision du cours 201-N11

Une fiche par chapitre, à lire avant la série du même chapitre : les confusions qui coûtent des points en évaluation, nommées une par une, et la rédaction attendue par le correcteur.