2023-2024 / INFO0947-1

Compléments de programmation

Durée

30h Th, 22h Pr, 45h Proj.

Nombre de crédits

 Bachelier en sciences informatiques5 crédits 

Enseignant

Benoît Donnet

Langue(s) de l'unité d'enseignement

Langue française

Organisation et évaluation

Enseignement au deuxième quadrimestre

Horaire

Horaire en ligne

Unités d'enseignement prérequises et corequises

Les unités prérequises ou corequises sont présentées au sein de chaque programme

Contenus de l'unité d'enseignement

L'objectif de ce cours est d'augmenter les connaissances et compétences des étudiants en programmation.

En particulier, le cours peut être décomposé en deux grandes parties:

  • Algorithmique. Dans cette partie, la construction rigoureuse de programmes est mise en avant: raisonnement inductif, formalisation d'un problème, construction entièrement guidée par l'invariant (approche constructive, triplet de Hoare). Cette construction rigoureuse est appliquée à la manipulation de structures de données de base, comme les tableaux et les fichiers. La récursivité et son élimination sont aussi abordées.  La complexité des algorithmes mis en place (itératifs ou récursifs) est analysée. Une introduction à la complexité théorique est aussi proposée.
  • Structures de Données. Dans cette partie, l'approche par type abstrait de données (TAD) est mise en avant. La spécification abstraite d'une structure de données et son implémentation (statique et/ou dynamique) sont discutés. Des structures de données linéaires, présentées sous la forme de TAD, sont proposées (liste, pile, file).
Le cours s'appuie sur le langage C.

La structure du cours est la suivante:

  • Introduction
  • Chapitre 1: Raisonnement Mathématique
  • Chapitre 2: Construction de Programme
  • Chapitre 3: Introduction à la Complexité
  • Chapitre 4: Récursivité
  • Chapitre 5: Types Abstraits de Données
  • Chapitre 6: Listes
  • Chapitre 7: Piles
  • Chapitre 8: Files
  • Chapitre 9: Elimination de la Récursivité
Les chapitres 1 à 4 et 9 concernent la partie relative à l'algorithmique.  Les chapitre 5 à 8 se rapportent à la partie sur les structures de données.

Acquis d'apprentissage (objectifs d'apprentissage) de l'unité d'enseignement

L'objectif de ce cours est d'augmenter les connaissances et aptitudes des étudiants en matière d'algorithmique et de programmation impérative.

La construction d'un programme et sa complexité seront mises en avant et l'approche constructive, via le triplet de Hoare, sera la base du cours.

Le langage de programmation utilisé est le C.

A la fin du cours, l'étudiant sera capable de formaliser (sous la forme d'assertions) un problème, d'en tirer des spécifications et un invariant formel sur lesquels il s'appuiera pour construire son programme. Il sera aussi à même d'utiliser une structure de données avancée et de définir entièrement (signature, sémantique et implémentation) un type de données abstrait.  L'étudiant sera aussi capable d'analyser sa solution en terme de complexité théorique.

En outre, l'étudiant aura appris à rédiger des rapports (pour les différents projets) à l'aide de l'outil LaTeX.

Savoirs et compétences prérequis

Les co-requis sont les suivants:

  • INFO0030: Projet de Programmation (eCampus).
Le cours suppose aussi une bonne connaissance du français (oral et écrit)

Activités d'apprentissage prévues et méthodes d'enseignement

En plus du cours théorique, des séances d'exercices (i.e., séance de répétitions) sur papier sont organisées de manière hebdomadaire. Chaque séance d'exercices dure 2h.  Les séances d'exercices sont obligatoires.  Chaque étudiant doit obligatoirement préparer un certain nombre d'exercices avant chaque séance de répétition.  Les ordinateurs/tablettes/smartphones sont à éviter durant les séances de répétition.

En outre, le cours propose deux projets, durant le quadrimestre, afin d'illustrer les concepts vus au cours. Chaque projet nécessite l'écriture d'un programme (en C) et la rédaction d'un rapport. Ces projets, à réaliser en binôme, sont obligatoires.

Enfin, une ou plusieurs séances "Collaborative Design & Build" (CDB) seront organisées durant le quadrimestre.

Des formations additionnelles sont aussi proposées (rédaction de rapports, utilisation de LaTeX).

Mode d'enseignement (présentiel, à distance, hybride)

Cours donné exclusivement en présentiel


Explications complémentaires:

Le cours théorique se donne au 2ème quadrimestre, en présentiel.

Le cours théorique se construit autour d'exemples et de petits exercices. L'auditoire est amené à participer activement au cours

Les étudiants sont aussi amenés à prendre des notes complémentaires et à participer activement au cours.  

Lectures recommandées ou obligatoires et notes de cours

Les notes du cours sont composées essentiellement de transparents (slides). Une version imprimée des slides (2/page) est disponible, dès le début du quadrimestre, à la Centrale des Cours. Une version électronique (PDF) des slides est aussi disponible sur la page Web du cours. Les étudiants sont supposés disposer au plus vite d'une version des slides.

Les énoncés des exercices sont disponibles, en version électronique, (PDF) sur la page Web du cours.  Une version imprimée sera proposée, dès le début du quadrimestre, par la Centrale des Cours.

Aucun livre n'est obligatoire dans ce cours. Cependant, l'étudiant désireux de disposer d'un support écrit additionnel peut se référer aux ouvrages suivants (ils ont servi pour l'élaboration du cours):

  • Jacques Courtin, Irène Kowarski. "Initiation à l'Algorithmique et aux Structures de Données. Volume 1". Editions Dunod. 1998 (2ème édition).
  • Jacques Courtin, Irène Kowarski. "Initiation à l'Algorithmique et aux Structures de Données. Volume 2". Editions Dunod. 1997 (2ème édition).
  • Michel Divay. "Algorithmique et Structures de Données Génériques". 2004 (2ème édition)
  • Jacques Julliand. "Cours et Exercices Corrigés d'Algorithmique. Vérifier, tester et Concevoir des Programmes en les Modélisant". Ed. Vuibert. 2010 (1ère édition)
  • Jean-Louis. Imbert. "Algorihmes Fondamentaux et Langage C". Ed. Ellipses. 2008 (1ère édition)
Enfin, pour réaliser au mieux les divers projets, les étudiants peuvent s'inspirer des documents "Critères de Langage" et "Critères de Style" fournis dans le cadre du cours INFO0030

Modalités d'évaluation et critères

Examen(s) en session

Toutes sessions confondues

- En présentiel

évaluation orale


Explications complémentaires:

Les étudiants sont évalués de deux façons: une série de  projets et l'examen.

Projets
Le cours sera composé de plusieurs projets. Les projets sont à réaliser en binôme. Les binômes sont constitués dès le début du quadrimestre. Il est interdit de changer de binôme durant le quadrimestre.

Les projets comptent pour 40% de la note finale.

La réalisation des projets est obligatoire. Tout étudiant n'ayant pas rendu tous les projets se verra interdire l'accès à l'examen de juin. Dans ce cas, l'étudiant sera directement reporté en seconde session (avec une note d'absence).

Examen
L'examen est oral et, bien entendu, obligatoire. Il aura lieu en juin. Il se fait à cours fermé et comporte deux phases, une phase durant laquelle l'étudiant est interrogé par le Professeur, une autre durant laquelle il doit coder une petite fonction/procédure devant l'Assistant (cette fonction/procédure est en relation avec les divers projets réalisés durant le quadrimestre).  La note de l'examen intervient pour 60% dans la note finale.

L'objectif principal de l'examen oral est de vérifier la capacité d'un étudiant à réfléchir par lui-même et sa capacité à adopter une démarche méthodologique stricte face à un problème.


Seconde Session
En cas d'échec en juin, il y a deux cas de figures qui s'offrent à l'étudiant:

  • l'étudiant a réussi les projets (note >= 10/20 pour chaque projet). L'étudiant devra seulement représenter l'examen oral en août.
  • l'étudiant n'a pas réussi tous les projets (au moins un projet avec une note < 10/20). L'étudiant devra refaire, seul, tous les projets en échec durant l'été. Il devra, en outre, repasser l'examen oral. A noter qu'aucun support ne sera offert, à l'étudiant, durant l'été pour ses projets.  La soumission des projets en seconde session est obligatoire pour pouvoir accéder à l'examen oral (une note d'absence sera alors assignée à l'étudiant).  L'étudiant peut repartir de son projet soumis durant le quadrimestre et l'améliorer (attention, si aucune amélioration substantielle n'est constatée, le projet se verra affecter la note de 0/20, quelque soit la note obtenue en première session)
Dans les deux cas, la clé de répartition des points entre l'examen et les projets est la même qu'en première session.

Stage(s)

Remarques organisationnelles et modifications principales apportées au cours

Le cours se donne au second quadrimestre.

Contacts

Professeur: Benoit Donnet (email -- Bureau 1.87b/B28)

Assistant: Géraldine Brieven (email -- Bureau 1.73b/B28)

Association d'un ou plusieurs MOOCs