INF1130 - Mathématiques pour l'informatique
Vous êtes ici : Syllabus du cours
[ A09 ] [ H09 ] [ A08 ] [ H08 ] [ A07 ] [ H07 ] [ A06 ] [ H06 ] [ A05 ] [ H05 ] [ A04 ] [ A03 ] [ H03 ] [ A02 ]
Accueil
Syllabus du cours
Documents
Nouveautés
Corrections
Forum de discussion
Aide

Devoirs
Examens
Résultats
Vos commentaires

PLAN DE COURS - Automne 2009


MATHÉMATIQUES POUR INFORMATICIEN - INF1130


Groupe 10

Lundi, de 15h00 à 16h30, local : SH-R810 (cours)
Mercredi, de 9h00 à 10h30, local : SH-R810 (cours)
Mercredi, de 11h00 à 13h00, local : SH-R810 (exercices)

Professeur: Anne Bergeron
Local: PK-4320
Téléphone: (514) 987-3000, poste 8214
Télécopieur: (514) 987-8477
Courriel: bergeron.anne@uqam.ca


Groupe 40

Jeudi, de 18h00 à 21h00, local : SH-R810 (cours)
Vendredi, de 18h00 à 20h00, local : SH-R810 (exercices)

Professeur: Anne Bergeron


Coordonnateur du cours: Anne Bergeron


Examen(s) commun(s):

Intra: Dimanche 25 octobre 14:00 à 17:00
Final: Dimanche 20 décembre 14:00 à 17:00


DESCRIPTION (du cours selon l'annuaire)

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. Sémantique d'un petit langage de programmation. Écriture de boucles simples à partir d'invariants. Introduction à la vérification de programmes. Preuves de boucles à l'aide d'invariants. 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. Chemins dans un graphe, hauteur d'une arborescence et exemples d'applications à l'analyse d'algorithmes. Parcours de graphes.


CONTENU DU COURS

  • Notions de base : Calcul propositionnel, calcul des prédicats et théorie naïve des ensembles. 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.

OBJECTIFS

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.

ÉVALUATION

Description sommaire Pour le Pondération
Devoir #1 Vendredi 16 octobre avant 16h 15%
Examen de mi-session Dimanche 25 octobre 14:00 à 17:00 35%
Devoir #2 Vendredi 11 décembre avant 16h 15%
Examen final Dimanche 20 décembre 14:00 à 17:00 35%

L'énoncé des devoirs est distribué 3 semaines avant la date de remise du travail. Aucun devoir n'est accepté après la date et l'heure de remise (16h00), puisque des solutionnaires seront publiés à ce moment. L'utilisation de livres et de documentation personnelle est permise aux examens. Les calculatrices ainsi que les téléphones cellulaires sont strictement interdits durant les examens. Les examens et les devoirs sont individuels. 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é

Un étudiant absent à un examen se verra normalement attribuer la note zéro pour cet examen. Cependant, si l'étudiant était dans l'impossibilité de se présenter à l'examen pour un motif valable, certains arrangements pourront être pris avec son enseignant. Pour ce faire, l'étudiant devra présenter à son enseignant l'un des formulaires prévus à cet effet accompagné des pièces justificatives appropriées (par ex., attestation d'un médecin que l'étudiant était dans l'impossibilité de se présenter à l'examen pour des raisons de santé, lettre de la Cour en cas de participation à un jury).

Une absence pour cause de conflit d'horaires d'examen n'est pas considérée comme un motif valable d'absence, à moins d'entente préalable avec la direction du programme et l'enseignant durant la période d'annulation des inscriptions avec remboursement : tel qu'indiqué dans le guide d'inscription des étudiants, il est de la responsabilité d'un étudiant de ne s'inscrire qu'à des cours qui ne sont pas en conflit d'horaire.

Pour plus de détails sur la politique d'absence aux examens du Département d'informatique et pour obtenir les formulaires appropriés, consultez le site web suivant : http://www.info.uqam.ca/enseignement/politiques/absence-examen


CALENDRIER

Voici une liste d'exercices pour les séances d'exercices. Le contenu de chacune des séances peut varier selon le groupe dans lequel vous êtes inscrits.

Séance Section Numéros
1 1.1 6, 7, 15, 17, 22
1.2 7, 9, 12, 13
1.3 5, 6, 13, 22, 23, 26, 27
2 1.4 4, 5, 6, 7, 9, 11, 15, 16, 20, 24
1.5 1, 3, 5, 6, 18, 19, 24, 30
3 1.6 2, 5, 6, 8, 9, 14, 15, 16, 19
1.7 5, 7, 9, 11, 12, 13, 15, 16, 19
4 2.3 9, 17, 27, 28
3.1 1, 3, 8, 9, 10, 11, 12, 13, 15, 16, 17
5 1.8 1, 2, 13, 15, 19, 20, 21
6 2.1 1, 3, 4, 7, 9, 20
2.2 1, 3, 4, 7, 8, 9
7 2.3 8, 10, 11, 13, 14, 24
3.2 7, 8, 12, 13, 14, 15, 19, 34
8 3.3 1, 5, 7, 20, 21, 23, 26, 27, 31, 36, 37, 38, 39, 40
3.4 2, 4, 6, 9, 10, 11, 14, 15, 16
9 6.1 2, 3, 4, 6, 15, 17, 19, 20, 21
6.3 1, 2, 4, 7, 8, 9, 10, 13, 14, 15, 16, 17
10 6.4 16, 17, 19, 20, 25, 27, 29
6.5 1, 2, 11, 12, 13, 14, 15, 19, 22, 25
11 7.1 2, 10
7.2 1, 2, 3, 4, 5, 7, 8, 9, 13, 14, 15, 16, 17
12 7.3 1, 3, 5, 7, 10, 11, 16, 17, 21
7.4 1, 3, 4, 5, 6, 10

RÉFÉRENCES

OBLIGATOIRES

  • Rosen, Kenneth H., Mathématiques discrètes, 2e édition, Chenelière/McGraw-Hill, 2001.
  • Walsh, T., Notes de cours INF1130: Mathématiques pour informaticien, UQAM, Automne 2001.
  • Site WEB : http://www.info2.uqam.ca/~inf1130

OPTIONNELLES

  • Arnold, A. et Guessarian, I., Mathématiques pour l'informatique, Masson, 1993, 349p.
  • Lipschutz, S., Mathématiques discrètes, Série Schaum, McGraw-Hill, Paris, 1990, 248 p.
  • Lipschutz, S., Mathématiques pour informaticien, Série Schaum, McGraw-Hill, Paris, 1983, 349 p.
  • Rosen, Kenneth H., Discrete Mathematics and its Applications, 5e édition, McGraw-Hill, 1995.
  • Stanat, D.F., et McAllister, D.F., Discrete Mathematics in Computer Science, Prentice Hall, 1977, 401p.

Retour à l'accueil | Contacts | Université du Québec à Montréal
Dernières modifications Janvier 2009