Mathématique: Outil pour l'Informaticien (In1Math)

Objectifs :

- Présenter les concepts de base et les structures mathématiques simples comme des outils précis, aptes à soutenir une réflexion informatique.

- Aborder un certain nombre d'algorithmes classiques, notamment sur les graphes.

Compétences :

connaissances scientifiques et rigueur
Compétence technique (précision, rigueur, fiabilité)
Capacité de compréhension face à un problème
Capacité d'élaboration d'une réponse à un problème
Expression écrite; rédaction d'un rapport
Capacité d'adaptation à de nouvelles situations
Travail en équipe
Maîtrise transversale de la discipline
Capacité d'abstraction

Prérequis :

- connaissances basiques en mathématique

- bonne faculté d'abstraire

- rigueur et précision

Contenu du cours :

(sous réserve)

1. Division dans les entiers - Nombres premiers - Algorithmes d'Eratosthene, d'Euclide et de Bezout

2. Logique des propositions et des prédicats - Calcul  booléen

3. Ensembles, suites et opérations sur les ensembles

4. Récurrence et induction. Invariants de boucle

5. Eléments d'analyse combinatoire et de calcul matriciel booléen

6. Implémentation des ensembles par tables de booléens et par utilisation des suites

7. Relations et graphes - Propriétés et opérations de clôtures

8. Techniques diverses d'implémentation des relations

9. Ensembles partiellement ordonnés, éléments extrémaux, treillis, algèbre de Boole

10. Relations d'équivalence.

Un ou deux sujets sont ensuite choisis parmi les suivants :

11. Fonctions, injections, surjections, bijections;  Permutations, cycles, transpositions, signatures.

12. Opérations binaires, semi-groupes, monoïdes, groupes; Structures algébriques quotients et produits;- Anneaux et algèbres de Boole.

13. Complément sur les graphes; arbres couvrants, algorithmes de Prim et de Kruskal;  problème du chemin le plus court, algorithmes de Dijkstra et de Floyd-Warshall.

14. Langages formels. Grammaires de Chomsky;  Langages réguliers et context-free;  Automates finis. Automates à comportement non déterminé; Automates et langages réguliers. Optimisation d'un automate.

15. Détection et correction d'erreurs de transmission; Codages linéaires. Codages de Hamming.

Méthode d'enseignement :

Cours magistraux (2h/semaine) présentés par des diaporamas PowerPoint. Ces diaporamas sont ensuite disponibles en libre service sur l'extranet.

Exercices pratiques (2h/semaine), dont une bonne partie sur machine (langage Java).

Au cours du second semestre, les étudiant ont à réaliser un dossier permettant de mettre en oeuvre les concepts abordés.

Lectures recommandées :

MARCHAND M., Outils mathématiques pour l'informaticien-  Bruxelles, De Boeck Université, 2005

VELU J., Méthodes mathématiques pour l'informatique - Paris, Dunod, 1987

KOLMAN B., BUSBY R.C., Discrete Mathematical structures for computer sciences,

New Jersey, Prentice Hall, 1984

BALAKRISHNAN V.K., Introductory Discrete Mathematics -  Prentice-Hall International, 1991

Méthode d'évaluation :

Examen partiel écrit en janvier.Dossier et examen oral (avec préparation écrite) en juin.