IN3ST02

Algorithmique

Date mise à jour : 09/07/2008

Statut :  Obligatoire

ESIEE  3e année S   1er semestre

ESIEE  3e année T   1er semestre

Horaires :

Horaire Cours : 16 h

Horaire TD : 12 h

Horaire TP : 12 h

Crédits ECTS :

2.5

Langue(s) de l'unite enseignee :

FRANCAISE

Responsable(s) :

MORELLE Albin (morellea@esiee.fr)

Objectif(s) :

- Savoir spécifier le calcul que l'on attend d'un programme - Savoir écrire un programme efficace et prouver qu'il réalise le calcul attendu - Savoir évaluer la complexité d'un programme et savoir choisir entre différents programmes réalisant le même calcul sur la base de leur complexité et des données à traiter - Connaître des algorithmes efficaces de recherche et de tri - Savoir représenter un ensemble - Maîtriser la programmation des structures de données en C

Pré-requis :

Savoir concevoir des algorithmes itératifs simples ; savoir programmer en C

Themes Cours T.D T.P P Introduction et rappels mathématiques 2h00 Conception et évaluation d'un algorithme 4h00 6h00 - conception d'un programme basé sur les invariants - introduction à la preuve formelle de Hoare - temps de calcul, complexité algorithmique, classe de problème Problèmes de recherche : séquentiel, dichotomique, arrière 2h00 Représentation des ensembles et opérateurs ensemblistes 4h00 2h00 8h00 - tables de hachage ; arborescences (binaires, générales, de recherche) - rappel : techniques de programmation en C Problèmes de tris 4h00 4h00 4h00 - tris comparatifs : quicksort, heapsort, split-and-merge - tris linéaires : tri par dénombrement

Nature de l'épreuve Commentaires Durée Coeff Examen partiel 2 1.5 Examen final 3 2.5

Bibliographie :

Documents de références
[1]	A. Morelle, Introduction à l'algorithmique, ESIEE

[2]	Thomas H. Cormen, et al., Introduction à l'algorithmique, Dunod (2002)