IN310 – Mathématiques pour l’Informatique

Info pratiques

Cours les mercredis de 15h30 à 17h00 en Amphi J, Bâtiment Fermat. Se référer à l’emploi du temps CELCAT.

TDs:

les lundis de 13h50 à 17h00, salle 103, bâtiment Buffon (groupe 2)
les mardis de 13h50 à 17h00, salle G107, bâtiment Germain (groupe DLBI),
les vendredis de 9h40 à 12h50, salle G107, bâtiment Germain (groupe 1)
les vendredis de 9h40 à 12h50, salle 326-328, bâtiment Buffon (groupe 3)

Chargée des cours : Christina Boura
Chargés des TDs : Coline Gianfrotta, Maya Chartouny, M’foukh Dounia et Pierre Varjabedian.

Liste des cours

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

Cours 1 (13/09/2023): Représentation des entiers. Rappels sur l’exponentielle et le logarithme abordés en TD.

Cours 2 (13/09/2023): Principe d’induction
Cours 3 (20/09/2023): Ensembles
Cours 4 (27/09/2023): Fonctions
Cours 5 (04/10/2023): Relations, Ordres, Équivalence
Cours 6 (11/10/2023): Anneaux, Corps, Arithmétique modulaire
Cours 7 (25/10/2023): Algorithme d’Euclide étendu, Théorème de Bézout
Cours 8 (09/11/2023): Algorithme d’Euclide étendu, Théorème de Bézout
Cours 9 (15/11/2023): Introduction aux matrices, systèmes linéaires
Cours 10 (22/11/2023): Déterminant
Cours 11 (06/12/2023): Inversion, Formules Cramer
Cours 12 (13/12/2023): Deuxième contrôle continu

Liste des TDs

TD 1 (18-22/09/2023): Entiers, changements de bases
TD 2 (25-29/09/2023): Induction et coefficients binomiaux
TD 3 (02-06/10/2023): Ensembles et fonctions
TD 4 (09-13/10/2023): Relations et classes d’équivalence
TD 5 (16-20/10/2023): Relations et classes d’équivalence
TD 6 (23-27/10/2023): Contrôle continu
TD 7 (06-10/11/2023): Arithmétique modulaire
TD 8 (13-17/11/2023): Algorithme d’Euclide étendu
TD 9 (20-24/11/2023): Révision sur les matrices
TD 10 (27/11/2023 - 01/12/2023): Déterminant
TD 11 (04-08/12/2023): Inversion

Contrôles continus

Les deux contrôles continus ont la forme d’un devoir sur table d’une durée d’une heure et demie. La participation est obligatoire. La note de contrôle continu finale est donnée par la moyenne des deux notes.

Premier contrôle Semaine du 23 octobre.

Deuxième contrôle Le mercredi 13 décembre à 15h30.

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.