TC101A : Algorithmique

Présentation :

Le but de ce cours est de présenter une approche de l'informatique par des aspects qui demeurent stables vis-à-vis des mutations techniques et technologiques. En effet, contrairement aux systèmes qui subissent toujours varient selon l'époque et répondent aux exigences d'objectifs toujours en évolution, ce module présente les principes fondateurs de l'algorithmique. Ainsi, on parlera de problèmes et de leur résolution, indépendamment de la médiation effective des machines et des langages, hormis les conventions adoptées ici pour l'écriture des algorithmes.

L'image de l'informatique se réduit en général à une pratique organisée autour d'une machine et d'un humain en situation de résolution d'un problème. Or cette image, qui doit beaucoup à la banalisation de l'informatique, n'est que la partie médiatique d'une science à part entière qui articule des principes, des méthodes, des exigences et des valeurs de rigueur. Cette image occulte également plusieurs aspects d'une discipline dont la complexité grandissante se reflète dans presque tous les secteurs de l'activité humaine de nos jours. Il est impensable de concevoir un modèle d'ingénieur étranger à l'informatique. Même s'il ne sera pas forcément amené à programmer lui-même, un ingénieur aura toujours à composer avec les potentialités offertes par l'informatique. Il est ainsi fondamental de comprendre les enjeux et limites de l'algorithmique (et au delà des performances de systèmes et programmes s'exécutant sur des machines).

Ce sont précisément ces grandes lignes d'idées qui font l'ambition de ce cours. Il s'agira de présenter les principales méthodes de résolution de problèmes sous l'angle algorithmique, et de savoir appliquer les bonnes méthodes aux bons problèmes.

On s'intéressera également à l'étude de la complexité des algorithmes étudiés. Cette partie a pour objectif de déterminer a priori (indépendamment de l'exécution sur une machine donnée) quelles seront les performances (coût d'exécution en temps, mémoire, accès réseau, etc.) d'un algorithme. Enfin une analyse en situation (avec exécution sur machine cette fois) sera réalisée. Cette partie, évidemment pratique, sera l'occasion de discuter d'outils fondamentaux pour l'ingénieur (simulation, plan d'expérience, analyse de données, etc.).

Le cours portera également sur les éléments de conception complémentaire avec la démarche d'écriture des algorithmes dans la résolution d'un problème par l'outil informatique (éléments de basiques de génie logiciel, démarche d'analyse descendante, notion de modularité, etc.), en complément avec l'apprentissage du langage C et du langage Java se déroulant en parallèle.

Pré-requis :

Le cours s'appuiera sur certains éléments présentés en parallèle dans les modules suivants :
- TC131C, Maîtrise de l'environnement numérique de travail (système d'exploitation)
- TC131A, Langage C (TP d'algo en langage C, donc faits après ce module)

Bien que les outils vus en cours soient indépendant des langages de programmation, nous emploierons le langage C pour la formalisation des algorithmes. Le formalisme de base sera donc présenté dans ce module, avant d'être complété dans le module TC131A.

Liens :

Certains exemples s'appuieront sur des éléments présentés en parallèle :
- TC 101C, Analyse harmonique et distributions
- TC 111B, Théorie des signaux et filtrage
- TC 131A, Codage, logique et langage C
- TC 131D, Bases de la programmation objet
- TC 131B, Méthodes et outils d'analyse numérique

Les structures de données et algorithmes vus pourront être approfondis dans les modules suivants :
- INF 413, Algorithmique avancée
- INF 435, Graphes
- MTS 443, Technologies du multimédia

Volume horaire : 21h

Contenu détaillé :

Cours 1 : Algorithme, outil de résolution de problèmes
- Indépendance vis-à-vis des langages
- Structure d'un algorithme (boite noire/blanche), démarche de conception
- Structuration des données, variables simples/complexes
- Notion de séquentialité
- Structures algorithmiques et pseudo-langage
- Notion de trace d'un algorithme
- Introduction à la complexité algorithmique

Cours 2 : Problèmes complexes, structuration de programmes
- Algorithmes paramétrés (procédures et fonctions)
- Décomposition modulaire, communication inter-modules
- Notion de récursivité, conception vs. coût mémoire/exécution
- Démarches d'analyse descendante/ascendante
- Notions de test et validation
- Familles d'algorithmes classiquement étudiées

Cours 3 : Analyse de complexité
- Motivations
- Critères d'analyse
- Focus sur le nombre d'opérations élémentaires et sur la mémoire
- Principales notations, focus sur O()
- Principales relations de récurrence
- Théorème général
- Classe de complexité
- Exécution des algorithmes : entre le rêve et la réalité

Cours 4 : familles et stratégies algorithmiques
- Les grandes familles d'algorithmes
- Algorithmes de tri
- Stratégies et schémas algorithmiques
- Optimisation des algorithmes

BE1 (3h - travail en groupes) : Démarches d'analyse et de conception

TP1 (3h) : Algorithmique et aléatoire, sensibilisation à la notion de simulation pour la construction de jeux de données

TP2 (3h - noté par binôme, compte-rendu à fournir en fin de séance) : Programmation d'algorithmes de tri simples, évaluation de leur complexité (travail préparatoire demandé)

Les séances de TP se dérouleront dans l'environnement Linux, et les programmes écrits en langage C seront compilés en ligne de commande.

Année 2012/2013
Dernière mise à jour le 06-SEP-12
Validation par le responsable de programme le