Durée
30h Th, 22h Pr, 45h Proj.
Nombre de crédits
| Bachelier en sciences informatiques | 5 crédits |
Enseignant
Langue(s) de l'unité d'enseignement
Langue française
Organisation et évaluation
Enseignement au deuxième quadrimestre
Horaire
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).
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é
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:
- MATH2019: Mathématiques pour l'Informatique (engagements pédagogiques).
- INFO0946: Introduction à la Programmation (eCampus).
- INFO0030: Projet de Programmation (eCampus).
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)
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)
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)