Algorithmique (In1Algo)

Objectifs :

Apprendre aux étudiants à résoudre un problème par voie informatique, en choisissant adéquatement la façon de représenter les données inhérentes au problème ;

en construisant un algorithme, c'est-à-dire une séquence de manipulations de ces données en vue de la production d'un résultat; en agençant le tout selon les principes de la programmation structurée et/ou dans un contexte orienté objet.

Compétences :

Compétence technique (précision, rigueur, fiabilité)
Capacité de compréhension face à un problème
Capacité d'élaboration d'une réponse à un problème
Expression écrite; rédaction d'un rapport
Capacité d'adaptation à de nouvelles situations
Capacité d'abstraction

Prérequis :

/

Contenu du cours :

Notions de base : Programme, input, output, variable, ... les sous-programmes: procédures, fonctions, méthodes; Les alternatives; Les booléens et les expressions booléennes; Les répétitives; les caractères et les chaînes de caractères; Objets et classes; les tableaux à une dimension; algorithmes classiques sur les tables: Insertion, recherche séquentielle, recherche dichotomique; algorithmes de tri: tri par insertion, par extraction, bubble-sort, tri de Shell, quick-sort, tri-fusion; fichiers séquentiels; tableaux à plusieurs dimensions; la récursivité; les listes linéaires; listes en table et listes chaînées; deux cas particuliers : Piles, Files; les arbres binaires; les comportements asymptotiques des algorithmes.

Méthode d'enseignement :

Le cours théorique présente les outils nécessaires, tant du point de vue de la représentation des données que de celui des algorithmes eux-mêmes.

Cette présentation est illustrée de nombreux exemples, petits ou moyens.

Les exercices partent toujours de l'énoncé d'un problème, exprimé en français; les étudiants doivent le comprendre, puis choisir la représentation des données et enfin élaborer l'algorithme dans un langage de description des algorithmes (pseudo-code ou macro-code) et/ou dans un langage de programmation (Java).

Une ou plusieurs fois durant l'année, un projet plus important est soumis aux étudiants. Ceux-ci le réalisent par équipes de deux et remettent un dossier complet qui intervient dans l'évaluation de fin d'année.

Lectures recommandées :

/

Méthode d'évaluation :

L'examen de janvier et l'examen de juin sont écrits ou sur ordinateur. Un problème est soumis aux étudiants. Ils doivent en fournir une solution informatique présentée sous forme de pseudo-code ou dans le langage de programmation qui a illustré le cours. Des questions ou sous-questions complémentaires peuvent s'y ajouter. En outre, en juin, ils doivent pouvoir reproduire et adapter un des algorithmes-types vus au cours.