Informatique 2- Structure de données et algorithmes PET-PI - 3PMKSDAL

Objectif(s)

L'enseignement introduit certaines des principales notions et structures de données à la base des solutions à de nombreux problèmes non numériques.

Il aborde la programmation récursive et les principales structures de données dynamiques et types abstraits utilisées aujourd'hui (listes, piles, files, arbres, graphes) et présente quelques implémentations et algorithmes utilisant ces structures de données.

Il renforce les compétences en génie logiciel : spécification, analyse, codage, compilation, tests, gestion de version.

Contenu(s)

Exemples de notions abordées :
Programmation récursive, notion de complexité
Notion de Type de Données Abstraites
Structures de données chaînées linéaires : listes, piles, files
Dictionnaires et tables de hachage
Structures de données arborescentes : arbres binaire

Tp : Ces notions sont mises en oeuvre BE par les étudiants, en langage C, sous Linux, sur des exemples concrets; Quelques exemples de problèmes traités :
Fractale de MandelBrot et Récursivité
Tri par tas
Jeu de carte de la bataille avec pile et file
Vérificateur orthographique et Table de Hachage
Calcul formel de dérivée d'expressions mathématiques et arbre binaire

Mini projet de fin de module. Exemples de sujets : recherche d'itinéraires dans le métro et le RER parisien par recherche du plus court chemin dans un graphe avec différents algorithmes : Dijkstra, Bellman, A-Star.

Cours informatique premier semestre 1A