v2.5.0 (3618)

Cours scientifiques - IN101 : Algorithmique et programmation

Domaine > Sciences et technologies de l'information et de la communication.

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.

24 heures en présentiel (8 blocs ou créneaux)
réparties en:
  • Contrôle : 2
  • Travaux dirigés en salle info : 12
  • Cours magistral : 6

Soit 2 heures de travail global estimé pour l’étudiant.

effectifs minimal / maximal:

145/197

Diplô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 20

Littérale/grade européen

Pour 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 :

Contrôle sur machine.
Tous documents personnels autorisés sauf Internet (et toute forme de communication).
Durée : 2-3h.

Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)
  • le rattrapage est obligatoire si :
    Note initiale < 6
  • le rattrapage peut être demandé par l'étudiant si :
    6 ≤ note initiale < 10
L'UE est acquise si Note finale >= 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, Python

Méthodes pédagogiques

PDFs des CMs et TDs disponibles, ainsi que les corrigés en fin de séance.

Support pédagogique multimédia

Oui

Veuillez patienter