Mathématiques pour l’informatique (Info 229)

Nouvelles

Semaine du 7 mai:

• mercredi 9 mai : cours/TD de 8h30 à 10h15

1  Objectifs

Apprendre à raisonner sur des structures utiles en informatique avec des outils adaptés :

• Objets syntaxiques (mots, listes, arbres, …)
• Equivalence, ordres
• Dénombrement
• …

2  Organisation

Evaluation

• Cours (1 séance 2h30 + 10 séances 1h45) + TD (10 séances de 2h00), TP (5 séances de 2h)
• Partiel (coeff 6) + devoirs (coeff 4) + Examen final (coeff 10)
  (seule une feuille A4 manuscripte recto-verso sera autorisée)

Devoirs

1. à rendre le 7/03 10h30 : devoir 1 (coeff 1) Correction

Planning

• Cours : mercredi 25 janvier 9h00-11h45 salle 228, puis mercredi 8h30-10h15 salle 112
• TD: mercredi 10h30-12h30
  • Groupe 1, salle 120, C. Paulin
  • Groupe 2, salle 111, D. Longuet

• Début semaine du 23 janvier 2012 (2h30 cours, pas de TD)
• Vacances d’hiver 27 février - 2 mars 2012
• Partiels : vendredi 16 mars après-midi Exercices de révision avec corrigé Partiel 2011 + corrigé Partiel 2012 + corrigé
• Vacances de printemps : 16 au 27 avril 2012
• Dernier cours-TD mercredi 9 mai (8h30-10h15)
• TP noté mercredi 9 mai matin (10h30-12h30)
• Examen session 1 : 30 mai 2012 9h-11h (feuille manuscripte recto-verso autorisée) Examen 2011 session 1 + corrigé
• Soutien : mercredi 13 juin 10h45-12h45 et jeudi 14 juin 14h-16h
• Examen session 2 (à confirmer) : 28 juin 2012 - 9h-11h Examen 2011 session 2

Travaux Pratiques

• Preuves sur ordinateur avec un assistant à la démonstration : Coq
• Jeudi matin : 02/02 - 16/02 - 29/03 - 12/04 + TP noté
  • Groupe 1, jeudi 10h45-12h45, salle 214, D. Cousineau
  • Groupe 2, jeudi 8h30-10h30, salle 214, D. Cousineau
• Documents
  • Guide d’utilisation de Coq
  • sujet TP 1 corrigé TP 1
  • sujet TP 2 corrigé TP 2
  • sujet TP 3 squelette solution TP 3 corrigé TP 3
  • sujet TP 4 squelette solution TP 4 corrigé TP 4
  • Devoir noté à rendre avant le vendredi 4 mai Enoncé Corrigé
  • TP noté le mercredi 9 mai de 10h30 à 12h30 salles 224 (TD 1) et 226 (TD 2) - guide Coq et corrigés TP autorisés.
    

3  Plan

Version préliminaire du cours (jan 2012)

1. Introduction
2. Quelques éléments de logique
   • TD 1
   • Règles de déduction naturelle
3. Théorie naive des ensembles
   • TD 2 (ensembles) TD 3 (fonctions) TD 4 (cardinal, ensemble dénombrable)
4. Système d’inférence, induction, récursion TD 5 (récurrence, définition par clôture) TD 6 (définitions récursives, mots)
5. Le paysage syntaxique TD 7 (mots) TD 8 (arbres, termes)
6. Équivalence et Ordres TD 9
7. Algèbre de Boole
8. Combinatoire

4  Programme officiel

• Ensembles: calcul ensembliste, cardinaux, ensembles dénombrables (argument de la diagonale de Cantor)
• Relations, Fonctions: relations, fonctions, fonctions partielles, opérations, compositions, relations d’équivalences, partitions, congruences
• Ordres: ordres et pré-ordres, applications monotones, ensembles totalement ordonnés, sous-ensembles, chaînes, majorants, minorants, ordres bien fondés, notion d’induction bien fondée, produits (lexicographique) de relations bien fondées, ensembles complets, treillis, points fixes de fonctions monotones
• Algèbre de Boole: définition algébrique, homomorphismes, anneaux de Boole, fonctions booléennes
• Algèbre combinatoire: permutations, arrangements, formule du binôme, suites récurrentes
• Eléments de probabilité discrète: espace de probabilité, probabilité conditionnelle, variable aléatoire, événements indépendants, chaînes de Markov

Références

[1]

André Arnold and Irène Guessarian. Mathématiques pour l’informatique. EdiScience. Dunod, 2005.

[2]

Jacques Vélu. Méthodes mathématiques pour l’informatique. Sciences Sup. Dunod, 2005.

Ce document a été traduit de L^AT_EX par H^EV^EA