Compléments d'Algorithmique (In2CplAlgo)

Objectifs :

Langage C

Apprentissage d'un langage de programmation structurée professionnel portable. Apprentissage d'un langage fortement répandu que nul informaticien ne peut ignorer

Structures de Données

Etudier les structures de données simples jusqu'à leur implémentation. Etudier le fonctionnement de structures de données plus compliquées. Apprendre à choisir la structure de données appropriée à un problème donné

Compétences :

connaissances scientifiques et rigueur
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
Capacité d'adaptation à de nouvelles situations
Capacité d'abstraction

Prérequis :

Langage C

La connaissance des base de l'algorithmique et des principes de programmation est indispensable pour aborder ce cours de langage C.

Structures de Données

Les bases de l'algorithmique et la connaissance des bases d'un langage de programmation tel que C ou Java sont nécessaires

Contenu du cours :

Langage C

Le cours aborde les divers éléments du langage C, les structures de bases, les fonctions, les structures complexes, les fichiers, les possibilités offertes par la librairie standard. Axé principalement sur le C ANSI (C89), il présente également les différences avec le C classique (Kernighan et Ritchie 1ère édition) et s'intéresse aux nouveautés les plus importantes introduite par le C 99.

Le cours est accompagné d'exercices pratiques.

Structures de Données

Le cours présente les structures de bases telles que pile, file, liste linéaire, arbre binaire, ABR en insistant sur le coté récursif de ces dernières structures. Il s'intéresse à la performance des algorithmes en terme de comportement asymptotique.

Le cours se poursuit par la présentation de diverses applications des arbres : files de priorités, code de Huffman ainsi qu'au problème du balancement des ABR (AVL, arbres bicolores).

Suit ensuite la présentation des structures basées sur des principes différents telles que les tables de hashing, les skip lists et les graphes. Sur ces derniers, il présente les différents problèmes classiques de parcours, arbre couvrant, distance la plus courte

Méthode d'enseignement :

Langage C

Le cours théorique présente les divers éléments du langage, insiste sur les erreurs fréquemment commises par les débutants et présente des programmes bien écrits. Il est accompagné par des séances d'exercices de programmation sur machines.

Structures de Données

Le cours présente les diverses structures de données vues, montre l'implémentation des structures de bases en C et en Java, illustre le fonctionnement des structures présentées par des démonstrations utilisant des applets Java. Il est l'occasion de présenter par le biais d'exemples quelques patterns de design.

Il est accompagné d'exercices pratiques de programmation mais aussi de réflexion, de compréhension du fonctionnement des structures vues et de choix de structures dans un contexte donné.

Lectures recommandées :

Langage C

Kernighan & Ritchie, The C Programming Language, second edition, Prentice Hall, 1988.

Harbison & Steele, C A Reference Manual (5th edition), Prentice Hall 2002.

Structures de Données

Goodrich & Tamassia, Data Structures and Algorithms in Java, 2nd ed. John Wiley & Sons, 2001.

M. Weiss, Data Structures & Problem Solving using Java, 2nd ed. Addison Wesley, 2001.

Carrano & Prichard, Data Abstraction and Problem Solving with Java : Walls and Mirrors, Addison Wesley, 2001.

Méthode d'évaluation :

Langage C

Une évaluation continue est organisée (interrogations écrites et ou sur machine). Un examen d'exercices complète cette évaluation.

Structures de Données

Un examen orienté exercices permet d'évaluer les acquis des étudiants