Mathématiques pour l’informatique (Info 229)

Nouvelles

• Devoir Coq à rendre le mardi 29 avril
• Devoir récurrence à rendre le mercredi 16 avril
  • Correction devoirs récurrence + Exo 4-TD6
• Exercice 4 feuille TD 6 à rendre le mercredi 26 mars
• Premier cours le mercredi 22 janvier 2014 de 8h30 à 10h15
• Premier TD le mercredi 29 janvier 2014 de 10h30 à 12h30
• Expérience d’utilisation de Wims pour des exercices d’application du cours accessible à partir de votre espace de travail numérique : Cours_Info229.

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 (11 séances 1h45+soutien 1h) + 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)

Planning

• Cours salle 112 : mercredi 8h30-10h15
• TD: mercredi 10h30-12h30
  • Groupe 1, salle 109, M. Rabie
  • Groupe 2, salle 112, C. Paulin

• Début semaine du 20 janvier 2014 (pas de TD)
• Vacances d’hiver du 24 au 28 février 2014
• Partiel (2h) : mercredi 12 mars 2014 9h30-11h30 bat 336 Partiel 2010-11 + corrigé, Partiel 2011-12 + corrigé, Partiel 2012-13 + corrigé, Partiel 2013-14 + corrigé
• Vacances de printemps : du 21 au 25 avril 2014
• Examen session 1 : du 15 au 22 mai 2014 (feuille manuscripte recto-verso autorisée) Examen 2010-11 session 1 + corrigé, Examen 2011-12 session 1 + corrigé, Examen 2012-13 session 1 + corrigé
• Soutien : semaine du 2 juin
• Examen session 2 : du 18 au 24 juin 2014 Examen 2010-11 session 2, Examen 2011-12 session 2, Examen 2012-13 session 2

Travaux Pratiques

• Preuves sur ordinateur avec un assistant à la démonstration : Coq
• Jeudi matin : 30/01 - 13/02 - 27/03 - 03/04 + TP noté
  • Groupe 1, jeudi 10h45-12h45, salle 213, Asma Tafat
  • Groupe 2, jeudi 8h30-10h30, salle 213, Asma Tafat
• Documents
  • Guide d’utilisation de Coq
  • sujet TP 1 squelette TP 1
  • sujet TP 2 squelette TP 2
  • sujet TP 3 squelette TP 3
  • sujet TP 4 squelette TP 4
• Devoir noté à rendre avant le mardi 29 avril Enoncé
• TP noté le mercredi 30 avril 10h30-12h30 salle 209 (groupe TP1) et 213 (groupe TP2)
  guide Coq et TP autorisés.
  • Sujet TP 2011, Sujet TP 2012, Enoncé TP 2013

3  Plan

1. Table des matières
2. Introduction
3. Quelques éléments de logique
   • TD 1
   • Règles logique
4. Théorie naive des ensembles
   • TD 2 (ensembles)
   • TD 3 (fonctions, ensembles finis) + feuille WIMS CC2 à compléter pour le 19 février
   • TD 4 (cardinal, ensemble dénombrable, récurrence)
5. Système d’inférence, induction, récursion
   • TD 5 (récurrence, définition par clôture)
   • TD 6 (définitions récursives, mots) dont exercice 4 à rendre pour le mercredi 26 mars
6. Le paysage syntaxique
   • TD 7 (mots, arbres, termes)
7. Équivalence et Ordres
   • TD 8 (équivalence, ordres)
8. Algèbre de Boole
   • TD 9 (ordres bien fondés, algèbre de Boole)
9. 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