Programmé en UV1 MAJ INF
Présentation :
Le but de ce cours est de présenter une approche de l'informatique par ce qui est, et de toute évidence restera, stable pour longtemps indépendamment des mutations techniques et technologiques.
En effet, contrairement aux systèmes qui subissent toujours la tension qu'exerce sur eux leur époque et en fait, répondent aux exigences d'objectifs toujours en évolution, ce cours présente des principes fondateurs de l'informatique et en particulier l'algorithmique.
Encore aujourd'hui, l'image stéréotypée de l'informatique se réduit injustement à 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. C'est aussi une image appauvrissante dans la mesure où elle occulte plusieurs aspects d'une discipline dont la complexité grandissante se reflète dans sa pénétration dans presque tous les secteurs de l'activité humaine de nos jours. Il est et sera impensable de concevoir un modèle d'ingénieur, d'aujourd'hui ou de demain, étranger à l'informatique. Mais alors, même s'il ne sera pas amené à programmer lui-même, un ingénieur a et aura toujours à composer avec les potentialités offertes par l'informatique.
Ces potentialités sont bien sûr le corrélât de ce qu'il est possible de réaliser à un moment donné d'évolution technique et technologique des machines. Mais, au fond, elles sont toutes inscrites dans cet état fondationnel de la science informatique dans la mesure où son fond commande l'ensemble, en précédant et situant tout autre aspect pratique. Il définit, plus avant, l'horizon et contraint l'évolution de ce qui est ou apparaît comme techniquement possible.
Ainsi, dans un premier temps on parlera de problèmes et de leur résolution sans se soucier de la médiation effective des machines et des langages. Dans un second temps nous étudierons le passage effectif des solutions algorithmiques apportées sur des machines. Cette seconde partie constituera une introduction à la programmation.
Objectifs (obsolète):
Ce sont précisément ces grandes lignes d'idées qui font l'ambition de ce cours. Un cours qui, en récusant volontairement l'opposition confortable mais réductrice entre théorie et pratique, cherche à placer son objet à une dimension pédagogique intermédiaire et résolument unificatrice. On s'intéressera particulièrement à l'étude de la complexité (i.e. pour simplifier, au coût d'exécution) des algorithmes étudiés.
Pré-requis :
Initiation à l'informatique et à la programmation (S1)
Liens :
Logique et complexité.
Théorie des graphes.
Recherche opérationnelle.
Bases de données.
Volume horaire :
21h
Contenu détaillé :
14 séances de 1h30 : 5 cours, 5 PC et 4 STP.
1) Introduction à l'algorithmique
1.1) Notions d'algorithmes
1.2) Familles de problèmes, familles d'algorithmes
1.3) Structures de contrôles, structures de données.
2) Algorithmes de tri simples et analyse de complexité
2.1) Tri bulle
2.2) Tri insertion
2.3) Tri sélection
3) Complexité algorithmique
3.1) Introduction et définition de la complexité
3.2) Analyse de la complexité des algorithmes de tri simples
4) Algorithmes de tris complexes
4.1) Tri rapide, tri fusion
4.2) Algorithmes de type diviser pour régner
4.3) Algorithmes de type probabiliste
4.4) Analyse de la complexité des algorithmes étudiés
5) Programmation dynamique et optimisation
6) Structures de données avancées
6.1) Listes, piles, files
6.2) Tables de haschage
6.3) Arbres (binaires, rouge-noir, etc.)
6.4) Graphes
6.5) Algorithmes de recherche d'information
7) Algorithmes de traitement de chaînes
7.1) Algorithme de recherche de mots
7.2) Algorithme de cryptage
7.3) Algorithme de compression
8) Algorithmes numériques
8.1) Représentation des nombres
8.2) Algorithmique du pivot de Gauss
Année 2006/2007
Dernière mise à jour le 12-SEP-06
Validation par le responsable de programme le
|
