L1SF
-
Math discrètes - 2015-16
12 semaines de cours le vendredi 8h-9h30 dans l'amphi Phys2 ; 1er
cours le 22 janvier
12 semaines de TD (1h30) ; début des TD lundi 25 janvier
Objectif du cours : analyser syntaxiquement les formules
et énoncés mathématiques, deviner les types d'objets apparaissant
dans les formules ou énoncés, expliciter très précisément les
définitions ou axiomes et les règles de calcul (règles de
réécriture) pour les premiers types d'objets : énoncés
(calculs=preuves), ensembles, applications entre ensembles, entiers
(constructions et raisonnements par récurrence), cardinalité des
ensembles, nombres (représentations et calculs algébriques),
permutations.
Présentation
du cours de 2013-15 (le programme et la présentation changent
cette année).
La page
du cours en 2014-15 (idem)
Progression du cours :
1.
(22jan) Discussion sur l'expressison "Mathématiques
discrètes", exemples d'objets, formules explicites,
variables libres ou liées
Sur le web : notice
wikipedia pour "Mathématiques discrètes" (en).
2. (29jan) symbole
ou mot désignant une constante par opposition à une
variable, dépend du contexte (ex. e=2.71.. en analyse ou
dans e∈E) ; tests pour décider si une variable est libre ou
liée ; type des constantes et variables, qq notations
classiques pour les types
3. (5fev) Rappel :
constantes, variables ; opérateurs, expressions formelles et
leur type, résumé en mots du langage courant d'une
expresion, définition d'une constante, assignation
d'une variable.
Calculs : suite de réécritures suivant des règles le plus
souvent implicites, ex. avec le développement décimal de
58/13 tel qu'enseigné en CM2-6ème
Sur le web : syntaxes admissibles pour le calcul sur WolframAlpha
: essayer int(sin(t),t,0,pi)
et integrate sin(2t)
for t from 0 to pi
4. (12fev) 1er thème
: Calcul propositionnel : description du langage,
connecteurs logiques, calcul des tables de vérité, déf. de
f(P,Q,...)≡g(P,Q,...), traductions en langage naturel de
P⇒Q, condition nécessaire, cond. suffisante, négation de
P⇒Q, cf "infraction à la loi") ; algèbre booléenne (B,+,×) :
description du langage, calculs algébriques, expression dans
B d'une formule f(P,Q,...) du calcul propositionnel,
application : simplification, tautologie
Un exemple
de calcul algébrique avec Sagemath, version
pdf
5. (26fev) Enoncés
avec quantificateur, table de vérité lorsque la variable ne
peut prendre qu'un nombre fini de valeurs, ex avec
∀x:{0,…,10}, n≤ n2-1, valeur de vérité par une
preuve sinon. Organisation d'une preuve (suite de
réécritures issues d'application des règles de
raisonnement), règle de réécriture (≡), règles associées à
∀, ∃ dans une hypothèse ou une conclusion.
6. (4mar) Retour sur
les preuves, exmples d'axiomes spécifiques à un type. Document
de cours.
Le type ensemble : langage (∈, =, ⊂, ∅, noms de variables),
expression {x, P(x)}, axiome pour l'égalité, existence et
unicité de ∅, paradoxe de Russel, axiomatique de
Zermelo-Fraenkel, couples, produit cartésien d'ens.,
relations.
Sur le web : Preuves : le
style de Fitch pour la déduction naturelle ; type
ensemble : paradoxe
de Russel et axiomes
de Zermelo-Fraenkel sur Wikipedia,
7. (11mar) Type
couple d'objets, relation entre élts de E et élts de F,
graphe d'une relation, application, composée de deux
applications, bijection, appl. injective, surjective,
préservation par composition. Type entier N (0, S:N→N, not.
1=S(0), n+1=S(n)), règle de raisonnement par récurrence.
Début cardinaux.
Lecture : axiomes de Péano
8. (18mar)
Construction d'une application sur N par récurrence un+1=f(n,un),
définition de m+n, m×n, mn par récurrence sur n,
ptés de +,×. Déf. ≤ sur N, ensemble {1,...,n}, relation
"être en bijection" entre ensemble, {1,...,n}≅{1,...,m}
ssi n=m (preuve par récurrence sur min(m,n), déf. E est fini
de card. n si E≅{1,...,n}, ptés #(E∪F), si A⊂E alors #A≤#E, #FE (au
passage pour e∈E fixé Φ:FE→F, Φ(f)=f(e) alors #(FE)=Σy∈F
#(Φ-1(y)), déf. de Σy∈F)
9. (25mar) Partiel
1h. Au programme : tout jusqu'aux cardinaux non compris.
10. (1avr) cardinal
de la réunion d'une famille d'ens. disjoints, de E×F, de FE,
de Inj(E,F) (ens. des appl. injectives de E dans F), de
l'ens. des permutations de {1,...,k} (notation k!), de
l'ens. des parties à k éléments de {1,...,n} (notation :
coefficient binomial), formule du binôme.
11. (8avr) Types de
nombres : représentation (décimale, couple d'entiers, etc),
opérations algébriques, synthèse pour N (def S(n), principe
de réc., +, ×, ≤), Z, Q (a/b ou dvt décimal périodique,
lien), R, hypothèse du continu (la représentation décimale
ne dit pas tout)
12. (15avr)
Permutations de {1,...,n}: orbite d'un élt sous l'action
d'une permutation, décomposition en cycles, problème des
cadeaux d'anniversaires, problème de la répartition des
convives sur une table ronde.
Sur le web : le
premier probleme et le
second sur MathStackExchange
13. (22avr, 1h)
Taille de l'orbite de 1 sous l'action de σi où σ
est le cycle (1 2 ... n) : n/pgcd(n,i), exemple avec n=4,5,8
, lien entre le nombre de i<n tel que σi est
un cycle de longueur n et les élts inversibles pour la
multiplication de l'anneau Z/nZ des entiers modulo n. |
Documents du cours :
Feuilles de TD 1 (25 jan 16) : variables
libres, va liées, constantes, expressions, type, formalisation
QCM 1 réponses (8,10fev) explications
Feuille de TD 2 (22fev) : calcul propositionnel
QCM 2 réponses (29fev, 2,7mar) explications
Feuille de TD 3 (7mar) : preuves formelles,
type ensemble
Quelques corrigés d'exercices des feuilles
1,2,3 (20mar), corrigé de l'ex. 2 de
la feuille 3 (18avr)
Feuille de TD 4 (21mar), corrigé
succint des ex. 2-5 (26avr).
Partiel du 25 mars et un
corrigé (26avr)
Feuille de TD 5 (15avr), corrigé
des ex. 1 et 2 ; corrigé succint
des ex. 5 et 9 (27avr) ; ex 5: essayer dans WolframAlpha 1.3 with 6913 repeating *3.1 with
41 repeating.
Examen du 3 mai et un corrigé,
corrigé de l'ex.2.
Session 2 du 17 juin
Corrigé : règles utilisées dans l'ex. 5,
corrigé très succint
Lectures :
La page d'un cours de
logique propositionnelle et du premier ordre à Grenoble
(calcul propositionnel, preuves formelles)
La page
d'un cours de math discrète à Marseille-Luminy (ensembles,
dénombrement)
J-Y. Girard, La théorie de la démonstration, Leçons de mathématiques
d'aujourd'hui Vol 2, Cf cette
page.
Liens :
La page du cours
de Méthodologie en 2001-04.
Le cours de
2011-12 par A. Hirschowitz, les exercices
WIMS, un corrigé
de l'examen (sur feuille) de juin 2013
Un
cours classique de maths discrètes (en anglais), d'autres
recencés sur cette
page.
page de la Licence
1ère année - parcours Mathématiques, page du Département
de
mathématiques
|