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.
Le matériel de cours est disponible à https://perso.ensta-paris.fr/~pessaux/teaching/in101/
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
- Travaux dirigés en salle info : 12
- Cours magistral : 6
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, PythonMéthodes pédagogiques
PDFs des CMs et TDs disponibles, ainsi que les corrigés en fin de séance.Support pédagogique multimédia
