% INF1132 — Mathématiques pour l'informatique % UQAM — Département d'informatique % Plan de cours — Automne 2020 * Horaires, locaux et enseignants: Responsable(s) du cours ======================= Coordination ------------ Meurs, Marie-Jean PK-4935 Enseignement ------------- Abdenbi, Moussa PK-4115 Groupes: 020 Zaier, Zied PK-4115 Groupes: 021 Brlek, Srecko PK-4715 Groupes: 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 ================ Notions de base : Calcul propositionnel, calcul des prédicats et théorie naïve des ensembles. Nombres entiers et division. Définitions et preuves par induction. Stratégies de preuve. Relations : Définitions et représentations. Propriétés des relations et principaux types de relations. Fonctions : Définitions et représentations. Opérations sur les fonctions. Récursion. Graphes : Définitions et représentations. Parcours d'un graphe. Arbres et forêts. Introduction à l'analyse d'algorithmes : Notion générale d'algorithme. Preuves d'arrêt et d'exactitude. Complexité spatiale et temporelle d'un algorithme. Algorithmes récursifs et équations de récurrence. Communication ============= Une page générale du cours est disponible sur Moodle. Elle contient les informations essentielles à tous les groupes cours, 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 également communiquées sur le forum Mattermost du cours. Ce forum sera le support principal du cours. Vous devez vous y inscrire ici : 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 : . Les contenus seront enregistrés dans la mesure du possible et disponibles pour visionnement via la page Moodle de votre groupe-cours. Vous aurez besoin d'un ordinateur personnel ou d'une tablette ou au minimum d'un telephone cellulaire pouvant accéder à internet pour suivre le cours, réaliser les tests et remettre vos travaux. Vous devrez obligatoirement **activer votre caméra lors des évaluations orales**. Modalités d'évaluation ====================== Description sommaire Date de remise / passation sur Moodle Pondération ---------------------- --------------------------------------- ------------- Devoir 1 Le 08 octobre avant minuit 10% Test 1 Du 10 au 13 octobre inclus 20% Devoir 2 Le 12 novembre avant minuit 10% Test 2 Du 14 au 16 novembre inclus 20% Devoir 3 Le 10 décembre avant minuit 15% Test 3 Du 12 au 14 décembre inclus 25% L'utilisation de livres et de documentation personnelle est permise pour réaliser les devoirs et les tests. Les tests 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.** **Des évaluations orales seront utilisées pour valider les résultats obtenus aux tests.** 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 : Médiagraphie ============ - Kenneth H. ROSEN, -- *Mathématiques discrètes* -- Édition révisée, Chenelière/McGraw-Hill, 2002.