IN310 – Mathématiques pour l’Informatique

Info pratiques

Cours les mercredis de 8h00 à 9h30, amphi G.

TDs:

Chargée des cours : Christina Boura
Chargés des TDs : Christina Boura et Cyril Hugounenq

Liste des cours

Il est recommandé de consulter la Bibliographie pour approfondir les contenus du cours et trouver plus d’exercices.

Première partie

Cours 1 (14/09/2016)
Représentation des entiers. Rappels sur l’exponentielle et le logarithme abordés en TD.
Cours 2 (21/09/2016)
Systèmes formels, Calcul des propositions.
Cours 3 (28/09/2016)
Syntaxe de calcul des prédicats.
Cours 4 (05/10/2016)
Sémantique du calcul des prédicats.

Deuxième partie

Cours 5 (12/10/2016)
Principe d’induction.
Cours 6 (19/10/2016)
Ensembles, Fonctions
Cours 7 (02/11/2016)
Relations, Ordres, Équivalence.
Cours 8 (09/11/2016)
Anneaux, Corps, Arithmétique modulaire.
Cours 9 (16/11/2016)
Algorithme d’Euclide étendu, Théorème de Bézout.

Troisème partie

Cours 10 (23/11/2016)
Introduction aux matrices.
Cours 11 (30/11/2016)
Déterminant, Pivot de Gauss.
Cours 12 (07/11/2016)
Formules de Cramer, Inversion.

Liste des TDs

Première partie

TD 1 (19-21/09/2016)
Entiers, changements de bases.
TD 2 (26-28/09/2016)
Propriétés du calcul des propositions et preuves élémentaires.
TD 3 (03-05/10/2016)
Calcul des prédicats et preuves en arithmétique.
TD 4 (10-12/10/2016)
Calcul des prédicats et preuves en arithmétique.

Deuxième partie

TD 5 (17-19/10/2016)
Induction et coefficients binomiaux.
TD 6 (31/10/2016 groupe 1 + BI - 2/11/2016 *groupe 2)
Ensembles et fonctions.
TD 7 (7-9/11/2016)
Relations et classes d’équivalence.
TD 8 (14-16/11/2016)
Arithmétique modulaire.
TD 9 (21-23/11/2016)
Algorithme d’Euclide étendu/Bézout.

Troisième partie

TD 10 (28-30/11/2016)
Révision sur les matrices.
TD 11 (05-07/12/2016)
Déterminant.
TD 12 (12-14/12/2015)
Inversion.

Contrôles continus

Les contrôles continus auront la forme d’un devoir sur table d’une durée d’une heure avant la séance de TD. La participation est obligatoire, une absence justifiée ou injustifiée vaut un zéro. La note de contrôle continu finale est donnée par la moyenne des deux meilleures notes.

Premier contrôle
15h15 lundi 19/10, salle D122 – 9h45 mercredi 21/10, salle G001. Sujet.
Deuxième contrôle
15h15 lundi 23/11, salle D122 – 9h45 mercredi 25/11, salle G001. Sujet.
Troisème contrôle
8h mercredi 12/12, salle D122 – 9h45 mercredi 14/12, salle G001.Sujet.

Sujets d’examen

Bibliographie

Voici quelques ouvrages de référence, pour la plupart disponibles à la bibliothèque universitaire. N’hésitez pas à ajouter vos propres références ou à ajouter des commentaires à celles qui sont déjà présentes.

Textes généraux

Mathématiques discrètes

A. Arnold, I. Guessarian. Mathématiques pour l’Informatique.
4e édition. Dunod, 2005. Chapitres 1-2 (ensembles, fonctions, relations), 3 (récursivité), 4-5 (logique) et 6 (combinatoire). Livre complet et plein d’exercices.
M. Marchand. Outils mathématiques pour l’informaticien.
2e édition. De Boeck Université, 2005. ISBN 2-8041-4963-3. Chapitres 1 (logique), 2 (ensembles), (récursivité), 3 (relations), 4 (fonctions) et 7 (structures algébriques). Livre facile d’accès. Avec exercices corrigés. Exemples en Java.
J. Vélu. Méthodes Mathématiques pour l’Informatique.
4e édition. Dunod, 2005. ISBN 2-10-049149-0. Chapitres 1-3 (ensembles), 4 (combinatoire), 5-6 (relations), 7 et 10-14 (logique), (récurrences). Livre classique, avec exercices. La récurrence arrive un peut tard et est assez technique.
L. Frécon. Eléments de mathématiques discrètes.
Presses polytechniques et universitaires romandes, 2002. ISBN 2-88074-479-2. Chapitres 0-5.
K. H. Rosen. Mathématiques discrètes (Discrete Mathematics and its applications).
Chenelière/McGraw-Hill, 2002. ISBN 2-89461-642-2. Excellent livre, mon préféré. Peu traduit en français et difficile à trouver. N’hésitez pas à l’acheter si vous arrivez à mettre les mains dessus, il vous sera utile aussi au deuxième semestre.

Algèbre linéaire

F. Liret, D. Martinais. Algèbre 1re année.
2e édition. Dunod, 2003. ISBN 2-10-005548-8. Côte BU : 512 LIR.

Logique

R. David, K. Nour, Karim, C. Raffalli. Introduction à la logique: théorie de la démonstration cours et exercices corrigés.
Dunod, 2004. ISBN 2-10-006796-6. Chapitres 1 et 2. Ouvrage plus poussé, pour les fanatiques de la Théorie de la preuve.

Excercices avec corrigés

R. Haggarty. Mathématiques discrètes appliquées à l’informatique (Discrete Mathematics for Computing).
Pearson Education France, 2005. ISBN 2-7440-7100-5. Chapitres 2, 3, 4, 5, 6 et 9.
J. Vélu, G. Avérous, I. Gil, F. Santi. Mathématiques pour l’Informatique.
Dunod 2008. ISBN 978-10-052052-7. Chapitres 1, 2, 5, 7 et 8.
B. Cintract, J-J Colin. Ensembles, Relations, Applications, Dénombrement.
CEPAD, 2009. ISBN 978-2-85428-881.0. Comme le titre l’indique, pas beaucoup d’exercices sur la récursion ici.

Pour approfondir

Fondements d’algorithmique

A. Aho et J. Ullman, Concepts fondamentaux de l’informatique (Fundations of Computer Science).
Dunod, 1993. ISBN 2-10-003127-9. Chapitres 2 (récursivité), 7 (ensembles, fonctions, relations), 12 et 14 (logique). Ouvrage classique qui fait la part belle à la réalisation sur ordinateur des concepts du cours, écrit par deux pontes de l’informatique. Les exemples de programmation sont en Pascal, mais ne vous laissez pas effrayer par ce langage en vérité très simple. Même en s’agissant d’un texte de niveau 2ème cycle, la lecture des chapitres indiqués est aisée et à votre portée: les avoir lus et compris et avoir fait les exercices est une garantie de valider le cours.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction à l’algorithmique (Introduction to Algorithms).
2e édition. Dunod, 1994. ISBN 2-10-003922-9. Chapitres 1-4 et Annexes A-B. Ouvrage classique. Ce texte est adapté à l’étudiant qui a tout compris à la récursivité et qui veut découvrir ce qui vient après.

Mathématiques discrètes

T. Brugère, A. Mollard. Mathématiques à l’usage des informaticiens.
Ellipses, 2003. ISBN 2-7298-1399-3. Chapitres 1 (ensembles), 2 (relations), 3 et 4 (logique), Annexes A (récursivité), B (logarithme), C (combinatoire) E (structures algébriques).
R. L. Graham, D. E. Knuth, O. Patashnik. Mathématiques Concrètes (Concrete Mathematics).
2e édition. Addison-Wesley 1994. Ouvrage classique, bible de l’informaticien théorique (et plus spécifiquement du combinatoriste). Pour les esprits les plus matheux parmi vous, à lire en accompagnement à The art of Computer Programming. Mais, même si vous n’avez pas l’esprit voué à la théorie, allez quand même lire le tout petit Chapitre 1 sur la récursivité.

Autres textes

D. E. Knuth. The Art of Computer Programming.
Volumes 1-5. Addison-Wesley, 1997-2011. ISBNs: 0-201-89683-4, 0-201-85392-2, 0-201-89684-2, 0-201-89685-0, 0-201-03804-8. La bible de l’informaticien, même si difficile d’accès. Sur 5 volumes (et encore en cours d’écriture), les volumes 1 et 4 sont les plus proches de ce cours.
D. R. Hofstadter. Gödel, Escher, Bach: les Brins d’une Guirlande Éternelle (Gödel, Escher, Bach: An Eternal Golden Braid).
Dunod, 1985. ISBN 978-2-10-052306-1. Ouvrage de divulgation. Si vous n’avez pas encore décidé de consacrer votre vie à l’informatique théorique, c’est parce que vous n’avez pas encore lu ce livre. Certes, le contenu informatique est un peu daté par endroit, mais l’exposition tellement simple et captivante de mathématiques parfois très compliquées garde toute sa fraîcheur.
Fork me on GitHub