Résumé de section

  • OBJECTIFS ET DESCRIPTION DU COURS

    Tout replier Tout déplier

    L'unité d'enseignement CSC 400 – Discrete Structures for Computer Science constitue l'un des fondements théoriques essentiels de la formation en informatique. Elle introduit les concepts mathématiques nécessaires à la compréhension, à l'analyse et à la conception des systèmes informatiques modernes. Ces concepts sont omniprésents dans les domaines de l'algorithmique, de la programmation, des bases de données, de l'intelligence artificielle, des réseaux informatiques, de la cybersécurité, de la cryptographie, de la théorie des langages, de la science des données et du génie logiciel.

    Contrairement aux mathématiques classiques qui étudient principalement les phénomènes continus, les structures discrètes s'intéressent aux objets finis ou dénombrables. Elles offrent un cadre rigoureux permettant de modéliser les données, de représenter les relations entre objets, de raisonner de manière logique et de résoudre des problèmes complexes à l'aide de méthodes formelles.

    Ce cours développe progressivement les connaissances théoriques et les compétences analytiques des étudiants en abordant notamment :

    ·         les fondements de la logique propositionnelle et de la logique des prédicats ;

    ·         les techniques de raisonnement mathématique et de démonstration ;

    ·         les ensembles, relations et fonctions ;

    ·         les méthodes de comptage et d'analyse combinatoire ;

    ·         les relations de récurrence ;

    ·         les graphes et leurs applications informatiques ;

    ·         les arbres et leurs structures hiérarchiques ;

    ·         les algèbres booléennes ;

    ·         les fondements de la théorie des nombres utiles en cryptographie ;

    ·         les structures algébriques élémentaires.

    Au-delà de l'acquisition de connaissances théoriques, cette unité d'enseignement vise à développer chez l'étudiant des compétences de raisonnement, d'abstraction, de modélisation et de résolution de problèmes qui constituent des prérequis indispensables pour les unités d'enseignement avancées en informatique.

    Une attention particulière est portée à l'utilisation des structures discrètes dans des contextes professionnels réels, notamment :

    ·         la modélisation de réseaux informatiques ;

    ·         la représentation des dépendances entre tâches ;

    ·         la conception d'algorithmes efficaces ;

    ·         l'analyse de la complexité algorithmique ;

    ·         les systèmes de sécurité informatique ;

    ·         les protocoles cryptographiques ;

    ·         les moteurs de recherche ;

    ·         les systèmes de recommandation ;

    ·         les compilateurs ;

    ·         les systèmes distribués.

    L'approche pédagogique alterne des exposés théoriques, des exercices guidés, des études de cas, des démonstrations, des travaux dirigés ainsi que des activités de résolution collaborative de problèmes. Les étudiants seront amenés à développer une rigueur scientifique indispensable à la pratique professionnelle de l'informatique.

  • PREREQUIS

    Voir le syllabus 

  • RESULTATS D'APPRENTISSAGE (LEARNING OUTCOMES)

    Voir le syllabus 

  • CRITERES D'EVALUATION (LEARNING ASSESSMENT CRITERIA)

    Voir le syllabus 

  • EVALUATION DE L'APPRENTISSAGE & PONDERATION

    Voir le syllabus 

  • SYLLABUS, LIVRES & AUTRES SUPPORTS DE COURS

  • SEMAINE 1 : Introduction aux structures discrètes et logique propositionnelle

    Contenus

    ·        Présentation du cours, de ses objectifs et des modalités d'évaluation

    ·        Introduction aux structures discrètes et à leur importance en informatique

    ·        Notion de proposition logique

    ·        Connecteurs logiques (ET, OU, NON, implication, équivalence)

    ·        Tables de vérité

    ·        Équivalences logiques fondamentales

    ·        Applications de la logique en informatique

    Objectifs pédagogiques

    À l'issue de cette semaine, l'étudiant devra être capable de :

    ·        comprendre le rôle des structures discrètes dans les sciences informatiques ;

    ·        distinguer une proposition logique d'une expression non propositionnelle ;

    ·        construire et interpréter des tables de vérité ;

    ·        appliquer les principales lois de la logique propositionnelle ;

    ·        formaliser des raisonnements simples à l'aide d'expressions logiques.

  • SEMAINE 2 : Logique des prédicats et méthodes de démonstration

    Contenus

    ·        Variables propositionnelles

    ·        Prédicats

    ·        Quantificateurs universels et existentiel

    ·        Négation des quantificateurs

    ·        Méthodes de démonstration

    ·        Démonstration directe

    ·        Démonstration par contraposée

    ·        Démonstration par contradiction

    ·        Principe de récurrence

    Objectifs pédagogiques

    À la fin de cette semaine, l'étudiant devra être capable de :

    ·        Utiliser correctement les quantificateurs ;

    ·        Traduire des énoncés en logique des prédicats ;

    ·        Choisir la méthode de démonstration adaptée à un problème ;

    ·        Construire une démonstration mathématique rigoureuse.

  • SEMAINE 3 : Théorie des ensembles, relations et fonctions

    Contenus

    ·        Ensembles et sous-ensembles

    ·        Opérations sur les ensembles

    ·        Produit cartésien

    ·        Relations binaires

    ·        Relations d'équivalence

    ·        Relations d'ordre

    ·        Fonctions

    ·        Applications injectives, surjectives et bijectives

    Objectifs pédagogiques

    À la fin de cette semaine, l'étudiant devra être capable de :

    ·        manipuler correctement les ensembles ;

    ·        analyser les propriétés des relations ;

    ·        distinguer les différents types de fonctions ;

    ·        utiliser les ensembles et fonctions pour modéliser des problèmes informatiques.

  • SEMAINE 4 : Combinatoire et techniques de dénombrement

    Contenus

    ·        Principes fondamentaux du dénombrement

    ·        Permutations

    ·        Arrangements

    ·        Combinaisons

    ·        Coefficients binomiaux

    ·        Binôme de Newton

    ·        Principe des tiroirs

    Objectifs pédagogiques

    À la fin de cette semaine, l'étudiant devra être capable de :

    ·        résoudre des problèmes de dénombrement ;

    ·        choisir la méthode combinatoire appropriée ;

    ·        appliquer le binôme de Newton ;

    ·        interpréter les résultats obtenus dans différents contextes.

  • SEMAINE 5 : Relations de récurrence et introduction aux graphes

    Contenus

    ·        Suites définies par récurrence

    ·        Relations de récurrence

    ·        Méthodes de résolution

    ·        Applications à l'analyse des algorithmes

    ·        Introduction aux graphes

    ·        Sommets et arêtes

    ·        Types de graphes

    ·        Représentation des graphes

    Objectifs pédagogiques

    À la fin de cette semaine, l'étudiant devra être capable de :

    ·        résoudre des relations de récurrence simples ;

    ·        analyser le comportement d'algorithmes récursifs ;

    ·        représenter correctement un graphe ;

    ·        identifier les principales propriétés des graphes.

  • SEMAINE 6 : EXAMEN A MIS PARCOURS

    Contenus évalués

    ·        L'évaluation portera sur l'ensemble des notions étudiées au cours des cinq premières semaines :

    ·        logique propositionnelle ;

    ·        logique des prédicats ;

    ·        méthodes de démonstration ;

    ·        théorie des ensembles ;

    ·        relations ;

    ·        fonctions ;

    ·        techniques de dénombrement ;

    ·        combinatoire ;

    ·        relations de récurrence ;

    ·        notions fondamentales sur les graphes.

    Objectifs

    ·        Vérifier l'acquisition des connaissances fondamentales nécessaires à la poursuite du cours et apprécier la capacité de l'étudiant à appliquer les méthodes étudiées dans des situations variées.

  • SEMAINE 7 : Théorie des graphes

    Contenus

    ·        Graphes orientés et non orientés

    ·        Parcours en profondeur (DFS)

    ·        Parcours en largeur (BFS)

    ·        Chaînes et cycles

    ·        Connexité

    ·        Graphes eulériens

    ·        Graphes hamiltoniens

    ·        Applications aux réseaux informatiques

    Objectifs pédagogiques

    À la fin de cette semaine, l'étudiant devra être capable de :

    ·        analyser la structure d'un graphe ;

    ·        appliquer les algorithmes de parcours ;

    ·        déterminer les propriétés de connexité ;

    ·        modéliser des réseaux à l'aide des graphes.

  • SEMAINE 8 : Arbres et structures hiérarchiques

    Contenus

    ·        Définition des arbres

    ·        Arbres enracinés

    ·        Arbres binaires

    ·        Parcours des arbres

    ·        Arbres de recherche

    ·        Arbres couvrants

    ·        Applications aux structures de données

    Objectifs pédagogiques

    À la fin de cette semaine, l'étudiant devra être capable de :

    ·        distinguer les différents types d'arbres ;

    ·        construire un arbre adapté à un problème donné ;

    ·        appliquer les méthodes de parcours ;

    ·        expliquer l'utilisation des arbres dans les systèmes informatiques.

  • SEMAINE 9 : Algèbre booléenne et circuits logiques

    Contenus

    ·        Algèbre de Boole

    ·        Lois fondamentales

    ·        Simplification des expressions booléennes

    ·        Tables de vérité

    ·        Portes logiques

    ·        Conception de circuits combinatoires

    Objectifs pédagogiques

    À la fin de cette semaine, l'étudiant devra être capable de :

    ·        appliquer les lois de l'algèbre booléenne ;

    ·        simplifier des expressions logiques ;

    ·        analyser des circuits numériques simples ;

    ·        établir le lien entre logique mathématique et architecture des ordinateurs.

  • SEMAINE 10 : Théorie des nombres et applications à la cryptographie

    Contenus

    ·        Divisibilité

    ·        Nombres premiers

    ·        PGCD et PPCM

    ·        Algorithme d'Euclide

    ·        Arithmétique modulaire

    ·        Congruences

    ·        Introduction aux principes mathématiques de la cryptographie

    Objectifs pédagogiques

    À la fin de cette semaine, l'étudiant devra être capable de :

    ·        résoudre des problèmes élémentaires de théorie des nombres ;

    ·        utiliser l'arithmétique modulaire ;

    ·        appliquer l'algorithme d'Euclide ;

    ·        expliquer les fondements mathématiques de la cryptographie.

  • SEMAINE 11 : Applications intégrées des structures discrètes

    Contenus

    ·        Modélisation de problèmes complexes

    ·        Applications des graphes aux réseaux

    ·        Structures discrètes et intelligence artificielle

    ·        Structures discrètes et bases de données

    ·        Structures discrètes et cybersécurité

    ·        Études de cas

    ·        Révision générale

    Objectifs pédagogiques

    À la fin de cette semaine, l'étudiant devra être capable de :

    ·        intégrer plusieurs notions du cours dans une même démarche de résolution ;

    ·        analyser un problème informatique complexe ;

    ·        proposer une modélisation mathématique cohérente ;

    ·        justifier les solutions retenues.

  • SEMAINE 12 : EXAMEN FINAL

    Contenus évalués

    ·        L'examen final couvre l'ensemble des notions étudiées durant le semestre, avec un accent particulier sur :

    ·        théorie des graphes ;

    ·        arbres ;

    ·        algèbre booléenne ;

    ·        théorie des nombres ;

    ·        applications des structures discrètes ;

    ·        modélisation de problèmes informatiques ;

    ·        intégration des concepts étudiés.

    Objectifs

    ·        L'examen final vise à vérifier que l'étudiant maîtrise les connaissances théoriques et qu'il est capable de mobiliser les différentes structures discrètes pour analyser, modéliser et résoudre des problèmes informatiques de manière rigoureuse, autonome et argumentée.

  • Nouvelle section