Descriptif
Ce cours a pour objectif d'apprendre à concevoir un algorithme de manière systématique et scientifique. Il illustre la démarche d'analyse, de formalisation, de conception et d'implantation d'algorithmes répondant à des spécifications exprimées sous différentes formes.
La notion de test de programme est abordée informellement afin de sensibiliser à la nécessité de vérifier le bon fonctionnement d'un programme sur des cas choisis de manière réfléchie.
Une attention particulière est mise sur la structuration des algorithmes puis des programmes afin de garantir maintenabilité, réutilisabilité mais également une complexité maîtrisée.
Une introduction à la complexité est proposée afin de poser le cadre permettant de parler de l'efficacité d'un algorithme.
Une séance est consacrée aux paradigmes de programmations dynamique et gloutonne. Ces formes d'algorithmes sont souvent présentées comme méthodes générales de conception d'algorithmes répondant à des problèmes dont la complexité est généralement très élevée.
La dernière séance est une ouverture sur un aspect plus théorique de l'informatique et vise à donner des intuitions sur les méthodes formelles, en particulier la preuve d'algorithmes. On y présente la manière dont on peut prouver la correction partielle ou complète d'algorithmes récursifs ou itératifs. L'objectif n'est pas d'aller jusqu'à l'utilisation d'assistants de preuve mais de rester au niveau de preuves "papier/crayon" en tentant toutefois de maintenir une rigueur et un niveau de détails raisonnables.
Le matériel de cours est disponible sur le Moodle.
Objectifs pédagogiques
- Analyser une spécification de besoin quelle que soit sa formulation.
- Déterminer les domaines des entrées et des sorties.
- Effectuer une décomposition récursive de problèmes en sous-problèmes pour élaborer un algorithme répondant à la spécification du problème initial.
- Implanter les algorithmes conçus dans un langage de programmation (C).
- Savoir tester un programme de manière raisonnable.
- Savoir structurer un programme de manière maintenable.
- Être capable d'estimer la complexité d'un algorithme simple.
- Être capable de concevoir un algorithme en étant attentif à sa complexité.
- Connaître le principe de la programmation dynamique et l'appliquer à bon escient.
- Connaître le principe de la programmation gloutonne et l'appliquer à bon escient.
- Contrôle : 2
- Cours magistral : 6
- Travaux dirigés en salle info : 12
effectifs minimal / maximal:
145/197Diplôme(s) concerné(s)
Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
MO101, IN102.
Format des notes
Numérique sur 20Littérale/grade européenPour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
Vos modalités d'acquisition :
- le rattrapage est obligatoire si :
- Note initiale < 6
- le rattrapage peut être demandé par l'étudiant si :
- 6 ≤ note initiale < 10
- Crédits ECTS acquis : 2 ECTS
- Scientifique acquis : 2
Le coefficient de l'UE est : 1
La note obtenue rentre dans le calcul de votre GPA.
L'UE est évaluée par les étudiants.
Programme détaillé
Séance 1 :
- Notions d'architecture des ordinateurs
- Rapides rappels sur le langage C
- Notion d'algorithme
Séance 2 :
- Différentes formes de spécification
- Un premier exemple
- Importance des domaines d'entrée et de sortie
Séance 3 :
- Élaboration d'un algorithme par raffinements successifs
- Importance du test
Séance 4 :
- Notions de complexité
Séance 5 :
- Paradigme diviser pour régner
- Paradigme de programmation dynamique
- Paradigme d'algorithme glouton
Séance 6 :
- Introduction à la preuve d'algorithmes
Séance 7 : contrôle de connaissances (sur machine)
Mots clés
Algorithme, Programmation, CMéthodes pédagogiques
PDFs des CMs et TDs disponibles, ainsi que les corrigés en fin de séance.Support pédagogique multimédia
