1 - 2

Logique propositionnelle. Équivalences propositionnelles. Prédicats et quantificateurs. Règles d'inférence. Cohérence d’un ensemble de spécifications. Types de preuve.

1

6

3

Ensemble : opérations sur les ensembles. Fonctions.

1

1.5

3 - 4

Modélisation. Identification des variables, des contraintes et de la fonction-objectif dans un problème d'optimisation. Solution admissible, solution optimale.

2

3

4-5

Théorie des graphes : types de graphes, terminologie, représentation et utilisation. Matrice d’adjacence d’un graphe. Connectivité. Chemins eulériens et hamiltoniens d’un graphe, circuit et applications. Problème du plus court chemin (algorithme de Dijkstra).

3

4.5

6

Théorie des graphes (suite): tri topologique (algorithme de Kahn), chemin de poids maximal, chemin critique.

3

3

7

Examen intra portant sur les cours 1 à 6

4

3

8

Arbres: définitions de base, théorèmes sur les arbres, arbre couvrant de poids minimal (algorithme de Prim).

4

3

 9

Introduction à la complexité des algorithmes: mesurer un temps de calcul à l’aide d’une fonction, notation grand-O et grand-Θ, résolution de sommations, fonction de complexité d’un algorithme.

5

4.5

10

Algorithmes récursifs. Fonctions récursives et relations de récurrence. Algorithmes de type diviser pour régner.

6

3

11

Preuves par récurrence. Principe de récurrence forte. Preuve de validité d’un algorithme récursif.

7

3

12 -13

Notions de base du dénombrement. Permutations et combinaisons. Dénombrement par relation de récurrence.

8

4.5

Total

39