Niveau I

Le premier niveau de ce chapitre vise à développer les compétences suivantes :

• Comprendre un algorithme et expliquer ce qu’il fait ;
• Concevoir une solution algorithmique à un problème, savoir le mettre en oeuvre (programmer) et savoir l’analyser ;
• Modifier un algorithme existant pour obtenir un résultat différent ;
• S'interroger sur l'efficacité d'un algorithme.

1. Introduction à l’algorithmique (8h)

• Qu'est-ce que l'algorithmique ?
• Quelle est l’utilité ? A quoi sert algorithmique ?
• Instructions de base d'un algorithme et pseudo-langage.
• Données et types de données, notion de types abstraits.
• Règles de réalisation d’un "bon" algorithme.
• Exemples reposant sur des algorithmes de tri dans une liste et de recherche dichotomique.

2. Algorithmes avancés (8h)

• Parcours d'arbres en profondeur et en largeur, arbres de recherche.
• Recherche d'un chemin dans un graphe.
• Recherche des composantes fortement connexes.
• Recherche d'un plus court chemin.
• Introduction aux problèmes et méthodes d'ordonnancement.

Niveau II

1. Calculabilité (4h)

L’informatique est une science du calcul binaire. Les fondements de cette science mais aussi les limites sont présentés dans cette unité. Les compétences développées dans cette unité vise:

• Déterminer la performance qualitative et quantitative d'un programme ;
• Reconnaître les problèmes complexes et non solvables.

La complexité en temps et en espace:

• Modèles de calcul, exemples, complexité en moyenne et dans le pire cas, exemples.
• Complexité des algorithmes de tri.
• Les classes de complexité P et EXPTIME.
• Exercices : complexité d’algorithmes classiques, illustration chronométrée.
• La classe NP, la NP-complétude.
• Exercices : modélisation propositionnelle et résolution à l’aide d’un solveur SAT.

2.  Dessiner (4h)

A développer

3.  Parallélisme et concurrence (4h)

Les supports informatiques modernes sont composés de plusieurs coeurs qui permettent la réalisation simultanée de plusieurs opérations. Aussi, pour tirer le meilleur profit de cet avancé technologique il est important de comprendre et de maîtriser les concepts associés à l’écriture d’algorithmes exprimant des traitements en parallèle.

• Comprendre ce qu’est un processus (thread)
• Mise en évidence des avantages des traitements parallèles
• Les problèmes de conflits et de dé-cohérence liés aux accès concurrents
• Les stratégies de synchronisation