Mon espace Me contacter

Cégep • Montréal

Mathématiques pour l'informatique, 201-N11

Le cours de mathématiques pour l'informatique 201-N11 sert de fondation aux techniques de l'informatique : logique, ensembles, numération et graphes. Les notions sont accessibles mais la rigueur de rédaction attendue déroute souvent.

9 séries d'exercices entièrement corrigés (96 exercices), 9 fiches de révision, un examen blanc. Gratuit, sans compte. Le même cours en anglais.

Logique et démonstration

  1. 1 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. Fiche
  2. 2 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. Fiche

Les nombres en machine

  1. 3 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. Fiche
  2. 4 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. Fiche

Ensembles, relations et fonctions

  1. 5 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. Fiche
  2. 6 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. Fiche

Récurrence, graphes et dénombrement

  1. 7 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. Fiche
  2. 8 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. Fiche
  3. 9 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. Fiche

Quand les chapitres sont faits

Une épreuve complète, en conditions d'examen. À faire une fois derrière vous les chapitres qu'elle couvre : elle mesure ce que vous savez faire sur une question jamais vue.

Examen blanc

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
  • 100 points
  • 150 minutes
Passer l'épreuve

Ce qu'il faut tenir avant

Le programme de Mathématiques pour l'informatique (201-N11) s'appuie sur un chapitre venu d'avant. Ce ne sont pas des révisions de confort : chacun est le point d'appui d'un chapitre listé ci-dessus, et un élève qui décroche en cours d'année décroche presque toujours sur l'un d'eux. Tous ont leur fiche de révision, à lire d'une traite avant la rentrée.

Secondaire 4

À lire sur ce niveau

Besoin d'un accompagnement et pas seulement d'exercices ? Maths et informatique au cégep

Vous cherchez un tuteur à Montréal ?

Contactez-moi pour une première séance. On travaille sur des exercices calibrés sur le niveau réel des évaluations.

Me contacter WhatsApp
Site par Studio Squalli