1

Complexité des algorithmes. Notation grand-O. Résolution de sommations.

4

3

2

Algorithmes récursifs. Relations de récurrence. Algorithmes de type diviser pour régner.

5

3

3 - 4

Logique. Équivalences propositionnelles. Prédicats et quantificateurs. Règles d'inférence. Méthodes de preuve.

1

6

5

Ensemble : opérations sur les ensembles.
Fonctions : injections, surjections, bijections.  

1

3

6

Dénombrement. Principes de base, permutations, arrangements et combinaisons. Dénombrement par relation de récurrence.

7

3

7

Examen intra portant sur les cours 1 à 6

3

8

Preuves par récurrence.

6

9 - 10

Arithmétique modulaire. Représentation des entiers dans une base quelconque. Entiers et algorithmes. Cryptographie RSA.

2

6

11

Représentation des entiers et manipulations bit à bit.

3

3

12 - 13

Théorie des graphes. Types de graphes, terminologie, représentation et utilisation. Chemins dans un graphe. Chemins eulériens et hamiltoniens. Problème du plus court chemin.

8

Total

39