% INF1132 — Mathématiques pour l'informatique % UQAM — Département d'informatique % Plan de cours — Été 2020 * Horaires, locaux et enseignants: Responsable(s) du cours ======================= Coordination ------------ Meurs, Marie-Jean PK-4935 poste 6139 Enseignement ------------- Meurs, Marie-Jean 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 étudiants 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. Modalités d'évaluation ====================== Description sommaire Date de remise / passation sur Moodle Pondération ---------------------- --------------------------------------- ------------- Devoir 1 Jeudi 04 juin avant minuit 10% Test 1 Du 06 au 09 juin inclus 20% Devoir 2 Jeudi 02 juillet avant minuit 10% Test 2 Du 04 au 07 juillet inclus 20% Devoir 3 Mercredi 12 août avant minuit 15% Test 3 Du 01 au 04 août inclus 25% Aucun devoir n'est accepté après la date et l'heure de remise. 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. Les tests pourront être accompagnés d'évaluations orales. 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.