% INF1132 — Mathématiques pour l'informatique % UQAM — Département d'informatique % Plan de cours — Hiver 2023 * Horaires, locaux et enseignants: Responsable(s) du cours ======================= Coordination ------------ Meurs, Marie-Jean Enseignement ------------- Giraudo, Samuele Groupes: 010, 040 Description du cours ==================== Connaître les notions de base de la logique et les notions mathématiques qui sous-tendent la programmation, en particulier celles qui sont utilisées dans la vérification de programmes et l'analyse de la complexité des algorithmes. - Rappel des notions suivantes: théorie naïve des ensembles, opérations sur les ensembles, cardinalité d'un ensemble, ensembles dénombrables, relations (fonctions, relations d'ordre, relations d'équivalence et partitions) - Algèbre relationnelle et applications aux bases de données - Introduction à la logique propositionnelle et au calcul des prédicats - Preuves par induction - Écriture de boucles simples - Notions élémentaires sur la complexité temporelle et spatiale des algorithmes - Notation asymptotique - Algorithmes de fouille et de tri - Analyse de la complexité d'algorithmes récursifs - Équations de récurrence - Graphes orientés, graphes non orientés, arbres, arborescences Objectif du cours ================= L'objectif principal du cours est de connaître les notions mathématiques de base utiles pour la conception d'algorithmes et le développement de programmes. En particulier, les étudiant.e.s devraient être en mesure d'utiliser ces notions dans les activités de programmation suivantes: - la définition de structures, - la définition de fonctions, d'opérations et de relations, - les techniques de représentation de structures, - le développement d'algorithmes, - les preuves d'arrêt et d'exactitude, - l'analyse de complexité d'algorithmes. Contenu du cours ================ Semaine Chapitre ---------- ----------------------------------------------------------------------- 1 et 2 01\. Logique 3 02\. Ensembles 4 03\. Dénombrement et 4. Fonctions 5 04\. Fonctions (suite) et 05. Comportement asymptotique des fonctions 6 06\. Algorithmes et complexité 7 et 9 07\. Nombres entiers et division 10 08\. Induction et récursivité 11 et 12 09\. Relations 13 10\. Graphes Les semaines sont données à titre indicatif seulement : le temps passé sur chaque chapitre dépend beaucoup des besoins des groupes. Communication ============= La page du cours est disponible sur Moodle. Elle contient les informations essentielles à tous les groupes, les notes de cours et de nombreuses ressources. Chaque groupe-cours a également une page Moodle dédiée qui rassemble les informations et les documents spécifiques à chaque groupe. Les informations seront communiquées sur le **forum Mattermost** du cours. **Ce forum sera le support principal du cours.** Vous devez vous y inscrire en suivant le lien fourni en haut de la page Moodle du cours. Formule pédagogique et matériel requis ====================================== Les cours et les démonstrations auront lieu aux jours et heures indiqués dans la description générale du cours fournie ici : . Pour les séances données en ligne, les contenus seront enregistrés **dans la mesure du possible** et disponibles pour visionnement via la page Moodle du groupe correspondant. Vous aurez besoin d'un ordinateur personnel, d'une tablette ou au minimum d'un téléphone cellulaire pouvant accéder à internet pour suivre le cours et remettre vos travaux. **Tous les travaux sont à rédiger en utilisant [LaTeX](https://fr.wikipedia.org/wiki/LaTeX).** **Si des entretiens individuels de validation orale des travaux s'avèrent nécessaires, vous devrez obligatoirement activer votre caméra lors de ces entretiens**. Modalités d'évaluation ====================== Description sommaire Date de remise Pondération ---------------------- ------------------------------------ ------------- Devoir 1 Le 17 février 2023 avant midi 15% Examen 1 Le 26 février 2023 de 9h30 à 12h30 35% Devoir 2 Le 21 avril 2023 avant midi 15% Examen 2 Du 30 avril 2023 de 9h30 à 12h30 35% L'utilisation de livres et de documentation personnelle est permise pour réaliser les devoirs et les examens. Les examens et les devoirs sont **individuels**. **Aucun devoir n'est accepté après la date et l'heure de remise.** **Tous les travaux sont à rédiger en utilisant [LaTeX](https://fr.wikipedia.org/wiki/LaTeX).** **Si cela s'avère nécessaire, des entretiens de validation orale seront utilisés pour valider les résultats obtenus aux examens. Ils pourront porter sur toute la matière de la session.** La note de passage est D. Une condition suffisante pour avoir D est d'avoir une moyenne pondérée aux examens et aux devoirs supérieure ou égale à **60%** (ET d'avoir réussi les validations orales si elles s'avèrent nécessaires). La note finale (en lettre, A+, A, etc.) pour la session est attribuée en fonction de l'atteinte des objectifs spécifiques lors des quatre évaluations. La distribution des résultats dans les groupes est aussi utilisée. En cas de plagiat ou de fraude, la sanction peut aller de la note zéro pour le travail ou l'examen, jusqu'à l'exclusion de l'université. Les règlements concernant le plagiat seront strictement appliqués. Pour plus de renseignements, consultez le site suivant : Dates importantes ================= Le calendrier universitaire officiel est ici : Quelques dates importantes sont rappelées ci-après mais elles ne sont valides qu'à la date de publication du plan de cours. Date Description --------------------------------- --------------------------------------- Jusqu'au 20 janvier Annulation de cours sans facturation 21 janvier au 13 mars Abandon de cours sans mention d'échec 17 février 2023 avant midi Remise du devoir 1 26 février 2023 de 9h30 à 12h30 Examen 1 27 février au 5 mars Relâche 7 avril Congé 10 avril Congé 21 avril 2023 avant midi Remise du devoir 2 30 avril 2023 de 9h30 à 12h30 Examen 2 Médiagraphie ============ - Kenneth H. ROSEN, -- *Mathématiques discrètes* -- Édition révisée, Chenelière/McGraw-Hill, 2002.