Programme des cours 2015-2016
INFO0947-1  
Compléments de programmation
Durée :
30h Th, 22h Pr, 45h Proj.
Nombre de crédits :
Bachelier en sciences informatiques7
Nom du professeur :
Benoît Donnet
Langue(s) du cours :
Langue française
Organisation et évaluation :
Enseignement au deuxième quadrimestre
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 du cours :
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. 
  • 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: Fichiers Séquentiels
  • 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) du cours :
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. 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:
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 interdits durant les séances de répétition. En outre, le cours propose divers 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.
Des formations additionnelles sont aussi proposées (rédaction de rapports, utilisation de LaTeX).
Mode d'enseignement (présentiel ; enseignement à distance) :
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.  A cette fin, les ordinateurs/tablettes/smartphones sont interdits durant le 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 :
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 (généralement trois). 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). Examens 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.
Durant l'examen oral, les étudiants peuvent être interrogé sur tout (ou partie) des projets donnés durant le quadrimestre ainsi que sur des problèmes inédits. 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
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 :
Le cours se donne au second quadrimestre.
Contacts :
Professeur: Benoit Donnet (benoit.donnet@ulg.ac.be) -- Bureau 1.15 (B28) Assistant: Simon Liénardy (simon.lienardy@ulg.ac.be) -- Bureau R.83a (B28)
Notes en ligne :
Site Web du cours
Le site web est important car il regroupe les informations de contact, les diverses notes de cours, et les énoncés des projets