MAT 1500


Mathématiques discrètes


Hiver 2013

Professeure:    Matilde Lalín

Échéancier:    th: mardi et vendredi 10h30 - 12h30 PV ROGER-GAUDRY G-815

tp: jeudi 13h30 - 15h30 PV ROGER-GAUDRY S-144 et G-715

Disponsibilité:   lundi 11h-12h, mardi 12h30-13h30, A. Aisenstadt 5145

Tel:   (514) 343-6689

couriel:    mlalin at dms . umontreal . ca

Auxiliaires d'enseignement: Aryan Bayani (dispo: jeudi 11h30 à 12h30. AA-5244)

              Nicolas Bouchard (dispo: mardi 15h30 à 16h30. AA-5255.)   

Manuel obligatoire:    Kenneth H. Rosen, Mathématiques discrètes, édition révisée, Chenelière Éducation (2002).


Information:



Devoir:

  • TP 10 (à discuter le 25 avril): §5.5: 4, 8, 22, 26, §A3: 4, 8 (c), (e), 12, 14.
  • TP 9 (à discuter le 18 avril): §5.2: 4(a), 4(e), 8, 20, §5.4: 6, 12, 14 §5.5: 3, 4, 22.
  • TP 8 (à discuter le 11 avril): §4.6: 12, 16, 26, 34, §5.1: 10, 14, 22. Consultation du intra 2.
  • TP 7,5 (à discuter pendant le cours du 2 avril): §4.3: 40, 52, 54.
  • TP 7 (à discuter le 28 mars): §4.1: 16, 18, 22, 26, 32, 34, 40, §4.2: 4, 6, 12, 14, §4.3: 18, 20, 22, 26, 28, 30.
  • TP 6 (à discuter le 21 mars): §3.2: 6, 10, 14, 20, 32, 38, §3.3: 4, 6, 11.
  • TP 5 (à discuter le 14 mars): §2.4: 12, 16, §2.5: 2, 4, 6, 10, 12, 22, 23, §3.1: 17.
  • TP 4 (à discuter le 28 février): §2.3: 16, 20 (lisez le 19 d'abord), 24, 28, 32, 34, §2.4: 2, 4. Consultation du intra 1.
  • TP 3,5 (à discuter pendant le cours du 15 février): §1.6: 8, 10, 22, 26.
  • TP 3 (à discuter le 14 février): §1.4: 5, 10, 12, 18, §1.5: 4, 10, 20, 26, 35.
  • TP 2 (à discuter le 7 février): §1.3: 6, 14, 20, 24, §3.1: 4, 9, 10, 12, 14, 22 (Un nombre réel est rationnel s'il peut être représenté comme le quotient de deux nombres entiers. Dans le cas contraire on dit que le nombre est irrationnel.)
  • TP 1 (à discuter le 31 janvier): §1.1: 2, 4, 6, 8, 14, 18, §1.2: 8, 10, 24.


Avis importants:

  • Les examens finaux sont corrigés, vous trouverez vos notes à StudiUM. La moyenne a été 26,03 sur 50. Si vous voulez voir votre examen, veuillez passer par mon bureau. Mes horaires sont irreguliers et je ne peux vous donner un horaire precis, mais si je suis la, vous pouvez toujours me demander de voir votre examen.
  • Disponibilités de pendant la semanine avril 29 - mai 2: lundi 12h-14h (Aryan, AA5244), mardi 15h30-17h30 (Nicolas, AA5255), mercredi 13h-15h (Matilde) Attention: je (Matilde) serai en voyage du 26 avril au 1 mai matin et j'aurai un acces limité au courriel.
  • Disponibilités de Matilde pendant la semanine avril 22-26: lundi 11h-12h, mardi 12h30-13h30, mercredi 11h-12h, vendredi 12h30-13h30. Aryan et Nicolas seront disponibles pendant leurs heures d'habitude.
  • Problèmes de révision pour le final:
    • § 1.5: 8, 19, 36.
    • § 1.6: 20, 35, 36, 38.
    • § 2.3: 21, 22, 23, 32, 36.
    • § 2.4: 2, 5, 15, 16.
    • § 2.5: 4, 8, 15, 19, 20.
    • § 3.1: 17, 26, 30, 34.
    • § 3.2: 26, 28, 32, 52.
    • § 4.1: 12, 17, 20, 38, 44, 48.
    • § 4.2: 13, 28, 32.
    • § 4.3: 21, 24, 25, 29, 39, 50.
    • § 4.6: 10, 28, 37, 40.
    • § 5.1: 18, 30, 31.
    • § 5.2: 11, 14, 24.
    • § 5.4: 8, 20.
    • § 5.5: 3, 10, 17.
    • § A3: 8, 13.
  • L'examen final inclura des sujets discutés dans les sections: § 1.5, 1.6, § 2.3, 2.4, 2.5, § 3.1, 3.2, 3.3, § 4.1, 4.2, 4.3, 4.6, § 5.1, 5.2, 5.4, 5.5, § A3. Aucune documentation ne sera permise à l'examen. Les calculatrices seront interdites.
  • Si vous avez besoin de voir ou de revoir votre examen venez me voir pendant mes dispoinibilités. J'ai déjà repondu a toutes les questions et demandes de révision par courriel.
  • Les examens sont corrigés, vous trouverez vos notes à StudiUM. La moyenne a été 14,42 sur 25. Vous aurez l'occasion de consulter vos examens pendant une partie du TP du 11 avril. Si vous avez une urgence de voir votre examen avant le 11 avril, je serai disponible a mon bureau le 10 avril de 10h à 12h. (Notez que pour des raisons d'ordre et de confidentialité je veux permettre seulement 5 étudiants à la fois dans mon bureau, alors, il est possible que vous deviez attendre selon votre ordre d'arrivée.) Voici le corrigé du intra 2
  • Disponibilités pendant la semaine du intra 2 (avril 2-4): mardi 12h30-13h30 (Matilde, AA5145) et 15h30-17h30 (Nicolas, AA5255), mercredi 10h-12h (Matilde, AA5145), 13h-14h (Aryan, AA5244) et 15h30-16h30 (Matilde, AA5145), jeudi 11h30-12h30 (Aryan, AA5244)
  • L'intra 2 portera sur les sections 2.3, 2.4, 2.5, 3.2, 3.3, 4.1, 4.2, 4.3. Aucune documentation ne sera permise à l'examen. Les calculatrices seront interdites.
  • Pour la semaine du 25 au 29 mars, je ne serai pas disponible à mon bureau lundi 25 mars et mardi 26 mars (le cours du 26 se déroulera comme d'habitude), mais je serai disponible mercredi 27 mars et jeudi 28 mars de 10h a 11h le deux jours. Je serai disponible aussi sur rendez-vous.
  • Si vous avez besoin de voir ou de revoir votre examen venez me voir pendant mes dispoinibilités.
  • Si vous avez demandé des corrections dans votre examen, elles ont déjà être faites. Si votre note a changé, vous avez reçu un courriel et votre note sur StudiUM a été changée. Si vous n'avez pas reçu de courriel, votre note n'a pas été changée. Si vous avez encore des questions, venez me voir pendant mes disponibilités.
  • Les examens sont corrigés, vous trouverez vos notes à StudiUM. La moyenne a été 16,55 sur 25. Vous aurez l'occasion de consulter vos examens pendant une partie du TP du 28 février. Voici le corrigé du intra 1
  • Disponibilités pendant la semaine du intra 1 (février 18-21): lundi 11h-12h (Matilde, AA5145) et 13h-14h (Aryan, AA5244), mardi 12h30-13h30 (Matilde, AA5145) et 15h30-17h30 (Nicolas, AA5255), mercredi 10h-12h (Matilde, AA5145), jeudi 11h30-12h30 (Aryan, AA5244)
  • L'intra 1 portera sur les sections 1.1, 1.2, 1.3, 1.4, 1.5, 1.6 et 3.1. Il faut savoir la définition de divisibilité (définition 1 de 2.3). Aucune documentation ne sera permise à l'examen. Les calculatrices seront interdites.
  • Examens des années anterieures (profs Benabdallah, Balbahri, et Hamel ont utilisé le même manuel que nous, cependant, ils n'ont pas couvert les sections dans le même ordre que nous, alors plusieurs problèmes dans ces intras appartient à notre intra 2).
  • Le manuel du cours est disponible à la librairie, G-307. Il est aussi disponible sous reserve à la bibliothèque Mathématiques et informatique.
  • Barème: Examen intra (2 x 25%), Examen final (50%)


Dates importantes:
  • Examen intra: le 21 février, 13h30 - 15h30 PV ROGER-GAUDRY E-310
  • Examen intra: le 4 avril, 13h30 - 15h30 PV ROGER-GAUDRY E-310
  • Examen final: le 2 mai, 13h30 - 16h30 PV ROGER-GAUDRY E-310


Thèmes:

  • le 26 avril: Révision § 4.1-A3 (dernier cours)
  • le 19 avril : § A3: fonctions génératrices (plus d'applications de dénombrements, le cas de séries infinies, applications aux récurrences). Évaluation de l'enseignement.
  • le 16 avril : § 5.5 dénombrement des fonctions surjectives, dérangements. § A3: fonctions génératrices (définition et application au problème de équations lineaires).
  • le 12 avril: § 5.4: exemple d'inclusion-exclusion avec 3 ensembles, le principe général, § 5.5: application du principe d'inclusion-exclusion, crible d'Ératosthène
  • le 9 avril: § 5.2: solution aux relations de récurrence linéaire homogènes à coefficients constants (pour degré 2, et pour degré k si l'équation caractéristique a des racines différentes), le cas des nombres de Fibonacci, § 5.4: principe d'inclusion-exclusion pour 2 et 3 ensembles.
  • le 5 avril: § 4.6: distribution d'objets discernables dans des boîtes, § 5.1: relations de récurrence pour résoudre des problèmes (exemples incluant la tour de Hanoi et les lapins de Fibonacci), § 5.2: définition de relation de récurrence linéaire homogène de degré k à coefficients constants et exemples.
  • le 2 avril: § 4.6: combinaisons avec remise, permutations d'objets indiscernables, Problèmes de TP 7,5.
  • le 26 mars: §4.3 plus de propriétés des coefficients binomiaux (identité de Pascal, Identité de Vandermonde, théorème du binôme, etc), §4.6 permutations avec remise, exemple 4 (billets) de combinaisons avec remise.
  • le 22 mars: §4.2 principe des nids de pigeon particuler et généralisé (finisant par exemple 7), §4.3 permutations et combinaisons, propriétés des coefficients binomiaux.
  • le 19 mars: §4.1 principe de la somme et du produit, inclusion-exclusion, diagrammes des arbres, §4.2 introduction au principe des nids de pigeon particulier.
  • le 15 mars: §3.2 ex 11, principe généralisé de l'induction, ex 13 et 14 (preuve du Théorème fondamental de l'arithmétique), §3.3 définitions récursives et nombres de Fibonacci. §4.1 introduction et ex 1.
  • le 12 mars: § 3.2 Le principe de l'induction avec beaucoup d'exemples (ex 2-9 de §3.2).
  • le 1 mars: § 2.5 preuve de l'existence et de l'unicité de l'inverse modulo m, théorème du reste chinois, nombres pseudo-premiers et petit théorème de Fermat.
  • le 26 février: § 2.4 exemples de l'algorithme d'Euclide, représentations des entiers, § 2.5 le pgcd comme combinaison linéaire, congruences linéaires (enoncé de l'existence et unicité de l'inverse modulo m).
  • le 22 février: § 2.3 La relation entre le pgcd et le ppcm, arithmétique modulaire, § 2.1 définition d'algorithme, § 2.4 l'algorithme d'Euclide
  • le 19 février: § 2.3 introduction aux nombres entiers et division, premiers, théorème fondamental de l'arithmetique, algorithme de division, pgcd, ppcm.
  • le 15 février: § 1.6 fonction strictement croissante/décroissante, composition, graphes, fonction plancher et plafond. Problèmes du TP 3,5.
  • le 12 février: § 1.5 union et intersection généralisées (continuation), § 1.6 fonctions, domaine, codomaine, image, preimage, portée, injection, surjection, bijection, fonction inverse,
  • le 8 février: § 1.4 ensemble universel et diagramme de Venn, puissance, produit cartésien § 1.5 union, intersection, ensembles disjoints, complément, propriétés des opérations,
  • le 5 février: § 3.1 démonstration (par absurde, cas par cas), démonstration avec quantificateurs (d'existence constructive et non constructive, contre-exemple). § 1.4 ensembles: éléments, ensemble vide, sous-ensemble, cardinalité.
  • le 1 février: § 1.3 la négation et les quantificateurs, § 3.1 les méthodes de preuve: règles d'inférence, contrevérités (d'affirmer la conclusion, d'ignorer l'hypothèse, raisonnement circulaire), démonstration (preuve directe, preuve indirecte). On a vu la définition 1 de § 2.3 pour suivre des exemples.
  • le 29 janvier: § 1.2 les équivalences logiques (continuation), § 1.3 la fonction propositionnelle, la quantification universelle, la quantification existentielle, les variables liées (l'ordre de quantificateurs), la négation et les quantificateurs.
  • le 25 janvier: § 1.1 l'implication, la réciproque, la contraposée, la biconditionelle, § 1.2 la tautologie, la contradiction, la contigence, et les équivalences logiques.
  • le 22 janvier: Bienvenus à la classe! Les mathématiques discrètes, de quoi s'agissent-elles? § 1.1 La logique des propositions (définition de proposition, négation, conjonction, disjonction, disjonction exclusive, implication).



Dernière mise à jour: le 21 janvier 2013 (ou plus tard)