v2.11.0 (5549)

Cours scientifiques - CSC_3IN01_TA : Algorithmique et programmation

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

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.

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

2 heures de travail personnel 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, C

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