Fork me on GitHub

IN310 – Mathématiques pour l’Informatique

Ceci est l’ancienne version du cours http://defeo.lu/in310/, utilisée jusqu’en 2013-2014.

Info pratiques

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

TDs les mardis de 9h45 à 13h00, salle 2202.

Chargé des cours : Luca De Feo http://defeo.lu.

Chargée des TDs : Mélanie Boudard

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 (10/09/2013)
Représentation des entiers. Rappels sur l’exponentielle et le logarithme abordés en TD.
Cours 2 (24/09/2013)
Systèmes formels, Calcul des propositions.
Cours 3 (01/10/2013)
Théorie de la preuve.
Cours 4 (08/10/2012)
Calcul des prédicats.

Deuxième partie

Cours 5 (15/10/2013)
Ensembles, Fonctions.
Cours 6 (22/10/2013)
Relations, Ordres, Équivalence.
Cours 7 (05/11/2013)
Principe d’induction.
Cours 8 (12/11/2013)
Définitions récursives, Ordres bien fondés, Entiers de Peano.

Troisème partie

Cours 9 (19/11/2013)
Récursivité et programmation.
Cours 10 (26/11/2013)
Anagrammes, Combinaisons, Triangle de Pascal.
Cours 11 (03/12/2013)
Preuves du théorème binomial, Permutations.
Cours 12 (10/12/2013)
Argument diagonal de Cantor, Paradoxe de Russel, Problème de l’arrêt.

Liste des TDs

Première partie

TD 1 (17/09/2013)
Entiers, changements de bases.
TD 2 (24/09/2013)
Propriétés du calcul des propositions et preuves élémentaires.
TD 3 (01/10/2013)
Vérité et déduction.
TD 4 (8/10/2013)
Calcul des prédicats et preuves en arithmétique.
Corrections
Correction TD 1 à 4.

Deuxième partie

TD 5 (15/10/2013)
Ensembles et fonctions.
TD 6 (22/10/2013)
Relations et classes d’équivalence.
TD 7 (05/11/2013)
Preuves par induction.
TD 8 (12/11/2013)
Définitions récursives.
Corrections
Correction TD 5 à 8.

Troisième partie

TD 9 (19/11/2013)
Problèmes récursifs.
TD 10 (26/11/2013)
Combinatoire élémentaire des mots.
TD 11 (03/12/2013)
Calculs avec les permutations.

Voici quelques Exercices et quelques Exercices Corrigés pour vous entraîner.

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.

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.

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.